기술면접 list- 자료구조

자료구조

배열(Array)

- 정적으로 필요한 만큼만 원소를 저장할 수 있는 공간이 할당됨. 각 원소의 주소는 연속적으로 할당됨. 

- index를 통해 O(1)에 접근 가능. 

- 삽입, 삭제는 O(N)

- 지정된 개수를 초과하는 경우 배열의 크기를 재할당한 후 복사해야함

리스트

- 노드(Node)들의 연결로 이루어진 자료구조

- 크기 제한이 없다(heap 용량이 충분하다면).

- 다음 노드에 대한 참조를 통해 원소를 접근(O(N))

- 노드의 삽입, 삭제에 강점을 가짐(O(1))

ArrayList

- 동적으로 크기가 조정되는 배열

- 배열이 가득 차는 경우 알아서 그 크기를 2배로 할당하고 복사를 수행

- 재할당에 걸리는 시간은 O(N)이지만, 자주 일어나는 일이 아니기 때문에 접근시간은 O(1)

스택(Stack)

- LIFO 방식

- 원소의 삽입, 삭제가 한쪽 끝에서만 이루어진다. 이 부분을 top이라 칭한다.

- 함수 호출 시 지역변수, 매개변수 정보를 저장하기 위한 공간인 스택으로 사용

트리(Tree)

- cycle이 없는 무방향 그래프를 트리라고 함

- 완전이진트리 기준으로 높이는 log N이 될 것임.

중위 순회 : 루트를 2번째로 탐색 (left-root-right)

전위 순회 : 루트를 1번째로 탐색(root-left-right)

후위 순회 : 루트를 3번째로 탐색(left-right-root)

레벨 순서 순회 : 노드를 레벨 순서로 방문. 이는 BFS와 동일하므로 큐를 통해 구현할 수 있음.

이진탐색트리(BST)

- 노드의 왼쪽은 노드의 값보다 작은 값들, 오른쪽은 노드의 값보다 큰 값으로 구성됨.

- 이상적인 상황에서의 탐색/삽입/삭제 모두 O(log N)

- 하지만 편향되는 경우에는 최악의 O(N)

큐(Queue)

- FIFO 방식

- 원소의 삽입과 삭제가 다른 부분(끝-처음)에서 일어난다.

- FIFO 운영체제, 은행 대기열 등

우선순위 큐(Priority Queue)

- FIFO가 아니라 데이터를 근거로 우선순위를 판단, 우선순위가 높은 것을 먼저 가져옴

- 구현 방법 3가지(배열, 연결리스트, 힙(heap))

1. 배열

- 간단하게 구현이 가능함

- 하지만 데이터 삽입 및 삭제 과정 중 O(N)(한 칸씩 당기거나 밀어야함)의 비효율 발생

- 삽입의 위치를 찾기 위해 배열의 모든 데이터를 탐색(우선순위가 가장 낮은 경우)

2. 연결리스트

- 삽입, 삭제는 O(1)

- 마찬가지로 삽입 위치를 찾기 위한 비효율 발생

3. 힙

- 위의 2가지 조건을 충족할 수 있다. 주로 힙을 사용하여 우선순위큐를 구현함.

- 힙은 완전이진트리의 성질을 만족하기 때문에 1차원 배열로 표현이 가능함. 이를 통해 leaf node에 O(1)에 접근이 가능하다. 

- 루트 인덱스에 따라 left, child 노드의 인덱스를 계산할 수 있다.

( root가 0이면 left=2*index+1, right= 2*index+2,  root가 1이면 left=2*index, right=2*index+1)

- 데이터의 삽입은 트리의 leaf 노드부터 시작됨.

- 삽입 후 heapify 과정을 통해 힙의 모든 부모-자식 노드의 우선순위에 맞게 설정한다(부모의 우선순위는 자식의 우선순위보다 커야 함)

- 삭제는 root 노드를 삭제하게 됨.(우선순위가 가장 큰 것)

- 삭제 후 마지막 leaf 노드를 루트 노드로 옮긴 뒤 heapify과정을 수행함.

해시 테이블

- 효율적인 탐색을 위한 자료구조

- key-value 쌍으로 이루어짐.

- 해시 함수를 통해 입력받은 key를 정수값(index)로 대응시킴

- 충돌(collision)에 대한 고려가 필요함

해싱의 충돌 해결책

1. 선형 조사법(linear probing)

- 충돌이 일어난 항목을 해시 테이블의 다른 위치에 저장

ex) ht[k], ht[k+1], ht[k+2]....

- 삽입의 경우

충돌이 ht[k]에서 일어났다면 ht[k+1]이 비어있는지를 조사, ht[k+2]를 조사..

테이블 끝에 도달하면 처음으로 이동, 그럼에도 불구하고 시작한 위치로 돌아오면 테이블이 가득 찬 경우

- 검색의 경우

ht[k]에 있는 키가 다른 값이면 ht[k+1]에 같은 키가 있는지 조사

비어있는 공간이 나오면 찾는 키가 없는 경우

검색을 시작한 위치로 돌아오면 찾는 키가 없는 경우

2. 이차 조사법

- h(k), h(k)+1, h(k)+4, h(k)+9...

- 선형조사법에서 발생하는 집적화를 완화하는 효과가 있다.

3.이중해시법

- 재해싱(rehashing)이라고도 불림

- 충돌로 인해 비어있는 버킷을 찾을 때 추가적인 해시 함수 h'()를 이용하는 방식

- h'(k)= C - (k mod C)

- 조사 위치

h(k), h(k)+h'(k), h(k)+2h'(k)

4. 체이닝

- 각 버킷은 고정된 개수의 슬롯 대신 유동적인 크기를 갖는 연결 리스트로 구성된다. 

- 충돌 뿐만 아니라 오버플로우 문제도 해결된다.

- 버킷 내에서 항목을 찾을 때는 연결 리스트를 순차 탐색

5. 해싱의 성능 분석

- 적재 밀도 또는 적재 비율 a : 저장되는 항목의 개수 n과 해시테이블의 크기 M의 비율

a=n/M

* 맵과 해쉬맵의 차이

- C++의 map 컨테이너는 이진탐색트리(최근에는 Red-Black Tree)를 사용. key값을 이용해 트리를 탐색하게 됨.

- 따라서 원소 접근, 삽입, 삭제는 O(log N)

- 반면에 해쉬맵은 O(1)에 접근 가능(key의 길이 제외한다면)

- 그럼에도 불구하고 C++ 공식 STL에 지원하지 않는 이유는 Collision을 해결하기 위한 방법이 안정적이지 못하기 때문(해쉬함수, collision 정책에 따라 성능의 차이가 큼)