오늘은 이번 주랑 지난 주에 따로 더 찾아보려고 모아 두었던 토픽들을 찾아보았다. 하노이의 탑은 이전에 부스트캠프 코테 준비하면서 풀었었는데 다시 한번 더 보니 이번에는 정말 이해한 것 같다. 동적 프로그래밍은 페어 분께서 메모이제이션이 동적 프로그래밍이라고 하셔서 찾아 보았다. 사실 이름에 왜 dynamic이 들어가는지 잘 모르겠지만... 동적이라는 영문 직역대신 본질적 의미를 살려 기억하며 풀기로 번역하기도 한다는 데 이쪽이 더 잘 맞는 것 같다. 피보나치 수열은 예시로 계속 나오는 데 하나의 문제를 푸는 데 이렇게나 많은 방법이 있다니...! 알고리즘은 안 풀리면 진짜 하루 종일 신경쓰여서 지옥인데 재밌기도 하다. 재밌다고 계속 자기암시를 걸어서 그런건지, 진짜 재밌는 건지...ㅎㅎㅎㅎ
Today I Learned
동적 프로그래밍 (Dynamic Programming)
알고리즘을 짤 때 흔히 사용하는 분할 정복 기법의 경우 문제를 쪼개서 풀다보면 반복하여 푸는 경우가 생긴다. 이 경우 매번 새로 연산하는 대신 값을 저장해 두었다가 재사용 하는 것이 효율적인데 이를 동적 프로그래밍이라고 한다.
동적 프로그래밍은 최적 부분 구조를 가진 중복 부분 문제에 적용 가능하다.
- 최적 부분 구조 (Optimal Substructure) : 문제의 답을 그 문제의 부분들의 답을 사용하여 구할 수 있는 구조
- 중복 부분 문제 (Overlapping Subproblems) : 부분 문제들이 중복되어 계산되는 문제
메모이제이션도 동적 프로그래밍 방법론의 하나다. 하향식 접근법인 메모이제이션 외 상향식 접근법인 타뷸레이션이 있다.
-
메모이제이션 (Memoization) : 계산 결과들을 메모해 두었다가 같은 계산을 해야하는 경우 연산을 새로하지 않고 메모된 값을 사용한다. 공간 비용으로 시간 비용을 줄이는 방법이다. 크기가 큰 문제부터 하위 문제로 접근하며 하위 문제의 값을 이미 구했는지 확인하며 푸는 방식이다.
-
타뷸레이션 (Tabulation) : 더 작은 하위 문제부터 푼 뒤 이를 이용해 더 큰 문제의 답을 푸는 방식아다. 일반적으로 다이나믹 프로그래밍은 이 상향식 방법을 말한다.
피보나치 수열을 하향식(메모이제이션)으로 구하기
function fibMemoize (n, memo) {
memo = memo || [0, 1]
if (memo[n]) return memo[n]
return memo[n] = fibMemoize(n-1, memo) + fibMemoize(n-2, memo)
}피보나치 수열을 상향식(타뷸레이션)으로 구하기
function fibTabulate (n) {
if (n <= 1) return n
const table = [0, 1]
for (let i = 2; i <= n; i++) {
table[i] = table[i-1] + table[i-2]
}
return table[n]
}재귀 : 순열과 조합
순열 (Permutation)
- 순서를 고려하여 n개 중 r개를 선택하여 나열하는 경우
- 순열 경우의 수 : n! / (n-r)!
function getPermutations (arr, num) {
// 결과를 담을 빈 배열 result 생성
const result = [];
// 만약 num이 1일 경우 (base case)
if (num === 1) return arr.map((el) => [el]);
// 그 외의 경우 재귀적으로 해결 (recursive case)
arr.forEach((fixed, idx, origin) => {
// ! arr에서 fixed 외 나머지를 담은 배열
const rest = [...origin.slice(0, idx), ...origin.slice(idx+1)];
// rest에서 num-1개를 선택하는 조합들 구하기
const combinations = getCombination(rest, num - 1);
// combinations에 담긴 조합들에 fixed를 더하기
const attached = combinations.map(combination => [fixed, ...combination]);
result.push(...attached);
})
// 결과 리턴
return result;
}
// 순열 경우의 수 : factorial(arr.)중복순열 (Permutation with Repetition)
- 순서와 중복을 고려하여 n개 중 r개를 선택하여 나열하는 경우
- 중복순열 경우의 수 : n to the power of r
function getPermutationsWithRepetition (arr, num) {
// 결과를 담을 빈 배열 result 생성
const result = [];
// 만약 num이 1일 경우 (base case)
if (num === 1) return arr.map((el) => [el]);
// 그 외의 경우 재귀적으로 해결 (recursive case)
arr.forEach((fixed, idx, origin) => {
// origin에서 num-1개를 선택하는 조합들 구하기
const combinations = getPermutationsWithRepetition(origin, num - 1);
// combinations에 담긴 조합들에 fixed를 더하기
const attached = combinations.map(combination => [fixed, ...combination]);
result.push(...attached);
})
// 결과 리턴
return result;
}
// 중복순열 경우의 수 : Math.pow(arr.length, num)조합 (Combination)
- 순서를 고려하지 않고 n개 중 r개를 선택하는 경우
- 조합 경우의 수 : n! / (n-r)!r!
function getCombinations (arr, num) {
// 결과를 담을 빈 배열 result 생성
const result = [];
// 만약 num이 1일 경우 (base case)
if (num === 1) return arr.map((el) => [el]);
// 그 외의 경우 재귀적으로 해결 (recursive case)
arr.forEach((fixed, idx, origin) => {
// ! arr에서 fixed 뒤에 있는 나머지를 담은 배열
const rest = origin.slice(idx + 1);
// rest에서 num-1개를 선택하는 조합들 구하기
const combinations = getCombination(rest, num - 1);
// combinations에 담긴 조합들에 fixed를 더하기
const attached = combinations.map(combination => [fixed, ...combination]);
result.push(...attached);
})
// 결과 리턴
return result;
}
// 조합 경우의 수 : 재귀 : 하노이의 탑
출처 : 프로그래머스
문제 설명
하노이 탑(Tower of Hanoi)은 퍼즐의 일종입니다. 세 개의 기둥과 이 기동에 꽂을 수 있는 크기가 다양한 원판들이 있고, 퍼즐을 시작하기 전에는 한 기둥에 원판들이 작은 것이 위에 있도록 순서대로 쌓여 있습니다. 게임의 목적은 다음 두 가지 조건을 만족시키면서, 한 기둥에 꽂힌 원판들을 그 순서 그대로 다른 기둥으로 옮겨서 다시 쌓는 것입니다.
- 한 번에 하나의 원판만 옮길 수 있습니다.
- 큰 원판이 작은 원판 위에 있어서는 안됩니다.
하노이 탑의 세 개의 기둥을 왼쪽 부터 A, B, C이라고 하겠습니다. A에는 n개의 원판이 있고 이 n개의 원판을 C 원판으로 최소 횟수로 옮기려고 합니다.
A 기둥에 있는 원판의 개수 n이 매개변수로 주어질 때, n개의 원판을 B 원판으로 최소로 옮기는 방법을 return하는 solution를 완성해주세요.
제한사항
- n은 15이하의 자연수 입니다.
입출력 예
- input : 2
- output : [[A, B], [A, C], [B, C]]
function hanoi(n) {
function move(n, start, temp, end) {
// base case : 원반이 한개뿐일 때, 시작 기중에서 도착 기둥으로 이동
if (n === 1) return [[start, end]];
// recursive case :
// n-1개의 원반이 시작 기둥에서 임시 기둥으로 이동
// +
// 마지막 가장 큰 원반이 시작 기둥에서 도착 기둥으로 이동
// +
// 임시 기둥에 있는 n-1개의 원반이 도착 기둥으로 이동
const startToTemp = move(n-1, start, end, temp);
const biggestDisk = [start, end];
const tempToEnd = move(n-1, temp, start, end);
return [...startToTemp, biggestDisk, ...tempToEnd];
}
return move(n, 'A', 'B', 'C');
}