코딩테스트 자주 출제되는 알고리즘 유형, 각 알고리즘 별 문제 접근 방법

코딩 테스트에서 자주 출제되는 주요 알고리즘 종류와 각 알고리즘의 특징, 그리고 어떤 문제 유형에 어떤 알고리즘이 적합한지에 대해 알아보겠습니다.

1. 그리디 알고리즘 (Greedy Algorithm)

• 특징: 각 단계에서 가장 좋아 보이는 선택을 하며 최종적인 해답에 도달하는 방법.
• 적용 예시: 최적의 해를 구하는 것이 중요하고, 각 선택이 서로 간섭이 없을 때 (즉, 한 선택이 다른 선택에 영향을 미치지 않을 때).

2. 분할 정복 (Divide and Conquer)

• 특징: 문제를 더 작은 문제로 나누어 해결한 후, 결과를 합쳐서 전체 문제의 해를 구함.
• 적용 예시: 큰 문제를 작은 문제로 분할하여 해결할 수 있는 경우, 주로 재귀적으로 구현됨.

3. 동적 계획법 (Dynamic Programming)

• 특징: 이전 단계의 결과를 저장하고 활용하여 중복 계산을 피하며 문제를 해결하는 방법.
• 적용 예시: 최적 부분 구조와 중복 부분 문제가 있을 때, 주로 최단 경로 문제나 최장 부분 수열 등에 사용됨.

4. BFS (너비 우선 탐색, Breadth-First Search)

• 특징: 시작 정점에서 가까운 정점부터 탐색하며 최단 경로를 찾는 알고리즘.
• 적용 예시: 최단 경로 문제, 두 노드 사이의 최소 거리를 찾는 문제에 사용됨.

5. DFS (깊이 우선 탐색, Depth-First Search)

• 특징: 한 정점에서 시작하여 그래프의 모든 정점을 탐색하는 알고리즘.
• 적용 예시: 그래프에서 사이클 찾기, 연결 요소 개수 세기 등에 사용됨.

6. 이분 탐색 (Binary Search)

• 특징: 정렬된 배열에서 중간 값과 비교하여 탐색 범위를 반으로 줄여나가는 방법.
• 적용 예시: 정렬된 배열에서 특정 값의 위치를 찾는 문제, 최솟값이나 최댓값 찾기 등에 사용됨.

7. 투 포인터 (Two Pointers)

• 특징: 배열이나 리스트에 포인터를 두 개 사용하여 해결하는 알고리즘.
• 적용 예시: 부분 배열의 합이나 특정 조건을 만족하는 구간을 찾는 문제에 사용됨.

8. 그래프 이론 (Graph Theory)

• 특징: 정점과 간선으로 이루어진 그래프를 다루는 이론적인 알고리즘들의 모음.
• 적용 예시: 최단 경로 문제, 최소 신장 트리(MST) 찾기, 네트워크 플로우 등 다양한 문제에 사용됨.

적용 방법

• 문제 특성 파악: 문제가 어떤 유형인지 파악하고, 각 알고리즘의 특성에 맞는 해결 방법을 고려합니다.
• 알고리즘 선택: 문제의 제약 조건과 입력 크기에 따라 적절한 알고리즘을 선택하여 구현합니다.
• 문제 해결 절차: 알고리즘을 적용하여 문제를 해결한 후, 시간 복잡도와 공간 복잡도를 고려하여 최적화합니다.

각 유형별 알고리즘 예제를 통해 자주 출제되는 문제 유형을 외우고 있으면 문제 풀이가 더욱 수월할 것이다.