여러분 안녕하세요! 이번 강좌에서는 물의 양을 구하는 문제를 통해 C++ 프로그래밍 언어의 기초와 알고리즘 문제 해결 과정을 자세히 살펴보겠습니다. 알고리즘 문제는 단순한 코드 작성을 넘어서, 문제를 어떻게 이해하고 해석할지에 대한 고민이 필요합니다. 따라서 이번에는 문제에 대한 접근 과정, 코드 작성, 성능 분석, 그리고 최적화 전략에 대해 자세히 다루도록 하겠습니다.
문제 설명
문제의 전반적 정의는 다음과 같습니다. 주어진 높이의 배열이 있을 때, 비가 올 경우 어떤 지역에 얼마나 많은 물이 고일 수 있는지를 계산하는 문제입니다. 이는 “Trapping Rain Water” 문제로 널리 알려져 있으며, 다양하고 흥미로운 해결 방법이 존재합니다.
문제 예시
높이 배열이 주어졌다고 가정해 보겠습니다. 아래의 배열을 예로 들어 볼까요:
{0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1}
위와 같은 배열이 주어질 때, 비가 내리면 다음과 같이 물이 고일 수 있습니다:
- 인덱스 0: 물이 고이지 않음
- 인덱스 1: 물이 고이지 않음
- 인덱스 2: 1 유닛의 물
- 인덱스 3: 물이 고이지 않음
- 인덱스 4: 1 유닛의 물
- 인덱스 5: 2 유닛의 물
- 인덱스 6: 1 유닛의 물
- 인덱스 7: 물이 고이지 않음
- 인덱스 8: 1 유닛의 물
- 인덱스 9: 1 유닛의 물
- 인덱스 10: 1 유닛의 물
- 인덱스 11: 물이 고이지 않음
따라서 총 고인 물의 양은 6 유닛입니다.
문제 접근 방법
문제를 해결하기 위해서는 먼저 어떻게 물이 고이는지를 이해해야 합니다. 물이 고일 수 있는 양은 특정 인덱스 주변의 높은 경계에 따라 결정됩니다. 예를 들어, 어떤 위치에서 물이 고이기 위해서는 그 위치의 양쪽에 더 높은 경계가 존재해야 하며, 이 두 경계의 낮은 부분이 물이 고일 수 있는 높이입니다.
이를 계산하는 방법으로는 여러 가지가 있으며, 여기서는 두 가지 방법을 소개할 것입니다:
- 투 포인터 방식
- DP(동적 프로그래밍) 방식
투 포인터 방식
첫 번째 접근 방식은 투 포인터를 사용하는 방법입니다. 왼쪽과 오른쪽에서 각각 포인터를 두고, 높은 벽을 기준으로 물의 양을 계산해 나가는 방식입니다. 이 방법은 O(n) 시간 복잡도로 보통 배열을 한 번만 순회하여 문제를 해결할 수 있습니다.
알고리즘 설명
- 배열의 왼쪽과 오른쪽 끝에 각각 포인터를 두고, 왼쪽과 오른쪽의 최대 높이를 저장할 변수를 초기화합니다.
- 두 포인터가 서로 교차할 때까지 반복합니다.
- 왼쪽 포인터의 현재 높이가 오른쪽 포인터의 높이보다 낮은 경우, 왼쪽 포인터를 한 칸 오른쪽으로 이동시키고, 해당 위치에 저장된 최대 높이와의 차이를 이용하여 고인 물의 양을 계산합니다.
- 그렇지 않은 경우, 오른쪽 포인터를 한 칸 왼쪽으로 이동시키고, 유사한 계산을 합니다.
코드 구현
#include#include using namespace std; int trap(vector & height) { if (height.size() == 0) return 0; int left = 0, right = height.size() - 1; int left_max = 0, right_max = 0; int water_trapped = 0; while (left < right) { if (height[left] < height[right]) { if (height[left] >= left_max) { left_max = height[left]; } else { water_trapped += left_max - height[left]; } left++; } else { if (height[right] >= right_max) { right_max = height[right]; } else { water_trapped += right_max - height[right]; } right--; } } return water_trapped; } int main() { vector height = {0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1}; cout << "Total water trapped: " << trap(height) << endl; return 0; }
동적 프로그래밍 방식
동적 프로그래밍을 사용하는 방법도 있습니다. 이 방법은 각 인덱스에서 물이 고일 수 있는 양을 사전에 계산해 놓은 배열을 바탕으로 진행됩니다. 이 또한 O(n) 시간 복잡도를 가집니다.
알고리즘 설명
- 정수 배열의 길이를 구하고, 두 개의 배열을 생성합니다. 하나는 왼쪽에서부터의 최대 높이 배열, 다른 하나는 오른쪽에서부터의 최대 높이 배열입니다.
- 왼쪽 최대 높이 배열을 채웁니다. 각 인덱스에서의 최대 높이는 이전 인덱스의 최대 높이와 현재 높이 중 더 큰 값을 선택하여 설정합니다.
- 오른쪽 최대 높이 배열을 채우는 과정도 유사하게 진행합니다.
- 마지막으로 각 인덱스의 고인 물의 양은 두 최대 높이 배열을 바탕으로 결정됩니다: min(left_max[i], right_max[i]) – height[i] 입니다.
코드 구현
#include#include using namespace std; int trap(vector & height) { if (height.size() == 0) return 0; int n = height.size(); vector left_max(n); vector right_max(n); int water_trapped = 0; // 왼쪽 최대 높이 계산 left_max[0] = height[0]; for (int i = 1; i < n; i++) { left_max[i] = max(left_max[i - 1], height[i]); } // 오른쪽 최대 높이 계산 right_max[n - 1] = height[n - 1]; for (int i = n - 2; i >= 0; i--) { right_max[i] = max(right_max[i + 1], height[i]); } // 고인 물의 양 계산 for (int i = 0; i < n; i++) { water_trapped += min(left_max[i], right_max[i]) - height[i]; } return water_trapped; } int main() { vector height = {0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1}; cout << "Total water trapped: " << trap(height) << endl; return 0; }
성능 분석
위의 두 가지 접근 방식 모두 O(n)의 시간 복잡도를 가집니다. 하지만 공간 복잡도가 중요한 경우, 투 포인터 방식이 더 효율적입니다. 반면 동적 프로그래밍 방식은 추가적인 O(n)의 공간을 필요로 하므로, 메모리 사용량이 중요한 경우 주의해야 합니다.
최적화 전략
C++ 코딩 테스트에서 성능을 극대화하기 위해 모집단, 배열 크기, 알고리즘 복잡도 등을 항상 고려해야 합니다. 또한 컴파일러 최적화에도 유의해야 하며, 불필요한 변수를 줄이고 메모리 관리에 신경을 기울이는 것이 좋습니다.
결론
이번 강좌에서는 물의 양 구하기 문제를 통해 C++의 기본적인 배열 처리 및 알고리즘 작성 방법을 알아보았습니다. 다양한 접근 방법과 각 방법의 장단점을 분석하면서, 어떻게 최적화할 수 있는지에 대해서도 살펴보았습니다. 앞으로의 코딩테스트에서 얻은 지식과 경험이 매우 유용하게 활용되길 바랍니다.
항상 연습하고 개선하는 여러분이 되길 바랍니다! 감사합니다.