레벨 3 문제들을 풉니다. 슬슬 어려워지네요. 푸는 시간도 점점 오래 걸리고 있습니다. 알고리즘 대회나 게임 프로그래밍을 할 것이 아니라면 Level 3까지 정도만 하시면 됩니다. 모든 문제는 제가 직접 푼 풀이이며, 더 나은 풀이가 있다면 알려주세요~ 못 푼 문제는 끙끙대며 풀어볼테니 스포 금지!
Level 3 1번~4번
앞으로의 문제들은 설명을 자세하게 해야할 것 같아 한 강의에 다루는 문제 개수를 대폭 줄였습니다. 저도 이제 문제 풀기에 급급해서 코드 정리를 못하고 있네요.
2 x n 타일링
이 문제는 설명을 링크를 통해 직접 보세요. 난이도가 상승할수록 설명하기도 힘들어지네요.
이 문제의 핵심은 이 문제를 피보나치로 풀 수 있다는 것을 깨닫는 것입니다. 왜 그러냐면요. 길이가 5인 사각형을 구성하는 개수는, 잘 보면 길이가 3인 사각형에 길이가 2인 가로 사각형 두개를 붙인 것 + 길이가 4인 사각형에 길이가 1인 세로 사각형을 붙인 것입니다. 이 규칙만 찾아낸다면 피보나치로 푸는 것은 쉽습니다.
재귀(탑다운 방식)로 시도했으나 호출 스택 에러가 납니다. 메모이제이션을 해도 소용없네요.
const cache = [1, 2, 3];
function solution(n) {
if (cache[n - 1]) return cache[n - 1];
cache[n - 1] = (solution(n - 1) + solution(n - 2)) % 1000000007;
return cache[n - 1];
}이럴 때는 바텀업 방식(반복문)으로 하면 됩니다.
function solution(n) {
const cache = [1, 2];
for (let i = 2; i < n; i++) {
cache[i] = (cache[i - 1] + cache[i - 2]) % 1000000007;
}
return cache[n - 1];
}마지막에 1000000007을 나누는 것 잊지 마시고요.
가장 긴 팰린드롬
팰린드롬 문제는 지겹네요. 뒤집어도 똑같은 문자열을 팰린드롬이라고 합니다. 문자열 s가 주어질 때 가장 긴 팰린드롬 길이를 return하면 됩니다. abacde라면 aba가 가장 긴 팰린드롬이니까 3입니다.
일단 팰린드롬 특성상 꺾이는 부분(반으로 접을 수 있는 부분)이 생깁니다. 길이가 홀수일 때랑 짝수일 때가 다르겠고요. 그 꺾이는 부분을 찾는게 핵심입니다. 꺾이는 부분을 찾았다면 그 부분을 기준으로 대칭인지 확인하면 되겠죠.
일단 특정 인덱스에서 가장 긴 팰린드롬을 찾는 알고리즘을 먼저 구현하고, 그 후에 이 문제를 구현해야겠습니다.
function pal(i, j) {
let left = i - 1;
let right = s[j] ? j + 1 : i + 1;
let count = s[j] ? 2 : 1;
while (s[left] && s[right] && s[left] === s[right]) {
count += 2;
left--;
right++;
}
return count;
}가운데 인덱스(i)를 주면, 가장 긴 팰린드롬을 찾는 코드입니다. 만약 길이가 짝수가 될 것 같으면 i보다 하나 더 큰 j까지 제공하면 됩니다.
function solution(s) {
function pal(i, j) {
let left = i - 1;
let right = s[j] ? j + 1 : i + 1;
let count = s[j] ? 2 : 1;
while (s[left] && s[right] && s[left] === s[right]) {
count += 2;
left--;
right++;
}
return count;
}
let answer = 1;
for (let i = 0; i < s.length; i++) {
if (s[i + 1] === s[i - 1] && s[i] === s[i + 1]) {
const count = Math.max(pal(i), pal(i, i + 1));
if (count > answer) answer = count;
} else if (s[i + 1] === s[i - 1]) {
const count = pal(i);
if (count > answer) answer = count;
} else if (s[i] === s[i + 1]) {
const count = pal(i, i + 1);
if (count > answer) answer = count;
}
}
return answer;
}이제 모든 인덱스에서 가장 긴 팰린드롬을 구하고, 그 중 뭐가 제일 긴지 찾으면 됩니다.
다른 분의 풀이를 보니까 모든 서브스트링을 찾은 후 팰린드롬 여부를 구한 것 같습니다. 모든 서브스트링을 찾기보다는 서브스트링을 긴 순서로 정렬해서 처음 찾은 팰린드롬의 길이를 구하는 게 더 좋아 보입니다.
거스름돈
1원, 2원, 5원 동전이 있다면 이걸로 특정 금액을 만드는 가짓수를 구하는 것입니다. 예를 들어 5원을 만들어야 하면 (1원 5개, 1원 3개 2원 1개, 1원 1개 2원 2개, 5원 1개)까지 4가지 경우가 있습니다.
이것도 Level 3의 다른 문제들과 비슷하게 예전에 구한 계산 결과가 다음 결과에 영향을 미칠 것 같습니다. 이 생각을 어떻게 떠올렸냐면, 2 x n 타일링 문제처럼 5원을 만드는 방법은, 4원에 1원을 더하는 방법 + 3원에 2원을 더하는 방법 + 2원에 3원을 더하는 방법 + ... 식으로 되기 때문입니다. 예전 결과들은 캐싱해두면 됩니다. 좀 더 응용된 다이나믹 프로그래밍이죠. 규칙만 찾아내면 쉽습니다.
이런 건 표를 만들어보면 좋습니다. 0원을 만드는 방법은 1가지가 꼭 있습니다(아무 동전도 안 쓰는 방법 1가지).
0 1 2 3 4 5 6 7 8 9 10 // 금액
1 1 1 1 1 1 1 1 1 1 1 // 1원
1 1 2 2 3 3 4 4 5 5 6 // 1,2원
1 1 2 2 3 4 5 6 7 8 10 // 1,2,5원
규칙이 보이시나요? ㅋㅋ 잘 찾지 않으면 찾기 어렵습니다.
0 1 2 3 4 5 6 7 8 9 10 // 금액
1 1 1 1 1 1 1 1 1 1 1 // 1원
1 1 2 2 3 3 4 4 5 5 6 // 1,2원
1 1 2 2 3 4 5 6 7 8 10 // 1,2,5원
1,2원으로 10원을 만드는 방법은, 1원으로 0, 2, 4, 6, 8, 10원을 만드는 방법의 합입니다.
0 1 2 3 4 5 6 7 8 9 10 // 금액
1 1 1 1 1 1 1 1 1 1 1 // 1원
1 1 2 2 3 3 4 4 5 5 6 // 1,2원
1 1 2 2 3 4 5 6 7 8 10 // 1,2,5원
1,2,5원으로 9원을 만드는 방법은, 2원으로 4, 9원을 만드는 방법의 합입니다.
즉, k개의 동전으로 n원을 만드는 방법은 k-1개의 동전으로 n원 만드는 방법 + k-1개의 동전으로 n-x원 만드는 방법 + k-1개의 동전으로 n-2x원 만드는 방법 + ....인 것입니다(x는 가장 큰 동전 액면가). 이전 결과들이 다음 결과 구하는 데 영향을 끼치는 것이죠.
function solution(n, money) {
const cache = [];
for (let i = 0; i < money.length; i++) {
for (let j = 0; j <= n; j++) {
if (!cache[i]) cache[i] = [];
if (i === 0) {
cache[i][j] = j % money[i] ? 0 : 1;
} else {
cache[i][j] = 0;
for (let mul = 0; j - money[i] * mul >= 0; mul++) {
cache[i][j] += cache[i - 1][j - money[i] * mul];
}
}
}
}
return cache[money.length - 1][n] % 1000000007;
}function solution(n, money) {
const cache = [];
for (let i = 0; i < money.length; i++) {
for (let j = 0; j <= n; j++) {
if (!cache[i]) cache[i] = [];
if (i === 0) {
cache[i][j] = j % money[i] ? 0 : 1;
} else {
cache[i][j] = j >= money[i] ? cache[i - 1][j] + cache[i][j - money[i]] : cache[i - 1][j];
}
}
}
return cache[money.length - 1][n] % 1000000007;
}처음에 시도한 두 가지 방식입니다. 이차원 배열(동전/금액)로 캐싱을 하고 있었는데 계속 시간 초과가 뜨더군요. 생각해보니 이차원 배열로 할 필요가 없다는 것을 나중에 깨달았습니다. 이전 동전 행을 재사용할 일이 없기 때문에 그냥 덮어씌워도 되는 것이었죠. Level 2의 땅따먹기에서 값을 누적한 것과 비슷합니다.
function solution(n, money) {
const cache = [];
for (let i = 0; i <= n; i++){
cache[i] = i % money[0] ? 0 : 1;
}
for (let i = 1; i < money.length; i++){
for(let j = money[i]; j <= n; j++){
cache[j] += cache[j - money[i]];
}
}
return cache[n] % 1000000007;
}일차원 배열로 다시 풀었더니 됩니다. 이렇게 다이나믹 프로그래밍 문제는 규칙을 찾는 게 중요합니다. 규칙을 찾은 후, 이전 결괏값들을 캐싱하면서 다음 결과를 계산해나가면 돼요.
참고로 비슷한 문제로 거스름돈을 가장 적은 동전 개수로 돌려주는 문제가 있습니다. 이것은 다이나믹이 아니라 그리디 프로그래밍으로 풀면 쉽습니다.
멀리뛰기
이것도 2 x n 타일링과 똑같습니다. 피보나치로 풀면 돼요. 한 번에 한 칸 또는 두 칸을 뛸 수 있을 때, 5칸을 뛰는 방법의 수는 3칸에서 두 칸 뛰기 + 4칸에서 한 칸 뛰기 방법을 더한 것입니다. 이전 계산 결과로 다음 결과를 구할 수 있게 되는 것이죠.
function solution(n) {
const cache = [1, 2];
for (let i = 2; i < n; i++) {
cache[i] = (cache[i - 1] + cache[i - 2]) % 1234567;
}
return cache[n - 1];
}마지막에 1234567로 나눠줘야 한다는 것만 조심합시다.
다음 시간에는 5~8번을 풀어보도록 하겠습니다. 다이나믹 프로그래밍 을 꼭 알아두세요!
익명