[백준] 15649. N과 M (1) 파이썬

DFS 재귀로 <순열과 조합> 공부하기.  * 12문제예정

문제집 출처 :: 백준 N과 M https://www.acmicpc.net/workbook/view/2052

 

---

** 수학/알고리즘 용어를 잘못 사용할 수도 있습니다. 댓글 달아주시면 참고하여 빠르게 보완하겠습니다. 

문제출처 https://www.acmicpc.net/problem/15649

 

[백준] 15649. N과 M (1) 파이썬

 

문제

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

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

입력

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

출력

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

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

---

<풀이 PASS>

# 1번. [백준] 15649
# 1~n 중에 m 개 뽑기. 중복 안되게. 순서있음.
[1,2] 와 [2,1] 서로 다른 거라고 본다.
n,m = map(int,input().split())
numbers = [i+1 for i in range(n)] # 1~n까지
is_number = [0 for _ in range(m)] # 출력 개수
check = [False for _ in range(len(numbers))] # 사용여부(씀=True, 안씀= False)
def dfs(idx,next):
    if idx >= m: # 0부터 m출력개수 되면
        print(*is_number)
        return
    for i in range(next,len(numbers)):
        #숫자를 사용 안했다면(OFF인것만 사용가능)
        if not check[i]:
            #나는 i 번째 숫자를 사용 (ON)
            check[i] = True
            #숫자를 배치하겠어
            is_number[idx] = numbers[i]
            # 다음은 알아서 재귀해~
            dfs(idx+1,next)
            #사용다했어 (OFF)
            check[i] = False
dfs(0,0)
 
 

 

<부가설명>

 
   if idx >= m: # 0부터 m출력개수 되면, m=n 이 같다면 순열
        print(*is_number)
 

* 9번째 행의 m = n 만큼이면 순열로

n,m = 3,3

 

* 재귀로 들어갈 때, for문에서 처음부터 끝까지 또 다 보기 때문에 사실 next는 계속 0부터여서

dfs(idx) 만 있어도 된다. 

 

 

<결과 확인>

---

<피드백 > - 2020.03.02

 

셩 : 군더더기 없이 깔끔한 순열 코드 잘 짜셨습니다
꼭 며칠 지난 후에도 백지상태에서 짤 수 있는지 순열, 조합 코드를 짤 수 있는지 테스트해서
완전히 자기 것으로 만드셔야합니다 계속해서 연습을 하다보면 자신만의 순열, 조합 템플릿이 만들어집니다.

 

 

---

---

 

 

<추가 연습> : 1) 주어진 요소들이 서로 다를 때, 순열을 배열로 넣어서 보자  2020.03.03

 

# DFS 서로 다른 값일 때, 순열 
 
numbers = [1,2,3]
is_number = [0 for _ in range(len(numbers))]
check = [False for _ in range(len(numbers))]
 
#사용함 = True
#사용안함 = False
def dfs(idx):
    if idx >= len(numbers):
        arr.append(list(is_number)) # Correct ★★★★★
        brr.append(is_number) # No!!!
        print(is_number) # 각 조합의 경우를 전부 보여주기
        return
    for i in range(len(numbers)):
        #숫자를 사용 안했다면
        if not check[i]:
            #나는 i 번째 숫자를 사용하겠어
            check[i] = True
            #숫자를 배치하겠어
            is_number[idx] = numbers[i]
            #난 잘 모르겠고 니가 알아서 처리해
            dfs(idx+1)
            #사용다했어
            check[i] = False
arr = []
brr = []
dfs(0)
print(arr,"내가 원하는 값")
# [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]
print(brr,"값이 다 똑같다니?!")
# [[3, 2, 1], [3, 2, 1], [3, 2, 1], [3, 2, 1], [3, 2, 1], [3, 2, 1]]
 
 

-참고 틀 : 멍토 스승님

 

 

# 리스트에, 리스트를 append 추가했는데. 
 
a = []
b=[1,1]
c =[]
d=[3,3]
# (1)
a.append(b) # 값만 넘긴게 아니고 주소로 연결됨
print(a)
# 결과 : [[1, 1]]
b[0] = 2 # 넣어줄 값 자체가 하나씩 변경되면
#b[1] = 2 
a.append(b) # 주소 참조라서 *앞에 했던 일도 변형*됨
print(a)
# 결과 : [[2, 1], [2, 1]]
 
# (2)
c.append(list(d)) # 새로 복사한걸 넣음
print(c)
# 결과 : [[3, 3]]
d[0] = 4 # 넣어줄 값 변경
d[1] = 4
c.append(list(d)) # ★새로운 곳에 복사되어 넣음★★★★
print(c)
# 결과 : [[3, 3], [4, 4]] 
 
# (3)
b = d # [4,4] 
a.append(b) # 리스트가 통째로 교체되면 그건 또 별도로 새로 넣어짐
print(a)
# 결과 : [[2, 1], [2, 1], [4, 4]]
 
 

 

주의할 점은 1) 리스트를 append 할 때, '주소 참조'인지와 '리스트 자체를 복제'하여 넣었는지의 차이 같다.

결과값만 보고 한참고민했다.... 문법 배울 때 스쳐 지나갔는데 다시 찾아봐야겠다...ㄷㄷ 기초는 계속 봐도 새롭다.

 

 

 

 

---

 

재귀는 반복문으로 표현 가능하고 , 반복문을 재귀로 표현 가능하다! 

 

상황과 문제의 특성에 따라 취사 선택을 한다는 뜻

"재귀가 만들어진 코드는 보기 쉽고 내가 짜기가 어렵다." 라는 말을 느끼고 있지만 노력 중!

왜냐하면 같은 문제인데 재귀로 짜본걸 오히려 반복문으로 짜려고 구조를 생각해보면 더 어려워서 ㅋㅋㅋ

 

유 : 물론 dfs를 반복문으로 구현한 점은 good! 입니다. dfs보다 반복문으로 구현하는것이 난이도가 더 높기 때문입니다. 그렇지만 반복문으로 구현을 할때 막히게 된다면 고생할 것 같습니다.

꼭 자유자재로 해 볼 날이 오겠지... >///<

 

---

 

<추후 학습 목표> 2020.03.04

순열을 짜는 3가지 템플릿이 존재하며

1. 별도의  used_check 리스트를 만들어 사용 여부를 재귀 앞뒤로 바꿔주기  

2. 자리바꾸기???

3. ???

0. 외부 라이브러리 이용하기(실전용, DFS 재귀 배우고 연습과정에서는 불필요)

 

 

https://blog.fupfin.com/?p=150