200===Dev Language/DS And Algorithm

코딩 테스트 필수! 알고리즘 패턴 총정리 🎯

블로글러 2024. 10. 30. 23:08

알고리즘 문제를 풀다 보면 자주 등장하는 패턴들이 있습니다. 오늘은 이런 패턴들을 하나씩 살펴볼게요!

1. 투 포인터 (Two Pointers) 👉👈

배열에서 두 개의 포인터를 조작하며 문제를 해결하는 방법입니다.

// 배열에서 합이 target인 두 수 찾기
public int[] findTwoSum(int[] nums, int target) {
    int left = 0;
    int right = nums.length - 1;

    while (left < right) {
        int sum = nums[left] + nums[right];
        if (sum == target) {
            return new int[]{left, right};
        }
        if (sum < target) left++;
        else right--;
    }
    return new int[]{};
}

주요 사용 사례 💡

  • 정렬된 배열에서 합이 특정 값인 원소 찾기
  • 배열에서 중복 원소 제거
  • 부분 배열의 합 구하기

2. 슬라이딩 윈도우 (Sliding Window) 🪟

고정 크기의 윈도우를 이동시키며 문제를 해결합니다.

// 길이가 k인 부분 배열의 최대 합 찾기
public int maxSubArraySum(int[] arr, int k) {
    int maxSum = 0;
    int windowSum = 0;

    // 첫 윈도우 합 계산
    for (int i = 0; i < k; i++) {
        windowSum += arr[i];
    }

    maxSum = windowSum;

    // 윈도우 슬라이딩
    for (int i = k; i < arr.length; i++) {
        windowSum = windowSum - arr[i-k] + arr[i];
        maxSum = Math.max(maxSum, windowSum);
    }

    return maxSum;
}

주요 사용 사례 💡

  • 연속된 부분 배열의 합
  • 문자열에서 가장 긴 중복없는 부분 문자열
  • 고정 길이 구간의 최대/최소값

3. DFS (깊이 우선 탐색) 🌲

그래프나 트리를 깊이 방향으로 탐색합니다.

public void dfs(int[][] graph, boolean[] visited, int node) {
    visited[node] = true;
    System.out.print(node + " ");

    for (int next : graph[node]) {
        if (!visited[next]) {
            dfs(graph, visited, next);
        }
    }
}

주요 사용 사례 💡

  • 경로 찾기
  • 순열/조합 생성
  • 그래프의 연결 요소 찾기

4. BFS (너비 우선 탐색) 🌊

그래프나 트리를 레벨 단위로 탐색합니다.

public void bfs(int[][] graph, int start) {
    Queue<Integer> queue = new LinkedList<>();
    boolean[] visited = new boolean[graph.length];

    queue.offer(start);
    visited[start] = true;

    while (!queue.isEmpty()) {
        int node = queue.poll();
        System.out.print(node + " ");

        for (int next : graph[node]) {
            if (!visited[next]) {
                queue.offer(next);
                visited[next] = true;
            }
        }
    }
}

주요 사용 사례 💡

  • 최단 경로 찾기
  • 레벨 단위 탐색
  • 최소 변환 횟수 구하기

5. 다이나믹 프로그래밍 (DP) 📝

큰 문제를 작은 문제로 나누어 해결합니다.

// 피보나치 수열 (Bottom-Up 방식)
public int fibonacci(int n) {
    int[] dp = new int[n + 1];
    dp[0] = 0;
    dp[1] = 1;

    for (int i = 2; i <= n; i++) {
        dp[i] = dp[i-1] + dp[i-2];
    }

    return dp[n];
}

주요 사용 사례 💡

  • 최적화 문제
  • 경로의 수 계산
  • 부분 집합의 합

6. 이진 탐색 (Binary Search) 🎯

정렬된 배열에서 효율적으로 값을 찾습니다.

public int binarySearch(int[] arr, int target) {
    int left = 0;
    int right = arr.length - 1;

    while (left <= right) {
        int mid = left + (right - left) / 2;

        if (arr[mid] == target) return mid;
        if (arr[mid] < target) left = mid + 1;
        else right = mid - 1;
    }

    return -1;
}

주요 사용 사례 💡

  • 정렬된 배열에서 값 찾기
  • 최적화 문제의 결정 문제화
  • Lower/Upper Bound 찾기

시간 복잡도 비교 ⏱️

패턴 시간 복잡도
투 포인터 O(n)
슬라이딩 윈도우 O(n)
DFS/BFS O(V + E)
DP 문제에 따라 다름
이진 탐색 O(log n)

마치며 🎁

이러한 패턴들은 마치 레고 블록처럼 조합해서 사용할 수도 있습니다.
예를 들어, 이진 탐색 + 투 포인터나 BFS + DP 등 다양한 조합이 가능하죠!

실전에서는 문제를 보고 어떤 패턴을 적용할지 빠르게 파악하는 것이 중요합니다.
많은 문제를 풀어보면서 패턴을 익혀보세요!


더 자세한 설명이 필요하신가요? 댓글로 남겨주세요! 😊

728x90