[Silver III] N과 M (1) - 15649

문제 링크

성능 요약

메모리: 35556 KB, 시간: 112 ms

분류

백트래킹

제출 일자

2024년 2월 22일 12:57:58

문제 설명

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

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

입력

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

출력

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

수열은 사전 순으로 증가하는 순서로 출력해야 한다.

# 순열 import
from itertools import permutations
import sys
input = sys.stdin.readline


def solution():
    N, M = map(int, input().split())
    # 1 ~ N+1에서 M개씩 순열 생성하기
    num_list = list(permutations(range(1, N+1), M))

	for answer in num_list:
        print(*answer)

solution()

순열(Permutations)

순열이란?

순열이란 몇 개를 골라 순서를 고려해 나열한 경우의 수. 서로 다른 n개 중 r개를 골라 순서를 정해 나열하는 가짓수(nPr)

특징

중복을 허용하지 않음
뽑힌 순서대로 나열하기 때문에 순서가 있음(같은 값이 뽑히더라도 순서가 다르면 다른 경우의 수)
permutaions(반복 가능한 객체, 선택 수)
조합(Combinations)와는 차이는 '순서 고려 여부'(순서가 달라도 같은 경우의 수 취급)

백트래킹(Back Tracking)

백트래킹이란?

백트래킹이란 현재 상태에서 가능한 모든 경로를 따라 들어가 탐색하다, 원하는 값과 불일치하는 부분이 발생하면 더 이상 탐색을 진행하지 않고 전 단계로 돌아가는 알고리즘

재귀적으로 문제를 하나씩 풀어가면서 현재 재귀를 통해 확인 중인 노드(상태)가 제한된 조건에 위배되는지 판단하고, 만약 해당 노드가 제한된 조건을 위배한다면 그 노드를 제외하고 다음 단계로 나아가는 방식

더 이상 탐색할 필요가 없는 상태를 제외하는 것을 가지치기(pruning)라고 함

DFS를 통해 모든 노드를 깊이 우선 탐색을 하면서 더 이상 필요가 없는 부분을 쳐내는 행위

경우의 수 : N! - 조건위배 노드
유망한 경우(promising) / 유망하지 않은 경우(pruning)