[백준] 15649번 N과 M (1) - Python

백준 실버3 15649번 N과 M (1) - Python

https://www.acmicpc.net/problem/15649

15649번: N과 M (1)

---

코드

방법1. 백트래킹

맞았습니다가 뜬 코드입니다. - 메모리 31256KB | 시간 140ms | 코드 길이 393B

import sys
input = sys.stdin.readline
N, M = map(int, input().rstrip().split())
ans = list()
visited = [False] * (N+1)
def back():
    if len(ans) == M:
        print(' '.join(map(str, ans)))
        return
    for i in range(1, N+1):
        if visited[i]:
            continue
        visited[i] = True
        ans.append(i)
        back()
        ans.pop()
        visited[i] = False
back()

백트래킹을 이용한 코드입니다.

 

백트래킹이란 DFS와 비슷한 개념입니다.

 

DFS(깊이 우선 탐색)는 완전탐색을 기본으로 하기 때문에 순회가능한 모든 경로를 탐색합니다.

때문에 불필요한 경로를 사전에 차단하지 않습니다.

 

반면 백트래킹은 순회하다가 어떤 노드가 해가 될 만한지, 즉 유망성(promising)을 판단하여 이전 노드인 부모노드로 돌아갑니다. 이를 가지치기(pruning) 이라고 합니다.

 

---

방법 2. itertools 의 permutations(순열) 함수 이용

메모리 31256KB | 시간 204ms | 코드 길이 195B

import itertools
n, m = map(int, input().split())
nums = [i for i in range(1, n+1)]
array = itertools.permutations(nums, m)
for i in array:
    for j in i:
        print(j, end = ' ')
    print()

---

Search🔍

• https://velog.io/@yusuk6185/%EB%B0%B1%EC%A4%80-15649-N%EA%B3%BC-M-1-%ED%8C%8C%EC%9D%B4%EC%8D%AC-with-%EB%B0%B1%ED%8A%B8%EB%9E%98%ED%82%B9

---

후기

엄마랑 산책가다가 미용실 열었길래 가서 잘랐는데..

 

망했네용. ㅋㅋ.

 

구렛나루 꽤 열심히 길렀는데.... 한 순간에..

 

난 분명 구렛나루 있는 숏컷 사진을 보여드렸는데... 왜......................................