[오독완 챌린지] 기술 면접 대비 CS 전공 핵심 요약집 (7일차)

오늘도 독서 완료!

오늘은 자료구조에 대해서 학습 했습니다. 자료구조를 들어오면 항상 복잡도, 빅오표기법이 나옵니다. 말 그대로 입력 값에 대한 알고리즘의 실행 속도 정도로 이해했는데요, 시간 복잡도를 통해서 이 알고리즘의 속도를 예측할 수 있습니다. 빅세타, 빅오메가 등이 있는데 빅오표기법을 사용하는 이유는 빅오 표기법이 최악의 경우 즉, 가장 느릴경우를 나타내기 때문에 적어도 이 속도 만큼의 안정성은 보장된다고 볼 수 있어서 사용합니다.

 

자료구조는 크게 선형 자료구조와 비선형 자료구조로 분류하는데, 선형은 말그대로 데이터가 linear한 것이므로 연속적인 것입니다. 기후 변화 메트릭의 변화 등 값이 지속적으로 연속되는 것을 말하고 변화 양상을 추적하기 좋습니다.

 

선형 자료구조의 가장 기본은 배열인데, 배열은 정해진 크기 만큼 데이터가 일렬로 저장되는 static한 자료 구조입니다. 요소(element)와 순서를 나타내는 index가 배열을 이루는 구성요소 입니다.

 

다음은 연결 리스트인데, 연결 리스트는 배열과 달리 크기가 정해져 있지 않는 dynamic한 자료 구조입니다. 이 둘의 차이점을 인식하는게 중요합니다. 연결 리스트는 앞과 뒤의 값이 연결되어 있어, 포인터라는 주소 값을 이용해서 자료를 계속 추가하게 됩니다. 따라서 배열처럼 값을 미리 지정할 필요없이 무한정 값을 추가할 수 있게됩니다.

 

다음으로 가장 중요한 스택과 큐가 등장합니다.

스택의 경우 데이터를 쌓는 형태로 마지막에 들어온 데이터가 먼저 나가는 LIFO(Last In First Out 후입선출)을 하게 됩니다. 매우 쉽게 말해서 우리가 바구니에 물건을 정리하는 방식이라고 생각하면 됩니다. 우리가 물건을 바구니에 쌓을 때 마지막에 쌓은 것을 가장 먼저 꺼낼 수 있기 때문입니다.

 

큐의 경우 데이터가 들어온 순서대로 먼저 나가는 FIFO(First In First Out 선입선출)을 하게 됩니다. 그래서 콘서트 티켓 대기표 같은 곳에서는 큐를 사용한다고 보면 됩니다. 먼저 온 사용자가 큐에 쌓여서 하나씩 번호표를 가져가는 형식입니다.

 

스택에는 무언가를 넣을 때 push, 빼낼 때 pop을 사용하며, 큐의 경우 데이터가 삽입할 때 enqueue, 빼낼 때 dequeue라는 방법을 사용합니다.