[25년 03차 / 문제풀이] 알고리즘 설계 기법

 

개념

 

☐ 분할정복법(Divide and Conquer)

 

●  문제를 쪼개서 각각 해결하는 방법

●  복잡한 문제를 분할하여 각각 해결, 이를 결합하여 문제를 해결하는 Top-Down 기법

●  분할 정복의 절차

- 분할(Divide) : 문제를 분할이 가능한 부분까지 분할

- 정복(Conquer) : 분할된 문제를 각각 해결(정복)

- 결합(Combine) : 정복된 문제를 모두 취합(결합)

●  분할 정복의 관련 알고리즘 : 퀵 정렬, 병합 정렬 

 

---

 

☐ 탐욕법(Greedy Algorithm)

 

●  매 단계 최선의 선택, 최적해 보장 못함

●  매 단계에서 최적의 선택을 함으로써, 최종적으로도 최적의 선택을 할 수 있게 하는 알고리즘 설계 기법

●  각 단계의 최선의 값을 택하기 때문에 전체적 관점에서는 최적해를 보장하지 못함

●  관련 알고리즘 : 거스름돈 문제, 최소 신장 트리, 다익스트라, 크루스컬, 허프만 코딩 등

- 최소 신장 트리(스패닝 트리, Spanning Tree)

+ 그래프의 최소 연결 부분 그래프

+ 최소 연결 = 간선의 수가 가장 적다

+ 브리지와 구내 정보 통신망(LAN)으로 구성된 통신망에서 루프(폐회로)를 형성하지 않으면서 연결을 설정하는 알고리즘

 

---

 

☐ 백트랙킹(Backtracking)

 

●  모든 경로 탐색, 막히면 돌아가서 다시 탐

●  가능한 모든 경로를 탐색하는 방식

●  찾는 도중 해가 아니어서 막히면, 되돌아가서 다시 해를 찾아가는 기법

●  최적화 문제와 결정 문제를 푸는 방법

●  백트랙킹의 관련 알고리즘 : DFS(깊이 우선 탐색) 

 

---

 

☐ 깊이 우선 탐색(DFS)

 

●  깊이 우선 탐색(DFS)의 개념 : 정점에서 자식 노드 방향으로 운행하면서 형제 노드와 자식 노드가 있을 때, 자식 노드를 우선 탐색하는 기법

●  깊이 우선 탐색의 특징 : 백트래킹을 허용하여 갔던 노드를 다시 되돌아가서 방문하지 않은 노드로 가는 것이 가능함 

●  깊이 우선 탐색의 방법 

- 정점부터 시작

- 자식 노드 방향으로 운행

- 자식 노드와 형제 노드, 둘 다 있을 때 자식 노드를 우선으로 탐색

- 자식 노드의 탐색이 모두 끝난 후 다시 형제 노드부터 탐색 시작

- 모든 노드를 한 번씩 방문함

●  깊이 우선 탐색의 예시

-  A의 자식 노드 : B, C, D로 진행 : A

- C는 자식 노드가 없으므로 B나 D로 진행 (문제 보기에 따라 결정)

- B로 진행할 경우 : A > B

+ B의 자식 노드 E로 진행 : A > B > E

+ E와 연결된 F로 진행 : A > B > E > F

+ F와 연결된 G로 진행 : A > B > E > F > G

+ C로 이동 : A > B > E > F > G > C

+ D로 이동 : A > B > E > F > G > C > D

 

---

 

 

문제

 

☐ 분할정복법(Divide and Conquer)

 

2023년-1차 40번. 알고리즘 설계 기법으로 거리가 먼 것은?

 

① Divide and Conquer
② Greedy
③ Static Block
④ Backtracking

정답 : 3
입력 답 : 2

 

2024년-3차 40번. 분할 정복(Divide and Conquer)에 기반한 알고리즘으로 피봇(pivot)을 사용하여 최악의 경우 n(n-1)/2회의 비교를 수행해야 하는 정렬(Sort)은?

 

① Selection Sort
② Bubble Sort
③ Insert Sort
④ Quick Sort

정답 : 4
입력 답 : 2

 

---

 

☐ 탐욕법(Greedy Algorithm)

 

2022년-3차 93번. 브리지와 구내 정보 통신망(LAN)으로 구성된 통신망에서 루프(폐회로)를 형성하지 않으면서 연결을 설정하는 알고리즘은?

 

① Spanning Tree Algorithm
② Diffie-Hellman Algorithm
③ Hash Algorithm
④ Digital Signature Algorithm

정답 : 1
입력 답 : 4

 

2023년-1차 40번. 알고리즘 설계 기법으로 거리가 먼 것은?

 

① Divide and Conquer
② Greedy
③ Static Block
④ Backtracking

정답 : 3
입력 답 : 2

 

 

---

 

☐ 백트랙킹(Backtracking)

 

2023년-1차 40번. 알고리즘 설계 기법으로 거리가 먼 것은?

 

① Divide and Conquer
② Greedy
③ Static Block
④ Backtracking

정답 : 3
입력 답 : 2

---

☐ 깊이 우선 탐색(DFS)

 

2024년-3차 39번. 다음 그래프에서 정점 A를 선택하여 깊이 우선 탐색(DFS)으로 운행한 결과는?

① ABECDFG
② ABECFDG
③ ABCDEFG
④ ABEFGCD

정답 : 4
입력 답 : 3

 

---