자료구조 / 알고리즘 짧막 지식 for 면접

# 시간 복잡도

 

- Big-O 표기법: 알고리즘 최악의 실행 시간 표기. 아무리 최악의 상황이여도 이정도의 성능은 보장한다는 의미다.

- 입력 n의 크기에 따른 순서: O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(2^n)

 

# 배열

 

데이터를 나열하고, 각 데이터를 인덱스에 대응하도록 구성한 데이터 구조

 

# 큐

 

가장 먼저 넣은 데이터를 가장 먼저 꺼낼 수 있는 자료구조. First In First Out

 

# 스택

 

가장 나중에 넣은 데이터를 가장 먼저 꺼낼 수 있는 자료구조. Last In First Out

 

# 링크드 리스트

 

물리적으로 떨어진 곳에 존재하는 데이터를 포인터, 즉, 다음 데이터를 가리키는 주소값을 이용해 연결하고 나열하는 데이터 구조.

 

배열은 미리 특정한 공간을 예약해야하지만, 링크드 리스트는 공간 예약이 필요없다. 그러나 '연결'을 위한 별도 데이터 공간이 필요하므로, 저장 공간 효율이 줄어든다.

 

연결 정보를 찾는 시간이 필요하므로 데이터 접근 속도가 느리다.

 

중간 데이터를 삭제하거나 추가 시, 앞 뒤 데이터의 연결을 재구성하는 추가 작업이 필요하다.

 

# 해쉬 테이블

 

키(key)에 데이터(value)를 저장하는 데이터 구조. 키를 통해 데이터를 바로 받아올 수 있으므로, 속도가 빠르다.

 

- 해쉬: 임의 값을 고정 길이로 변환하는 것

- 해싱 함수: 키에 대해 산술 연산을 이용해 데이터 위치를 찾을 수 있는 함수

- 해쉬 값 or 해쉬 주소: 해쉬 테이블에서 특정 키를 통해 알아낸 데이터 위치

 

- 데이터 저장/읽기/검색 속도가 빨라서, 중복 데이터 확인도 빠르다.

- 여러 키에 해당하는 주소가 동일할 경우, 충돌 해결을 위한 별도 자료구조가 필요하다.

- 위와 같은 문제 해결을 위해 일반적으로 저장 공간이 좀 더 많이 필요하다.

 

* 충돌 해결 기법

 

1) Chaining 기법: 해쉬 테이블 저장 공간 외의 공간을 활용한다.

충돌 발생 시, 링크드 리스트를 사용해 데이터를 추가로 뒤에 연결시켜 저장하는 방법이다.

 

2) Linear Probing 기법: 해쉬 테이블 저장 공간 안의 공간을 활용한다.

충돌 발생 시, 해당 해쉬 주소의 다음 주소부터 맨 처음 나오는 빈 공간에 저장하는 방법이다.

 

* 시간 복잡도: 데이터를 저장/읽기할 때 최적 = O(1), 최악 = O(n) (충돌 모두 발생 시)

 

# 트리

 

Node와 Branch를 이용해서, 사이클을 이루지 않도록 구성한 그래프형 자료 구조. 이진 트리의 구조로, 탐색 알고리즘을 위해 많이 사용.

 

- 이진 트리(Binary Tree): 노드의 최대 Branch가 2개인 트리

- 이진 탐색 트리(Binary Search Tree, BST)

: 이진 트리에서, 부모 노드의 왼쪽 자식 노드 값은 부모보다 작고, 오른쪽 자식 노드 값은 부모보다 크다는 조건이 있을 때.

 

- 이진 탐색 트리는 위와 같은 규칙 덕분에, 탐색 속도를 개선할 수 있다는 장점이 있다.

- 알고리즘 자체가 복잡하다는 단점.

 

* 시간 복잡도

 

- 평균 시간 복잡도는 O(logn)이지만 이는 균형 잡혀있을 때만 그러하다.

- 최악의 경우 한쪽으로만 노드가 쏠려 링크드 리스트 형태가 되는데, 이때는 O(n)이 된다.

 

# 힙

 

데이터에서 최댓값과 최솟값을 빠르게 찾기 위해 고안된 완전 이진 트리다. 완전 이진 트리는 노드를 삽입할 때 최하단 왼쪽 노드부터 차례대로 삽입하는 트리다. 부모노드보다 자식노드 값이 항상 더 작다는 규칙이 있다.

 

- 배열에 데이터를 넣고, 최대/최소를 찾으려면 O(n)이 걸린다.

- 힙에 데이터를 넣고, 최대/최소를 찾으려면 O(logn)이 걸린다. 확실히 힙이 더 빠르다.

 

- 최댓값을 구하기 위한 Max Heap 구조와, 최솟값을 구하기 위한 Mini Heap 구조로 분류가 가능하다.

- Max Heap의 경우, 각 노드의 값은 해당 노드의 자식 노드가 가진 값보다 크거나 같다.

- BST와 힙의 공통점은 둘 다 이진 트리, 차이점은 노드에 데이터를 넣는 규칙.

 

* 시간 복잡도: n개의 노드를 가지는 힙에 데이터 추가/삭제 시 시간 복잡도 O(logn)

 

# 버블 정렬 (Bubble Sort)

 

두 인접한 데이터를 비교해서, 앞에 있는 데이터가 뒤에 있는 데이터보다 크면 자리를 바꾸는 알고리즘. 그렇지 않으면 그대로 두고 다음 데이터와 비교한다. 최적 O(n), 최악 O(n^2)

 

# 선택 정렬 (Selection Sort)

 

주어진 데이터 중 최솟값을 찾고, 해당 최솟값을 데이터 맨 앞에 위치한 값과 교체한다. 맨 앞의 위치를 뺀 나머지 데이터를 동일한 방법으로 반복한다. 최적 O(n^2), 최악 O(n^2)

 

# 삽입 정렬 (Insertion Sort)

 

두 번째 인덱스부터 시작, 해당 인덱스의 데이터를 임시로 따로 저장하고, 그 인덱스의 뒤쪽 데이터들과 비교하여, 자신보다 큰 데이터 바로 뒤에 삽입한다. 최적 O(n), 최악 O(n^2)

 

# 재귀 용법 (Recursive Call)

 

고급 정렬 알고리즘에서 사용한다. 함수 안에서 동일 함수를 호출한다.

 

# 동적 계획법 (Dynamic Programming)

 

입력 크기가 작은 부분 문제들을 해결한 후, 해당 부분 문제의 결과를 이용해서 상위 문제를 풀어나가고, 최종적으로 전체 문제를 해결하는 알고리즘 기법이다. 대표적으로 피보나치 수를 찾는 알고리즘에 쓰일 수 있다.

 

- Memoization 기법 사용: 프로그램 실행 시 이전에 계산한 값을 저장하여, 다시 계산하지 않도록 해 전체 실행 속도를 빠르게 하는 기술

 

# 분할 정복 (Divide and Conquer)

 

문제를 나눌 수 없을 때까지 나누어서, 각각을 풀면서 다시 합병하여 문제의 답을 얻는다.

재귀 함수로 구현하며, 대표적으로 퀵/병합 정렬에 쓰인다.

 

# 동적 계획법과 분할 정복의 공통점과 차이점

 

- 공통점: 문제를 가장 작은 단위로 분할해서 최종 문제를 푸는데 사용한다.

- 차이점: 동적 계획법은 부분 문제가 중복되고, 상위 문제 해결 시 그 부분 문제들이 재활용되고, Memoization 기법 사용

              분할 정복은 부분 문제가 중복 X고, 상위 문제 해결 시 그 부분 문제들이 재활용 X고, Memoization 기법 사용 X

 

# 퀵 정렬 (Quick Sort)

 

기준(pivot)을 정해서, 기준보다 작은 데이터는 왼쪽, 기준보다 큰 데이터는 오른쪽으로 모으고, 각 왼쪽과 오른쪽은 다시 동일 함수를 호출해 위 작업을 반복한다. 즉, pivot을 기준으로 계속 왼쪽/오른쪽으로 나눈 다음 나중에 쭉 합침. 분할 정복의 예시.

 

# 병합 정렬 (Merge Sort)

 

하나의 배열을 반으로 계속해서 자르면서 마지막에 원소가 1개일 때까지 계속 잘라나가고, 잘라진 조각들이 합쳐지면서 동시에 정렬되도록 하는 알고리즘. 분할 정복의 예시.

 

# 순차 탐색 (Sequential Search)

 

데이터가 담겨있는 리스트를 앞에서부터 하나씩 비교하여 찾는 방법. 데이터 길이가 n일 때 최적 O(1), 최악 O(n)

 

# 이진 탐색 (Binary Search)

 

데이터가 이미 정렬되어있다는 가정하에, 가운데 원소를 우선 뽑아놓고 그것보다 작거나 큰 범위에서 또 가운데 원소를 뽑으며, 탐색 범위를 좁혀가는 식으로 원하는 데이터를 찾는 기법. 데이터 길이가 n일 때 최악 O(logn)

 

# 그래프

 

실제 세계의 현상이나 사물을 노드(Node)와 엣지(Edge)로 표현하기 위해 사용된다.

 

- simple path: 처음과 끝 노드를 제외하고 중복된 노드가 없는 경로

- cycle: simple path의 처음과 끝 노드가 동일한 경우의 그래프

 

# BFS (Breadth First Search, 너비 우선 탐색)

 

그래프에서, 노드들과 같은 레벨에 있는 노드들(형제 노드들)을 먼저 탐색하는 방식. 방문할 노드는 큐, 방문한 노드도 큐로 구현.

 

# DFS (Depth First Search, 깊이 우선 탐색)

 

그래프에서, 노드들의 자식을 먼저 탐색하는 방식. 방문할 노드는 큐, 방문한 노드는 스택으로 구현.

 

* BFS와 DFS 모두 대표적인 그래프 탐색 알고리즘이며, 노드 수 V, 엣지 수 E일 때 시간 복잡도 O(V+E)이다.

 

# 탐욕 알고리즘 (Greedy Algorithm)

 

최적의 해에 가까운 값을 찾기 위해 사용된다. 근사치 추정에 이용된다. 여러 경우 중 하나를 선택할 때마다, 매순간 최적이라고 생각되는 경우를 선택하는 방식으로 진행해서, 최종적인 값을 구하는 방식이다. 그러나, 매순간, 그때마다 최적의 선택을 하기 때문에 구한 값이 최적이 아닐수도 있다.

 

# 다익스트라 알고리즘 (Dijkstra Algorithm)

 

방향이 있는(유향) 가중치 그래프에서, 한 노드에서 다른 모든 노드 간의 가장 짧은 거리를 구하는, 최단 경로 탐색 알고리즘 중 하나. 탐욕 알고리즘의 한 종류다.

 

특정 출발점 노드와 연결되어있는 노드들 간의 거리를 배열에 기록하고, 그 거리들 중 최단 거리가 기록되도록 배열을 업데이트 한다. 만약 최단 거리가 배열에 업데이트되는 경우엔 그 업데이트된 노드와 거리 정보가 우선 순위 큐에 들어가게 되고, 그 우선 순위 큐에서 노드와 거리 정보를 꺼내 이용하여, 출발점 노드와 다른 노드 간의 거리를 계산하고 업데이트하게 된다.

 

# MST (Minimun Spanning Tree, 최소 신장 트리)

 

- 신장 트리(Spanning Tree)

: 원래 그래프의 모든 노드가 연결되어 있으면서, 동시에 트리의 구조를 지닌, 즉 사이클이 없는 구조를 만족하는 그래프

 

- MST

: 가능한 spanning tree 중에서, 엣지의 가중치 합이 최소인 spanning tree

 

# 크루스컬 알고리즘 (Kruskal Algorithm) - MST를 위한 알고리즘 ①

 

그래프의 엣지들을 최소 비용(가중치) 기준으로 정렬한 다음, 모든 노드를 연결하되 사이클이 생기지 않도록 연결하여 MST를 만드는 알고리즘. 이때 Union-Find 알고리즘이 사용된다.

 

- Union-Find 알고리즘

: 노드를 연결했을 때 사이클이 생기는지 안 생기는지를 체크하고, 사이클이 생기면 버리고, 안 생기면 두 노드 부분집합을 연결해서 하나의 부분집합으로 만드는 알고리즘. 그리고 Union-Find 알고리즘 과정 중 union-by-rank 기법과 path compression 기법 사용됨.

 

* union-by-rank 기법 (union 시 사용)

: 각 트리에 대해 높이(rank)를 기억해두고, union 시 각 트리의 높이가 다르면, 높이가 작은 트리를 높이가 큰 트리에 붙인다.

 

*  path compression 기법 (find 시 사용)

: find 과정으로 루트 노드 찾고, find 과정을 거친 노드들을 루트 노드에 다이렉트로 연결하는 기법

 

⇒ 두 기법을 사용하면 노드 수가 무한정 늘어나도 크루스컬 알고리즘의 시간 복잡도가 O(1), 즉 상수값에 가깝다는 것이 증명됨

 

# 프림 알고리즘 (Prim's Algorithm) - MST를 위한 알고리즘 ②

 

그래프에서, 특정 노드에서 시작해, 노드에 인접한 엣지 중 최소 엣지로 연결된 노드를 선택하고, 해당 노드에서 다시 최소 엣지로 연결된 노드를 선택하는 방식으로 MST를 확장하는 방식.

 

# 크루스컬 알고리즘과 프림 알고리즘의 공통점/차이점

 

- 공통점: 둘 다 탐욕 알고리즘에 기반을 두어서, 매순간 최적의 선택을 하게 되어있다.

- 차이점: 크루스컬 알고리즘은 전체 엣지를 고려하지만, 프림 알고리즘은 지금까지 연결된 노드들에 있는 엣지들만 고려한다.

 

* 시간 복잡도

: 크루스컬 알고리즘 → 처음엔 O(n), union-by-rank 사용 시 O(logn), path compression 사용 시 O(1)

  프림 알고리즘 (개선된 것) → 노드 수 V, 엣지 수 E일 때, O(ElogV)