백트래킹(Backtracking)이란 해를 찾는 도중 해가 아니면 되돌아가서 다시 해를 찾아가는 방법을 말한다.
방식에 따라서 깊이우선탐색(Depth-first search, DFS)과 너비우선탐색(Breadth-first search, BFS)으로 나눌 수 있다.
깊이우선탐색(Depth-first search, DFS) jinho-study.tistory.com/865?category=999578
깊이 우선 탐색(depth-first search, DFS) (백준 문제 포함)
깊이 우선 탐색(DFS)은 현재 정점과 인접한 간선들을 하나씩 검사하다가, 아직 방문하지 않은 정점으로 통하는 간선이 있다면 그 간선을 방문하고, 이 과정에서 더 이상 방문할 곳이 없다면, 마
jinho-study.tistory.com
너비우선탐색(Breadth-first search, BFS) jinho-study.tistory.com/866?category=999578
너비 우선 탐색(breadth-first search, BFS) (백준 문제 포함)
너비 우선 탐색(BFS)은 시작 정점을 방문한 후 시작 정점에 인접한 모든 정점들을 먼저 탐색하는 방법이다. 가까운 정점을 전부 저장해놓고 순서대로 방문해야 하기 때문에 스택으로는 구현이
jinho-study.tistory.com
백트래킹 문제로는 대표적인 예시로 여덟 퀸 문제가 있다.
백준 9663번 N-Queen)
def check(n):
for i in range(n):
if row[n] == row[i] or abs(row[n]-row[i]) == n-i:
return 0
return 1
def dfs(n):
global res
if n == N:
res += 1
else:
for i in range(N):
row[n] = i
if check(n):
dfs(n+1)
N = int(input())
row = [0]*N
res = 0
dfs(0)
print(res)
백준 알고리즘 문제 풀이)
백준 알고리즘 9663번 N-Queen(python)
대표적인 브루트포스 알고리즘 & 백트래킹 문제이다. row[n] == row[i] -> 같은 열 확인, abs(row[n]-row[i]) == n-i -> 대각선 확인 def check(n): for i in range(n): if row[n] == row[i] or abs(row[n]-row[..
jinho-study.tistory.com
백준 알고리즘 15649번 N과 M (1)(python)
기본적인 백트래킹 문제이다. def dfs(i): if i == M: print(*li) return ; for n in range(1, N+1): if check[n]: continue check[n] = 1 li[i] = n dfs(i+1) check[n] = 0 N, M = map(int, input().split()) che..
jinho-study.tistory.com
백준 알고리즘 15650번 N과 M (2)(python)
기본적인 백트래킹 문제이다. def dfs(n): if n == M: print(*li) return for i in range(N): if check[i]: continue check[i] = 1 li.append(i+1) dfs(n+1) li.pop() for j in range(i+1, N): check[j] = False N..
jinho-study.tistory.com
백준 알고리즘 15651번 N과 M (3)(python)
기본적인 백트래킹 문제이다. def dfs(n): if n == M: print(*li) return for i in range(N): if check[i]: continue li.append(i+1) dfs(n+1) li.pop() N, M = map(int, input().split()) check = [0]*N li = []..
jinho-study.tistory.com
백준 알고리즘 15652번 N과 M (4)(python)
기본적인 백트래킹 문제이다. def dfs(n): if n == M: print(*li) return for i in range(N): if check[i]: continue li.append(i+1) dfs(n+1) li.pop() check[i] = 1 for j in range(i+1, N): check[j] = 0 N, M..
jinho-study.tistory.com
백준 알고리즘 15654번 N과 M (5)(python)
기본적인 다이나믹 프로그래밍 문제이다. def dfs(n): if n == M: print(*t) return ; for i in range(N): if check[i]: continue t.append(li[i]) check[i] = 1 dfs(n+1) t.pop() check[i] = 0 N, M = map(int, i..
jinho-study.tistory.com
백준 알고리즘 19699번 소-난다!(python)
백트래킹 & 소수 판정(에라토스테네스의 체) 문제이다. 꽤 좋은 퀄리티의 문제인 것 같다. def dfs(depth): if depth == M: s.add(sum(li)) for i in range(N): if check[i]: continue li.append(nums[i]) check[i..
jinho-study.tistory.com
백준 알고리즘 1182번 부분수열의 합(python)
브루트포스 알고리즘 & 백트래킹 문제이다. PyPy3로 제출해야 통과된다. def dfs(depth, k): if depth == k and sum(li) == S: s.append(li) return ; for i in range(N): if check[i]: continue li.append(nums[i..
jinho-study.tistory.com
백준 알고리즘 10819번 차이를 최대로(python)
브루트포스 알고리즘 & 백트래킹 문제이다. def dfs(depth): if depth == N: res.append(sum(abs(li[i+1]-li[i]) for i in range(N-1))) return ; for i in range(N): if check[i]: continue li.append(nums[i]) c..
jinho-study.tistory.com
백준 알고리즘 15655번 N과 M (6)(python)
기본적인 백트래킹 문제이다. def dfs(depth): if depth == M: print(*li) for i in range(N): if check[i]: continue li.append(nums[i]) check[i] = 1 dfs(depth+1) li.pop() for j in range(i+1, N): check[j]..
jinho-study.tistory.com
백준 알고리즘 15656번 N과 M (7)(python)
기본적인 백트래킹 문제이다. def dfs(depth): if depth == M: print(*li) return ; for i in range(N): li.append(nums[i]) dfs(depth+1) li.pop() N, M = map(int, input().split()) nums = sorted(map(int, inp..
jinho-study.tistory.com
백준 알고리즘 15657번 N과 M (8)(python)
기본적인 백트래킹 문제이다. def dfs(depth): if depth == M: print(*li) return ; for i in range(N): if depth == 0 or li[-1] <= nums[i]: li.append(nums[i]) dfs(depth+1) li.pop() N, M = map(int, input()..
jinho-study.tistory.com
백준 알고리즘 18429번 근손실(python)
브루트포스 알고리즘 & 백트래킹 문제이다. 현재 근육량 + 현재 운동 키트 중량 - K가 0 이상일 때만 재귀 함수로 진입하고 depth(운동 일수)가 성공적으로 N이 되었다면 cnt를 올려주면 된다. def dfs(d
jinho-study.tistory.com
백준 알고리즘 19949번 영재의 시험(python)
브루트포스 알고리즘 & 백트래킹 문제이다. depth > 1 and li[depth-2] == li[depth-1] == i(현재 선택한 답과 그 전의 2개의 답이 같음) 조건을 성립하지 않는 답을 추가하고, 정답을 10개 다 선택했다면 점수
jinho-study.tistory.com
백준 알고리즘 15663번 N과 M (9)(python)
기본적인 백트래킹 문제이다. 그냥 리스트를 사용해서 중복인지 아닌지 확인하면 무조건 시간초과가 나와서, 딕셔너리(해시)를 사용해서 풀었다. 해시는 진짜 진짜 진짜 엄청 빠르다!! def dfs(dept
jinho-study.tistory.com
백준 알고리즘 15664번 N과 M (10)(python)
기본적인 백트래킹 문제이다. 15663번 N과 M (9)과 비슷한 문제이다. def dfs(depth): if depth == M: s = ' '.join(map(str, li)) if s not in d: d[s] = 1 print(s) return ; for i in range(N): if check[i]: c..
jinho-study.tistory.com
백준 알고리즘 15665번 N과 M (11)(python)
기본적인 백트래킹 문제이다. 15663번 N과 M (9)와 비슷한 문제이다. def dfs(depth): if depth == M: s = ' '.join(map(str, li)) if s not in d: d[s] = 1 print(s) return ; for i in range(N): li.append(nums..
jinho-study.tistory.com
백준 알고리즘 15666번 N과 M (12)(python)
기본적인 백트래킹 문제이다. 15663번 N과 M (9)와 비슷한 문제이다. def dfs(depth): if depth == M: s = ' '.join(map(str, li)) if s not in d: d[s] = 1 print(s) return ; for i in range(N): if depth == 0..
jinho-study.tistory.com
백준 알고리즘 5568번 카드 놓기(python)
그냥 백트래킹 형식으로 쉽게 풀었다. def dfs(depth): if depth == k: s.add(''.join(map(str, li))) return ; for i in range(n): if check[i]: continue li.append(nums[i]) check[i] = 1 dfs(depth+1) li.pop(..
jinho-study.tistory.com
백준 알고리즘 6603번 로또(python)
단순한 백트래킹 문제이다. def dfs(depth): if depth == 6: print(*li) return ; for i in range(n): if check[i]: continue li.append(nums[i]) check[i] = 1 dfs(depth+1) li.pop() for j in range(i+1, n): ch..
jinho-study.tistory.com
https://jinho-study.tistory.com/1095
백준 알고리즘 14888번 연산자 끼워넣기(python)
브루트포스 알고리즘 & 백트래킹 문제이다. 나누기 처리를 할 때 int(n1 / n2) 또는 -(-n1 / n2) 같은 방식으로 나눠야 하는데, 처음에 이걸 몰라서 계속 틀렸다. def dfs(res, i, add, sub, mul, div): global N..
jinho-study.tistory.com
'Agorithm > 자료구조, 알고리즘 정리' 카테고리의 다른 글
| 다익스트라(Dijkstra) 알고리즘 (백준 문제 포함) (0) | 2021.03.22 |
|---|---|
| 우선순위 큐, 힙(Priority Queue, heap) (백준 문제 포함) (0) | 2021.03.22 |
| 동적 계획법(Dynamic programming) (백준 문제 포함) (0) | 2021.03.17 |
| 너비 우선 탐색(breadth-first search, BFS) (백준 문제 포함) (0) | 2021.03.10 |
| 깊이 우선 탐색(depth-first search, DFS) (백준 문제 포함) (0) | 2021.03.10 |