동적 계획법(Dynamic Programming)은 복잡한 문제를 더 작은 하위 문제로 나누어 해결하는 강력한 기법입니다. 특히 최댓값이나 경우의 수를 구하는 문제에서 효율적입니다. 다음은 동적 계획법을 활용하여 두 가지 유형의 문제를 해결하는 방법입니다.
1. 최댓값 문제: 중복 문자가 없는 가장 긴 부분 문자열
문제 설명: 주어진 문자열에서 중복 문자가 없는 가장 긴 부분 문자열의 길이를 구합니다. (예: LeetCode "Longest Substring Without Repeating Characters")
분석:
dp[i]: 문자열s[i]로 끝나는 중복 문자가 없는 가장 긴 부분 문자열의 길이.s[i]와 같은 문자가 이전에 나타났던 가장 가까운 위치s[j]를 찾습니다.- 만약
j가-1이라면 (이전 문자가 없다는 의미),dp[i] = dp[i-1] + 1입니다. - 만약
dp[i-1] < i - j라면 (이전 동일 문자가 현재 부분 문자열 범위 밖에 있다면),dp[i] = dp[i-1] + 1입니다. - 만약
dp[i-1] >= i - j라면 (이전 동일 문자가 현재 부분 문자열 범위 안에 있다면),dp[i] = i - j입니다. - 첫 번째 경우(이전 문자가 없는 경우)는 두 번째 경우에 포함될 수 있습니다.
j < 0이면dp[i-1] < i는 항상 참이므로dp[i-1] < i - j도 참이 됩니다.
1.1. 방법 1: 동적 계획법 + 선형 탐색
각 반복에서 이전의 동일한 문자를 선형으로 탐색합니다. 이 방식은 공간 복잡도를 O(1)으로 줄일 수 있습니다.
- 시간 복잡도: O(N2)
- 공간 복잡도: O(1)
class Solution {
public:
int lengthOfLongestSubstring(string s) {
int currentMaxLen = 0; // 현재까지의 최대 길이
int currentLen = 0; // 현재 부분 문자열의 길이
for (int i = 0; i < s.length(); ++i) {
int prevIndex = i - 1;
// 현재 문자와 같은 문자를 이전에서 찾습니다.
while (prevIndex >= 0 && s[prevIndex] != s[i]) {
--prevIndex;
}
// 부분 문자열의 시작 인덱스를 기준으로 길이를 계산합니다.
int distance = i - prevIndex;
if (distance > currentLen) {
currentLen += 1; // 길이가 늘어납니다.
} else {
currentLen = distance; // 길이가 이전 문자의 위치에 의해 제한됩니다.
}
currentMaxLen = max(currentMaxLen, currentLen);
}
return currentMaxLen;
}
};
1.2. 방법 2: 동적 계획법 + 해시 테이블
해시 테이블을 사용하여 각 문자의 마지막 등장 위치를 저장합니다. 이를 통해 O(N) 시간 복잡도를 달성할 수 있습니다.
- 시간 복잡도: O(N)
- 공간 복잡도: O(k) (k는 문자 집합의 크기, 일반적으로 상수)
#include <unordered_map>
class Solution {
public:
int lengthOfLongestSubstring(string s) {
unordered_map lastSeenIndex; // 문자별 마지막 등장 인덱스 저장
int maxLen = 0; // 전체 최대 길이
int currentStreak = 0; // 현재까지의 연속 길이
int prevMatchIndex = 0; // 이전 매칭된 문자의 인덱스 (부분 문자열 시작점)
for (int i = 0; i < s.length(); ++i) {
if (lastSeenIndex.find(s[i]) == lastSeenIndex.end()) {
// 문자가 처음 나오거나, 현재 부분 문자열 범위 밖에 있다면
prevMatchIndex = -1;
} else {
prevMatchIndex = lastSeenIndex[s[i]];
}
lastSeenIndex[s[i]] = i; // 현재 문자의 인덱스 업데이트
// 현재 문자가 이전에 나왔던 위치와 현재 부분 문자열의 시작점(prevMatchIndex)을 비교
int effectiveStart = max(prevMatchIndex + 1, i - currentStreak);
currentStreak = i - effectiveStart + 1;
maxLen = max(maxLen, currentStreak);
}
return maxLen;
}
};
2. 경우의 수 문제: 숫자를 문자열로 번역
문제 설명: 주어진 숫자를 문자열로 번역하는 경우의 수를 구합니다. 각 숫자는 'a'부터 'z'까지 매핑되며, 두 자리 숫자도 특정 범위(10~25)에 해당하면 하나의 문자로 번역될 수 있습니다. (예: LeetCode "Translate Number")
분석:
dp[i]: 숫자num의 첫i개의 숫자를 번역하는 경우의 수.- 숫자
num[i]를 독립적으로 번역할 경우: 경우의 수는dp[i-1]가지입니다. - 숫자
num[i-1]과num[i]를 합쳐 두 자리 숫자로 번역할 경우 (10~25 범위): 경우의 수는dp[i-2]가지입니다. - 따라서, 두 자리 번역이 가능한 경우
dp[i] = dp[i-1] + dp[i-2]이고, 불가능한 경우dp[i] = dp[i-1]입니다. - 초기 상태:
dp[0] = 1(빈 문자열의 경우의 수),dp[1] = 1(한 자리 숫자의 경우의 수).
2.1. 방법 1: 문자열 탐색
숫자를 문자열로 변환한 후, 문자열을 순회하며 두 자리 숫자를 조합할 수 있는지 확인합니다.
- 시간 복잡도: O(N)
- 공간 복잡도: O(N) (문자열 저장 공간)
#include <string>
#include <vector>
class Solution {
public:
int translateNum(int num) {
string s = to_string(num);
if (s.empty()) return 0;
int n = s.length();
// dp[i]는 s[0...i-1]까지 번역하는 경우의 수
vector<int> dp(n + 1);
dp[0] = 1; // 빈 문자열의 경우의 수
dp[1] = 1; // 첫 번째 문자의 경우의 수
for (int i = 2; i <= n; ++i) {
// 현재 문자와 이전 문자를 합친 두 자리 숫자
string twoDigits = s.substr(i - 2, 2);
// 두 자리 숫자가 10과 25 사이에 있는지 확인
if (twoDigits[0] == '1' || (twoDigits[0] == '2' && twoDigits[1] <= '5')) {
dp[i] = dp[i - 1] + dp[i - 2]; // 두 가지 번역 가능
} else {
dp[i] = dp[i - 1]; // 한 가지 번역만 가능
}
}
return dp[n];
}
};
2.2. 방법 2: 나머지 연산 활용 (더 공간 효율적)
숫자를 오른쪽에서 왼쪽으로 처리하며 나머지와 몫을 사용하여 동적 계획법을 구현합니다. 이는 추가적인 문자열 변환 없이 O(1) 공간 복잡도를 달성합니다.
- 시간 복잡도: O(log10N) (숫자의 자릿수만큼 반복)
- 공간 복잡도: O(1)
class Solution {
public:
int translateNum(int num) {
if (num < 0) return 0; // 음수는 처리하지 않음
int lastDigit = num % 10; // 마지막 숫자
int currentNum = num / 10; // 나머지 숫자
int prevWays = 1; // dp[i-1]에 해당 (이전까지의 경우의 수)
int currentWays = 1; // dp[i]에 해당 (현재까지의 경우의 수)
while (currentNum > 0) {
int prevDigit = currentNum % 10; // 이전 숫자 (오른쪽에서 두 번째 숫자)
int combined = prevDigit * 10 + lastDigit; // 두 자리 숫자 조합
int nextWays;
if (combined >= 10 && combined <= 25) {
// 두 자리로 번역 가능: 이전 경우의 수 + 이전 이전 경우의 수
nextWays = prevWays + currentWays;
} else {
// 두 자리로 번역 불가능: 이전 경우의 수만 사용
nextWays = prevWays;
}
// 다음 반복을 위해 값 업데이트
currentWays = prevWays;
prevWays = nextWays;
lastDigit = prevDigit; // 마지막 숫자를 이전 숫자로 업데이트
currentNum /= 10; // 숫자 처리
}
return prevWays; // 최종 경우의 수
}
};