난이도

Silver 3

풀이 참고 유무

x

막힌 부분

x

문제

문제 바로가기

자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.

1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열

입력

첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)

출력

한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.
수열은 사전 순으로 증가하는 순서로 출력해야 한다.

예제 입력

4 2

예제 출력

1 2
1 3
1 4
2 1
2 3
2 4
3 1
3 2
3 4
4 1
4 2
4 3

문제 검토

백트랙킹을 사용하는 문제이다.
깊이가 깊어질 수록 더 많은 조건에서 문제를 탐색해야한다는 점에서 백트랙킹을 사용해야한다.

풀이(python)

Python

import sys
input=sys.stdin.readline
c=list()
n,m=map(int,input().split())
def dfs(depth): 
    global n,m    
    for x in range(1,n+1):
        if x not in c:
            c.append(x)
            #깊이에 도달하면 
            if depth==m:
                print(' '.join(map(str,c)))            
            #아직 깊이가 아니라면 재귀
            else:
                dfs(depth+1)
            #이걸 실행할 때 쯤이면 깊이에 도달한 직후거나 return하면서 조건을 회수하는 중임
            c.remove(x)                
dfs(1)   

#아이디어
#for문을 n만큼반복 해당 수를 list에 넣고 다음 수가 list에 있는지 확인 후 없으면 list에 add, 만약 다 깊이에 도달한다면 사용한 요소를 삭제하면서 return

#시간 복잡도
#백트랙킹은 중복이 가능할 때는 O(n^n)(n=8 까지 가능함), 중복이 불가능할 때는 O(n!)(n=10까지 가능함)의 수행시간을 갖는다.
#이 문제에서는 선택하면서 올라온 숫자들을 그 뒤에서는 선택하지 못하는 순열이므로 O(n!)의 시간복잡도를 갖게되고
#연산횟수는 대략 8!=40,320 정도로 보인다.
#n의범위가 작기 때문에 아무 문제없이 해결될 것으로 보임

자료구조
#set은 탐색할 때 O(1)의 시간이 있어서 리스트보다 효율적이지만 순서가 상관없다는 점에서 출력에 문제가 생길 수 있다.abs
#이 문제는 list로 풀어도 시간복잡도에서 아무 문제가 없기 때문에 list로 풀겠다.
import sys

Python - 방문체크로 시간 줄이기

import sys
input=sys.stdin.readline
c=list()
n,m=map(int,input().split())
visited=[0 for _ in range(n+1)]
def dfs(depth): 
    global n,m    
    for x in range(1,n+1):
        if visited[x]==0:
            c.append(x)
            #방문체크
            visited[x]=1
            #깊이에 도달하면 
            if depth==m:
                print(' '.join(map(str,c)))                
            #아직 깊이가 아니라면 재귀
            else:
                dfs(depth+1)
            #이걸 실행할 때 쯤이면 깊이에 도달한 직후거나 return하면서 조건을 회수하는 중임
            c.remove(x)#pop을 사용해도 상관 없음                
            #방문해제
            visited[x]=0
dfs(1)    

위처럼 list를 in으로 O(n)에 시간을 사용하지 않고 방문체크로 O(1)의 시간복잡도를 사용하여 문제를 해결할 수 있다.

이렇게 되면 아래처럼 시간 차이가 많이 나는 것을 볼 수 있다.
(밑 - 방문체크 x, 위 - 방문체크 o)

걸린 시간

14:55 - 첫 풀이 기준

총평

백트랙킹은 n의 범위가 매우 작다.
재귀할 떄 종료시점을 잘 정하고 사용한 자료구조는 romve나 pop을 통해 재활용하도록 하자.