6주차 코딩테스트 요점(재귀함수와 정렬)

1. 하노이 탑

하노이 탑 문제에 대한 저의 코드입니다. 문제의 핵심은 

위와 같은 재귀 패턴 찾기 입니다. n개의 이동 방식은 n-1개 이동 -> 타겟 원판 이동 n-1개 원판 이동 입니다. 이를 재귀를 표현하는것이 해결 방법 입니다. 

hanoi(n-1,start,end,sub)

print(f'{start} {end}')

hanoi(n-1,sub,start,end)

이 코드의 매개변수 순서는 

위 그림을 보면서 생각하는게 편합니다. 처음 n-1개를 sub로 옮겨야 하기 때문에 start시작으로 목표는 sub가 되는 겁니다. 

그 후 타겟을 옮긴 후 n-1개 옮기는 것도 같은 방식으로 sub에서 end로 옮기므로 매개변수를 저렇게 줘야 합니다. 

 

2. 정렬

정렬은 매우 잘 정리되어있는 사이트가 있어 이걸 공유하겠습니다.

https://roytravel.tistory.com/328

[자료구조] 기본 정렬 알고리즘 총 정리

 

3. 데이터 바꾸기

위 코드와 같이 a, b =b, a 식으로 a와 b의 값을 바꿀 수 있습니다. temp와 같은 변수를 따로 만들어 담지 않아도 되어 편할거 같습니다.  하지만 문자열에서는 불가능 합니다. 

 

4. range()

range(start, stop, step) 구조에 step 에 음수를 주면 값이 적어지게 됩니다. stop은 미만이므로 -1을 주면 0까지만 가게 됩니다. 즉 i-1부터 0까지 거꾸로 가게 됩니다. 

 

5. for~else

파이썬에만 있는 문법으로 for 문이 break로 끝나지 않을때만 실행하는 코드입니다. 

 

6. extend

extend는 append와 비슷하게 리스트 뒤에 값을 추가하는 기능을 하지만 리스트를 append하면 리스트인 상태로 추가 되지만 extend는 한펀 풀어서 추가하게 됩니다. 즉 1차원 리스트를 extend하면 시퀀스로 들어가지고 2차원 리스트를 extend하면 1차원 리스트가 들어갑니다.