주요 알고리즘 설계 기법들

주요 알고리즘 설계 기법들

1. 분할 정복 (Divide and Conquer)
   • 방법: 큰 문제를 작은 하위 문제로 나누고, 각각을 독립적으로 해결한 후 그 결과를 결합하여 전체 문제의 해결책을 찾습니다.
   • 적용 예시:
     • 병합 정렬(Merge Sort): 배열을 반으로 나누고, 각 부분을 재귀적으로 정렬한 후 합병합니다.
     • 퀵 정렬(Quick Sort): 피벗을 기준으로 배열을 나누고, 각 부분을 재귀적으로 정렬합니다.
     • 이진 탐색(Binary Search): 정렬된 배열에서 중간 요소를 확인하여 탐색 범위를 반으로 줄입니다.
2. 동적 계획법 (Dynamic Programming)
   • 방법: 중복되는 하위 문제들의 결과를 저장하고 재사용하여 효율적으로 전체 문제를 해결합니다.
   • 적용 예시:
     • 피보나치 수열: 이전 두 항의 합을 이용하여 새로운 항을 계산합니다.
     • 최장 공통 부분 수열: 두 시퀀스 간의 가장 긴 공통 부분 수열을 찾습니다.
     • 배낭 문제(Knapsack Problem): 무게 제한 내에서 최대 가치를 가진 물건 조합을 찾습니다.
3. 탐욕 알고리즘 (Greedy Algorithm)
   • 방법: 각 단계에서 현재 상황에서 가장 좋아 보이는 선택을 하여 문제를 해결합니다.
   • 적용 예시:
     • 크루스칼 알고리즘: 최소 신장 트리를 구성하기 위해 가장 가벼운 간선부터 선택합니다.
     • 다익스트라 알고리즘: 최단 경로 문제를 해결하기 위해 가장 낮은 가중치를 가진 경로를 선택합니다.
4. 백트래킹 (Backtracking)
   • 방법: 가능한 모든 해를 탐색하면서, 현재 선택이 유망하지 않으면 이전 단계로 돌아가 다른 선택을 시도합니다.
   • 적용 예시:
     • N-Queen 문제: 체스 판에서 N개의 퀸이 서로를 공격하지 않도록 배치합니다.
     • 해밀턴 경로 문제: 모든 정점을 한 번씩 거쳐가는 경로를 찾습니다.
5. 분기 한계 (Branch and Bound)
   • 방법: 백트래킹과 유사하나, 상한 또는 하한을 사용하여 탐색 범위를 제한합니다.
   • 적용 예시:
     • 여행하는 외판원 문제(TSP): 모든 도시를 방문하는 최소 비용 경로를 찾습니다.
     • 정수 선형 프로그래밍: 제약 조건 하에서 목적 함수를 최적화합니다.
6. 랜덤화 알고리즘 (Randomized Algorithm)
   • 방법: 알고리즘의 일부 단계에서 무작위 선택을 활용합니다.
   • 적용 예시:
     • 랜덤화 퀵 정렬: 피벗을 무작위로 선택하여 평균적인 성능을 개선합니다.
     • 랜덤화 프림 알고리즘: 최소 신장 트리를 구성할 때 무작위 선택을 활용합니다.
7. 브루트 포스 (Brute Force)
   • 방법: 가능한 모든 경우의 수를 시험해 보며 문제를 해결합니다.
   • 적용 예시:
     • 문자열 검색: 문자열 내 모든 위치에서 패턴을 비교합니다.
     • 암호 해독: 가능한 모든 키 조합을 시도합니다.
8. 휴리스틱 (Heuristic)
   • 방법: 문제 해결을 위한 직관적이거나 경험적인 접근 방법을 사용합니다.
   • 적용 예시:
     • 퍼즐 게임: 가장 가능성이 높은 움직임을 선택합니다.
     • AI 알고리즘: 복잡한 문제에서 최선의 추정치를 선택합니다.
9. 비교 기반 정렬 알고리즘 (Comparison-Based Sorting Algorithms)
   • 방법: 요소들 간의 상대적인 순서를 비교하여 정렬합니다.
   • 적용 예시:
     • 힙 정렬(Heap Sort): 이진 힙 자료 구조를 사용하여 요소들을 정렬합니다.
     • 버블 정렬(Bubble Sort): 인접한 요소들을 비교하고 필요에 따라 교환합니다.
     • 삽입 정렬(Insertion Sort): 각 요소를 적절한 위치에 삽입하여 정렬합니다.