algorithm

Algorithm (알고리즘)

알고리즘 기본 ▶︎ 🗒

• 시간복잡도와 공간복잡도
• 완전 탐색 알고리즘 (Brute Force)
  • DFS와 BFS
  • 순열, 조합, 부분집합
• 백트래킹 (Backtracking)
• 분할 정복법 (Divide and Conquer)
• 탐욕 알고리즘 (Greedy)
• 동적 계획법 (Dynamic Programming)

알고리즘 응용

• 정렬 알고리즘 (Insertion / Selection / Bubble / Merge / Quick / Heap / Radix / Counting Sort)
• 그래프
  • 최단 경로 알고리즘 (다익스트라, 벨만-포드, 플로이드-워셜)
  • 분리 집합(Union Find)과 크루스칼(Kruskal) 알고리즘
• 두 포인터 (two-pointer)
• 문자열 처리 알고리즘
  • KMP 알고리즘

---

질의응답

DFS와 BFS의 장단점에 대해 각각 설명해 주세요.

1. BFS 장점
   1. 너비를 우선으로 탐색하기 때문에 답이 되는 경로가 여러개인 경우에도 최단경로임을 보장합니다.
   2. 최단 경로가 존재한다면, 어느 한 경로가 무한히 깊어진다 해도 최단경로를 반드시 찾을 수 있습니다.
   3. 노드의 수가 적고 깊이가 얕은 해가 존재할 때 유리합니다.
2. BFS 단점
   1. 재귀 호출을 사용하는 DFS와는 달리 큐를 이용해 다음에 탐색할 노드들을 저장합니다. 이 때, 노드의 수가 많을 수록 필요없는 노드들까지 저장해야하기 때문에 더 큰 저장공간이 필요합니다.
   2. 노드의 수가 늘어나면 탐색해야하는 노드 또한 많아지기 때문에 비현실적입니다.
3. DFS 장점
   1. BFS에 비해 저장공간의 필요성이 적고 백트래킹을 해야하는 노드들만 저장해주면 됩니다.
   2. 찾아야하는 노드가 깊은 단계에 있을 수록, 그 노드가 좌측에 있을 수록 BFS보다 유리합니다.
4. DFS 단점
   1. 답이 아닌 경로가 매우 깊다면, 그 경로에 깊이 빠질 우려가 있습니다.
   2. 내가 지금까지 찾은 최단경로가 끝까지 탐색 했을 때의 최단경로가 된다는 보장이 없습니다.

---

라이브러리 없이 정렬을 구현하려고 할 때 어떤 정렬 방식을 사용해 구현할 것이고 왜 그렇게 생각하는지 성능 측면에서 얘기를 해주세요.

(예시 답안) 퀵소트로 구현할 것입니다. 퀵소트는 average case에서 nlgn의 시간복잡도를 가지며 공간복잡도 측면에서도 제자리 정렬이기 때문에 좋은 성능을 가집니다. worst case의 경우 n^2의 시간복잡도를 가지지만 worst case가 나타날 경우는 확률적으로 매우 낮습니다. (자료가 n개일 때 오름차순 또는 내림차순 -> 2/n!)

퀵소트에서 최악의 경우 시간복잡도를 개선시킬 수 있는 방법이 있을까요?

피벗의 위치를 다르게 설정함으로써 시간복잡도를 개선시킬 수 있습니다. 일정한 위치에 대해서만(ex. 첫번째 element) 피벗을 설정하는 것보다 첫번째, 마지막 element 중 무작위로 선택한다거나 첫번째, 가운데, 마지막 element 중 중간값을 계산하여 피벗을 설정했을 때 시간복잡도를 더 개선시킬 수 있습니다.

머지소트의 분할 정복 과정에 대해 단계별로 설명해주세요.

• Divide : 초기 배열을 2개의 배열로 분할
• Conquer : 각 부분 배열을 정렬
• Combine : 부분 배열을 하나의 배열로 결합

---

MST(Minimum Spanning Tree)를 구하는 알고리즘에 대해 설명하고, 각각 어떤 상황에서 사용하는 것이 적절한지 설명해 주세요.

정점의 개수 : V, 간선의 개수 : E

대표적으로 프림 알고리즘과 크루스칼 알고리즘이 있습니다. 프림 알고리즘은 정점을 선택하고 그것과 연결된 가장 적은 비용의 정점을 선택하는 방식이며, O(ElogV)의 시간복잡도를 가집니다. 크루스칼 알고리즘은 모든 간선에 대하여 가장 비용이 적은 간선을 선택하는 방식이며 O(ElogE)의 시간복잡도를 가집니다. 프림 알고리즘은 정점의 개수에 비해 간선이 많이 주어진 경우 사용하는 것이 좋고, 크루스칼 알고리즘은 간선의 개수에 비해 정점이 많이 주어진 경우 사용하는 것이 좋습니다.

Minmum Spanning Tree를 찾기 위한 프림 알고리즘의 동작원리 또는 특징에 대해 설명해주세요

1. 시작 단계에서는 시작 정점만이 MST(최소 비용 신장 트리) 집합에 포함된다.
2. 앞 단계에서 만들어진 MST 집합에 인접한 정점들 중에서 최소 간선으로 연결된 정점을 선택하여 트리를 확장한다.즉, 가장 낮은 가중치를 먼저 선택한다.
3. 위의 과정을 트리가 (N-1)개의 간선을 가질 때까지 반복한다.

Minmum Spanning Tree를 찾기 위한 크루스칼 알고리즘의 동작원리 또는 특징에 대해 설명해주세요

1. 그래프의 간선들을 가중치의 오름차순으로 정렬한다.
2. 정렬된 간선 리스트에서 순서대로 사이클을 형성하지 않는 간선을 선택한다.
   1. 즉, 가장 낮은 가중치를 먼저 선택한다.
   2. 사이클을 형성하는 간선을 제외한다.(Union-Find 사용)
3. 해당 간선을 현재의 MST(최소 비용 신장 트리)의 집합에 추가한다.

---

최단경로를 구하기 위한 알고리즘을 두 가지 이상 말하고 어떤 차이점이 있는지 설명해주세요.

• 다익스트라 : 하나의 시작 정점 ~ 모든 다른 정점까지의 최단 경로를 구한다.
• 벨만포드 : 하나의 시작 정점 ~ 모든 다른 정점까지의 최단 경로를 구한다. + 가중치가 음수일 때도 사용이 가능하다. (음의 사이클 검사 가능)
• 플로이드 와샬 : 모든 정점 ~ 모든 정점까지의 최단 경로를 구한다.

다익스트라 알고리즘 동작원리 또는 특징을 시간복잡도와 연관지어 설명해주세요.

(방법 1)

1. 출발 노드 S에서 모든 노드들까지의 최단 거리를 저장하는 배열 D를 초기화한다.
2. 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택한다. (D 배열 검사)
3. 선택한 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 배열 D를 갱신한다.
4. 모든 노드를 방문할 때까지 3, 4 과정을 반복한다.
5. 노드의 개수를 V라고 할 때, 총 V*V번 연산이 필요하므로 O(V^2)의 시간복잡도를 가진다.

(방법 2 - 힙/우선순위큐 사용)

1. 출발 노드 S에 대하여 D 배열을 초기화할 때 D[S] = 0을 해준다. 이와 동시에 힙에 노드 정보(번호, 거리 : [S, 0])를 넣어준다.
2. 힙에서 맨 위에 있는 노드 I를 꺼낸다.
3. 만일 꺼낸 노드 I의 거리 정보가 현재 D[I]보다 크다면 이미 방문한 노드일 것이므로 무시한다.
4. I를 대상으로 다익스트라 알고리즘을 수행하는데, D 배열이 갱신될 경우 그 노드 정보를 힙에 넣는다.
5. 힙에 노드가 없을 때까지 2-4 과정을 반복한다.
6. 노드의 개수를 V, 간선의 개수를 E라고 할 때 시간 복잡도는 O(ElogV) 이다.

다익스트라 알고리즘에서 힙(우선순위큐)을 사용할 경우 어떤 점에서 시간복잡도가 개선이 되나요?

다익스트라 알고리즘에서 방문하지 않은 노드 중 최단 거리가 가장 짧은 노드를 선택하는 과정이 있는데, 이 과정에서 O(노드의 개수)만큼의 비용이 발생하게 됩니다. 힙(우선순위큐)을 사용할 경우 그 비용을 O(log{힙에 저장한 노드의 개수})로 줄일 수 있습니다.

벨만포드 알고리즘 동작원리 또는 특징을 시간복잡도와 연관지어 설명해주세요.

1. 음의 가중치를 가지는 간선도 가능하므로, 음의 사이클의 존재 여부를 따져야 한다.
2. 최단 거리를 구하기 위해서 V - 1번 E개의 모든 간선을 확인한다.
3. 음의 사이클 존재 여부를 확인하기 위해서 한 번 더 (V번째) E개의 간선을 확인한다.
4. 이 때 거리 배열이 갱신되었다면, 그래프 G는 음의 사이클을 가진다.
5. 따라서 총 V x E 번 연산하므로 O(VE)의 시간복잡도를 가진다.

플로이드 와샬 알고리즘 동작원리 또는 특징을 시간복잡도와 연관지어 설명해주세요.

1. 사이클이 없다면 음수 가중치를 가져도 적용 가능하다.
2. 동적 계획법(Dynamic Programming)으로 접근한다.
3. 모든 가능한 경유지에 대해서 모든 정점 -> 모든 정점으로 가는 최단 거리를 확인하므로 연산 횟수는 V^3이고, 따라서 시간복잡도는 O(V^3)

---

KMP 알고리즘에 대해 설명해주세요.

Kunth, Morris, Prett이 만든 알고리즘이라서 각 이름의 앞자리를 따서 KMP라고 지어졌습니다. 문자열이 불일치할 때 그 다음 문자부터 다시 탐색을 시작하는 것이 아니라 지금까지 일치했던 정보들을 버리지 말고 재사용 함으로써 몇칸 정도는 건너 뛰어서 탐색하자는 아이디어에서 알고리즘이 탄생했습니다. 접두사와 접미사 정보를 가지고 문자열을 점프해가며 탐색하는데, Naive한 문자열 탐색 알고리즘이 O(NM)의 시간복잡도를 갖는 반면에 KMP알고리즘은 O(N+M)의 시간복잡도를 갖습니다.

라빈 카프 알고리즘에 대해 설명해주세요.

문자열의 해시함수값을 이용합니다. 탐색 대상 문자열의 길이를 M이라고 했을 때 글을 M칸씩, 한칸 한칸 옮겨가며 부분 문자열을 떼어내고 해시함수값을 구하여 탐색 문자열의 해시함수값과 비교합니다. 해시함수값 충돌이 없다는 가정하에 글의 길이를 N이라고 하면 O(N-M)의 시간복잡도를 갖습니다.

라빈 카프 알고리즘이 KMP보다 빠른가?

사실상 그렇지 않습니다. 탐색 문자열의 길이가 길어질 수록 해시함수값에 충돌이 생길 확률이 높습니다. 따라서 해시함수값이 일치한다고 무조건 문자가 일치한다고 보장할 수 없기 때문에 해시함수값이 일치했을 때 문자열을 직접 비교하는 2차적인 검증이 필요합니다. 따라서 평균적으로 라빈 카프 또한 O(N+M)의 시간복잡도가 요구됩니다.

자료구조의 한 종류인 트라이를 설명해주세요.

트라이는 문자열을 저장하고 효율적으로 탐색하기 위한 트리 형태의 자료구조이다. 기본적으로 k진트리 구조를 띠고 어떤 문자열 집합 S와 문자열 A가 있다고 할 때 A가 S안에 존재하는지 찾는데에 사용되는 자료구조이다.

트라이의 장점과 단점을 설명해주세요.

이분탐색은 탐색하는데에 있어 검색어의 최대 길이 M * 전체 데이터 N 중 O(M log N)을 사용하게 되는데 이에 반해 트라이는 문자열 탐색에서의 전체 데이터의 길이인 시간복잡도 O(N)을 가지게 되어 매우 효율적이다. 하지만 트라이의 단점은 공간 복잡도가 높다. 알파벳을 저장하는 형태라면 1 depth당 26개의 공간이 사용될 수 있다.

트라이 자료구조를 사용한 적이 있나요? 경험을 이야기해주세요.

모범 답안) 알고리즘을 공부하는 과정에서 트라이 자료구조를 이용하여 아호코라식 알고리즘을 작성하여 문제를 해결했던 경험이 있습니다. 아호코라식 알고리즘은 KMP에서 사용하는 Failure Function을 트라이로 확장시킨 알고리즘으로 문자열 탐색에 사용하였습니다.

---

투포인터라는 알고리즘 문제 해결 전략이 있습니다. 어떤 알고리즘이고 주로 어떤 문제를 해결하는데 사용되나요?

배열을 가리키는 포인터 2개를 이용해서 포인터를 한칸 씩 움직이며 특정 구간 내에서 원하는 값을 얻을 때 사용합니다. 예를 들면 연속되는 배열의 구간 중 특정 조건을 만족하는 가장 짧은 구간을 구하는 문제에서 사용될 수 있습니다.