[백준] 수열 - 재귀함수 구현 정리 (2)

사용 언어 - Python3

문제 -  15654, 15655, 15656번

• 백준 백트래킹 세트로 공부하기
• 15654,15655,15651,15656번
• 15654번 정해진 list 안에서 수열 만들기
• 15655번 정해진 list + 중복 X 시작포인트 지정 수열
• 15656번 정해진 list + 중복 O

15654번: N과 M (5)

 

정답

인프런 코테 강의  '2주만에 통과하는 알고리즘 코딩테스트(2023년)' 복습

재귀함수로 풀어보기

 

1. 15654번 (정해진 list 안에서 수열 만들기)

방문하지 않은 list_n 원소를 한 개씩 방문하기

def recur(number):
    if len(arr) == m:
        print(*arr)
        return
    
    for i in range(n):
        if not visited[i]:
            visited[i] = 1
            arr.append(list_n[i])
            recur(number+1)
            arr.pop()
            visited[i] = 0

n, m = map(int,input().split())
list_n = list(map(int,input().split()))
list_n.sort()

visited = [0 for _ in range(n+1)]
arr = []
recur(0)

https://github.com/yyeongeun/codingtest/blob/main/BAEKJOON/15654_N%EA%B3%BCM5.py

 

 

2. 15655번 (정해진 list, 중복X  시작포인트 지정 수열)

중복X = list_n[i] 가 또 들어가면 안된다.

시작포인트 지정 = for문 number부터 시작, recur(i+1)

def recur(number):
    if len(arr) == m:
        print(*arr)
        return
    
    for i in range(number,n):
        if list_n[i] not in arr:
            arr.append(list_n[i])
            recur(i+1)
            arr.pop()

n, m = map(int,input().split())
list_n = list(map(int,input().split()))
list_n.sort()
arr = []
recur(0)

https://github.com/yyeongeun/codingtest/blob/main/BAEKJOON/15655_N%EA%B3%BCM6.py

 

 

3. 15656번 (정해진 list, 중복O 수열)

recur()

def recur():
    if len(arr) == m:
        print(*arr)
        return
    
    for i in range(n):
        arr.append(list_n[i])
        recur()
        arr.pop()
    
n, m = map(int,input().split())
list_n = list(map(int,input().split()))
list_n.sort()
arr = []
recur()

https://github.com/yyeongeun/codingtest/blob/main/BAEKJOON/15656_N%EA%B3%BCM7.py