반복과 재귀, 순열, 완전 탐색

• 반복과 재귀

반복과 재귀는 유사한 작업을 수행할 수 있다.

반복 → 수행하는 작업이 완료될 떄까지 계속 반복

루프 (for, while 구조), 반복문은 코드를 n번 반복시킬 수 있다.

for i in range(1,4):
    for j in range(1, 4):
        for z in range(1, 4):
            for h in range(1, 4):
                print(i*10**3 + j*10**2 + z*10 + h)

# 1111
# 1112
# 1113
# ...
# 3323
# 3331
# 3332
# 3333

재귀는 주어진 문제의 해를 구하기 위해 동일하면서 더 작은 문제의 해를 이용한다.

큰 문제 해결을 위해 더 작은 문제로 쪼개고 결과들을 결합한다. 재귀 함수로 구현!

재귀호출은 n 중 반복문을 만들어낼 수 있다.

 

• 재귀를 연습하기 전 알아야 할 함수의 특징 1

함수를 호출할 때 int 타입 객체를 전달하면 값만 복사된다!

 

• 재귀를 연습하기 전 알아야 할 함수의 특징 2

함수가 끝나면 Main 으로 되돌아 오는 것이 아니라 해당 함수를 호출했던 곳으로 돌아온다!

 

재귀호출의 시작은 무한 재귀호출을 막는 것부터!

무한 재귀호출을 막아주는 if문 등을 ‘기저조건’ 이라고 한다.

 

• 0 1 2 3 4 5 5 4 3 2 1 0 을 재귀호출을 이용하여 구현하는 코드

def kfc(v):
    if v == 6:
        return
    print(v, end=' ')
    kfc(v+1)
    print(v, end=' ')

kfc(0)

# 0 1 2 3 4 5 5 4 3 2 1 0 

 

재귀 호출을 트리 형태로 간략화하여 그리면

기저조건 → level = 층수, 깊이

한 함수 내 재귀 호출 횟수 → branch = 가지 수가 된다.

 

# branch = 2
# level = 3

def run(level):
    if level == 3:
        return

    for i in range(2):
        run(level + 1)

 

• 순열

서로 다른 N개에서 R개를 중복없이, 순서를 고려하여 나열하는 것

 

• 순열 구현 원리

재귀호출할 때마다 이동 경로 흔적을 남기고 가장 마지막 레벨에 도달했을 때 이동 경로를 출력한다.

이동 경로 (흔적) → 보통 ‘path’ 라고 명명

 

path = []

def kfc(v):
    if v == 2:
        print(path)
        return

    for i in range(3):
        path.append(i)
        kfc(v + 1)
        path.pop()

kfc(0)

 

• 중복순열 [1,1,1] ~ [6,6,6] 까지 출력하는 코드

path = []

def kfc(v):
    if v == 3:
        print(*path)
        return

    for i in range(1, 7):
        path.append(i)
        kfc(v + 1)
        path.pop()

kfc(0)

# 가지 = 6
# 층수 = 3

 

• (추가) 중복순열 [1 1 1 1 1] ~ [4 4 4 4 4] 까지 출력하는 코드

path = []

def kfc(v):
    if v == 5:
        print(*path)
        return

    for i in range(1, 5):
        path.append(i)
        kfc(v + 1)
        path.pop()

kfc(0)

# 가지 = 4
# 층수 = 5

 

• 중복을 취급하지 않는 ‘순열’ 구현 방법 (원래 순열은 중복을 허용하지 않는다)

중복 순열 코드에서 중복을 제거하는 코드를 넣으면 순열 코드가 된다.

전역 리스트를 사용하여 중복을 판단하고 제거한다.

 

• N개의 주사위를 던져서 나올 수 있는 모든 중복 순열(Type1)과 순열(Type2)을 출력하는 코드

N과 Type을 입력 받는다. (주사위 개수, 순열 타입)

def kfc(v):     # 중복 순열
    if v == 0:
        print(*path)
        return

    for i in range(1, 7):
        path.append(i)
        kfc(v - 1)
        path.pop()

def bbq(v):     # 순열
    if v == 0:
        print(*path)
        return

    for i in range(1, 7):
        if used[i] is True:
            continue
        used[i] = True
        path.append(i)
        bbq(v - 1)
        path.pop()
        used[i] = False

path = []
used = [False for _ in range(7)]
N, Type = map(int, input().split())
if Type == 1:
    kfc(N)
else:
    bbq(N)

 

• 완전 탐색 (= Brute-Force)

모든 가능한 경우를 시도해보아 정답을 찾아내는 알고리즘

가능한 모든 케이스를 탐색하는 알고리즘 = 완전 탐색 알고리즘

 

• 가지치기가 들어간 코드

def kfc(v, sum):
    if sum > 10:    # 가지치기
        return

    if v == 0:
        if sum <= 10:
            print(f'{path} = {sum}')
            return

    for i in range(1, 7):
        path.append(i)
        kfc(v - 1, sum + i)
        path.pop()

path = []
kfc(3, 0)

 

순열은 중복이 허용되지 않기에 점점 선택할 수 있는 가지수가 줄어들고 이전의 선택에 영향을 받는다.

이 2가지를 적용해줄 장치가 필요한 것.

# NxN 2차 배열에서
# 항상 현재 위치(r,c)에서
# 오른쪽(r,c+1) 또는 아래(r+1, c) 방향 중 선택
# 마지막은 (N-1, N-1)에 도착한 경우
N = 3
arr = [[0] * N for _ in range(N)]
cnt = 0
def find_path(r, c): # (r, c) 현재 위치
    global cnt
    arr[r][c] = 1
    if r == N-1 and c == N-1:
        cnt += 1
        for line in arr:
            print(*line)
        print('----------------------')
        return

    # 길을 계속 갑시다.
    # 두가지 선택지를 각각 한번씩 해보는거다....
    # 오른쪽(r, c+1)로
    if c + 1 < N:
        find_path(r, c+1)
    # 아래(r+1, c)
    if r + 1 < N:
        find_path(r+1, c)

    arr[r][c] = 0

find_path(0, 0)
print('모든 경로수 = ', cnt)