***문제 설명 하노이 탑(Tower of Hanoi)은 퍼즐의 일종입니다. 세 개의 기둥과 이 기동에 꽂을 수 있는 크기가 다양한 원판들이 있고, 퍼즐을 시작하기 전에는 한 기둥에 원판들이 작은 것이 위에 있도록 순서대로 쌓여 있습니다. 게임의 목적은 다음 두 가지 조건을 만족시키면서, 한 기둥에 꽂힌 원판들을 그 순서 그대로 다른 기둥으로 옮겨서 다시 쌓는 것입니다.
1. 한 번에 하나의 원판만 옮길 수 있습니다. 2. 큰 원판이 작은 원판 위에 있어서는 안됩니다.
하노이 탑의 세 개의 기둥을 왼쪽 부터 1번, 2번, 3번이라고 하겠습니다. 1번에는 n개의 원판이 있고 이 n개의 원판을 3번 원판으로 최소 횟수로 옮기려고 합니다.1번 기둥에 있는 원판의 개수 n이 매개변수로 주어질 때, n개의 원판을 3번 원판으로 최소로 옮기는 방법을 return하는 solution를 완성해주세요.
***제한사항 n은 15이하의 자연수 입니다.
***입출력 예
n
result
2
[[1,2],[1,3],[2,3]]
***입출력 예 설명 입출력 예 #1_다음과 같이 옮길 수 있습니다.
## solution.JavaScript
1. 문제의 접근 방식
1) 원반이 1개일 때, 해당 원반을 출발지에서 목적지로 직접 옮깁니다. 이것이 재귀 알고리즘에서의 기본 단계입니다.
3-3. hanoi(n-1, 경유지, 출발지, 목적지): 경유지에 있는 작은 원반들을 목적지로 이동.
2. 문제풀이
// n => 이동할 원반의 갯수
// a => 원반이 위치한 기둥 번호
// b => 목적지 기둥 번호
// c => 경유할 기둥
function solution(n) {
const answer = [];
function hanoi(n, a, b, c) {
// 원반이 1개일 경우 목적지로 이동
if (n === 1) {
answer.push([a, c]);
return;
}
// n-1개의 원반을 경유지로 이동
hanoi(n - 1, a, c, b);
// 가장 큰 원반을 목적지로 이동
answer.push([a, c]);
// n-1개의 원반을 경유지에서 목적지로 이동
hanoi(n - 1, b, a, c);
}
hanoi(n, 1, 2, 3);
return answer;
}
/*
테스트 1
입력값 〉 2
기댓값 〉 [[1, 2], [1, 3], [2, 3]]
실행 결과 〉 테스트를 통과하였습니다.
*/
1. ` solution ` 함수는 하노이 탑 문제를 해결하기 위한 메인 함수입니다. 이동 경로를 저장할 배열 answer를 초기화합니다.
2. `hanoi` 함수는 재귀적으로 호출되며, 주어진 기둥 번호 a에서 시작하여 목적지 기둥 번호 c로 최소한의 움직임으로 원반을 이동합니다.
3. `n === 1`인 경우, 즉 원반이 1개일 때는 해당 원반을 목적지로 직접 이동하고 이동 경로를 answer 배열에 추가합니다.
4. 그렇지 않은 경우, 큰 원반을 제외한 나머지 원반들을 경유지로 이동하고, 가장 큰 원반을 목적지로 이동한 뒤, 다시 나머지 원반들을 목적지로 이동합니다.
5. `hanoi` 함수를 호출하여 하노이 탑 문제를 해결하고, 최종적으로 이동 경로가 담긴 `answer` 배열을 반환합니다.
3. 다른사람의 문제풀이 및 접근방식 분석
function solution(n, from = 1, by = 2, to = 3) {
return (n===1) ? [[from, to]] : [...solution(n-1, from, to, by), ...solution(1, from, by, to), ...solution(n-1, by, from, to)]
}
/*
테스트 1
입력값 〉 2
기댓값 〉 [[1, 2], [1, 3], [2, 3]]
실행 결과 〉 테스트를 통과하였습니다.
*/
/*
function solution(n, from = 1, by = 2, to = 3) {
return (n === 1)
? [[from, to]] // 원반이 1개일 경우, 직접 목적지로 이동
: [
...solution(n - 1, from, to, by), // n-1개의 원반을 경유지로 이동
...solution(1, from, by, to), // 가장 큰 원반을 목적지로 이동
...solution(n - 1, by, from, to) // n-1개의 원반을 경유지에서 목적지로 이동
];
}
*/
1) n === 1) ? [[from, to]] : [...solution(n-1, from, to, by), ...solution(1, from, by, to), ...solution(n-1, by, from, to)] 원반이 1개일 경우에는 바로 목적지로 이동한 경로를 반환합니다. 그렇지 않은 경우에는 다음 세 가지 경로를 결합한 배열을 반환합니다.
1-1. n-1개의 원반을 경유지로 이동한 경로
1-2. 가장 큰 원반을 목적지로 이동한 경로
1-3. n-1개의 원반을 경유지에서 목적지로 이동한 경로
2. 귀 호출을 통한 해결
2-1. 재귀 호출을 통해 작은 문제로 나누어 해결하고, 이를 조합하여 전체 문제를 해결합니다. 2-2. 각 호출은 원반이 1개일 때까지 반복되며, 각 호출이 반환하는 경로들을 합쳐 최종적인 이동 경로를 구합니다.
# 재귀함수란?
재귀 함수는 함수가 자기 자신을 호출하는 특성을 가진 함수를 말합니다. 즉, 문제를 해결하기 위해 동일한 함수를 여러 번 호출하여 문제를 해결하는 방법입니다.
# 재귀함수 특징
1. 자기 자신을 호출하는 형태
함수 내에서 자기 자신을 호출하는 형태를 갖추고 있어야 합니다.
2. 탈출 조건 (Base Case)
무한히 반복되지 않도록 종료 조건이 필요합니다. 재귀 호출이 계속되다가 특정 조건에 도달하면 더 이상 호출하지 않고 종료하는 부분이 필요합니다.
# 재귀함수 사용방법
function factorial(n) {
// Base Case: 탈출 조건
if (n === 0 || n === 1) {
return 1;
} else {
// Recursive Case: 자기 자신을 호출하면서 문제를 작은 부분으로 분할
return n * factorial(n - 1);
}
}
// 예제 사용
console.log(factorial(5)); // 5! = 5 * 4 * 3 * 2 * 1 = 120
# 재귀함수 주의사항
1. Base Case 누락 주의
재귀 함수에서 가장 중요한 부분은 Base Case를 정확하게 설정하는 것입니다. Base Case를 설정하지 않거나 잘못 설정하면 무한 재귀에 빠질 수 있습니다.
2. 스택 오버플로우 주의
재귀 함수를 사용할 때, 함수 호출이 계속 쌓이면서 스택 메모리를 소비하게 됩니다. 일정 깊이 이상의 재귀 호출이 발생하면 스택 오버플로우가 발생할 수 있습니다.
