빈코의 개발일지

오늘은 해쉬맵과 윈도우 미러링을 이용하여 주어진 단어 안에서 모든 아나그램을 찾는 문제를 풀어보려 합니다😄 개요 이번 문제의 핵심은 저번 포스팅과 마찬가지로 해쉬맵을 사용하는 방법과 윈도우 미러링 방식을 사용하여 시간복잡도를 해결하는 것이 관건일 것 같네요😀 Setting📙 public class AllAnagram { public static void main(String[] args) { AllAnagram T = new AllAnagram(); Scanner sc = new Scanner(System.in); String a = sc.next(); String b = sc.next(); System.out.println(T.solution(a,b)); } } 입력값으로는 두 단어가 주어집니다. 첫 ..

오늘은 해쉬맵을 이용하여 주어지는 두 단어가 아나그램인지 판별하는 문제를 풀어보려고 합니다. 아나그램은 두 단어가 알파벳 나열 순서가 달라고 구성이 같을 때의 경우를 의미합니다😀 개요 이번 문제의 핵심은 서두에서 언급했듯이 해쉬맵의 기능들을 사용하는 것이 될 것 같네요😊 Setting📙 public class Anagram { public static void main(String[] args) { Anagram T = new Anagram(); Scanner sc = new Scanner(System.in); String a = sc.next(); String b = sc.next(); System.out.println(T.solution(a,b)); } } 입력값은 문제에 나와있는 것 처럼 두 단어가..

오늘은 배열을 이용하여 격자판의 봉우리 개수를 구하는 문제를 풀어보려고 합니다😀 개요 이번 문제는 이중 배열을 이용하는 방법과 각 격자에서 상하좌우를 확인하는 방법 총 2가지가 핵심이 될 것 같네요😊 Setting📙 public class Peak { public static void main(String[] args) { Peak T = new Peak(); Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int[][] arr = new int[n][n]; for(int i = 0; i < n; ++i){ for(int j = 0; j < n; ++j){ arr[i][j] = sc.nextInt(); } } System.out.println(T...

오늘은 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..

오늘은 BFS를 활용하여 토마토 문제를 풀어보려 합니다. 토마토 문제는 근방에 익은 토마토가 있다면 하루가 지나 같이 익게 되고, 모든 토마토가 다 익을 때까지의 날짜 수를 구하는 문제입니다😄 개요 이 문제의 핵심은 BFS 알고리즘을 활용과 Queue의 원리, 여러 시작점에서 동시다발적으로 여러개의 토마토가 익는 부분, 상자의 상하좌우 확인 방법, 익은 토마토를 체크 총 5가지가 되겠네요😀 TomatoPoint📙 class TomatoPoint { public int x,y; TomatoPoint(int x, int y) { this.x = x; this.y = y; } } TomatoPoint 클래스는 상자판에서 행,열을 입력할 때 사용합니다. 근방에 익은 토마토에 의해 해당 토마토가 익을 때 큐에 쌓..

오늘은 BFS를 활용하여 미로의 최단 경로를 구해보는 문제를 풀어볼 예정입니다. 이전 포스팅에서 풀어 본 DFS를 활용한 미로 탐색과 풀이법이 유사하기 때문에 참고하면 좋을 듯하네요😊 개요 이 문제의 핵심은 BFS 알고리즘 활용과 Queue의 원리, 지나간 경로는 다시금 못 지나가게 막는 방법, 격자의 상하좌우 확인 총 4가지가 될 것 같아요. 한번 코드로 풀어볼까요? Point📙 class Point { public int x,y; Point(int x, int y) { this.x = x; this.y = y; } } Point 클래스는 격자판에서 x축, y축을 입력할 때 사용합니다. Queue에 지나간 격자를 넣거나 빼서 사용할 때 Point 클래스를 사용하여 현재 위치를 파악할 때 사용합니다. 자..

오늘은 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 탐색 알고리즘을 사용한 동전 교환 문제를 풀어보려 합니다😊 개요 이 문제의 포인트는 DFS 탐색 알고리즘을 활용, 배열을 내림차순으로 하여 시간을 단축하였는가, 탐색하지 않아도 될 상황을 제한하였는가 총 3가지 인 것 같아요. 바로 코드를 보면서 확인해 볼게요😀 Main📙 public class ExchangeCoins { static int n, m, result = Integer.MAX_VALUE; public static void main(String[] args) { ExchangeCoins T = new ExchangeCoins(); Scanner sc = new Scanner(System.in); n = sc.nextInt(); Integer[] arr = new Integer[..

오늘은 탐색 알고리즘인 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 ..