Algorithm/DFS&BFS&백트래킹&재귀

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

HANNI하니 2023. 10. 30. 13:45

사용 언어 - Python3

문제 -  15649, 15650, 15651, 15652번

  • 백준 백트래킹 세트로 공부하기
  • 15649,15650,15651,15652번
  • 15649번 중복X 수열
  • 15650번 중복X 시작포인트 지정 수열
  • 15651번 중복O 수열
  • 15652번 중복O 시작포인트 지정 수열

 

  • 15649번 [1 2] [1 3] [1 4] [2 1] [2 3] [2 4] [3 1] [3 2] [3 4] [4 1] [4 2] [4 3]
  • 15650번 [1 2] [1 3] [1 4] [2 3] [2 4] [3 4]
  • 15651번 [1 1] [1 2] [1 3] [1 4] [2 1] [2 2] [2 3] [2 4] [3 1] [3 2] [3 3] [3 4] [4 1] [4 2] [4 3] [4 4]
  • 16652번 [1 1] [1 2] [1 3] [1 4] [2 2] [2 3] [2 4] [3 3] [3 4] [4 4]
 

15649번: N과 M (1)

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

www.acmicpc.net

 

 

정답

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

재귀함수로 풀어보기

 

1. 15649번 (중복X 수열)

[1 2] [1 3] [1 4] [2 1] [2 3] [2 4] [3 1] [3 2] [3 4] [4 1] [4 2] [4 3]

arr 리스트에 방문하지 않은 i를 추가해준다.

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

arr = []
n, m = map(int,input().split())
visited = [0 for _ in range(n+1)]
recur(1)

 

2. 15650번 (중복X  시작포인트 지정 수열)

[1 2] [1 3] [1 4] [2 3] [2 4] [3 4]

arr 리스트에 있지 않은 i를 추가해준다.

for문의 시작 위치 = number ( number보다 큰 숫자부터 들어갈 수 있다 )

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

arr = []
n, m = map(int,input().split())
recur(1)

 

3. 15651번 (중복O 수열)

[1 1] [1 2] [1 3] [1 4] [2 1] [2 2] [2 3] [2 4] [3 1] [3 2] [3 3] [3 4] [4 1] [4 2] [4 3] [4 4]

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

n, m = map(int,input().split())
arr = []
recur()

 

 

4. 15652번 (중복O 시작포인트 지정 수열)

[1 1] [1 2] [1 3] [1 4] [2 2] [2 3] [2 4] [3 3] [3 4] [4 4]

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

n ,m = map(int,input().split())
arr = []
recur(1)