본문 바로가기

DFS4

백준_15658_연산자 끼워넣기(2) https://www.acmicpc.net/problem/15658 15658번: 연산자 끼워넣기 (2) N개의 수로 이루어진 수열 A1, A2, ..., AN이 주어진다. 또, 수와 수 사이에 끼워넣을 수 있는 연산자가 주어진다. 연산자는 덧셈(+), 뺄셈(-), 곱셈(×), 나눗셈(÷)으로만 이루어져 있다. 연산자의 개수 www.acmicpc.net 문제요약) N개의 수로 이루어진 수열, 연산자기 주어지는데 연산자의 개수는 N - 1보다 많을 수도 있다. 수와 수 사이에 연산자를 하나씩 넣어서, 수식을 만들 수 있다. 단, 주어진 수의 순서는 바꾸지 못한다. 식의 계산은 연산자 우선 순위를 무시하고 앞에서부터 진행한다. 나눗셈은 정수 나눗셈으로 몫만 취한다. 음수를 양수로 나눌 때는 C++14의 기준.. 2023. 4. 21.
백준_14888_연산자 끼워넣기 https://www.acmicpc.net/problem/14888 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, www.acmicpc.net 문제요약) N개의 수로 이루어진 수열, N-1 개의 연산자(+, -, x, /)가 주어진다. 수와 수 사이에 연산자를 하나씩 넣어서, 수식을 만들 수 있다. 단, 주어진 수의 순서는 바꾸지 못한다. 식의 계산은 연산자 우선 순위를 무시하고 앞에서부터 진행한다. 나눗셈은 정수 나눗셈으로 몫만 취한다. 음수를 양수로 나눌 때는 C++14의 기준에.. 2023. 4. 21.
백트래킹(BackTracking)의 개념과 DFS와의 차이 백트래킹(BackTracking)의 정의 현재 상태에서 가능한 모든 후보군을 따라 들어가며 탐색한다. 해가 아니거나 다시 돌아가서(=back) 최적의 해를 찾는다. 백트래킹의 구현 보통 백트래킹의 구현은 BFS와 DFS와 함께 구현한다. 재귀로 보통 구현되고, 재귀 함수가 호출되고 조건에 맞지 않으면 종료되고 그전에 호출된 재귀로 돌아오므로, 백트래킹에서 말하는 ‘가능성이 없으면 후보를 포기해 정답을 찾아가는’ 방식이다. 안되는 조건은 없애면서 탐색하기 때문에 시간복잡도가 선형적으로 증가할 법한 문제에서 백트래킹을 적용하면 시간복잡도를 줄일 수 있다. 모든 경우의 수에서 한정 조건을 만족하는 경우를 탐색하는 것이기 때문에 완전 탐색 기법인 BFS와 DFS가 모두 구현이 가능하다. 하지만 한정 조건에 부합.. 2023. 4. 11.
그래프(Graph)의 탐색 👉 깊이 우선 탐색(DFS)와 너비 우선 탐색(BFS) 깊이 우선 탐색(DFS, Depth-First Search) 루트 노드(혹은 다른 임의의 노드)에서 시작해서 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법 즉, 넓게(wide) 탐색하기 전에 깊게(deep) 탐색하는 것이다. 모든 노드를 방문 하고자 하는 경우에 이 방법을 선택한다. →너비 우선 탐색보다 좀 더 간단하다. ➕참고 스택(Stack) 자료구조를 이해 해야 힌다. DFS 동작 과정과 구현 [탐색 방법] 탐색 시작 노드를 스택에 삽입하고 방문처리 한다. (재방문 방지를 위함) 스택 최상단 노드에 방문하지 않은 인접노드가 있다면 그 노드를 스택에 넣고 방문처리 한다. 인접노드가 없으면 스택에서 최상단 노드를 꺼낸다. 방문하지 않은 노드가 없을 때 까지 반복한다. [동.. 2023. 4. 11.