개발하는 동그리

문제 풀이 설명 (summary)각 도둑 A,B 가 각각 흔적 누적 개수 이상이 되면 실패한다. A 도둑이 남긴 흔적의 누적개수의 최솟값을 리턴해야 하므로 깊이 우선 탐색을 활용하여 도달했을 때 A도둑의 누적 개수를 기록 하여, 기존값과 비교해서 작은값을 저장해서 관리초기값 그대로라면 -1 출력 문제 풀이 접근법DFS 방식 가능DP 방식 가능 풀이 코드 (Code)import java.util.ArrayDeque;public class Main { public static void main(String[] args) { int[][] info = new int[][]{{1,2},{2,3},{2,1}}; int n = 4; int m = 4; Syst..

문제 풀이 설명 (summary)짝수인 경우 무조건 나누기홀수인 경우 -1 이동0이 될 때까지 반복 문제 풀이 접근법그리디 알고리즘(Greedy Algorithm)모든 상황에 순간이동이 무조건 우선적으로 실행하면 됨.현재 상황에 최적화 된 풀이로 진행 풀이 코드 (Code)public class Main { public static void main(String[] args) { int N = 6; System.out.println(solution(N)); } private static int solution(int s) { int ans = 0; while (s > 0) { if (s % 2 == 0) { ..

Deque / BFS / DFS 정리BFS (queue) -> add / poll : 먼저 들어온 데이터가 먼저 나가는 구조- FIFO (First In, First Out)- 삽입 (add): 데이터를 **뒤쪽(Rear)**에 추가.- 삭제 (poll): 데이터를 **앞쪽(Front)**에서 제거.DFS (stack) -> push / pop : 나중에 들어온 데이터가 먼저 나가는 구조- LIFO (Last In, First Out)- 삽입 (Push): 데이터를 **위쪽(Top)**에 추가.- 삭제 (Pop): 데이터를 **위쪽(Top)**에서 제거.-> BFS : Queue : 너비 우선 (Breadth) : 가까운 정점부터 탐색.-> DFS : Stack : 깊이 우선 (Depth) : 최대한 깊..

주제대표적인 알고리즘 기법(DP vs 다익스트라 vs 완전탐색) 구분하기 ✅ 알고리즘 세 가지 분류분류대표 기법주로 사용하는 상황완전탐색 (Brute Force)백트래킹, DFS, BFS가능한 모든 경우를 직접 탐색해야 할 때 (최대값, 조합 등)동적 계획법 (DP)Memoization, Tabulation중복된 하위 문제가 있고, 최적해를 저장하여 재활용 가능할 때다익스트라 (Dijkstra)우선순위 큐 기반 최단 경로가중치가 있는 그래프에서 최소 거리, 최소 비용 계산 시 ✅  각 기법의 특징 비교항목완전탐색동적 계획법 (DP)다익스트라시간 효율성가장 낮음 (보통 O(2ⁿ), O(n!))중간 (O(N²) ~ O(N×M))높음 (O(E log V))공간 효율성낮거나 중간중간 (DP 테이블 필요)중간 (..

문제 풀이 설명 (summary)전체 모양을 2차 배열모양으로 변경삼각형 모양이 있는 위치를 좌표로 변환홀수, 짝수에 따라 나올 수 있는 경우의 수 구분(DP) 각 인덱스에 나올 수 있는 경우의 수를 누적 마지막 인덱스를 출력 (모든 누적 결과 합) 문제 풀이 접근법정형화된 그리드 경로 문제는 BFS보다 DP가 훨씬 효율적입니다.BFS는 주로 최단거리 혹은 가중치가 있는 경로 탐색에 적합합니다.현재 문제에서는 단순 경로 수 계산 문제이기 때문에, DP 방식이 시간적으로 훨씬 효율적인 것입니다. 풀이 코드 (Code)import java.util.Arrays;public class Main { public static void main(String[] args) { int n = 4; ..

문제 풀이 설명 (summary)완전 탐색을 하려고 생각할 수도 있으나, 경우의 수가 너무 커져 시간초과로 실패할 수 있다.그래서, DP를 활용해서 좌표마다 누적해서 원하는 목적지의 좌표 값을 구한다.또한 (오른쪽, 아래)로만 이동하기 때문에 최단거리로 가는건 고려하지 않아도 된다.목적지에 도착하는 거리는 도착하면 모두 동일하다.  문제 풀이 접근법정형화된 그리드 경로 문제는 BFS보다 DP가 훨씬 효율적입니다.BFS는 주로 최단거리 혹은 가중치가 있는 경로 탐색에 적합합니다.현재 문제에서는 단순 경로 수 계산 문제이기 때문에, DP 방식이 시간적으로 훨씬 효율적인 것입니다. 풀이 코드 (Code)import java.util.ArrayDeque;public class Main { public st..

문제 풀이 설명 (summary)DP (동적 계획법, Dynamic Programming), Bottom-Up 활용피보나치 수열 풀이처럼 접근 문제 풀이 접근법가중치가 있는지 확인 풀이 코드 (Code)import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.*;public class Main { static int testCase; static int destination; static int[] P; static List shortcuts = new ArrayList(); public static void main(String[] args) ..

문제 풀이 설명 (summary)Node 클래스를 만들어서 index 를 변수로 사용하여 Deque 로 활용또는 우선순위 큐를 사용 문제 풀이 접근법최단거리를 찾아야 하기 때문에 BFS로 접근우선 순위 큐와 같이 자동정렬 함으로써 index 가 낮은걸 먼저 처리하도록 처리Deque 활용 또는 우선순위큐 사용 풀이 코드 (Code)import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.ArrayDeque;import java.util.Deque;import java.util.PriorityQueue;import java.util.StringTokenizer;public c..

문제 풀이 설명 (summary)Node 클래스를 만들어서 index 를 변수로 사용하여 Deque 로 활용또는 우선순위 큐를 사용 문제 풀이 접근법최단거리를 찾아야 하기 때문에 BFS로 접근우선 순위 큐와 같이 자동정렬 함으로써 index 가 낮은걸 먼저 처리하도록 처리Deque 활용 또는 우선순위큐 사용 풀이 코드 (Code)import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.ArrayDeque;import java.util.Deque;import java.util.PriorityQueue;import java.util.StringTokenizer;public c..

문제 풀이 설명 (summary)2차 배열에 주어진 조건으로 맵 구성방향에 따라 queue 에 추가하고 방문한 위치는 방문 여부 체크안전 영역의 개수를 구하는 문제 모든 위치에서 시작해서 종료될 때마다 카운트최종 카운트 출력 문제 풀이 접근법너비우선 탐색 (BFS) 삽입 (add) / 삭제 (poll) : 먼저 들어온 데이터가 먼저 나가는 구조FIFO (First In, First Out) 풀이 코드 (Code)public class Main { static boolean[][] visited; static int size; static int[][] map; static int[] dx = {-1, 0, 1, 0}; static int[] dy = {0, 1, 0, -1}; ..