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

5.1 복잡도

시간복잡도

• 어떠한 알고리즘 로직이 얼마나 오랜 시간이 걸리는지를 나타냄
• 보통 빅오 표기법을 통해 나타냄
  • 가장 영향을 많이 끼치는 항의 상수인자를 빼고 나머지 항을 없앤 것
• 효율적인 코드로 개선하는데 사용되는 척도
• 아래와 같은 코드는 알고리즘에 필요한 시간이 10n^2+n 인데 빅오 표기법으로 나타내면 O(n^2)이 됨

for(int i=0 ; i<10 ; i++) {
	for(int j=0 ; j<n ; j++) {
		for(int k=0 ; k<n ; k++) {
			cout << k << '\n';
		}
	}
}
for(int k=0 ; k<n ; k++) {
    cout << k << '\n';
}

 

 

공간 복잡도

• 프로그램을 실행시켰을 때 필요로 하는 자원 공간의 양
• 정적 변수로 선언된 것 말고도 동적으로 재귀적인 함수로 인해 공간을 계속해서 필요로 할 경우도 포함됨
• 아래와 같은 배열이 있을 때 a 배열은 1004 * 4 바이트 크기의 공간 복잡도를 가짐

int a[1004];

 

5.2 선형 자료 구조

연결리스트

• 데이터를 감싼 노드를 포인터로 연결해서 공간적인 효율성을 극대화시킨 자료구조
• 삽입과 삭제는 O(1), 탐색에는 O(n)이 걸림
• next 포인터만 갖는 싱글 연결 리스트, prev와 next 포인터를 모두 갖는 이중 연결 리스트, 이중연결 리스트와 같지만 마지막 노드의 next 포인터가 헤드 노드를 가리키는 원형 이중 연결 리스트가 있음
• 랜덤 접근이 불가능하고 순차적 접근을 통해 탐색해야 함

 

배열

• 같은 타입의 변수들로 이루어져 있고, 크기가 정해져 있으며(정적 배열), 인접한 메모리 위치에 있는 데이터를 모아놓은 집합
• 중복을 허용하고 순서가 있음
• 인덱스를 통해 랜덤 접근이 가능함
• 탐색에 O(1), 삽입과 삭제는 O(n)이 걸림
• 따라서 추가와 삭제를 많이 한다면 연결리스트를, 탐색을 많이 한다면 배열로 하는 것이 좋음
• 배열은 모든 요소를 앞으로 옮겨야 삽입이 가능하여 O(n)이 걸리지만, 연결리스트는 포인터를 바꿔서 연결만 하면 되어서 O(1)로 가능함

 

벡터

• 동적으로 요소를 할당할 수 있는 동적 배열
• 컴파일 시점에 개수를 모른다면 사용
• 중복 허용, 순서 있고, 랜덤 접근 가능
• 탐색과 맨 앞 또는 맨 뒤의 요소를 삭제하거나 삽입할 때는 O(1), 중간에 요소를 삭제하고 삽입할 때는 O(n)
• 벡터는 push_back을 할 때마다 크기를 증가시키는 것이 아니라 2의 제곱승+1마다 벡터의 크기를 2배로 늘림. 이렇게 크기를 증가시키는 평균적인 복잡도를 계산하면 상수 시간에 가까운 amortized 복잡도를 가진다는 것을 알 수 있음. 따라서 O(1)의 시간 복잡도를 가짐

 

스택

• 가장 마지막으로 들어간 데이터가 가장 처음으로 나오는 성질(LIFO)
• 재귀 함수, 웹 브라우저 방문 기록 등에 사용됨
• 삽입 및 삭제에 O(1), 탐색에 O(n)이 걸림

 

큐

• 가장 먼저 넣은 데이터가 먼저 나오는 성질 (FIFO)
• 삽입 및 삭제에 O(1), 탐색에 O(n)이 걸림
• CPU 작업을 기다리는 프로세스, BFS, 스레드 행렬 등에 사용됨

 

5.3 비선형 자료 구조

일렬로 나열하지 않고 자료 순서나 관계가 복잡한 구조

그래프

• 정점(vertex)과 간선(edge)으로 이루어진 자료 구조
• 단방향 간선 / 양방향 간선
• 정점으로 나가는 간선을 outdegree, 정점으로 들어오는 간선을 indegree라고 함
• 간선과 정점 사이에 드는 비용을 가중치라고 함

 

트리

• 그래프 중 하나로 그래프처럼 정점과 간선으로 이루어져 있음.
• 트리 구조로 배열된 일종의 계층적 데이터의 집합이다. 부모 자식 계층 구조를 가짐
• 간선 수는 노드 수 - 1 라는 규칙을 가짐
• 두 노드 사이의 경로는 반드시 존재함
• 맨 위의 루트 노드, 내부노드, 자식이 없는 리프 노드로 구성됨
• 이진트리: 자식의 노드 수가 두개 이하인 트리

 

이진 탐색 트리

• 노드의 오른쪽 하위 트리에는 노드 값보다 큰 값, 왼쪽 하위 트리에는 노드 값보다 작은 값이 들어 있는 트리
• 오른 쪽에는 큰 값, 왼쪽에는 작은 값만 있기 때문에 검색에 용이함
• 보통의 경우는 탐색, 삽입, 삭제 모두 O(logn)이지만 최악의 경우 O(n)이 걸림
• 하지만 이진 탐색 트리는 삽입 순서에 따라 선형적일 수 있기 때문에 최악의 경우 O(n)이 걸림
  • 예를 들어 정렬된 상태로 삽입된 경우 (5,4,3,2,1)

https://thebook.io/080200/ch08/05/

 

AVL 트리

• 최악의 경우 선형적인 트리가 되는 것을 방지하고, 스스로 균형을 잡는 이진 탐색 트리
• 오른쪽, 왼쪽 두 자식 서브트리의 높이 차이는 최대 1이다.
• 높이 차이가 1보다 커지면 회전을 통해 균형을 맞춰 높이 차이를 줄인다
• 탐색, 삽입, 삭제 모두 O(logn), 삽입과 삭제를 할 때마다 균형을 맞추기 위해 트리의 일부를 왼쪽 혹은 오른쪽으로 회전시키며 균형을 잡음
  • Balance Factor를 활용해 균형이 무너졌는지를 판단함
  • BF(K) = K의 왼쪽 서브트리의 높이 - K의 오른쪽 서브트리의 높이
  • AVL트리의 모든 노드의 BF가 -1, 0, 1중 하나여야 한다. 이를 벗어나면 회전이 필요한 상태!

Right Rotation (https://code-lab1.tistory.com/61)

Left Rotation (https://code-lab1.tistory.com/61)

 

레드 블랙 트리

• 균형 이진 탐색 트리로 탐색, 삭제, 삽입 모두 O(logn)
• 각 노드는 빨간색 또는 검은색의 색상을 나타내는 추가 비트를 저장하며, 삽입 및 삭제 중에 트리가 균형을 유지하도록 하는데 사용됨
• C++ STL의 set, multiset, map, multimap등이 레드 블랙 트리를 이용해 구현되어 있음

 

5.3.3 힙

• 완전 이진 트리 기반의 자료 구조
• 최대힙: 루트 노드에 있는 키는 모든 자식에 있는 키 중에서 가장 커야 함. 각 노드의 자식 노드와의 관계도 이와 같은 특징이 재귀적으로 이루어져야 함
• 최소힙: 루트 노드에 있는 키는 모든 자식에 있는 키 중에서 가장 작아야 함. 각 노드의 자식 노드와의 관계도 이와 같은 특징이 재귀적으로 이루어져야 함

 

5.3.4 우선 순위 큐

• 우선순위 대기열이라고도 하며, 대기열에서 우선순위가 높은 요소가 우선 순위가 낮은 요소보다 먼저 제공되는 자료 구조
• 힙을 기반으로 구현됨

 

5.3.5 맵

• 특정 순서에 따라 키와 매핑된 값의 조합으로 형성된 자료 구조
• "알고리즘": 1, "운영체제": 2 와 같이 string: int 형태로 값을 할당해야 할 때
• 정렬을 보장하지 않는 unordered_map과 정렬을 보장하는 map 두 가지가 있음

 

5.3.6 셋

• 특정 순서에 따라 고유한 요소를 저장하는 컨테이너
• 중복되는 요소는 없고 오로지 unique한 값만 저장하는 자료구조

 

5.3.7 해시테이블

• 무한에 가까운 데이터들을 유한한 개수의 해시 값으로 매핑한 테이블
• 작은 크기의 캐시 메모리로도 프로세스를 관리하도록 할 수 있음
• 삽입, 삭제, 탐색 시 평균적으로 O(1)의 시간 복잡도를 가지며 unordered_map으로 구현함
• 각 key값에 해시 함수를 적용해 배열의 고유한 index를 생성하고, index를 활용해 값을 저장하거나 검색함
• 실제 값이 저장되는 장소를 버킷 또는 슬롯이라고 함
  • ("John Smith", "521-1234")인 데이터를 크기가 16인 해시 테이블에 저장한다.
  • index를 hash_function("John Smith") % 16 연산을 통해 index 값을 계산한다. 그리고 array[index]에 전화번호를 저장함
  • 해싱 구조로 데이터를 저장하면 key 값으로 데이터를 찾을 때 해시 함수를 한 번만 수행하면 되므로 매우 빠르게 데이터를 저장/삭제/조회할 수 있다.

https://mangkyu.tistory.com/102