소개
동적 계획법(Dynamic Programming, DP)은 코딩 테스트에서 자주 등장하는 핵심 알고리즘 기법입니다. 복잡한 문제를 효율적으로 해결할 수 있어 많은 기업의 코딩 테스트에서 중요하게 다뤄집니다. 이 글에서는 동적 계획법의 개념을 리뷰하고, 코딩 테스트에서의 적용 방법, 실제 문제 해결 과정, 최적화 전략, 그리고 주요 팁들을 다룰 것입니다. 특히 코딩 테스트에서 동적 계획법이 어떻게 활용될 수 있는지에 초점을 맞추겠습니다.
알고리즘 리뷰
동적 계획법의 핵심은 복잡한 문제를 작은 하위 문제로 나누고, 그 결과를 저장하여 재사용하는 것입니다. 이는 중복 계산을 줄이고 효율성을 높이는 장점이 있습니다. 코딩 테스트에서 동적 계획법은 최적화 문제나 경우의 수를 세는 문제에 자주 사용됩니다. 그러나 메모리 사용량이 증가할 수 있고, 적절한 하위 문제 정의가 어려울 수 있다는 단점이 있습니다. 게임 개발에서는 경로 찾기, 리소스 최적화, AI 결정 등에 활용될 수 있습니다.
관련 문제 유형 분석
동적 계획법이 주로 적용되는 문제 유형은 다음과 같습니다:
1.
최적화 문제: 최소 비용 경로, 배낭 문제 등이 해당합니다. 이러한 문제는 게임에서 최적의 아이템 조합이나 최단 경로 찾기에 응용될 수 있습니다.
2.
경우의 수 계산: 계단 오르기, 타일 채우기 등의 문제가 있습니다. 게임 레벨 디자인이나 퍼즐 게임 메커니즘 설계에 활용될 수 있습니다.
3.
수열 또는 문자열 처리: 최장 공통 부분 수열(LCS), 편집 거리 등이 있습니다. 게임 내 대화 시스템이나 텍스트 매칭에 사용될 수 있습니다.
각 유형에 접근할 때는 문제의 상태를 정의하고, 점화식을 세우는 것이 중요합니다. 작은 문제부터 해결하며 결과를 저장하고, 이를 바탕으로 더 큰 문제를 해결해 나가는 방식으로 접근합니다.
실제 코딩 테스트 문제 해결
다음은 코딩 테스트에서 나올 수 있는 동적 계획법 문제 예시입니다:
"N x M 크기의 게임 맵이 있습니다. 각 칸에는 아이템의 가치가 적혀있습니다. 플레이어는 왼쪽 상단에서 시작하여 오른쪽 하단으로 이동하며, 한 번에 오른쪽이나 아래로만 이동할 수 있습니다. 플레이어가 얻을 수 있는 아이템의 최대 가치를 구하세요."
이 문제는 다음과 같이 해결할 수 있습니다:
1.
2D DP 테이블을 생성하여 각 위치까지의 최대 가치를 저장합니다.
2.
각 칸의 최대 가치는 왼쪽 칸과 위쪽 칸 중 큰 값에 현재 칸의 가치를 더한 값입니다.
3.
맵을 순회하며 DP 테이블을 채웁니다.
#include <vector>
#include <algorithm>
class Solution {
public:
int maxItemValue(vector<vector<int>>& map) {
int n = map.size();
int m = map[0].size();
vector<vector<int>> dp(n, vector<int>(m, 0));
// 초기화
dp[0][0] = map[0][0];
// 첫 행 초기화
for (int j = 1; j < m; j++) {
dp[0][j] = dp[0][j-1] + map[0][j];
}
// 첫 열 초기화
for (int i = 1; i < n; i++) {
dp[i][0] = dp[i-1][0] + map[i][0];
}
// DP 테이블 채우기
for (int i = 1; i < n; i++) {
for (int j = 1; j < m; j++) {
dp[i][j] = max(dp[i-1][j], dp[i][j-1]) + map[i][j];
}
}
return dp[n-1][m-1];
}
};
C++
복사
이 코드는 맵을 순회하며 각 위치까지의 최대 가치를 계산합니다. 최종적으로 오른쪽 하단 칸의 값이 플레이어가 얻을 수 있는 최대 가치가 됩니다.
최적화 및 효율성 개선
위 해결책의 시간 복잡도는 O(NM)이고, 공간 복잡도도 O(NM)입니다. 이는 대부분의 경우 충분히 효율적이지만, 더 최적화할 수 있습니다.
공간 복잡도를 개선하기 위해 2D 배열 대신 1D 배열을 사용할 수 있습니다:
int maxItemValue(vector<vector<int>>& map) {
int n = map.size();
int m = map[0].size();
vector<int> dp(m, 0);
dp[0] = map[0][0];
for (int j = 1; j < m; j++) {
dp[j] = dp[j-1] + map[0][j];
}
for (int i = 1; i < n; i++) {
dp[0] += map[i][0];
for (int j = 1; j < m; j++) {
dp[j] = max(dp[j], dp[j-1]) + map[i][j];
}
}
return dp[m-1];
}
C++
복사
이 최적화된 버전은 공간 복잡도를 O(M)으로 줄였습니다. 시간 복잡도는 여전히 O(N*M)이지만, 캐시 효율성이 향상되어 실제 실행 시간이 단축될 수 있습니다.
코딩 테스트 팁과 트릭
1.
문제의 상태를 정확히 정의하세요. 게임 맵 문제에서는 "현재 위치까지의 최대 가치"가 상태입니다.
2.
점화식을 세우세요. 위 문제에서는 dp[i][j] = max(dp[i-1][j], dp[i][j-1]) + map[i][j] 입니다.
3.
기저 사례(Base case)를 잊지 마세요. 첫 행과 첫 열의 초기화가 중요합니다.
4.
반복문의 순서에 주의하세요. 의존성을 고려하여 올바른 순서로 DP 테이블을 채워야 합니다.
5.
메모리 사용을 최적화하세요. 1D 배열로 충분한 경우 2D 배열을 사용하지 마세요.
결론
동적 계획법은 게임 개발 관련 코딩 테스트에서 자주 등장하는 강력한 도구입니다. 복잡한 최적화 문제를 효율적으로 해결할 수 있으며, 맵 탐색, 리소스 관리, AI 결정 등 다양한 상황에 적용할 수 있습니다. 문제의 상태를 정확히 정의하고, 점화식을 세우며, 메모리 사용을 최적화하는 연습을 통해 동적 계획법 마스터에 한 걸음 더 가까워질 수 있습니다.
