면접을 위한 CS 전공지식 노트: 5장 자료구조

5.1 복잡도: 시간복잡도, 공간복잡도

시간복잡도: 문제를 해결하는데 걸리는 시간과 입력의 함수 관계. 보통 빅오표기법으로 나타냄.

※ 빅오표기법: 입력 범위 n을 기준으로 로직이 몇 번 반복되는지 나타내는 것.

-> 효율적인 코드로 개선하는 데 쓰이는 척도

 

공간복잡도: 프로그램을 실행시켰을 때 필요로 하는 자원 공간의 양.

 

자료구조에서의 시간 복잡도 - 평균 시간 복잡도

자료구조	접근	탐색	삽입	삭제
배열	O(1)	O(n)	O(n)	O(n)
스택	O(n)	O(n)	O(1)	O(1)
큐	O(n)	O(n)	O(1)	O(1)
이중 연결 리스트	O(n)	O(n)	O(1)	O(1)
해시 테이블	O(1)	O(1)	O(1)	O(1)
이진 탐색 트리	O(log n)	O(log n)	O(log n)	O(log n)
AVL 트리	O(log n)	O(log n)	O(log n)	O(log n)
레드 블랙 트리	O(log n)	O(log n)	O(log n)	O(log n)

 

5.2 선형 자료구조: 요소가 일렬로 나열되어 있는 자료 구조

연결 리스트: 데이터를 감싼 노드를 포인터로 연결해서 공간적인 효율을 극대화시킨 자료구조. 삽입 및 삭제 O(1), 탐색 O(n).

- 싱글 연결 리스트: next 포인터만 가짐

- 이중 연결 리스트: next 포인터와 prev 포인터를 가짐

- 원형 이중 연결 리스트: next 포인터와 prev 포인터를 가지고 마지막 노드의 next 포인터가 head 노드를 가리킴.

 

배열: 같은 타입의 변수들로 이루어져 있고, 크기가 정해져 있으며, 인접한 메모리 위치에 있는 데이터를 모아놓은 집합. 중복을 허용하고 순서가 있음. 삽입 및 삭제 O(n), 탐색 O(1).

 

※ 랜덤 접근과 순차적 접근

- 랜덤 접근: 임의의 인덱스에 해당하는 데이터에 접근 가능. e.g., 배열

- 순차적 접근: 데이터가 저장된 순서대로 접근. e.g., 연결 리스트

 

벡터: 동적으로 요소를 할당할 수 있는 동적 배열. 중복을 허용하고 순서가 있고 랜덤 접근 가능. 탐색, 맨 뒤의 요소를 삭제하거나 삽입 O(1), 맨 뒤나 맨 앞이 아닌 요소의 삭제와 삽입 O(n).

 

스택: 가장 마지막으로 들어간 데이터가 가장 첫 번째로 나오는 성질을 가진 자료구조. LIFO(Last-In-First-Out)

 

큐: 먼저 집어넣은 데이터가 먼저 나오는 성질을 지닌 자료구조. FIFO(First-In-First-Out)

 

5.3 비선형 자료 구조: 일렬로 나열하지 않고 자료 순서나 관계가 복잡한 구조. 일반적으로 트리나 그래프.

그래프: 정점과 간선으로 이루어진 자료 구조.

   - 단방향 간선

   - 양방향 간선

- 가중치: 간선과 정점 사이에 드는 비용.

 

트리: 그래프 중 하나. 루트 노드, 내부 노드, 리프 노드로 구성.

- 이진 트리: 자식 노드가 2개 이하인 트리

   - Full Binary Tree: 자식 노드가 0개 또는 2개

   - Complete Binary Tree: 왼쪽에서부터 채워져 있는 이진 트리

   - Degenerate Binary Tree: 자식 노드가 1개

   - Perfect Binary Tree: 모든 노드가 꽉 차 있는 이진 트리

   - Balanced Binary Tree: 왼쪽 노드와 오른쪽 노드의 높이 차이가 1 이하인 이진 트리.

 

힙: 완전 이진 트리 기반의 자료 구조. 최소 힙과 최대 힙.

 

우선순위 큐: 대기열에서 우선순위가 높은 요소가 먼저 제공되는 자료 구조. 힙 기반.

 

맵: 특정 순서에 따라 키와 매핑된 값의 조합으로 형성된 자료 구조. 레드 블랙 트리 기반.

 

셋: 특정 순서에 따라 고유한 요소를 저장하는 컨테이너. 중복되는 요소 없음.

 

해시 테이블: 무한에 가까운 데이터들을 유한한 개수의 해시 값으로 매핑한 테이블.