1. 문제
세 개의 장대가 있고 첫 번째 장대에 반경이 서로 다른 n개의 원판이 반경이 큰 순서대로 쌓여있다.
아래 규칙에 따라 첫 번째 장대에서 세 번째 장대로 옮길 때 필요한 이동 순서를 출력하는 프로그램을 작성하라
단, 이동 횟수는 최소가 되어야 한다 (원판의 개수는 1 <= N <= 100)
1. 한 번에 한 개의 원판만을 다른 탑으로 옮길 수 있다
2. 쌓아 놓은 원판은 항상 위의 것이 아래의 것보다 작아야 한다
2. 알고리즘 분류
* 임의 정밀도/ 큰 수 연산
* 재귀
3. 접근 방식
재귀 함수를 먼저 공부해야 한다
왜냐하면 마지막 원판을 목표 기둥으로 보내기 위해서는 다른 원판들을 계속해서 옮겨야 하기 때문!
쉽게 설명하자면, 나머지 원판들 (N-1) 은 임시 기둥 B 로 옮기고
제일 큰 원판 N 을 목표 기둥 C 로 보내고, 다시 N-1 을 목표 기둥으로 보내는 작업을 진행한다
ex. N = 1 일 때는 N 을 A -> C 로 한 번만 보내면 된다 (이동 횟수 1회)
N = 2 일 때는 작은 원판을 A -> B 로, 큰 원판을 A -> C 로, 작은 원판을 B -> C 로 보낸다 (이동 횟수 3회)
N = 3 일 때는 N-1 을 A -> B 로 보내고 (N = 2 에서 이동 횟수 3회), N 을 A -> C 로 보낸 다음에
다시 N-1 을 B -> C 로 보내야 한다 (B -> A, B -> C, A -> C, 이동 횟수 3회)
N = 4 일 때는 N-1: A -> B (N = 3, 7회), N: A -> B (1회), N-1: B -> C (N = 3, 7회) (이동 횟수 15회)
결론적으로, N 개의 원판이 있을 때, N-1 을 임시 기둥으로 한 번 옮겨야
가장 큰 원판 N 이 목표 기둥으로 옮길 수 있다
그런 다음에 N-1 원판을 목표 기둥으로 옮기면 작업이 종료된다
따라서 f(n) = 1 + 2f(n-1) 이 되고, 결국 이동 횟수는 2^N - 1 이다
+ 추가로, 원판이 짝수 개일 때는 처음 원판을 임시 기둥으로 옮기고
홀수 개일 때는 처음 원판을 목표 기둥으로 옮긴다
그래서 재귀 함수를 공부했다
재귀 함수 개념은 알겠는데 디버깅도 안 되고 헷갈려서 문제를 많이 풀어봐야겠다
4. 코드
첫번째 시도
def hanoi(n: int, x: int, y: int, count: int) -> None:
if n > 1:
# N-1 을 시작 기둥에서 임시 기둥으로 옮기기
count = hanoi(n-1, x, 6-x-y, count)
print(x, y)
count += 1 # Count 쓰려고 했는데 도저히 못 쓰겠음
if n > 1:
# N-1 을 임시 기둥에서 목표 기둥으로 옮기기
count = hanoi(n-1, 6-x-y, y, count)
return count
if __name__ == '__main__':
n = int(input())
count = 0
print(2 ** n -1) # 이동 횟수 출력하기
count = hanoi(n, 1, 3, count)
두번째 시도
Print 를 Main 으로 뺐더니 메모리 초과가 뜸
+ 근데 지금 다시 보니까, result int 로 선언하고
count 에서 하노이 호출해서 저장하고ㅋㅋㅋㅋ뭐지 싶다
# n 개의 원판을 첫 번째 장대에서 세 번째 장대로 옮긴다
# 한 번에 한 개의 원판만을 다른 탑으로 옮길 수 있다
# 위의 원판이 아래 원판보다 작아야 한다
def hanoi(n: int, x: int, y: int, result: int) -> None:
if n > 1:
# N-1 을 시작 기둥에서 임시 기둥으로 옮기기
count = hanoi(n-1, x, 6-x-y, result)
result.append(f"{x} {y}")
# count += 1 # Count 쓰려고 했는데 도저히 못 쓰겠음
if n > 1:
# N-1 을 임시 기둥에서 목표 기둥으로 옮기기
count = hanoi(n-1, 6-x-y, y, result)
# return count
if __name__ == '__main__':
n = int(input())
# count = 0
result = []
print(2 ** n -1) # 이동 횟수 출력하기
count = hanoi(n, 1, 3, result)
# 리스트에 저장한 출력 값을 한 번에 출력하기
# 문자열 메서드 Join 을 사용하여 리스트에 있는 요소들을
# 줄바꿈 문자 \n 로 연결한 후 출력한다
print("\n".join(result))
세번째 시도
6-x-y 가 마음에 안 들어서 from to temp 받는 거로 변경했다
근데 나머지는 다 비슷해서 그런지 똑같이 메모리 초과가 떴다
# n 개의 원판을 첫 번째 장대에서 세 번째 장대로 옮긴다
# 한 번에 한 개의 원판만을 다른 탑으로 옮길 수 있다
# 위의 원판이 아래 원판보다 작아야 한다
def hanoi(n: int, fromP: int, toP: int, tempP: int, result: list) -> None:
if n > 1:
# N-1 을 시작 기둥에서 임시 기둥으로 옮기기
count = hanoi(n-1, fromP, tempP, toP, result)
result.append(f"{fromP} {toP}")
if n > 1:
# N-1 을 임시 기둥에서 목표 기둥으로 옮기기
count = hanoi(n-1, fromP, toP, fromP, result)
if __name__ == '__main__':
n = int(input())
# count = 0
result = []
print(2 ** n -1) # 이동 횟수 출력하기
# 1번에서 3번으로 이동, 2번은 임시 기둥
hanoi(n, 1, 3, 2, result)
# 리스트에 저장한 출력 값을 한 번에 출력하기
# 문자열 메서드 Join 을 사용하여 리스트에 있는 요소들을
# 줄바꿈 문자 \n 로 연결한 후 출력한다
print("\n".join(result))
네번째 시도
N <= 20 일 때만 과정을 출력하도록 설정하고
print 를 재귀에서 호출했더니 이번에는 런타임 에러가 떴다 ㅡ.ㅡ
+ 근데 또 지금 다시 보니까, 두번째 재귀에서 from to from 이라고 했네,... 젠장
그래서 두번째 재귀 고치고 다시 해봤는데 똑같이 런타임 에러가 나왔다
# n 개의 원판을 첫 번째 장대에서 세 번째 장대로 옮긴다
# 한 번에 한 개의 원판만을 다른 탑으로 옮길 수 있다
# 위의 원판이 아래 원판보다 작아야 한다
def hanoi(n: int, fromP: int, toP: int, tempP: int) -> None:
# N 이 1 일 때는 바로 From -> To 로 옮기기
if n == 1:
print(f"{fromP} {toP}")
# N-1 을 시작 기둥에서 임시 기둥으로 옮기기
hanoi(n-1, fromP, tempP, toP)
# 가장 큰 원판 N 을 from -> To 옮기기
print(f"{fromP} {toP}")
# N-1 을 임시 기둥에서 목표 기둥으로 옮기기
hanoi(n-1, fromP, toP, fromP)
# return count
if __name__ == '__main__':
n = int(input())
print(2 ** n -1) # 이동 횟수 출력하기
# N 이 20 보다 큰 경우 과정 출력 안 해도 됨
if n <= 20:
# 1번에서 3번으로 이동, 2번은 임시 기둥
hanoi(n, 1, 3, 2)
다섯번째 시도
설마설마 했는데 hanoi 함수 안에서 if n == 1: 일 때 return 을 안 해주고 있었다
GPT 한테 저게 왜 중요한 거냐고 물어보니, return 문은 함수의 실행을 종료하고, 호출한 함수로 돌아가게 만들어서
n == 1 일 때 return 문을 통해 해당 호출이 끝나고, 상위 호출로 돌아가서 계속 진행할 수 있게 만든다고 한다
재귀 호출이 깊어질 때, 호출 스택의 메모리 사용량이 급격하게 증가하는데, Return 문이 있으면
함수가 더 이상 실행되지 않으므로 스택의 메모리 사용을 줄일 수 있게 된다고 했고
마지막으로 reutrn 이 없으면 함수가 계속해서 자신을 호출하게 되어 불필요한 재귀 호출이 계속 발생할 수 있다고 한다
return 잘 써 줘야겠다!
# n 개의 원판을 첫 번째 장대에서 세 번째 장대로 옮긴다
# 한 번에 한 개의 원판만을 다른 탑으로 옮길 수 있다
# 위의 원판이 아래 원판보다 작아야 한다
def hanoi(n: int, fromP: int, toP: int, tempP: int) -> None:
# N 이 1 일 때는 바로 From -> To 로 옮기기
if n == 1:
print(f"{fromP} {toP}")
return
# N-1 을 시작 기둥에서 임시 기둥으로 옮기기
hanoi(n-1, fromP, tempP, toP)
# 가장 큰 원판 N 을 from -> To 옮기기
print(f"{fromP} {toP}")
# result.append(f"{fromP} {toP}")
# N-1 을 임시 기둥에서 목표 기둥으로 옮기기
hanoi(n-1, tempP, toP, fromP)
if __name__ == '__main__':
# 기둥 개수 입력받기
n = int(input())
print(2 ** n -1) # 이동 횟수 출력하기
# N 이 20 보다 큰 경우 과정 출력 안 해도 됨
if n <= 20:
# 1번에서 3번으로 이동, 2번은 임시 기둥
hanoi(n, 1, 3, 2)
+ 09/17 TUE 복습하다가 ChatGPT 한테 자세한 로직을 물어봤다
맞습니다! 재귀 함수가 호출되는 순서를 좀 더 자세히 설명해 드리면, n == 3일 때의 재귀 과정은 아래와 같습니다.
1. 처음 호출 (n == 3)
hanoi(3, 1, 3, 2)이때 n == 1이 아니므로 hanoi(2, 1, 2, 3)으로 재귀 호출이 먼저 실행됩니다.
2. 두 번째 호출 (n == 2)
hanoi(2, 1, 2, 3)에서 다시 n == 1이 아니므로 이번에는 hanoi(1, 1, 3, 2)로 재귀 호출이 실행됩니다.
3. 세 번째 호출 (n == 1)
이제 hanoi(1, 1, 3, 2)에서 n == 1이므로, print(f"{fromP} {toP}"), 즉 print("1 3")이 출력됩니다. 그 후 return이 되어 이 호출은 종료됩니다.
4. 두 번째 호출로 돌아옴 (n == 2)
이제 n == 1에 해당하는 부분이 끝났으니, 다시 n == 2의 호출로 돌아옵니다. 여기서 print(f"{fromP} {toP}"), 즉 print("1 2")가 실행됩니다. 그 다음 hanoi(1, 3, 2, 1)이 호출됩니다.
5. 네 번째 호출 (n == 1)hanoi(1, 3, 2, 1)이 호출되고, n == 1이므로 print(f"{fromP} {toP}"), 즉 print("3 2")가 실행됩니다. 그 후 return이 되어 종료됩니다.
6. 처음 호출로 돌아옴 (n == 3)
이제 다시 처음 호출된 n == 3으로 돌아옵니다. 여기서 print(f"{fromP} {toP}"), 즉 print("1 3")이 실행됩니다. 그리고 다시 hanoi(2, 2, 3, 1)이 호출됩니다.
7. 다섯 번째 호출 (n == 2)
hanoi(2, 2, 3, 1)에서 n == 1이 아니므로 hanoi(1, 2, 1, 3)이 호출됩니다.
8. 여섯 번째 호출 (n == 1)hanoi(1, 2, 1, 3)에서 n == 1이므로 print(f"{fromP} {toP}"), 즉 print("2 1")이 실행됩니다. 그 후 return이 됩니다.
9. 다섯 번째 호출로 돌아옴 (n == 2)
이제 n == 2로 돌아와서 print(f"{fromP} {toP}"), 즉 print("2 3")이 실행됩니다. 그리고 마지막으로 hanoi(1, 1, 3, 2)이 호출됩니다.
10. 일곱 번째 호출 (n == 1)
마지막으로 hanoi(1, 1, 3, 2)에서 n == 1이므로 print(f"{fromP} {toP}"), 즉 print("1 3")이 실행됩니다. 그 후 return이 되어 종료됩니다.
이 과정을 정리하면, n == 1에 도달할 때마다 원반을 옮기고 (print 후 return), 각 호출이 끝난 후에는 이전 호출로 돌아가서 남은 부분을 처리하는 방식입니다.
'알고리즘' 카테고리의 다른 글
| [백준] 1181 단어 정렬 Python (0) | 2024.09.13 |
|---|---|
| [백준] 1110 더하기 사이클 Python (0) | 2024.09.12 |
| [백준] 2571 수 정렬하기2 Python (0) | 2024.09.10 |
| [백준] 2750 수 정렬하기 Python (0) | 2024.09.10 |
| [백준] 9020 골드바흐의 추측 Python (1) | 2024.09.09 |