[25년 03차 / 문제풀이] 알고리즘 설계 기법
개념
☐ 분할정복법(Divide and Conquer)
● 문제를 쪼개서 각각 해결하는 방법
● 복잡한 문제를 분할하여 각각 해결, 이를 결합하여 문제를 해결하는 Top-Down 기법
● 분할 정복의 절차
- 분할(Divide) : 문제를 분할이 가능한 부분까지 분할
- 정복(Conquer) : 분할된 문제를 각각 해결(정복)
- 결합(Combine) : 정복된 문제를 모두 취합(결합)
● 분할 정복의 관련 알고리즘 : 퀵 정렬, 병합 정렬
☐ 탐욕법(Greedy Algorithm)
● 매 단계 최선의 선택, 최적해 보장 못함
● 매 단계에서 최적의 선택을 함으로써, 최종적으로도 최적의 선택을 할 수 있게 하는 알고리즘 설계 기법
● 각 단계의 최선의 값을 택하기 때문에 전체적 관점에서는 최적해를 보장하지 못함
● 관련 알고리즘 : 거스름돈 문제, 최소 신장 트리, 다익스트라, 크루스컬, 허프만 코딩 등
- 최소 신장 트리(스패닝 트리, Spanning Tree)
+ 그래프의 최소 연결 부분 그래프
+ 최소 연결 = 간선의 수가 가장 적다
+ 브리지와 구내 정보 통신망(LAN)으로 구성된 통신망에서 루프(폐회로)를 형성하지 않으면서 연결을 설정하는 알고리즘
☐ 백트랙킹(Backtracking)
● 모든 경로 탐색, 막히면 돌아가서 다시 탐
● 가능한 모든 경로를 탐색하는 방식
● 찾는 도중 해가 아니어서 막히면, 되돌아가서 다시 해를 찾아가는 기법
● 최적화 문제와 결정 문제를 푸는 방법
● 백트랙킹의 관련 알고리즘 : DFS(깊이 우선 탐색)
문제
☐ 분할정복법(Divide and Conquer)
2023년-1차 40번. 알고리즘 설계 기법으로 거리가 먼 것은?
① Divide and Conquer
② Greedy
③ Static Block
④ Backtracking
정답 : 3
입력 답 : 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