본문 바로가기

알고리즘22

깊이 우선 탐색(dfs) dfs 대해 알아보기 전에 그래프에 대한 기초가 필요하다. https://hongcode.tistory.com/32https://hongcode.tistory.com/32를 참고 하자. 깊이 우선 탐색(dfs) DFS(Depth First Search) 이름 뜻 그대로 루트 노드나 임의의 노드에서 시작하여 최대로 진입할 수 있는 깊이까지 탐색하고 다시 돌아와 다른 노드로 같은 방식으로 탐색하는 방법을 말한다. 장점 최선의 경우, 가장 빠른 알고리즘이다. 운이 좋게 항상 해에 도달하는 올바를 경로를 선택하다면, dfs가 최소 실행시간에 해를 찾는다. bfs에 비해 저장공간의 필요성이 적다. 백트레킹을 해야 하는 노드들만 저장해주면 된다. 단점 찾은 해가 최적이 아닐 가능성이 있다.(알고리즘은 항상 최악의경.. 2022. 3. 11.
분할정복(Divide and Conquer) 분할 정복 알고리즘은 말 그대로 분할하고 정복하는 알고리즘이다. 먼저 문제를 나눌 수 없을 때까지 나누어 각각을 풀고 다시 합병하여 문제의 답을 얻는다. 어떻게 푸는가? Divide : 문제가 분할이 가능한 경우 두 개 이상의 문제로 나눈다. (가장 중요!!!) Conquer : 나눠진 문제가 여전히 분할이 가능하면, 또 Divide를 수행하고, 그렇지 않으면 문제를 푼다. 문제의 크기를 최대로 줄이게 되면 바로 답을 구할 수준이 됨, 이게 재귀 함수를 이용해서 문제를 풀 때의 기저 사례와 같음, 그래서 분할 정복은 재귀 호출과 궁합이 잘 맞음 Combine : Conquer 한 문제들을 통합해서 원래 문제의 답을 얻는다. 위 그래프가 분할정복 알고리즘의 대략적인 모습이다. 가장 많이 볼 수 있는 문제인.. 2022. 3. 11.
BOJ 11047 동전 0 문제 링크 : https://www.acmicpc.net/problem/11047 11047번: 동전 0 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수) www.acmicpc.net 요약 N 개의 종류의 동전이 있고 각 동전은 무수히 많다. 동전을 조합해서 가치의 합을 K로 만들려고 할 때 필요한 동전의 최소 개수를 구하는 문제이다. 풀이 첫 번째 예제 입력값을 보자 1, 5, 10, 50, 100, 500, 1000, 5000, 10000, 50000의 가치를 가진 동전들로 4200원을 만들어야 .. 2022. 3. 10.
BOJ 15748 Rest Stops 문제 링크 : https://www.acmicpc.net/problem/15748 15748번: Rest Stops The first line of input contains four integers: $L$, $N$, $r_F$, and $r_B$. The next $N$ lines describe the rest stops. For each $i$ between $1$ and $N$, the $i+1$-st line contains two integers $x_i$ and $c_i$, describing the position of the $i$-th rest st www.acmicpc.net 요약 으.. 영어 문제 간단하게 해석해보자면 Farmer John과 Bessie가 등산을 한다, Jhon과 .. 2022. 3. 10.

티스토리툴바