[Algorithm] 코딩테스트 알고리즘 선택 트리

알고리즘 선택 결정 트리

1. 투포인터 (Two Pointers)

적합 조건:

• 정렬된 배열에서 쌍(pair) 탐색 필요 시
• 연속된 부분 수열/문자열 처리 (최장/최단 구간)
• O(N²) → O(N) 시간 복잡도 개선 필요 시

예시 문제:

• 두 수의 합 찾기 (Two Sum)
• 최대 부분 배열 합 (Maximum Subarray)
• 중복 없이 가장 긴 부분 문자열 (Longest Substring Without Repeating Characters)

2. BFS/DFS

적합 조건:

BFS	DFS
최단 경로 탐색 (미로, 게임 맵)	모든 경로 탐색/백트래킹 필요
레벨 순회 (트리/그래프)	사이클 감지/연결 성분 분석
가중치 없는 그래프	복잡한 제약 조건 있는 문제

예시 문제:

• BFS: 미로 탈출 최단 경로
• DFS: N-Queens 문제

3. 동적 계획법 (DP)

적합 조건:

• 중복 계산 발생 (피보나치 수열)
• 최적 부분 구조 존재 (Knapsack 문제)
• 문제를 하위 문제로 분할 가능

핵심 접근법:

    memo = {} 
    def fib(n): 
        if n in memo: 
            return memo
        if n <= 2: 
            return 1 
        memo = fib(n-1) + fib(n-2) 
        return memo

예시 문제:

• 최장 증가 부분 수열 (LIS)
• 코인 변경 문제 (Coin Change)

4. 백트래킹

적합 조건:

• 모든 가능한 조합 탐색 필요 (순열/조합)
• 조건부 프루닝으로 탐색 공간 축소 가능
• 결정 문제 (예/아니오 경로 선택)

예시 문제:

• 스도쿠 풀이
• 여행하는 세일즈맨 문제 (TSP)

5. 이진 탐색 (Binary Search)

적합 조건:

• 정렬된 데이터에서 값 탐색
• 최소/최대 값 찾기 (parametric search)
• O(log N) 시간 복잡도 요구 시

예시 문제:

• 회전된 정렬 배열 탐색
• 예산 분배 최대 값 찾기