Algorithm14 [Algorithm] DFS & BFS 이해하기 DFS : 한 드라마를 몰아서 본다(Stack이나 재귀함수를 사용) BFS : 여러 드라마를 한 편씩 본다.(Queue나 LinkedList를 사용) DFS 또는 BFS로 풀어야 하는 대표적인 유형 1. 경로 탐색 유형(최단거리, 시간) 2. 네트워크 유형(연결) 3. 조합 유형(모든 조합 만들기) DFS가 동작 검증이 쉽다. 하나씩 조합을 만들어서 정답과 비교하기 때문에 조합이 잘 나왔는지 확인이 쉽다. 하지만 수행 시간 관점에서는 복불복 운이 좋으면 첫 번째 조합이 최적의 답, 최악의 경우에는 모든 조합을 다 만들어 보면서 시간을 낭비하게 된다. BFS는 한 번에 여러 조합들을 한 칸 한 칸씩 만들다 보니 조합이 완성되어 정답과 비교하는 시점에 언제 이렇게 만들어졌는지 또는 어디서부터 틀린 건지 분석.. 2022. 11. 26. [Algorithm] Greedy-1 public class Greedy { // 그리디 // 금액 n과 거스름돈 단위 배열 arr이 주어질 때 최소한의 동전 갯수로 거스름돈을 주려고 한다. public static void solution(int n, int[] arr) { int cnt = 0; int val = 0; for (int i = 0; i < arr.length; i++) { cnt += n / arr[i]; n = n % arr[i]; if (n == 0) { System.out.println(cnt + "개의 동전만으로 거스름돈 가능"); break; } } } public static void main(String[] args) { // TODO Auto-generated method stub int n = 1260; i.. 2022. 11. 26. 이전 1 2 3 다음