문제 문제 이해하기N의 크기가 작고 2차원 배열을 모두 탐색 해야하기에 DFS 사용완전 탐색하면서 1과 인접한 단지의 크기를 리턴해야한다.크기들을 오름차순 정렬해서 출력해야한다. 코드import java.io.*;import java.util.*;public class 단지번호붙이기 { static int[][] arr; static boolean[][] visited; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int N = Integer.parseInt(br.read..
문제 문제링크 문제 이해하기위치 `N`에서부터 `K` 로 이동해야한다.이동 방법은 3가지 방법이 존재한다.현재 위치 - 1현재 위치 + 1현재 위치 * 2N에서 K까지 걸리는 최소 시간을 구해야한다.어떤 알고리즘이 가능한지 검토완전탐색모든 경로를 탐색해야해서 너무 많은 시간이 걸린다.그리디 현재의 최선 값이 전체 결과의 최선이 되지 않기에 사용하지 못한다.DFS한 경로를 끝까지 탐색한 뒤 다른 경로를 탐색하기 때문에 최단 시간에 적합하지 않는다.BFS가중치가 동일한 그래프에서 최단 경로를 찾는데 적합하다.BFS는 레벨 단위로 탐색하므로 가장 먼저 도달한 경로가 최단 경로임을 보장한다.시간 복잡도는 O(V+E) 코드import java.io.*;import java.util.*;public class 숨바..
문제두 용액 링크 풀이N은 최대 10^5 이기에 n^2 알고리즘은 안되서 처음에는 이진 탐색을 이용하려고 생각했으나 투 포인터를 이용하면 더 빠르게 값을 찾을 수 있을 것 같아 투 포인터로 문제를 해결했다. 코드package org.algorithm.baekjoon.silver;import java.io.*;import java.util.*;public class 두_용액 { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int N = Integer.parseInt(br.readLin..
문제기타레슨 링크 풀이이분 탐색 문제로 가장 먼저 블루레이의 크기를 정해야 한다. 블루레이의 가장 작은 길이는 배열의 max 값이 되고 가장 큰 길이는 모든 배열의 합이 된다.max와 sum의 값으로 mid 값을 구한뒤 arr를 반복문을 돌려 inerSum의 값이 mid와 같거나 커지면 count를 증가시키고, 작으면 inserSum에 해당 값을 더해준다.count 출력값을 출력해준다. 코드import java.io.*;import java.util.*;public class 기타_레슨 { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStr..
문제선분 위의 점 풀이N과 M의 최대 개수는 100,000이고 시간 제한은 1초이기에 n^2 은 시간초과가 발생합니다. 무조건 M번은 반복문을 돌려야 하고 실행당 포함하는 점의 개수를 구하기 위해 longN의 시간복잡도를 갖는 탐색 알고리즘이 필요합니다. 그래서 이분 탐색을 이용해 해당 문제를 풀었습니다. 선분위의 점의 개수는 선분이 포함한 점의 `최대값의 인덱스 - 최소값의 인덱스 + 1` 을 통해 구할 수 있습니다.선분의 최소값의 인덱스는 선분의 왼쪽값과 `같거나 큰(큰 값들 중 최소)값`의 점 인덱스를 의미하고 최대값의 인덱스는 선분의 오른쪽값과 `같거나 작은(작은 값들 중 최대)값`의 점 인덱스를 의미하고, 해당 인덱스들은 이분탐색을 통해 구할 수 있습니다. 수도 코드정수타입 N, M을 입력받는..
문제암기왕 링크풀이가장 먼저 생각났던 방식은 2중 반복문을 돌며 수첩 1에 적힌 값을 찾는 방식이었다. 하지만 시간 조건은 2초, N, M은 최대 1,000,000 개수를 갖을 수 있기에 다른 방법은 생각한 결과 Set, 이진 탐색 방법을 생각해냈다. Set을 이용한 풀이수첩1에 해당하는 값을 Set 자료구조에 저장수첩2의 값을 입력받아서 Set에 존재하는지 확인하고 존재하면 1, 없으면 0을 bw에 작성T(테스트 케이스)가 모두 종료되면 버퍼에 저장되 문자열을 flush해서 내용을 출력한다.import java.io.*;import java.util.HashSet;import java.util.Set;import java.util.StringTokenizer;public class Main { p..