빈코의 개발일지

오늘은 DFS를 활용하여 입력받은 격자판에서 섬의 개수를 구하는 문제를 풀어보려고 합니다😊 개요 이번 문제의 핵심은 DFS 알고리즘 활용, 8가지 방향으로 이동하는 방법, 섬을 만났을 때 체크, 출발점 체크 총 4가지가 될 것 같네요😀 Setting📙 public class Island { static int result = 0, n; static int[] dx = {-1, -1, 0 ,1 ,1 ,1, 0, -1}; static int[] dy = {0 ,1 ,1 ,1, 0, -1, -1, -1}; public static void main(String[] args) { Island T = new Island(); Scanner sc = new Scanner(System.in); n = sc.nextI..

오늘은 DFS를 활용한 미로 탐색 문제를 풀어보려고 합니다😄 개요 이 문제의 핵심은 DFS 알고리즘 활용과 상하좌우 4방향으로 이동하는 방법이 주가 될 것 같아요. 한번 코드로 풀어볼까요? 📌 사전 지식으로 DFS의 원리와 Stack이 쌓이고 pop 되는 과정을 알아야 합니다. 모르시는 분은 해당 링크를 클릭해서 확인해주세요😀 Setting📙 public class MazeSearch { static int[] dx = {-1, 0, 1, 0}; static int[] dy = {0 ,1, 0, -1}; static int[][] board; static int result = 0; public static void main(String[] args) { MazeSearch T = new MazeSear..

오늘은 탐색 알고리즘인 DFS를 활용하여 합이 같은 부분집합 구하기, 최대 무게 구하기, 최대 점수 구하기 총 3문제를 풀어보려고 합니다. Stack 활용을 모르신다면 이해하시기 어렵기 때문에, 관련 포스팅을 참고해 주세요😊 개요 하단에서 풀어 볼 3개의 문제는 모두 DFS의 부분 집합을 활용하는 문제입니다. 첫 번째, 합이 같은 부분집합 구하기 문제를 잘 이해하시면 나머지 2개의 문제도 비슷한 맥락이기 때문에 이해하기 쉽습니다😊 합이 같은 부분집합 구하기📙 이 문제의 포인트는 마지막 노드까지 갔을 때(부분 집합)의 총합을 구하는 방법과 각각의 부분 집합이 입력된 자연수 집합의 절반과 같은지 체크하는 것입니다. 예시에서 1, 3, 5, 6, 7, 10 집합이 주어졌고, 이 집합의 총합은 32이며 절반 값..

오늘은 지난 포스팅인 DFS & BFS 기초에 이어서 알고리즘을 활용하여 Tree 말단 노드까지의 가장 짧은 경로를 구하는 간단한 문제를 풀어 볼 예정입니다😄 개요 사실 최단 경로를 구하는 문제는 대게 BFS(넓이 우선 탐색)를 이용하여 문제를 풀지만, DFS로도 풀 수 있는 문제가 왕왕 있기 때문에 2가지 문제 풀이법 모두 진행해보려 합니다. 문제는 위 그림처럼 1번 노드에서 시작해 가장 말단 노드까지 가는 최단 경로를 구하는 문제입니다. 여기서 말단 노드는 하위 노드가 없는 노드를 뜻하며 그림에서는 4, 5, 3에 해당하겠네요! 가장 짧은 간선을 구하기 때문에 한 개의 간선만 필요한 3번 노드가 말단 노드로 지정되고, 정답은 간선의 개수이기 때문에 1이 되겠습니다😊 이전 포스팅과 마찬가지로 Node ..

오늘은 Java 알고리즘에서 빼먹을 수 없는 DFS와 BFS에 대해 알아보려고 합니다. DFS는 Depth First Search의 약자로 깊이 우선 탐색을 말하고, BFS는 Breadth First Search의 약자로 너비 우선 탐색을 말합니다. 이 둘은 그래프 자료구조에서 완전 탐색을 수행하는 탐색 기법입니다😊 개요 앞서 말씀드린 그래프를 탐색하기 위한 대표적인 알고리즘 DFS, BFS를 이해하기 위해서는 스택(Stack), 큐(Queue), 재귀(Recursive)를 먼저 알아야 합니다. 스택과 재귀를 모르신다면 링크를 클릭해서 선수 학습을 해주세요😅 재귀 함수와 스택 프레임 코딩 테스트를 준비하면서 완전탐색, DFS, Back tracking 등의 알고리즘 개념을 접하게 되고, 자연스레 스택 프..