[CS 면접 스터디] 1주차

date

Sep 3, 2023

slug

cs-week1

author

status

Public

죠르디님의 CS 강의 내용 정리 Part.1

Array 배열

바이트 단위로 할당됨.

비트 단위 할당X

크기 변경 불가. 고정되어 있음.

Dynamic Array 동적 배열

데이터가 연속적으로 연결되어 있는 형태

크기가 동적으로 변경될 수 있다. 근본적으로 배열 기반 구현 방식이다.

파이썬에서의 배열은 기본적으로 동적 배열(dynamic array)의 형태를 띕니다.

처음 배열 선언할때 사이즈 지정 굳이X

static 배열은 동일하지만, initial 크기가 있기 때문에, 그게 꽉 차게 된다면 두배로 늘린다. … 반복

리사이징이 최대한 일어나지 않게 하는 것이 중요하다.

→ 언어마다 해당하는 솔루션은 다름.

동적 배열의 크기를 조정하는 방식: 증가량을 줄여서 메모리 낭비를 줄일건지 vs 증가량을 늘려서 메모리 낭비가 조금 더 있는 대신 발생 횟수를 줄일건지의 차이

shift 연산

왼쪽으로 한칸씩 미루면 x2가 됨.

0111 (7)→ 1000 (14)

Part2

Linked List

메모리 상에서는 데이터가 불연속적으로 저장되어 있으나, 논리적으로 연속성을 구현한 선형 자료구조이다.

실제로 메모리 상에서 비연속적으로 데이터가 저장된다.

다음 값이 있는 주소를 계속 찾아야함.

시간 복잡도: O(N)

링크드 리스트는 코테에서 많이 사용되지 않음.

Array vs Dynamic Array vs Linked List 총 비교

Queue 큐

데이터가 연속적으로 저장되어 있는 선형 자료구조이다.

FIFO 구조

Deque 데크

큐와 달리 끝부분이 두개 (끝부분에서 add, pull 가능)

Part.4

Stack 스택

데이터가 연속적으로 연결되어 있는 선형 자료구조

LIFO 구조

Part.5

HashTable

다음주로…

면접에서 제일 많이 나옴…. 중요…. 메모….

[CS 면접 스터디] 1주차 - 자료구조