💻 백준 15650: N과 M (2)

문제 소개 🧐

자연수 N과 M이 주어졌을 때, 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열을 모두 구하는 문제입니다. 단, 고른 수열은 오름차순이어야 합니다.

입력 📝

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

출력 📤

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

제한 ❌

  • 시간: 1초
  • 메모리: 512MB

첫 번째 시도: itertools.combinations 활용 👊

Idea

파이썬의 itertools 라이브러리에 있는 combinations 함수를 사용하면, 주어진 리스트에서 원하는 개수만큼의 모든 조합을 쉽게 얻을 수 있다. 이를 활용하여 1부터 N까지의 숫자 중 M개를 뽑는 모든 조합을 구하고, 각 조합을 출력하면 문제를 해결할 수 있다.

Code

from itertools import combinations
import sys

n, m = map(int, sys.stdin.readline().split())

# 1부터 n까지의 숫자 리스트 생성
nums = range(1, n + 1)

# combinations를 사용하여 모든 조합 생성
li = list(combinations(nums, m))

# 각 조합을 형식에 맞게 출력
for num in li:
    print(*num)

Result

  • 성공! combinations 함수는 내부적으로 효율적인 알고리즘으로 구현되어 있어, 이 문제의 제약 조건 내에서 충분히 빠르게 동작하는 듯

추가 학습: itertools의 시간 복잡도 📚

  • product() (중복 순열): O(r * n^r)
  • permutations() (순열): O(n!)
  • combinations() (조합): O(nCr)
  • combinations_with_replacement() (중복 조합): O(nHr)

combinations는 조합(Combination)을 계산하며, 시간 복잡도는 n개 중 r개를 선택하는 경우의 수에 비례한다. 이 문제처럼 N과 M이 작은 경우에는 매우 효율적이다.

개선할 부분 🤔

  • 만약 itertools를 사용하지 않고 직접 구현해야 한다면, 백트래킹(Backtracking) 알고리즘을 사용하여 재귀적으로 조합을 생성하는 방법을 고려해볼 수 있을 것 같다