(BOJ)-15649, Python

문제 요약

출처: (BOJ)15649 - N과 M (1)

$N, M$이 주어졌을 때, $1$부터 $N$까지의 숫자 중에서 $M$개를 중복없이 뽑아 생성한 수열들을 출력하는 문제이다.

• 사전 순으로 증가하는 순서로 출력

접근 과정

1. 완전탐색 접근

범위를 $1$부터 $N$까지로 타겟하고, 수열의 길이만큼 $M$개의 반복문을 작성하려 했지만, 아래 코드처럼 $M$에 따라 반복문의 개수를 조정하는 것이 쉽지 않았다..

코드 구현

N, M = map(int, input().split())

for i in range(1, N+1):
    for j in range(1, N+1):
        for k in range(1, N+1):
	        .....

2. 재귀적 접근

유동적으로 반복문을 돌릴 방법을 고민하다가, 하나의 반복문을 가진 함수를 여러번 호출하면 되지 않을까하는 생각이 들었다. 가지를 뻗어나가듯이 함수를 호출하여 모든 경우를 찾아내고, 길이가 끝에 도달했을 경우에 반환하는 그림이 그려졌다..! 이를 기반으로 아래 코드를 작성하였다!

코드 구현

def recursion(N, M, arr):
    if M == 0:
        print(*arr)
        return
    
    for i in range(1, N+1):
        if i in arr:
            continue
        arr.append(i)
        recursion(N, M-1, arr)
        arr.pop()

N, M = map(int, input().split())
arr =[]
recursion(N, M, arr)

회고

재귀라는 개념은 알고 있었지만, 어떤 상황에서 재귀 호출을 사용하는 것이 적절한지 명확히 알지 못했었다. 이를 생각해보니, 재귀라는 키워드 자체에만 집중했던 것이 원인이었다. 완전탐색을 바탕으로 재귀를 활용해 직접 코드를 작성해보니, 재귀 호출이 유동적인 반복이 필요할 때 꽤 유용하다는 점을 배울 수 있었다!