백트래킹 문제 및 풀이 (Python)

코테 준비를 위한 알고리즘 공부 순서 

 위 링크에서 백트래킹 알고리즘 문제를 풀고 풀이를 기록하는 게시글입니다. 

 

 

6. 백트래킹

• 해를 찾는 도중에 막히면 더 이상 깊이 들어가지 않고, 이전 단계로 되돌아가서 해를 찾아나가는 기법을 말한다. 최적화 문제와 결정 문제를 푸는 방법이 된다고 한다.
• DFS vs 백트래킹
  -  백트래킹은 해를 찾아가는 도중에 지금의 경로가 해가 될 거 같지 않으면, 더 이상 깊이 들어가지 않고 이전 단계로 다시 돌아간다. 이를 가지치기라고 하는데, 불필요한 부분을 쳐내고 최대한 올바른 방향으로 나아가는 방식이기 때문에 DFS보다 효율적이다. 하지만, N!의 경우의 수를 가진 최악의 문제에서는 여전히 지수함수의 시간복잡도가 걸려서 처리가 불가능할 수도 있다. 따라서, 가지치기를 얼마나 잘하느냐에 따라 효율성이 결정된다.
  - DFS는 가능한 모든 경로(후보)를 탐색한다. 불필요할 거 같은 경로를 사전에 차단하지 않기 때문에 경우의 수를 최적으로 줄이지 못한다. 따라서 N!의 경우의 수를 가지는 문제는 DFS로 처리하지 못할 가능성이 매우 크다.
  - 백트래킹은 모든 가능한 경우의 수 중에서 특정한 조건을 만족하는 경우만 살펴보는 것이다! 즉, 답이 될만한 가능성이 없으면 더 이상 탐색을 진행하지 않고 가지치기를 하면서 최적해를 구하는 것이다.
  - 주로 문제풀이에서는 DFS 등으로 모든 경우의 수를 탐색하는 과정에서, 조건문을 걸어서 답이 절대로 될 수 없는 상황을 정의하고, 그런 상황일 때는 탐색을 중지시킨 뒤 다시 이전 단계로 돌아가서 다른 경우를 탐색하도록 구현할 수 있다
  

설명출처

 

문제

(❌ 표시는 혼자 못푼 문제)

 

2023. 12. 14. 9일차 (3)

1. 15649번 N과 M(1) (실버3)  문제링크

문제 해석

자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.
- 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열

제한: 1초 512MB

 

입력

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

 

출력

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

 

코드

중복 없이 M 개를 골랐고, 중복되는 수열을 여러 번 출력하면 안된다고 했다.

이는 1 2 와 2 1 은 다르다는 것을 의미한다.

순열문제라는 것을 캐치해야한다. 중복없이 M개를 순서 고려해서 뽑는 문제

236ms

arr = []
def dfs(cnt):
    if cnt == M:
        for i in arr:
            print(i, end=" ")
        print()

    for i in range(0, N):
        if not visited[i]:
            visited[i] = True
            arr.append(i+1)
            dfs(cnt+1)
            arr.pop()
            visited[i] = False


N, M = map(int , input().split())

visited = [False] * N
dfs(0)

 

permutations 사용한 코드

백트래킹으로 구현하지는 않았지만 의도적으로 백트래킹을 사용해야하는게 아니면 순열 문제 나올때는 permutations를 쓰도록 하자.

map(" ".join,) 을 사용하기 위해서 리스트의 요소는 문자열이어야한다!

48ms

from itertools import permutations

N, M = map(int, input().split())
print("\n".join(map(" ".join, permutations([str(i+1) for i in range(N)], M))))

2023. 12. 14. 9일차 (4)

2. 15650번 N과 M(2) (실버3)  문제링크

문제 해석

자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.
- 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열
- 고른 수열은 오름차순이어야 한다.

제한: 1초 512MB

 

입력

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

 

출력

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

 

코드

중복없이 M개 , 순서를 고려하지 않고. -> 조합 문제인걸 캐치해야한다.

40ms

arr = []
def dfs(cnt, idx):
    if cnt == M:
        for i in arr:
            print(i+1, end=" ")
        print()

    for i in range(idx, N):
        if not visited[i]:
            visited[i] = True
            arr.append(i)
            dfs(cnt+1, i+1)
            arr.pop()
            visited[i] = False


N, M = map(int , input().split())

visited = [False] * N
dfs(0,0)

 

combinations 를 이용한 코드

44ms

from itertools import combinations

N, M = map(int, input().split())
print("\n".join(map(" ".join, combinations([str(i+1) for i in range(N)], M))))

 

2023. 12. 14. 9일차 (5)

3. 15651번 N과 M(3) (실버3)  문제링크

문제 해석

자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.
-1부터 N까지 자연수 중에서 M개를 고른 수열
-같은 수를 여러 번 골라도 된다.

제한: 2초 512MB

 

입력

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

 

출력

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

 

코드

N개 중에 M개 . 같은 수를 여러번 골라도 되는 것. 중복되는 수열을 여러번 출력하면 안되는 것.

1 2 / 2 1 은 같지 않은 것 -> 즉 순서 고려.

중복 순열이라는 것을 캐치해야한다. (순열 조건에 같은 수를 여러번 골라도 되는 조건이 추가되었다.)

2820ms

arr = []
def dfs(cnt):
    if cnt == M:
        for i in arr:
            print(i, end=" ")
        print()
        return

    for i in range(0, N):
        arr.append(i+1)
        dfs(cnt+1)
        arr.pop()


N, M = map(int , input().split())
dfs(0)

 

product를 이용한 코드

리스트에서 n개를 뽑는 중복 순열을 구하기위해 product([], repeat=n) 형태로 사용한다.  repeat= 써줘야한다.

298ms

from itertools import product

N, M = map(int, input().split())
print("\n".join(map(" ".join, product([str(i+1) for i in range(N)], repeat=M))))

2023. 12. 15. 10일차 (1)

4. 15652번 N과 M(4) (실버3)  문제링크

문제 해석

자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.
- 1부터 N까지 자연수 중에서 M개를 고른 수열
- 같은 수를 여러 번 골라도 된다.
- 고른 수열은 비내림차순이어야 한다.
    - 길이가 K인 수열 A가 A1 ≤ A2 ≤ ... ≤ AK-1 ≤ AK를 만족하면, 비내림차순이라고 한다.

제한: 1초 512MB

 

입력

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

 

출력

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

 

코드

N중에 M개를 고르고, 같은 수를 여러 번 골라도 되고, 순서 상관 없는 것(1 2 / 2 1 을 동일하게보는것) -> 중복 조합이라는 것을 캐치해야한다.

68ms

arr = []
def dfs(cnt, idx):
    if cnt == M:
        for i in arr:
            print(i+1, end=" ")
        print()
        return

    for i in range(idx, N):
        arr.append(i)
        dfs(cnt+1, i)
        arr.pop()


N, M = map(int , input().split())

visited = [False] * N
dfs(0,0)

 

combinations_with_replacement 를 이용한 코드

44ms

from itertools import combinations_with_replacement

N, M = map(int, input().split())
print("\n".join(map(" ".join, combinations_with_replacement([str(i+1) for i in range(N)], M))))

 

추가문제

5. 9663 N-Queen (골드4)  문제링크

 

6. 17136번 색종이 붙이기 (골드2)  문제링크