jun-wiki
Pages (Latest 10 updated) :
재귀의 핵심을 깨달음
고졸(진짜임) 사토루가 돼버렸다.
외판원 순회 문제 등 재귀함수 문제를 몇 개 더 풀어보니
재귀함수 활용 법을 깨닫게 되었다.
물론 아직 코드로 바로바로 쓰기엔 약간 무리가 있으나
이제 처음 터득했으니 쩔 수 없다.
무하한 루프는 제어하기 쉽지 않다.
잘못 다룰 경우 결과에 접근이 안되니 말이다.
추가로 아오와 아카도 배웠다.
순전술식
⌜아오⌟float('inf')
술식반전
⌜아카⌟ float('-inf')
이 둘을 합쳐 가상의 함수를 만들어 무한한 계산량을 가진 루프를 구현가능하다.
허식 자
⌜무라사키⌟ </span>
while True:
print("∞")
대충 재귀 + for문은 기본 골자가 이렇게 이루어진다.
# 재귀의 ⌜핵심⌟
def perm(path, used):
# path: 현재까지 만들어진 순열(리스트)
# used: 이미 쓴 숫자 인덱스 표시 (True/False 리스트)
if len(path) == n:
# [1] 순열 하나 완성 시점(종료조건)
print(path)
# 원하는 작업 수행(여기선 단순 출력)
return
for i in range(n):
# [2] n개의 숫자 중 한 개 선택
if not used[i]:
# [3] 아직 안 쓴 숫자만 사용
used[i] = True
# [4] i번째 숫자 선택 표시
perm(path + [nums[i]], used)
# [5] 현재 숫자 추가해 다음 자리로 재귀 호출
used[i] = False
# [6] 되돌아오면 선택 취소(백트래킹)
nums = [1, 2, 3]
# 예시 숫자 리스트
n = len(nums)
used = [False] * n
# 방문 체크 배열 초기화
perm([], used)
# 순열 생성 시작 (path=[], used=모두 False)