본문 바로가기

자바 자료구조 알고리즘/DFS & BFS

 (5)
코딩 테스트 Java BFS 활용 문제 풀기 개요 목적 Java BFS 기초 이해와 문제 풀이 해당 글에서는 재귀함수와 BFS기초를 알아보았다. 이번 시간에는 BFS 활용 문제를 풀면서 BFS 문제 풀이 실력을 늘려보자. 동전 교환 3 1 2 5 15 풀이 최소 개수를 구하는 문제이기 때문에, BFS를 사용하는 것이 유리하다. DFS의 경우, 1,2,5로 시작할 때, 1+1+1+1+1 1에서 1을 더하는 모든 경우의 수를 구한 후에, 값이 나오지 않으면, 2로 넘어가고 5로 넘어간다. 반면에, BFS는 L=1인경우 동전을 하나 사용했을 경우 합을 구한 후에 답이 없다면, L=2 동전 두개 사용한 경우 합을 구하는 방식으로 메소드가 진행된다. 그래서 동전을 3개 사용했을 때, 5+5+5를 구하는 경우의 수를 빠르게 찾을 수 있다. import jav..
코딩 테스트 Java DFS 활용 문제 풀기 개요 목적 Java DFS 기초 이해와 문제 풀이 해당 글에서는 재귀함수와 DFS 기초를 알아보았다. 이번 시간에는 DFS 활용 문제를 풀면서 DFS 문제 풀이 실력을 늘려보자. 합이 같은 부분집합(DFS : 아마존 인터뷰) 6 1 3 5 6 7 10 풀이1. ch 배열( 해당 숫자 포함될 때, 안될 때 - 사용) import java.util.*; class Main { static int n; static int[] arr; static int[] ch; static int half; static boolean result; public void DFS(int v) { if (v == n+1) { System.out.println(Arrays.toString(ch)); int sum = 0; for ..
Java 그래프 문제 -인접 행렬, 인접 리스트 ,DFS, BFS 개요 목적 이번 시간에는 코딩 테스트 그래프 문제를 풀기 위한 그래프 인접 행렬 인접 리스트 표현 문제 풀이 방식에 대해서 알아본다. DFS, BFS 방식의 그래프 문제들을 풀어보면서 심화 그래프 문제 풀이 방법도 알아보자. 그래프와 인접 행렬 무방향 그래프, 방향 그래프, 가중치 방향 그래프를 컴퓨터가 이해할 수 있는 인접 행렬로 표현을 해보자. 1. 무방향 그래프 무방향 그래프는 양방향 그래프라고도 한다. 해당 그래프가 이루어진 노드와 엣지(간선)의 숫자 집합을 나열해보면, 1 2 1 3 2 4 2 5 3 4 3 1 4 2 5 2 이 들어온 수를 grab[a][b] = 1 grap[b][a]로 체크를 하면 인접 행렬을 구할 수 있다. 1 2 3 4 5 1 1 1 2 1 1 1 3 1 1 4 1 1 5..
Java BFS 기초 이해와 문제 풀이 개요 목적 이번 시간에는 BFS 쉬운 문제들을 풀어보면서 BFS 동작 원리와 풀이 방법에 대해서 알아보자. BFS 넓이 우선 탐색 문제를 통해서 알아보기 이진 트리 노드가 주어졌을 때 목표 0: 1 1: 2 3 2: 4 5 6 7 이런식으로 각 레벨 별로 탐색하는 알고리즘을 한번 작성해보자 풀이 import java.util.LinkedList; import java.util.Queue; public class 이진트리순회 { static class Node{ int data; Node lt, rt; public Node(int val) { data=val; lt=rt=null; } } public static void BFS(Node node) { Queue queue = new LinkedList()..
Java DFS 기초 이해와 문제 풀이 개요 목적 DFS 깊이 우선 탐색을 재귀 함수로 많이 표현하기 때문에 재귀 함수 동작 과정을 먼저 이해해야 한다. 아래 문제들을 풀면서 재귀 함수가 어떻게 진행되는 지 파악하면서 공부해보자. 그리고 기초적인 DFS 문제들을 풀면서 DFS에 대한 이해를 해보자. 재귀 함수 문제 풀이 1. 해당 재귀 함수가 어떻게 진행될까 생각해보기 public class Main { public static void DFS(int n) { if (n == 0) { return; } else { DFS(n - 1); //6번 라인 System.out.print(n + " "); //7번 라인 } } public static void main(String[] args){ DFS(3); } } DFS(3) 에서 6번 라인에 D..
반응형

티스토리툴바