[Python] 15652 N과 M(4)

2022. 6. 10. 16:20· Algorithm/Recursion & Backtracking
목차
  1. A. 접근
  2. B. 코드 분석
  3. 전체 코드
  4. B-1. 준비
  5. B-2. 풀이
  • 문제
  • 입력
  • 출력
  • 문제 풀이
    • A. 접근

문제

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

  • 1부터 N까지 자연수 중에서 M개를 고른 수열
  • 같은 수를 여러 번 골라도 된다.
  • 고른 수열은 비내림차순이어야 한다.
    • 길이가 K인 수열 A가 A1 ≤ A2 ≤ ... ≤ AK-1 ≤ AK를 만족하면, 비내림차순이라고 한다.

입력

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

출력

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

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

문제 풀이

A. 접근

백트래킹을 통해 수열을 구하는 문제. 백트래킹이 조금 약해서 N과 M 문제를 다 풀어보고자 한다.

더보기

N과 M 문제에서 백트래킹은 재귀 구조를 사용하며 해를 찾아간다. DFS와 연관이 있다. 트리에서 깊이 먼저 탐색하는 것과 유사하다.
여기서 N과 M의 포인트는 비내림차순이며 중복을 허용한다는 점이다.

보통 백트래킹으로 수열을 찾거나 순서를 찾는 문제에서는 이러한 구조가 종종 쓰인다.

ans.append(num[i])
backtracking(n + 1)
ans.pop()

더보기

이렇게 깊게 먼저 탐색한 후에 부모 노드로 다시 간 다음 다른 노드로 가는 그런 구조이다.

미로를 탐색한다고 할 때, 갈림길에서 왼쪽으로 갔다가 길이 막히면 다시 나와서 오른쪽 길로 다시 가는 그런 느낌이다.

중복을 허용하지 않는다면 방문 테이블을 만들어두는 것이 좋다. 그런데 이것은 중복을 허용하기 때문에 따로 방문테이블을 만들지 않았고, 비내림차순이기 때문에 정렬을 해주어 문제를 풀었다.

B. 코드 분석

전체 코드

n, m = map(int, input().split())

arr = [i for i in range(1, n + 1)]

ans = []

def solve(idx, cnt):
    if cnt == m:
        print(*ans)
        return

    for i in range(idx, n):
        ans.append(arr[i])
        solve(i, cnt + 1)
        ans.pop()

solve(0, 0)

B-1. 준비

n, m = map(int, input().split())

arr = [i for i in range(1, n + 1)]

ans = []

수를 입력 받아 배열을 만들어주고, 출력 때 사용할 리스트로 ans를 만들었다.

B-2. 풀이

def solve(idx, cnt):
    if cnt == m:
        print(*ans)
        return

    for i in range(idx, n):
        ans.append(arr[i])
        solve(i, cnt + 1)
        ans.pop()

solve(0, 0)

cnt는 수열의 길이이다. 수열의 길이가 문제의 조건을 만족하면 Unpacking을 통해 출력한다.

    for i in range(idx, n):
        ans.append(arr[i])
        solve(i, cnt + 1)
        ans.pop()

for 반복문에서 range의 인자로 idx를 설정하였다. 이후 다시 idx 자리에 i를 삽입했다. 이것은 비내림차순을 위해 설정했다. 이렇게 하여 idx 이전은 고려하지 않고 같거나 큰 값만 수열에 추가되게 된다.

총평

백트래킹은 항상 발목을 잡았었는데 슬슬 잘 풀린다.

 

'Algorithm > Recursion & Backtracking' 카테고리의 다른 글

[Python] 15663 N과 M(9)  (0) 2022.06.11
[Python] 15657 N과 M(8)  (0) 2022.06.10
[Python] 15656 N과 M(7)  (0) 2022.06.10
[Python] 15655 N과 M(6)  (0) 2022.06.10
[Python] 15654 N과 M(5)  (0) 2022.06.10
  1. A. 접근
  2. B. 코드 분석
  3. 전체 코드
  4. B-1. 준비
  5. B-2. 풀이
'Algorithm/Recursion & Backtracking' 카테고리의 다른 글
  • [Python] 15657 N과 M(8)
  • [Python] 15656 N과 M(7)
  • [Python] 15655 N과 M(6)
  • [Python] 15654 N과 M(5)
턴태
턴태
import { Dream } from "future";
턴태
턴태의 밑바닥부터 시작하는 de-vlog
턴태
전체
오늘
어제
  • ROOT (187)
    • Node.js (37)
      • ES6 (1)
      • TypeScript (3)
      • Express.js (16)
      • NestJS (16)
      • JS (24)
    • 프론트엔드 (29)
      • CS (5)
    • 백엔드 (1)
      • 검색 (2)
      • Database (1)
    • 기타 툴 (1)
      • git (1)
    • 데브옵스 & 인프라 (19)
      • Kubernetes (15)
      • Docker (2)
      • Monitoring (1)
      • IaC (1)
    • Algorithm (90)
      • Implementation & simulation (5)
      • Math (4)
      • Brute Force (1)
      • String (0)
      • Graph (5)
      • Recursion & Backtracking (19)
      • Divide & Conquer (2)
      • Dynamic Programming (18)
      • Greedy (13)
      • Priority Queue (2)
      • Binary Search (6)
      • Data Structure (7)
      • Shortest Path (5)
      • Minimum Spanning Tree (1)
      • Sorting (1)
      • Prefix Sum (1)
    • Linux (1)
      • Ubuntu (1)
    • Diary (5)
      • Algorithm (1)
      • Conference (1)
      • Retrospective (3)
    • Book (0)
      • Self-Development (0)

블로그 메뉴

  • 홈
  • 태그
  • 방명록

공지사항

인기 글

태그

  • GREEDY
  • 백트래킹
  • 오먹
  • 함수형 프로그래밍
  • 인프런
  • Omuk
  • k8s
  • 네스트
  • 익스프레스
  • 백준
  • 디프만
  • Toy Project
  • 타입스크립트
  • dynamic programming
  • python
  • node.js
  • Express
  • 쿠버네티스
  • nestjs
  • 인프런X디프만
  • backtracking
  • 노드
  • 토이프로젝트
  • baekjoon
  • 파이썬
  • 자바스크립트
  • 다이나믹 프로그래밍
  • TypeScript
  • N과 M
  • Kubernetes

최근 댓글

최근 글

hELLO · Designed By 정상우.v4.2.1
턴태
[Python] 15652 N과 M(4)
상단으로

티스토리툴바

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.