1.Summary

알고리즘 개념 정리

알고리즘 공부 시 핵심이 되는 5가지 분야를 명확히 정리했습니다.

1. 탐색과 정렬 (Searching & Sorting)

알고리즘	시간복잡도	비고
선형 탐색	$O(n)$
이진 탐색	$O(\log n)$	정렬된 자료에서 탐색
버블 정렬	$O(n^2)$	인접한 두 요소 비교
선택 정렬	$O(n^2)$	최소값 선택 후 교환
삽입 정렬	$O(n^2)$	정렬된 부분에 삽입
합병 정렬	$O(n\log n)$	분할 후 병합
퀵 정렬	평균 $O(n\log n)$, 최악 $O(n^2)$	피벗 기준 분할

---

2. 그리디(Greedy) 알고리즘

현재 단계의 최적해를 선택하여 전체 문제의 최적해를 구함

• 예시: 거스름돈 문제, 최소 신장 트리(Kruskal, Prim)

---

3. 분할 정복(Divide and Conquer)

큰 문제를 작은 부분 문제로 나누어 해결하고 병합

• 예시: 합병 정렬, 퀵 정렬, 거듭제곱 계산

---

4. 동적 프로그래밍(Dynamic Programming)

최적 부분 구조와 중복된 부분 문제를 메모이제이션을 활용해 해결

• 예시: 피보나치 수열, 배낭 문제, 최장 공통 부분 수열(LCS)

---

5. 그래프(Graph) 알고리즘

위상 정렬(Topological Sort)

• 방향성 비순환 그래프(DAG)에서 순서를 정하는 알고리즘
• BFS 혹은 DFS 이용해 구현
• 주로 작업 스케줄링 문제에서 사용

최소 신장 트리(MST)

모든 노드를 최소 비용으로 연결하는 트리

크루스칼(Kruskal) 알고리즘

• 모든 간선을 가중치 순으로 정렬
• 사이클이 형성되지 않는 가장 작은 간선을 선택
• Union-Find 자료구조 사용
• 시간복잡도: $O(E\log E)$

프림(Prim) 알고리즘

• 하나의 노드에서 시작해 가장 낮은 가중치를 가진 연결 노드를 선택하며 확장
• 우선순위 큐(힙)를 사용하여 효율적 구현
• 시간복잡도: $O(E\log V)$

최단 경로(Shortest Path)

다익스트라(Dijkstra)

• 음수 가중치 없는 그래프에서 최단 경로
• 우선순위 큐를 이용해 탐색
• 시간복잡도: $O(E\log V)$

벨만-포드(Bellman-Ford)

• 음수 가중치를 포함한 그래프에서 최단 경로 탐색 가능
• 모든 간선을 V-1번 완화(relaxation)
• 음수 사이클 감지 가능
• 시간복잡도: $O(VE)$

플로이드-워셜(Floyd-Warshall)

• 모든 정점에서 다른 모든 정점까지 최단 경로 탐색
• DP를 이용한 점화식: \(D_{ij}^{(k)} = \min(D_{ij}^{(k-1)}, D_{ik}^{(k-1)} + D_{kj}^{(k-1)})\)
• 시간복잡도: $O(V^3)$

---

그래프 알고리즘(심화 정리)

그래프 알고리즘은 그래프라는 자료구조(노드와 간선으로 구성된)를 활용하여 특정 문제를 해결하는 알고리즘이다.

여기선 특히 중요한 알고리즘들인 위상 정렬, 크루스칼 알고리즘, 프림 알고리즘을 중점으로 살펴볼게.

---

① 위상 정렬(Topological Sort)

정의

방향성 비순환 그래프(DAG, Directed Acyclic Graph)에서 정점들을 순서대로 나열하는 알고리즘이다.
주로 작업의 선후 관계를 결정할 때 사용된다.

• 진입차수(Indegree)를 활용한 방식이 대표적이다.
• 결과가 유일하지 않을 수 있다. (조건 만족 시 여러 답 존재 가능)

동작 원리

1. 모든 노드의 진입차수를 계산한다.
2. 진입차수가 0인 노드를 큐(queue)에 넣는다.
3. 큐에서 노드를 하나씩 빼면서, 그 노드와 연결된 간선을 제거한다. 간선이 제거된 노드의 진입차수가 0이 되면 큐에 넣는다.
4. 큐가 빌 때까지 위 과정을 반복한다.

시간 복잡도

• 간선 수 ( E ), 정점 수 ( V )일 때: [ O(V + E) ]

---

② 크루스칼 알고리즘(Kruskal Algorithm)

정의

최소 신장 트리(MST, Minimum Spanning Tree)를 찾는 대표적인 알고리즘이다.
MST란 모든 노드를 연결하면서 가장 낮은 가중치 합을 가지는 트리다.

• 그리디(Greedy) 기반 알고리즘이다.

동작 원리

1. 간선을 가중치 기준으로 오름차순 정렬한다.
2. 가중치가 가장 낮은 간선부터 순서대로 선택한다.
   • 이때, 선택한 간선이 사이클을 형성하면 선택하지 않는다.
3. 선택된 간선의 개수가 노드 수 - 1이면 종료된다.

사이클 판별 방법

• Union-Find 자료구조 활용

시간 복잡도

• 간선 수 ( E ), 정점 수 ( V )일 때: [ O(E\log E) \quad (\because\text{정렬 시간}) ]

---

③ 프림 알고리즘(Prim Algorithm)

정의

크루스칼과 마찬가지로 최소 신장 트리(MST)를 찾는 그리디 알고리즘이다.
크루스칼이 간선 중심이라면, 프림은 노드 중심으로 확장된다.

동작 원리

1. 임의의 노드에서 시작하여 이 노드를 포함한 집합을 만든다.
2. 현재 집합에서 연결 가능한 간선 중 가장 가중치가 낮은 간선을 골라 연결한다.
   • 연결된 노드를 집합에 포함한다.
3. 집합에 포함된 노드가 전체 노드를 포함할 때까지 반복한다.

구현 시 유의사항

• 우선순위 큐(힙)을 사용하여 매번 최적의 간선을 효율적으로 선택한다.

시간 복잡도

• 간선 수 ( E ), 정점 수 ( V )일 때:
  • 단순 구현: ( O(V^2) )
  • 힙 사용 최적화: ( O(E\log V) )

---

세 알고리즘의 요약 비교

알고리즘	방식	주 용도	시간 복잡도
위상 정렬	DAG에서 순서 찾기	작업 스케줄링	( O(V + E) )
크루스칼	가중치 낮은 간선 선택(Union-Find 활용)	MST 구성	( O(E\log E) )
프림	노드 기준 확장(우선순위 큐 활용)	MST 구성	( O(E\log V) )

---

실제 동작 예시

위상정렬 예시

다음 그래프를 예시로 하자.

A → B → D
↓    ↘︎
C → E

1. 진입차수:
   • A(0), B(1), C(1), D(1), E(2)
2. 진입차수 0인 A 큐에 추가 → A 선택 후 B,C 진입차수 감소
3. B, C 진입차수 0이므로 큐에 추가 → 선택 반복 (예: A→B→C→D→E 순서)

---

크루스칼 예시 (MST)

간선: {A-B(1), A-C(3), B-C(1), B-D(4), C-D(1)}

1. 정렬 후: A-B(1), B-C(1), C-D(1), A-C(3), B-D(4)
2. A-B 선택, B-C 선택, C-D 선택
   (사이클 없으므로 최소 신장 트리 완성)

• 총 가중치: (1+1+1=3)

---

프림 예시 (MST)

같은 그래프에서 시작노드 A라고 하면:

1. A에서 최소 간선 A-B(1) 선택 → 노드 집합 {A,B}
2. 집합 {A,B}에서 최소 간선 B-C(1) 선택 → 집합 {A,B,C}
3. 집합 {A,B,C}에서 최소 간선 C-D(1) 선택 → 집합 {A,B,C,D}

• 총 가중치: 역시 (1+1+1=3)