백트래킹 : M과 N, 순열

점점 조건이 변화하는 순열구하기 문제라고 생각하면 된다

 

15649번 1~N 까지 중복없이 순열고르기 https://www.acmicpc.net/problem/15649

 - 중복되는 수 없이 ->  visited 리스트를 통한 방문 기록

15649번: N과 M (1)

N, M = map(int, input().split())
nums = [x for x in range(1, N+1)]
output = []
visited = [False]*N


def solve(depth, N, M):
    if depth == M:
        print(' '.join(map(str, output)))
        return

    for i in range(N):
        if not visited[i]:
            visited[i] = True
            output.append(nums[i])
            solve(depth+1, N, M)
            output.pop()
            visited[i] = False


solve(0, N, M)

 

15650번 1~N까지, 길이가 M인 중복없는 수열을 오름차순으로 모두 구하기 https://www.acmicpc.net/problem/15650

 - 중복되는 수 없이 -> visited를 통한 방문기록

 - 오름차순 -> sorted함수를 통한 숫자 정렬 (이 문제는 리스트가 주어지지 않고, 1~N 까지를 생성해서 진행 : 정렬됨)

                -> start_index를 활용한 더 큰수 출력

15650번: N과 M (2)

N, M = map(int, input().split())
nums = [x for x in range(1, N+1)]
output = []
visited = [False]*N


def solve(depth, start_index, N, M):
    if depth == M:
        print(' '.join(map(str, output)))
        return

    for i in range(start_index, N):
        if not visited[i]:
            visited[i] = True
            output.append(nums[i])
            solve(depth+1, i, N, M)
            output.pop()
            visited[i] = False


solve(0, 0, N, M)

혹은, 중복을 배제하기 위해서 visited를 별도로 생성하지 않고 (이 전 문제의 코드를 재사용 한 경우 존재)

start_index를 활용해 중복을 배제시키는 방법도 있다. (이 방법은 리스트 내부에 중복되는 수가 없기 때문에 가능하다)

 

N, M = map(int, input().split())
nums = [x for x in range(1, N+1)]
output = []


def solve(depth, start_index, N, M):
    if depth == M:
        print(' '.join(map(str, output)))
        return

    for i in range(start_index, N):
        output.append(nums[i])
        solve(depth+1, i+1, N, M)
        output.pop()


solve(0, 0, N, M)

 

15651번 1~N까지 M개의 수를 고를 수열 https://www.acmicpc.net/problem/15651

 - 중복없음

 - 증가할 필요도 없음

15651번: N과 M (3)

N, M = map(int, input().split())
nums = [x for x in range(1, N+1)]
output = []


def solve(depth, N, M):
    if depth == M:
        print(" ".join(map(str, output)))
        return

    for i in range(N):
        output.append(nums[i])
        solve(depth+1, N, M)
        output.pop()


solve(0, N, M)

그래프 탐색만 하면 된다. 어떻게 보면 제일 단순한 문제

 

15652번  https://www.acmicpc.net/problem/15652

  - 중복 허용

  - 순열은 비내림차순 : 크거나 같은 수가 오른쪽으로 오는 순열 -> start_index를 사용해 반복문을 제한하면 된다.

15652번: N과 M (4)

N, M = map(int, input().split())
nums = [x for x in range(1, N+1)]
output = []


def solve(depth, start_index, N, M):
    if depth == M:
        print(" ".join(map(str, output)))
        return

    for i in range(start_index, N):
        output.append(nums[i])
        solve(depth+1, i,  N, M)
        output.pop()


solve(0, 0, N, M)

 

 

15654번 https://www.acmicpc.net/problem/15654

  - 중복되는 수 금지 -> visited를 통한 방문 기록

  - 증가하는 순서로 출력 -> 입력받은 num list를 정렬한 뒤 진행

15654번: N과 M (5)

import sys
N, M = map(int, input().split())
nums = sorted(list(map(int, sys.stdin.readline().split())))

output = []
visited = [False]*N


def solve(depth, N, M):  # reculsive
    # stop condition
    if depth == M:
        print(' '.join(map(str, output)))
        return

    for i in range(N):
        if not visited[i]:  # 방문기록 점검, 일종의 그래프 탐색
            visited[i] = True
            output.append(nums[i])
            solve(depth+1, N, M)
            output.pop()
            visited[i] = False


solve(0, N, M)

 

15655번 https://www.acmicpc.net/problem/15655

  - 오름차순으로 출력 -> 리스트 정렬, start_index를 통한 반복문 통제

  - 중복되는 수 금지 - > visited 를 통한 방문 점검

15655번: N과 M (6)

N, M = map(int, input().split())
nums = sorted(list(map(int, input().split())))

output = []
visiited = [False]*N


def solve(depth, start_index, n, m):
    if depth == m:
        print(' '.join(map(str, output)))

    for i in range(start_index, n):
        if not visiited[i]:
            visiited[i] = True
            output.append(nums[i])
            solve(depth+1, i, n, m)
            output.pop()
            visiited[i] = False


solve(0, 0, N, M)

 

15656번 https://www.acmicpc.net/problem/15656

  - 같은 수 출력 가능

  - 수열은 증가하는 순서대로 출력 -> 리스트 정렬 후 진행

  - 특별한 조건 없음 -> 그냥 하면 됨

15656번: N과 M (7)

N, M = map(int, input().split())
nums = sorted(list(map(int, input().split())))

output = []


def solve(depth, n, m):
    if depth == m:
        print(' '.join(map(str, output)))
        return

    for i in range(len(nums)):
        output.append(nums[i])
        solve(depth+1, n, m)
        output.pop()


solve(0, N, M)

 

15657번  https://www.acmicpc.net/problem/15657

  - 중복가능

  - 비내림차순 -> start_index를 통한 반복문 통제

15657번: N과 M (8)

N, M = map(int, input().split())
nums = sorted(list(map(int, input().split())))

output = []


def solve(depth, start_point, n, m):
    if depth == m:
        print(' '.join(map(str, output)))
        return

    for i in range(start_point, n):
        output.append(nums[i])
        solve(depth+1, i, n, m)
        output.pop()


solve(0, 0, N, M)

 

15663번 https://www.acmicpc.net/problem/15663

  - 중복되는 수열 통제 -> 숫자 리스트 내에 같은 수가 여러개 나오기 때문에 새로운 아이디어가 필요하다

 

   -> overLap이라는 변수를 추가해서 같은 수는 피하도록 한다

   -> visited 방문 검사는 당연하다

 

  - 증가하는 순서 출력 -> 리스트를 정렬한다.

15663번: N과 M (9)

N, M = map(int, input().split())
nums = sorted(list(map(int, input().split())))

output = []
visited = [False]*N


def solve(depth, n, m):
    if depth == m:
        print(' '.join(map(str, output)))
        return
    overLap = 0
    for i in range(n):
        if not visited[i] and nums[i] != overLap:
            output.append(nums[i])
            visited[i] = True
            overLap = nums[i]
            solve(depth+1, n, m)
            visited[i] = False
            output.pop()


solve(0, N, M)

 

15664번  https://www.acmicpc.net/problem/15664

  - 비내림차순 -> start_index

  - 중복 금지 -> visited

  - 증가하는 수열 -> 리스트 정렬

15664번: N과 M (10)

N, M = map(int, input().split())
nums = sorted(list(map(int, input().split())))

output = []
visited = [False]*N


def solve(depth, start_point, n, m):
    if depth == m:
        print(' '.join(map(str, output)))
        return
    overLap = 0
    for i in range(start_point, n):
        if not visited[i] and nums[i] != overLap:
            output.append(nums[i])
            visited[i] = True
            overLap = nums[i]
            solve(depth+1, i, n, m)
            visited[i] = False
            output.pop()


solve(0, 0, N, M)

 

15665번 https://www.acmicpc.net/problem/15665

  - 숫자 중복 허용

  - 수열들은 증가하는 순서대로 출력 -> 리스트 정렬, 

  - 중복되는 수열 없이 -> overLap 사용

15665번: N과 M (11)

N, M = map(int, input().split())
nums = sorted(list(map(int, input().split())))

output = []


def solve(depth, N, M):
    if depth == M:
        print(' '.join(map(str, output)))
        return
    overlap = 0
    for i in range(N):
        if nums[i] != overlap:
            overlap = nums[i]
            output.append(nums[i])
            solve(depth+1, N, M)
            output.pop()


solve(0, N, M)

 

15666번 https://www.acmicpc.net/problem/15666

  - 수 중복 허용

  - 비 내림차순 ->  start_index

  - 수열 중복 불가능 -> overLap

15666번: N과 M (12)

N, M = map(int, input().split())
nums = sorted(list(map(int, input().split())))

output = []


def solve(depth, start_index, N, M):
    if depth == M:
        print(' '.join(map(str, output)))
        return
    overlap = 0
    for i in range(start_index, N):
        if nums[i] != overlap:
            overlap = nums[i]
            output.append(nums[i])
            solve(depth+1, i, N, M)
            output.pop()


solve(0, 0, N, M)

 

여기까지 총 12문제를 해결하는 방법과 아이디어를 살펴보았다.

 

물론 더 효율적인 코드는 있다. 

하지만 나는 이 12개의 문제가 일맥상통하는 면이 있다는 점을 보여주고 싶었다.

 

끝!