[2024.02.27] 완전 탐색

반복과 재귀

• 반복과 재귀는 유사한 작업을 수행할 수 있다.
• 반복은 수행하는 작업이 완료될 때까지 계속 반복
  루프 (for, while 구조)
  반복문은 코드 n번 반복시킬 수 있다.
• 재귀는 주어진 문제의 해를 구하기 위해 동일하면서 더 작은 문제의 해를 이용하는 방법
  하나의 큰 문제를 해결할 수 있는 더 작은 문제로 쪼개고 결과들을 결합

def KFC(x):
    if x == 2:
        return
    print(x)
    KFC(x+1)
    print(x)

KFC(0)
print('끝')

#결과: 0 1 1 0 끝

재귀함수는 무조건 기저조건이 있어야 함.

def recur(x):
    if x == 6:
        return
    print(x, end=' ')
    recur(x+1)
    print(x, end=' ')

recur(0)

#결과: 0 1 2 3 4 5 5 4 3 2 1 0

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

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

run(0)

순열

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

중복순열?
: 서로 다른 N개에서 R개를 중복을 허용하고, 순서를 고려하여 나열하는 것

중복순열 구현 원리
1) 재귀호출을 할 때마다, 이동 경로를 흔적으로 남긴다.
2) 가장 마지막 레벨에 도착했을 때, 이동 경로를 출력한다.

#중복순열
path = []

def KFC(x):
    if x == 2:
        print(path) #마지막 레벨에 도달했을 때 출력
        return
    
    for i in range(3):
        path.append(i)
        KFC(x+1)
        path.pop()

KFC(0)

#결과
[0, 0]
[0, 1]
[0, 2]
[1, 0]
[1, 1]
[1, 2]
[2, 0]
[2, 1]
[2, 2]

#중복순열 [1,1,1] ~ [6,6,6] 출력
#branch : 6, level : 3
path = []

def KFC(x):
    if x == 3:
        print(*path) #마지막 레벨에 도달했을 때 출력
        return
    
    for i in range(1, 7):
        path.append(i)
        KFC(x+1)
        path.pop()

KFC(0)

중복을 취급하지 않는 순열 구현 방법
1) 중복순열 코드를 작성한다.
2) 중복을 제거하는 코드를 추가하면 순열 코드가 된다.

중복을 제거하는 원리

• 전역 리스트를 사용하면 이미 선택했던 숫자인지 아닌지 구분할 수 있다.
• 이를 used 배열 또는 visited 배열이라고 한다.

#중복없는 순열
path = []
used = [False for _ in range(7)]
def KFC(x):
    if x == 2:
        print(*path) #마지막 레벨에 도달했을 때 출력
        return
    
    for i in range(1, 7):
        if used[i] == True:
            continue
        used[i] = True
        path.append(i)
        KFC(x+1)
        path.pop()
        used[i] = False

KFC(0)

#결과
1 2
1 3
1 4
1 5
1 6
2 1
2 3
2 4
2 5
2 6
3 1
3 2
3 4
3 5
3 6
4 1
4 2
4 3
4 5
4 6
5 1
5 2
5 3
5 4
5 6
6 1
6 2
6 3
6 4
6 5

#중복순열
path = []

def KFC(x):
    if x == 2:
        print(*path) #마지막 레벨에 도달했을 때 출력
        return
    
    for i in range(1, 7):
        path.append(i)
        KFC(x+1)
        path.pop()

KFC(0)

#결과
1 1
1 2
1 3
1 4
1 5
1 6
2 1
2 2
2 3
2 4
2 5
2 6
3 1
3 2
3 3
3 4
3 5
3 6
4 1
4 2
4 3
4 4
4 5
4 6
5 1
5 2
5 3
5 4
5 5
5 6
6 1
6 2
6 3
6 4
6 5
6 6

완전 탐색

• 완전탐색 문제 1. 주사위 눈금의 합
  3개의 주사위를 던져 나올 수 있는 모든 경우에 대해, 합이 10이하가 나오는 경우는 총 몇가지 인가?

path = []
cnt = 0

def KFC(x, sm):
    global cnt

    if sm > 10:
        return

    if x == 3:
        if sm <= 10:
            print(f'{path} = {sm}')  # 마지막 레벨에 도달했을 때 출력
        cnt += 1
        return

    for i in range(1, 7):
        path.append(i)
        KFC(x + 1, sm + i)
        path.pop()

KFC(0, 0)
print(cnt)


#결과
[1, 1, 1] = 3
[1, 1, 2] = 4
[1, 1, 3] = 5
[1, 1, 4] = 6
[1, 1, 5] = 7
[1, 1, 6] = 8
[1, 2, 1] = 4
[1, 2, 2] = 5
[1, 2, 3] = 6
[1, 2, 4] = 7
[1, 2, 5] = 8
[1, 2, 6] = 9
[1, 3, 1] = 5
[1, 3, 2] = 6
[1, 3, 3] = 7
[1, 3, 4] = 8
[1, 3, 5] = 9
[1, 3, 6] = 10
[1, 4, 1] = 6
[1, 4, 2] = 7
[1, 4, 3] = 8
[1, 4, 4] = 9
[1, 4, 5] = 10
[1, 5, 1] = 7
[1, 5, 2] = 8
[1, 5, 3] = 9
[1, 5, 4] = 10
[1, 6, 1] = 8
[1, 6, 2] = 9
[1, 6, 3] = 10
[2, 1, 1] = 4
[2, 1, 2] = 5
[2, 1, 3] = 6
[2, 1, 4] = 7
[2, 1, 5] = 8
[2, 1, 6] = 9
[2, 2, 1] = 5
[2, 2, 2] = 6
[2, 2, 3] = 7
[2, 2, 4] = 8
[2, 2, 5] = 9
[2, 2, 6] = 10
[2, 3, 1] = 6
[2, 3, 2] = 7
[2, 3, 3] = 8
[2, 3, 4] = 9
[2, 3, 5] = 10
[2, 4, 1] = 7
[2, 4, 2] = 8
[2, 4, 3] = 9
[2, 4, 4] = 10
[2, 5, 1] = 8
[2, 5, 2] = 9
[2, 5, 3] = 10
[2, 6, 1] = 9
[2, 6, 2] = 10
[3, 1, 1] = 5
[3, 1, 2] = 6
[3, 1, 3] = 7
[3, 1, 4] = 8
[3, 1, 5] = 9
[3, 1, 6] = 10
[3, 2, 1] = 6
[3, 2, 2] = 7
[3, 2, 3] = 8
[3, 2, 4] = 9
[3, 2, 5] = 10
[3, 3, 1] = 7
[3, 3, 2] = 8
[3, 3, 3] = 9
[3, 3, 4] = 10
[3, 4, 1] = 8
[3, 4, 2] = 9
[3, 4, 3] = 10
[3, 5, 1] = 9
[3, 5, 2] = 10
[3, 6, 1] = 10
[4, 1, 1] = 6
[4, 1, 2] = 7
[4, 1, 3] = 8
[4, 1, 4] = 9
[4, 1, 5] = 10
[4, 2, 1] = 7
[4, 2, 2] = 8
[4, 2, 3] = 9
[4, 2, 4] = 10
[4, 3, 1] = 8
[4, 3, 2] = 9
[4, 3, 3] = 10
[4, 4, 1] = 9
[4, 4, 2] = 10
[4, 5, 1] = 10
[5, 1, 1] = 7
[5, 1, 2] = 8
[5, 1, 3] = 9
[5, 1, 4] = 10
[5, 2, 1] = 8
[5, 2, 2] = 9
[5, 2, 3] = 10
[5, 3, 1] = 9
[5, 3, 2] = 10
[5, 4, 1] = 10
[6, 1, 1] = 8
[6, 1, 2] = 9
[6, 1, 3] = 10
[6, 2, 1] = 9
[6, 2, 2] = 10
[6, 3, 1] = 10
108

• SWEA 단순 2진 암호코드 (강사님 풀이)

import sys
sys.stdin = open('input.txt', 'r')

#테스트케이스 수 T
T = int(input())

#매직테이블 암호코드 7자리 -> 숫자로 변환
d_to_num = {
    '0001101': '0',
    '0011001': '1',
    '0010011': '2',
    '0111101': '3',
    '0100011': '4',
    '0110001': '5',
    '0101111': '6',
    '0111011': '7',
    '0110111': '8',
    '0001011': '9'
}

for tc in range(1, T+1):
    #입력
    N, M = map(int, input().split()) #배열의 세로 크기  N, 가로 크기 M
    barcode = [input() for _ in range(N)] #N * M 크기의 배열을 barcode

    #로직
    #2진 암호코드를 읽어들이는 부분
    def decode(barcode):
        #입력받은 바토드로부터 암호 코드 8자리 수를 반환 (문자열 형태로)
        for row in set(barcode):
            row = row.rstrip('0') #뒷쪽에 '0' 문자열을 지우기
            if len(row) == 0:
                continue
            #뒤를 기준으로 56개의 문자열을 가져오기
            row = row[len(row)-56:len(row)]

            result = ''
            #바코드를 7개 단위로 잘라서 읽는 과정
            for idx in range(0, len(row), 7):
                #암호코드 하나의 값
                digit = d_to_num[row[idx:idx+7]]
                result += digit

        return result

    #2진 암호코드를 검증 (10의 배수인지)
    def is_valid(password):
        #홀수자리와 짝수자리를 각각 더한다
        odd = 0 #홀수
        even = 0 #짝수
        #홀수자리만 더하기
        for idx in range(0, len(password), 2):
            odd += int(password[idx])
        #짝수자리만 더하기
        for idx in range(1, len(password), 2):
            even += int(password[idx])

        # odd = sum(map(int, password[::2]))
        # even = sum(map(int, password[1::2]))

        if (odd * 3 + even) % 10 == 0:
            return True
        else:
            return False

    #문자열로 되어있는 8자리 암호
    password = decode(barcode)
    ans = 0

    #검증단계
    if is_valid(password):
        #password의 각 자릿수의 합을 계산
        for idx in range(len(password)):
            ans += int(password[idx])

    #출력
    print(f'#{tc} {ans}')