알고리즘 문제를 풀다 보면 자주 등장하는 패턴들이 있습니다. 오늘은 이런 패턴들을 하나씩 살펴볼게요!
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
'200===Dev Language > DS And Algorithm' 카테고리의 다른 글
문제 해결의 마법 🧙♂️ - 더 똑똑하게 문제 해결하기 (0) | 2024.10.30 |
---|---|
슬라이딩 윈도우(Sliding Window) 완전 정복! 🪟 (0) | 2024.10.30 |
알고리즘 풀이, 이렇게 시작하세요! 🎯 (0) | 2024.10.30 |
Why might insertion sort be inefficient for large datasets? (1) | 2024.06.11 |
What is an Algorithm? (0) | 2024.06.08 |