개발하는 동그리

[알고리즘] BFS(queue) vs DFS (stack)

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}; ..

문제친구네트워크 체감 난이도골드1 문제 풀이 소감매번 테스트 케이스마다 네트워크 활성화 된 친구를 어떻게 계산할지 (key)- 각 노드별로 크기를 key를 이용해 저장해놓고 union 합산할 때 key도 더해줌숫자가 아닌 문자열을 어떻게 배열로 관리할 지 (key)- hashMap을 통해 문자열마다 value (-parent key) 값을 할당해서 필요할 때 꺼내씀 코드public class Main { static int[] parents; static int[] sizes; // 각 집합의 크기 static HashMap nameMap; public static void main(String[] args) throws IOException { BufferedReade..

기법알고리즘 기법 [유니온파인드] (Union-Find) 체감 난이도골드 3 설명유니온-파인드(또는 Disjoint-Set)는 서로소 집합(Disjoint Sets)을 효율적으로 관리하는 자료 구조로, 주로 그래프에서 연결성 문제를 해결하는 데 사용됩니다. 이 기법은 다음 두 가지 핵심 연산을 기반으로 작동합니다:Find (루트 찾기): 원소가 속한 집합(트리)의 대표자(루트 노드)를 찾습니다.경로 압축(Path Compression)을 통해 트리의 깊이를 줄여 이후 연산을 더 빠르게 수행할 수 있도록 최적화합니다.Union (집합 병합): 두 집합을 하나로 병합합니다.크기(Size Union) 또는 랭크(Rank Union)를 기준으로 병합하여 트리의 깊이를 최소화합니다.-- 정리 --각각의 리스트에서..