재귀함수

어떤 함수의 바디에서 자기 자신을 다시 호출하는 것을 재귀함수라고 한다. A 함수가 B 함수를 부르게 되면 컴퓨터 메모리(스택 프레임)에서는 호출된 순서대로 함수를 관리한다. 컴퓨터는 한 번에 한 개의 일밖에 못하기 때문에 현재 실행시켜야하는 라인이 어디인지를 관리를 할 때 스택 구조로 관리한다. 함수 호출 시 스택에 쌓는 형식으로!
재귀 함수도 결국 비슷한 개념이다.
a 라는 함수가 자기 자신인 a 를 호출하므로 스택에는 a 위에 a 가 쌓이게 된다.

K 개 중 하나를 N 번 선택하기

k 중 하나를 n 번 선택할 때 반복문으로도 처리할 수 있겠지만, 재귀함수를 사용할 수 있다. 만약 3개 선택한다고 한다면 for 문을 3번 쓰면 되는데 n 이 늘어나면 for 문을 여러개 작성하기가 번거로워진다. 이럴 때 재귀 함수를 사용하면 더 유연한 코드를 생성할 수 있다.

n 진수를 만들 때 해당 방법이 사용될 수 있다.
N자리의 이진수를 출력할 때 반복문으로도 짤 수 있지만 재귀적으로 k 번째 자리에 0과 1 중 선택하는 함수를 만든 다음 이를 재귀적으로 호출한다면 n 자리의 이진수를 만들 수 있다. 예를 들어 3자리의 이진수를 만들 때
첫 번째 자리를 0 혹은 1로 넣을 수 있다.
그렇게 갈래가 나눠지고 나면 남은 자리수는 2자리이다.
두번째 자리도 0 혹은 1로 넣을 수 있다. 여기서도 갈래가 나눠지고, 남은 자리수는 1자리 이다.
남은 한 자리도 0 또는 1을 넣으면 남은 자리수는 0자리로 재귀 호출을 종료하면 된다.

적절한 종료 조건을 넣지 않는다면 무한으로 호출될 수 있으므로 종료 조건이 필요하다.

이진수 만들기를 재귀함수로 간단하게 구현하면 다음처럼 만들 수 있다.

arr = []
def c(n):
	if (n>3):
    	return
    arr.append(0)
    c(n+1)
    arr.pop()
       
    arr.append(1)
    c(n+1)
	arr.pop()

1. k개 중에 1개를 n번 뽑기

https://www.codetree.ai/missions/2/problems/n-permutations-of-k-with-repetition?&utm_source=clipboard&utm_medium=text

입력 형식
첫째 줄에 K와 N이 공백을 사이에 두고 주어집니다.

1≤K≤4

1≤N≤8

출력 형식
서로 다른 순서쌍의 개수 만큼의 줄에 걸쳐 한 줄에 하나씩 순서쌍의 상태를 공백을 사이에 두고 출력합니다. 이때 앞에서 부터 봤을 때 사전순으로 앞선 순서쌍부터 출력합니다.

예제1
입력:
2 2

출력:
1 1
1 2
2 1
2 2

문제 설명
k, n 두개의 숫자가 주어진다. 1부터 k 까지 n개의 숫자를 중복 상관없이 고른다. 해당 문제애서는 중복해서 골라도 된다. 이러한 문제를 보고 이걸 재귀함수로 풀어야겠다! 생각을 하면 다음을 정해야한다.
1. 재귀함수가 해야할 일 : 해당 문제에서는 1~k 중에 숫자 하나를 고르는 것
2. 재귀함수의 종료조건 : 해당 문제에서는 n 번만 호출하기 위한 조건이 된다.

내가 짠 코드
내가 짠 코드는 다음과 같은데 해설을 본 결과 다음의 개선점이 있다. 우선 for 문에서 불필요한 코드가 있다. arr 에 수를 넣고 다음 재귀 호출을 하는 데서 순간적으로 숫자 넣고 -> 다음 재귀 호출하고 -> 다시 뺴고 -> 다음 재귀 호출하자! 라고 생각을 했는데 for 문 안에 있기 때문에 재귀 호출을 두 번 하는 건 불필요한 과정이다. 이렇게 잘못 짠 코드 때문에 종료 조건 확인 부분에서 불필요하게 배열의 길이를 확인하는 코드가 추가되었는데 만약 해당 for 문을 수정한다면 이 불필요한 if 문도 삭제할 수 있다 .

k, n = tuple(map(int, input().split()))
arr = []


def make_p(cnt):
    if cnt > n:
        if len(arr)==n:
            for elem in arr:
                print(elem, end=' ')
            print()
        return
    
    for i in range(1, k+1):
        arr.append(i)
        make_p(cnt+1)
        arr.pop()
        make_p(cnt+1)
    

make_p(1)

K개 중 하나를 N번 선택하기 (Conditional)

이번에는 k 개 중에 하나를 n 번 선택할 떄 조건이 있는 문제이다. 예를 들어 n 자리의 2진수를 출력하는 코드를 나타내는 문제에서 0이 인접해서 등장하면 안된다는 조건이 붙을 떄처럼 조건이 붙은 선택 문제에서 사용한다.
재귀함수 호출 시 조건문을 작성하여 해당 조건(0일 때는 최초 0 이거나 바로 직전이 0 이 아닐 경우만 추가 가능하게) 하에 재귀 호출을 해줄 수 있다.

1. 특정 조건에 맞게 k개 중에 1개를 n번 뽑기

https://www.codetree.ai/missions/2/problems/n-permutations-of-k-with-repetition-under-constraint?&utm_source=clipboard&utm_medium=text

입력 형식
첫째 줄에 K와 N이 공백을 사이에 두고 주어집니다.

1≤K≤4

1≤N≤8

출력 형식
조건을 만족하는 서로 다른 순서쌍의 개수 만큼의 줄에 걸쳐 한 줄에 하나씩 순서쌍의 상태를 공백을 사이에 두고 출력합니다. 이때 앞에서 부터 봤을 때 사전순으로 앞선 순서쌍부터 출력합니다.

예제1
입력:
2 1

출력:
1
2

이 문제는 이전에 짠 코드에서 조건이 붙은 문제이다. 탐색을 할 때 체크를 해서 재귀 호출이 아예 안일어나게 만들던지 답을 출력할 떄 세 번 연속인 케이스를 체크해서 출력을 안하게 하던지 두 가지 방법 중에 고를 수 있는데 탐색할 때 컷하는 코드가 더 추천된다.

내가 짠 코드

k, n = tuple(map(int, input().split()))
arr = []

def make_p(cnt):
    if cnt > 3:
        if arr[-1]==arr[-2] and arr[-2]==arr[-3]:
            return 

    if cnt > n:
        for elem in arr:
            print(elem, end=' ')
        print()
        return


    for i in range(1, k+1):
        arr.append(i)
        make_p(cnt+1)
        arr.pop()

make_p(1)

N개중에 M개 고르기 (Simple)

1. n개 중에 m개 뽑기

https://www.codetree.ai/missions/2/problems/n-choose-m?&utm_source=clipboard&utm_medium=text

입력 형식
첫째 줄에 N과 M이 공백을 사이에 두고 주어집니다.
1≤M≤N≤10

출력 형식
조합의 개수 만큼의 줄에 걸쳐 한 줄에 하나씩 조합의 상태를 공백을 사이에 두고 출력합니다. 이때 앞에서 부터 봤을 때 사전순으로 앞선 조합부터 출력하며, 한 조합 내에서는 숫자들을 오름차순으로 정렬하여 출력합니다.

예제1
입력:
3 2

출력:
1 2
1 3
2 3

내가 짠 코드

n, m = tuple(map(int, input().split()))
arr = []

# 마지막으로 넣은 수도 같이 넣어줘서 이 숫자 밑의 수는 넣지 않는다.
def make_c(cnt, idx):

    if cnt > m:
        for elem in arr:
            print(elem, end=' ')
        print()
        return

    for i in range(idx, n+1):
            arr.append(i)
            # 방금 넣은 애의 다음 숫자들만 넣을 수 있다.
            make_c(cnt + 1, i+1)
            arr.pop()


make_c(1, 1)

2. xor 결과 최대 만들기

https://www.codetree.ai/missions/2/problems/max-of-xor?&utm_source=clipboard&utm_medium=text

입력 형식
첫 번째 줄에는 n과 m이 공백을 사이에 두고 주어지고, 두 번째 줄에는 n개의 정수가 공백을 사이에 두고 주어집니다.

0≤정수≤1,000,000
1≤m≤n≤20

출력 형식
m개의 숫자를 골랐을 때 가능한 xor 결과의 최댓값을 출력합니다.

입력:
5 3
1 2 3 4 5

출력:
7

예제로 문제를 이해해보자. 위 예제에서는 1은 001 2는 010 3은 011 4는 100 5는 101 인데
가장 큰 값이 나오려면 처음 자리수가 1 이 되는 게 최우선이고 다음 글자들도 1이 되면 좋다.
위 예시에서는 001 + 011 + 101 을 하면 111 로 7이 최대가 된다.

내가 짠 코드
처음에 중복을 고려하지 않았더니 시간 초과가 났다. 선택 문제에서는 중복 여부를 꼭 확인해야겠다.

n, m = tuple(map(int, input().split()))

arr = list(map(int, input().split()))

ds = []
max_v = 0


def find_max(cnt, idx):
    global max_v

    if cnt > m:
        for elem in ds:
            elem = bin(elem)
        result = ds[0]
        for i in range(1, len(ds)):
            result = result ^ ds[i]
        max_v = max(max_v, result)
        return
    for i in range(idx, len(arr)):
        ds.append(arr[i])
        find_max(cnt + 1, i+1)
        ds.pop()


find_max(1, 0)
print(max_v)

N개중에 M개 고르기 (Conditional)

조건 자체가 가변화되는 경우에 어떻게 처리할지.
n 자리 이진 수 중에서 1의 개수가 정확히 m 개인 수만 구해서 출력할 때 for 문 안에 if 문을 m 개를 작성하는 건 어려울 것 같다. 이처럼 조건 자체라 m 개로 가변화되어 있다면 종료 조건에서 출력 전에 안되는 애들을 컷하고 되는 애들만 출력해주면 된다.

순열 만들기

1. 크기가 n인 순열

https://www.codetree.ai/missions/2/problems/n-permutation?&utm_source=clipboard&utm_medium=text

내가 짠 코드

n = int(input())

arr = []
def make_p(cnt):
    if cnt > n:
        for elem in arr:
            print(elem, end=' ')
        print()
        return
    
    for i in range(1, n+1):
        if arr.count(i) >= 1:
            continue
        arr.append(i)
        make_p(cnt+1)
        arr.pop()
    
make_p(1)

2.수들의 합 최대화하기

https://www.codetree.ai/missions/2/problems/max-sum-of-numbers/description

입력 형식
첫 번째 줄에 n이 주어집니다.
두 번째 줄부터 n개의 줄에 걸쳐 한 줄에 n개씩의 정수가 공백을 두고 주어집니다.

1 ≤ n ≤ 10

1 ≤ 주어지는 정수 ≤ 10,000

출력 형식
조건을 만족하며 얻을 수 있는 합 중 최댓값을 출력합니다.

예제1
입력:
3
3 5 3
5 8 4
2 7 1
출력:
15

내가 짠 코드

n = int(input())
arr = [list(map(int, input().split())) for _ in range(n)]
max_sum = 0

def backtrack(row, selected_cols, current_sum):
    global max_sum

    # 종료 조건 달성
    if row == n:
        max_sum = max(max_sum, current_sum)
        return
    
    for col in range(n):
        if col in selected_cols:
            continue
        # 현재 행(row)에서 열(col)을 선택하고 다음 행으로 넘어감
        backtrack(row + 1, selected_cols + [col], current_sum + arr[row][col])

# 초기 호출: 첫 번째 행부터 시작, 선택된 열은 없고 합은 0
backtrack(0, [], 0)

print(max_sum)