[2 과목] 알고리즘 설계 기법

📌 관련 기출문제:

• 2024년 3회 : 알고리즘 설계 기법으로 거리가 먼 것은?

☑︎ 분할 정복법 (Divide & Conquer)

문제를 더 작은 하위 문제로 나누고, 각각 해결한 후 합쳐서 원래 문제를 푸는 방식.
예: 병합 정렬, 퀵 정렬, 이진 탐색

☑︎ 동적 계획법 (Dynamic Programming)

복잡한 문제를 중복되는 작은 문제로 나누고, 결과를 저장하여 중복 계산을 피하는 방식.
예: 피보나치 수열, 배낭 문제, 최장 공통 부분 수열

☑︎ 탐욕법 (Greedy Method)

매 단계에서 가장 최선의 선택을 하는 방식. 전체 최적 해를 보장하지는 않음.
예: 동전 거스름돈 문제, 크루스칼 알고리즘

☑︎ 퇴각 검색법 (Backtracking)

해를 찾다가 조건에 맞지 않으면 이전 단계로 되돌아가서 다시 탐색하는 방식.
예: N-Queen, 미로 찾기, 순열 생성

☑︎ 분기 한정법 (Branch & Bound)

가능한 해의 공간을 트리 형태로 나누고, 유망하지 않은 해를 잘라내는 방식.
예: 외판원 문제, 최적 경로 탐색

☑︎ 근사해법 (Approximation Algorithm)

최적 해를 구하기 어렵거나 시간이 오래 걸릴 때, 근사적으로 좋은 해를 빠르게 구하는 방식.
예: NP-완전 문제에서 사용