면접을 위한 CS 전공지식 노트 5장

자료구조란?

효율적으로 데이터를 관리하고 수정 , 삭제 , 탐색 ,저장할 수 있는 데이터 집합

 

C++는 STL을 기반으로 전반적인 자료구조를 가장 잘 설명할 수 있는 언어

STL 이란 ? C++의 표준템플릿 라이브러리이자 스택,배열 등 데이터 구조의 함수 등을 제공하는 라이브러리의 묶음

 

 

시간복잡도

- 빅오표기법 으로 표기를 하며 , 입력 크기에 대해 어떠한 알고리즘이 실행되는 데 걸리는 시간입니다.

주요 로직의 반복 횟수를 중점으로 츨정되며, 보통 빅오 표기법으로 나타냅니다 예를 들어 "입력크기 n"의 모든 입력에

대한 알고리즘에 필요한 시간이 n^2이라고 하면 이중 for문을 생각하면된다. 이것을 빅오표기법으로 표기하면

O(n^2)으로 표기한다. 가장 영향을 많이 끼치는 항의 상수 인자를 빼고 나머지 항을 없앤 것입니다.

 

 

공간복잡도

프로그램을 실행시켰을 때 필요로 하는 자원 공간의 양, 정적 변수로 선언된 것 말고도 동적으로 재귀적인 함수로 인해 공간을 계속해서

필요로 할 경우도 포함한다.

 

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

이진탐색트리는 최악의 조건에 O(n)이다 한쪽으로 치우칠 수 있다.

 

선형 자료 구조

 

연결리스트

- 연결리스트는 데이터를 감싼 노드를 포인터로 연결해서 공간적인 효율성을 극대화 시킨 자료구조,

삽입과 삭제가 O(n)이 걸리며 탐색에는 O(n)이 걸립니다.

 

그림처럼 previous 포인터와 Next포인터로 앞과 뒤의 노드를 연결시킨 것이 연결리스트이며, 연결리스트는 싱글 연결리스트 ,이중 연결리스트,원형 이중 연결리스트가 있습니다. 맨앞의 있는 도르르 헤드라고도 합니다.

 

싱글 연결 리스트: next 포인터만 가집니다

이중 연결 리스트: next 포인터와 prev포인터를 가집니다.

원형 이중 연결 리스트: 이중 연결 리스트와 같지만 마지막 노드의 next포인터가 헤드노드를 가리키는 것을 의미, 원형 연결 리스트

 

C++에서 이중 연결리스트 예제

앞에서 요소를 넣을 때 push_front , 뒤에서 요소를 넣을 때 push_back() , 중간에 요소를 넣는 insert()

 

배열

배열은 같은 타입의 변수들로 이루어져 있고, 크기가 정해져 있으며,인접한 메모리 위치에 있는 데이터를 모아놓은 집합, 또한 중복을 허용하고 순서가 있습니다. 접근 참조에 O(1)의 시간복잡도를 가지며 랜덤접근이 가능합니다. 삽입과 삭제에는 O(n)이 걸립니다. 따라서 추가와 삭제를 많이하는 것은 연결리스트,접근을 많이하는 것은 배열로 하는 것이 좋습니다.

 

 

랜덤 접근과 순차적 접근

직접 접근이라고 하는 랜던접근은 동일한 시간에 배열과 같은 순차적인 데이터가 있을 때 임의의 인덱스에 해당하는 데이터에 접근할 수 있는 기능, 이는 데이터를 저장된 순서대로 검색해야하는 순차적 접근과는 반대입니다.

 

n번째 요소의 접근은 배열이 빠리고 연결리스트는 느립니다. 배열의 경우 그저 상자 위에 있는 요소를 접근하면 되기 때문에 O(1)의 시간복잡도를 가집니다. 연결리스트와 같은 경우 매번 상자를 순차적으로 열어야하기 때문에 O(n)의 시간복잡도를 가집니다.

참조가 많이 일어나는 작업의 많은 경우 배열이 빠르고, 연결리스트는 느립니다. 하지만 데이터 추가 및 삭제는 연결리스트가 더 빠르고 배열은 느립니다.

 

벡터

동적으로 요소를 할당할 수 있는 동적배열, 컴파일 시점에 개수를 모른다면 벡터를 써야합니다. 또한 중복을 허용하고 순서가 있고 랜덤 접근이 가능합니다. 탐색과 맨뒤 요소를 삭제하거나 탐색하는데 O(1)이 걸리며, 맨 뒤나 맨앞이 아닌 요소를 삭제하고 삽입하는데 O(n)의 시간이 걸립니다.

 

스택 

ex) 재귀함수 or 방문기록

스택은 가장 마지막으로 들어간 데이터가 가장 첫번째로 나오는 성질(LIFO,last in first out)을 가짐, 삽입 및 삭제에 O(1), 탐색에 O(n)이 걸립니다.

 

큐

ex) cpu작업을 기다리는 프로세스, 스레드 행렬, 너비우선탐색,캐시

먼저 넣은 데이터가 먼저 나오는 성질(FIFO, first in first out)

삽입과 및 삭제에 O(1), 탐색에 O(n)이 걸립니다.

 

 

비선형 자료 구조

비선형 자료구조란 일렬로 나열하지 않고 자료 순서나 관계가 복잡한 구조를 말합니다. 일반적으로는 트리, 그래프

 

 

 

그래프

 

그래프는 정점과 간선으로 이루어진 자료를 말합니다.

 

정점과 간선

정점은 target , 간선은 Line이라고 생각하면 된다.



outdegree: 정점으로 나가는 간선

indegree: 들어오는 간선

 

가중치: 1번노드와 2번노드로 가는 비용

 

트리

 

그래프 중 하나로 그래프의 특징처럼 정점과 간선으로 이루어져 있고,트리 구조로 배열된 일종의 계층적 데이터 집합,

root node,internal node,leaf node(자식이 없는 노드)로 이루어진 집합의 숲.

 

 

트리의 높이와 레벨

- 다음은 트리의 높이와 레벨을 설명한 그림입니다.

 

깊이: 트리에서의 깊이는 각 노드마다 다르며, 루트 노드부터 특정 노드까지 최단 거리로 갔을 때의 거리를 말합니다. 예를들어 4번 노드의 깊이는 2입니다.

 

높이: 트리의 높이는 루트 노드부터 리프노드까지 거리 중 가장 긴 거리를 의미하며, 앞 그림의 트리 높이는 3 입니다.

 

레벨: 1번 노드를 0레벨 ,2번노드,3번 노드를 1레벨, 1번노드를 1레벨이라고 한다면 2,3번 노드는 2레벨

 

서브트리: 트리 내에 있는 부분집합, 5번,6번,7번 노드가 이 트리의 하위 집합으로 "저 노드들은 서버트리이다" 라고 합니다.

 

이진 트리

- 이진 트리는 자식의 노드 수가 두 개 이하인 트리를 의미합니다.

 

이진트리 종류

 

- 정이진 트리(full binary tree): 자식노드가 0 또는 두개의 이진트리를 의미합니다.

- 완전 이진트리(complete binary tree): 왼쪽에서부터 채워져 있는 이진 트리를 의미합니다. 마지막 레벨을 

제외하고는 모든 레벨이 완전히 채워져 있으며, 마지막 레벨의 경우 왼쪽부터 채워져 있습니다.

- 변질 이진트리(degenerate binary: 자식 조드가 하나밖에 없는 이진 트리를 의미합니다.

- 포화 이진트리(perfect binary tree): 모든 노드가 꽉 차 있는 이진트리를 의미합니다.

- 균형 이진 트리(balanced binary tree): 왼쪽과 오른쪽 노드의 높이 차이가 1이하인 이진 트리를 의미합니다.

map,set을 구성하는 레드 블랙 트리는 균형 이진트리 중 하나 입니다.

 

이진탐색트리

 

BST는 노드의 오른쪽 하위트리에는 "노드 값보다 큰 값"이 있는 노드만 포함되고, 왼쪽 하위 트리에는 "노드 값 보다 작은 값"이 들어가는 트리를 말합니다.

 

보통 요소를 찾을 때 이진탐색트리는 O(logn)이 걸립니다. 하지만 최악의 경우 O(n)이 걸립니다.

 

그 이유는 이진탐색 트리는 삽입 순서에 따라 선형적일 수 있다.

 

 

 

AVL 트리



앞서 설명한 최악의 경우 선형적인 트리가 되는 것을 방지하고 스스로 균형잡힌 이진탐색트리 입니다.

두 자식 서브트리의 높이는 항상 1만큼 차이 난다는 특징이 있다. 탐색,삽입,삭제, 모두 시간 복잡도가

O(logN)이며 삽입,삭제할 때마다 균형이 안 맞는 것을 맞추기 위해 트리 일부를 왼쪽 혹은 오른쪽으로 회전ㄴ시키며 균형을 잡습니다.

 

레드 블랙 트리

레드 블랙 트리는 균형 이진 탐색 트리로 탐색, 삽입, 삭제 모두 시간 복잡도가 O(logN)입니다.

각 노드는 빨간색 또는 검은색의 색상을 나타내는 추가 비트를 저장하며, 삽입 및 삭제 중에 트리가 균형을 유지하도록 하는데 사용됩니다.

 

참고로 "모든 리프 노드와 루트 노드는 블랙이고 어떤 노드가 레드이며 그 노드의 자식은 반드시 블랙이다" 등의 규칙을 기반으로

균형을 잡는 트리입니다.

 

 

 

힙

 

힙은 완전 이진 트리 기반의 자료 구조이며, 최소힙과 최대힙 두 가지가 있고 해당 힙에 따라 특정한 특징을 지킨 트리를 말합니다.

 

최대힙: 루트 노드에 있는 키는 모든 자식에 있는 키 중에서 가장 커야 합니다. 또한 각 노드의 자식 노드와의 관계도 이와같은 특징이 재귀적으로 이루어져야 합니다.

 

최소힙: 최소힙에서 루트 노드에 있는 키는 모든 자식에 있는 키 중에서 최솟값이어 합니다. 또한 각 노드의 자식 노드와의 관계도 이와 같은 특징이 재귀적으로 이루어저야 합니다.

 

힙에는 어떠한 값이 들어와도 특정 힙의 규칙을 지키게 만들어져 있습니다. 

 

최대힙의 삽입

 

 

 

 

 

 

최대힙의 삭제

 

최대힙에서는 최댓값은 루트 노드이므로 루트노드가 삭제되고, 그 이후 마지막 노드와 루트 노드를 스왑하여 또 다시 스왑 등의 과정을 거쳐 재구성할 수 있습니다.

 

우선순위 큐

 

우선순위 큐는 우선순위 대기열이라도 하며, 대기열에서 우선순위가 높은 요소가 우선순위가 낮은 요소보다 먼저 제공되는 자료구조 입니다.

 

우선순위 큐는 힙을 기반으로 구현됩니다.

 

맵

 

특정 순서에 따라 키와 매핑된 값의 조합으로 형성된 자료 구조입니다. key value를 써서 할당한다.

레드블랙트리자료 구조를 기반으로 형성되고 삽입하면 자동으로 정렬됩니다.

 

맵을 쓸때는 map<string,int) 형태로 구현합니다. 배열과 비슷하게 clear함수로 모든요소를 삭제할 수 있고 size()로 map의 크기를 구할 수 있습니다. 또한 erase()로 해당 키와 매핑된 키값을 지울 수 있습니다.

 

map은 해시테이블을 구현할 때 쓰며 정렬을 보장하지 않은 unordered_map과 정렬을 보장하는 map이 있다.

 

map을 순회할 때는 키에 해당하는 key을 first, 키에 매핑된 값에 해당하는 값을 second로 탐색 합니다.

 

 

셋

 

셋은 특정 순서에 따라 고유한 요소를 저장하는 컨테이너이며,중복되는 요소는 없고 오로지 유니크한 값만 저장한다.

 

해시테이블

 

해시테이블은 무한에 가까운 데이터들을 유한한 개수의 해시 값으로 매핑한 테이블입니다. 삽입,삭제.,탐색 시 평균적으로

O(1)의 시간을 가지며 unordered_map으로 구현합니다.

 

정리

HASHMAP

HASHTABLE

CONCURRENTHASHMAP

key와 value에 null 허용	O	X	X
동기화 보장(Thread-safe)	X	O	O
추천 환경	싱글 쓰레드	멀티 쓰레드	멀티 쓰레드

 

결론

싱글 쓰레드 환경이면 HashMap을, 멀티 쓰레드 환경이면 HashTable이 아닌 ConcurrentHashMap을 쓰자. 그 이유는 HashTable보다 ConcurrentHashMap이 성능적으로 우수하기 때문이다. 앞에서도 언급했듯이 HashTable은 쓰레드간 락을 걸어 데이터를 다루는 속도가 느리다. 반면, ConcurrentHashMap은 Entry 아이템별로 락을 걸어 데이터를 다루는 속도가 빠르다.