알고리즘.... 어렵다

항해 2주차

본격적인 알고리즘 마라톤이 시작되었다....
스스로 풀어보려고 노력하지만 처음 접해보는 코딩이라... 문제를 손으로 풀줄 알겠는데... 이걸 어떻게 컴퓨터한테 시켜야할지 막막하다... 특히 하노이탑 문제에서... 1단계 n-1 단계의 모든걸 옮기는 함수를 실행한다는것... 2단계는 그이후에 마지막 제일 큰 거를 목표한 곳에 옮기는것 3단계 이제 n-1개를 목표한곳에 다시 옮기는것 .... 이건 수학적으로 an = 2an-1 +1 이란게 이해가 가는데... 이걸 왜 재귀함수를 써서 답안과 같이 쓰는지 아직도 잘 이해가 안간다....
an +1 = 2(an-1 +1) so an = 2^n - 1
파이썬 에서 함수로는
def hanoi_tower(n, start, end): #start 에서 end로 다 옮겨준다는 함수
if n == 1:
print(start, end)
return

hanoi_tower(n - 1, start, 6 - start - end)  # 1단계  start에서 end로 가기 위해선 end 말고 다른곳에 다 옮겨놔야함
print(start, end)  # 2단계   맨 마지막꺼 하나를 이제 옮겨지는곳으로 옮기는 과정
hanoi_tower(n - 1, 6 - start - end, end)  # 3단계     이거 전체다를 목표한곳으로 이제 다 옮겨주는 함수

A4용지에 n=3 일때 하나씩 전개해보니 컴퓨터가 계산하는 방식을 알게되었지만 이를 어떻게 이용해서 재귀함수를 직접 짜야할지 감이 안잡힌다 ...

좋은 웹페이지 즐겨찾기