백준 15649번 N과 M (1) 파이썬 풀이

Python

[Python] 백준 알고리즘 온라인 저지 2693 N번째 큰 수

15649 N과 M

https://www.acmicpc.net/problem/15649

15649번: N과 M (1)

처음 문제를 접했을 땐 순열로 출력하면 되겠다고 생각하였다. 백트래킹 알고리즘을 잘 알지 못해 같이 소개하며 두 가지 방법 모두 풀이해보려고 한다.

 

알고리즘 분류

• 백트래킹

---

소스코드 1 (permutation)

from itertools import permutations

n, m = map(int, input().split())
nums = [i for i in range(1, n+1)]

p = list(permutations(nums, m))

for i in p:
    print(' '.join(map(str,i)))

---

코드 1 풀이

순열을 이용하여 값들을 출력하면 쉽게 풀이할 수 있다(제출하여도 정답처리). 1부터 n까지의 수들을 배열로 넣어주고 이 배열에 permutaion 함수를 이용해 다른 배열로 만들어준다. 이후 모든 요소들을 출력해주면 된다.

---

소스코드 2

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

s = []

def dfs():
    if len(s) == m:
        print(' '.join(map(str, s)))
        return

    for i in range(1, n + 1):
        if i not in s:
            s.append(i)
            dfs()
            s.pop()

dfs()

---

백트래킹 알고리즘 (Backtracking Algorithm)

백트래킹은 모든 조합을 시도해서 문제의 해를 찾는다. 해를 얻을 때까지 모든 가능성을 시도한다. 가능성은 아래 사진과 같이 트리 형식으로 표현할 수 있고 탐색 중 오답을 만나면 이전 분기점으로 돌아간다.

깊이 우선 탐색

이러한 깊이 우선 탐색을 DFS(Depth First Search)라고 불리고 이는 대표적인 완전 탐색 방법이다.

하지만 이 방식은 모든 경우를 시도하기 때문에 비효율적으로 작동할 수도 있다. 여기서 백트래킹을 사용하는 이유를 찾을 수 있다.

백트래킹 알고리즘은 DFS의 비효율적인 경로를 차단하고 가능성이 있는 루트를 검사하는 방법이다.

---

코드 2 풀이

문제를 풀이하며 이 방법에 대해 알아보자. 백트래킹은 보통 재귀함수로 풀이된다.

함수를 호출하고 해를 출력할 조건으로 s라는 빈 배열과 m의 값이 같을 때 수와 공백으로 출력하도록 하고

for문을 이용해 모든 방법을 찾아볼 수 있도록 맨 앞의 수를 지정해준다. 수들의 중복 요소를 검사하는 조건문을 작성하고 중복이 아니라면 리스트 s에 그 수를 추가하고 다시 함수를 호출한다. 

재귀함수 부분에서 예를 들어 n=3, m=2일 때

i=1, s = [1] -> [1, 2] -> [1] -> [1, 3]

i=2, s = [2] -> [2, 1] -> [2] -> [2, 3]

i=3, s = [3] -> [3, 1] -> [3] -> [3, 2]

로 출력하고 pop 하며 결과를 계속 출력하게 된다. 1부터 들어가기 때문에 오름차순으로 잘 출력되게 된다. m이 커진다고 해도 방식은 같다 1부터 n까지 수를 하나씩 넣어 놓고 길이가 m이 될 때까지 재귀하는 것이다.

 

아이러니하게 첫 번째 코드가 시간은 더 빠르다는 점을 알 수 있었다. 하지만 백트래킹 알고리즘이 메모리는 적게 소요되었다.

---

코드 1 풀이 결과

15649 풀이 결과

코드 2 풀이 결과

15649 백트래킹 풀이 결과