개발하는데 다 이유가 있겠지

[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)