Algorithm/Baekjoon
[백준] 3273 두 수의 합 - Java
[백준] 3273 두 수의 합 - Java
2022.05.05이분 탐색을 활용해 빠르게 찾자 import java.util.*; import java.io.*; public class Main{ public static void main(String[] args) throws IOException{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int N = Integer.parseInt(br.readLine()); int[] arr = new int[N+1]; StringTokenizer st = new StringTokenizer(br.readLine()); for(int i=1; i
[백준] 2110 공유기 설치 - Java
[백준] 2110 공유기 설치 - Java
2022.05.04매개 변수 탐색을 활용해서 풀 수 있는 문제이다. C개의 공유기를 N개의 집에 적당히 설치해서, 가장 인접한 두 공유기 사이의 최대 거리를 구하시오. => 두 공유기 사이의 최대 거리를 적당히 설정했을 때 C개의 공유기를 설치할 수 있는지 구하시오. 공유기 C개를 설치할 수 있는지에 대한 확인은 그리디 느낌으로 일단 싹다 설치해놓고 C이상이면 true, 아니면 false를 반환하도록 작성했다. 매개 변수 탐색은 이분 탐색을 기반으로 함을 잊지 말자. import java.util.*; import java.io.*; public class Main{ static int N; static int C; static int[] Home; public static void main(String[] args) t..
[백준] 2805 나무 자르기 - Java
[백준] 2805 나무 자르기 - Java
2022.05.04매개 변수 탐색을 활용해 풀 수 있는 문제이다. 알고리즘 분류에 매개 변수 탐색이라고 나와있어서 쉽게 찾을 수 있지만.. 어떤 문제를 매개 변수 탐색으로 풀 수 있는지, 어떤 경우에 매개 변수 탐색이 효율적인지 알아두자. 매개 변수 탐색을 활용하기 위해 문제를 적절하게 변형하자. 적어도 M미터의 나무를 집에 가져가기 위해서 절단기에 설정할 수 있는 높이의 최댓값을 구해라. => 절단기에 특정 높이를 설정했을 때 적어도 M미터의 나무를 집에 가져갈 수 있는가? import java.util.*; import java.io.*; public class Main{ static int N; static int M; static int[] tree; public static void main(String[] ar..
[백준] 2470 두 용액 - Java
[백준] 2470 두 용액 - Java
2022.05.04해당하는 용액을 빠르게 찾아야 한다. 먼저 이분 탐색을 활용해 풀어보자. 용액의 특성값 합이 0에 가장 가까워야 한다. 용액에 대해 오름차순으로 정렬을 수행한 후, target을 -arr[i]로 설정하고 이분 탐색을 진행하자. 1. target이 특성값 배열의 최댓값보다 크면 R + 1을 반환한다. 2. 1의 경우가 아니면 target과 가장 근접한 요소의 인덱스를 반환한다. 이진 탐색 코드는 자주 사용되니, 정형화된 스타일을 익혀 두자. import java.util.*; import java.io.*; public class Mabn{ public static void main(String[] args) throws IOException{ BufferedReader br = new BufferedRe..
[백준] 7795 먹을 것인가 먹힐 것인가 - Java
[백준] 7795 먹을 것인가 먹힐 것인가 - Java
2022.05.04원소를 하나하나 비교하고 있으면 시간 초과가 날 게 뻔하다. 이분 탐색을 통해 빠르게 비교하자. 이분 탐색을 할 때 배열의 인덱스에 주의하자. 0부터 시작하는 것 보다 1부터 시작하도록 조작한 후 이분 탐색을 수행했을 때 실수를 줄일 수 있더라... import java.util.*; import java.io.*; public class Main{ public static void main(String[] args) throws IOException{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int T = Integer.parseInt(br.readLine()); StringTokenizer st; for(int..
[백준] 1182 부분수열의 합 - Java
[백준] 1182 부분수열의 합 - Java
2022.05.02재귀함수를 사용해 백트래킹을 구현해서 풀 수 있는 문제이다. 백트래킹 알고리즘에서 가장 중요한 부분은 재귀함수의 올바른 정의이다. 재귀함수와 반복문잉 본직적인 차이가 없음을 이해하고 재귀함수를 정의하자.. 재귀적 스타일에 익숙해 지는 게 중요하다. 종료 조건 명시해두고, 인덱스를 하나씩 늘려 가며 "이렇게 작성하면 모든 경우를 셀 수 있겠다." 라는 믿음을 가지자. import java.util.*; import java.io.*; public class Main { static int N; static int S; static int ans; static int arr[]; public static void main(String[] args) throws IOException { BufferedRead..
[백준] 15500 이상한 하노이 탑 - Java
[백준] 15500 이상한 하노이 탑 - Java
2022.05.01스택을 사용해서 풀 수 있는 문제이다. 기존 하노이 탑에서 조건이 많이 수정돼서 재귀를 사용할 필요가 없다. 1 2 3 세 개의 장대가 주어지고, 3번 장대에 탑을 쌓아주면 되는 상황이다. 1. 1번 장대에 걸린 요소들을 검사해 3번 장대에 들어갈 순서인지 확인하고, 맞으면 3번 아니면 2번으로 옮긴다. 2. 2번 장대에 대해서도 위와 같은 작업을 수행한다. 3. 3번 장대에 탑이 완성되면 마무리한다. import java.util.*; import java.io.*; public class Main { static StringBuilder sb; public static void main(String[] args) throws IOException{ BufferedReader br = new Buffe..
[백준] 11729 하노이 탑 이동 순서 - Java
[백준] 11729 하노이 탑 이동 순서 - Java
2022.05.01재귀를 사용해서 풀 수 있는 문제이다. 재귀함수.. 공부하고 있긴 한데 생각하고 구현하기가 참 어렵다.. 이렇게 작동하겠지? 라고 작성하는 정도는 어떻게 할 수 있을 것 같은데, 코드의 작동을 하나하나 따라가서 분석하는게 쉽지 않다.. 재귀는 dfs bfs 백트래킹 등등 여러 알고리즘에 활용되고, 중요한 테크닉이다. 꾸준히 관련된 문제 풀어보고 공부해서 익숙해져야겠다. import java.util.*; import java.io.*; public class Main { static StringBuilder sb; public static void main(String[] args) throws IOException{ BufferedReader br = new BufferedReader(new Input..
[백준] 17952 과제는 끝나지 않아! - Java
[백준] 17952 과제는 끝나지 않아! - Java
2022.05.01스택 자료구조를 사용해 하라는 대로 구현하면 풀 수 있는 문제이다. import java.util.*; import java.io.*; public class Main { static long arr_koong[] = new long[68]; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int N = Integer.parseInt(br.readLine()); Stack stack = new Stack(); StringTokenizer st; int ans = 0; for (int i = 0; i < N; i++)..
[백준] 9625 BABBA - Java
[백준] 9625 BABBA - Java
2022.05.01dp를 이용해 풀 수 있는 간단한 문제이다. import java.util.*; import java.io.*; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int K = Integer.parseInt(br.readLine()); BABBA temp = new BABBA(1, 0); for(int i = 0; i
[백준] 2257 화학식량 - Java
[백준] 2257 화학식량 - Java
2022.04.25스택을 사용해 층을 나눠 계산했다. 1. H C O 이 입력되면 해당하는 숫자를 계산해 넣어준다. 2. 여는 괄호가 입력되면 0을 push해 층을 하나 늘린다. 3. 닫는 괄호가 입력되면 여는 괄호가 나온 후 ~ 닫는 괄호가 나온 시점까지의 결과를 집계해 계산한다. 4. 숫자가 나오면 바로 전 항목에 곱해준 뒤 넣어준다. import java.util.*; import java.io.*; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String str = br.readLine(..
[백준] 2304 창고 다각형 - Java
[백준] 2304 창고 다각형 - Java
2022.04.25두 번 계산해서 풀었다. 정방향으로 계산하면서 가장 높은 높이에 대한 기둥을 얻고, 가장 높은 기둥 전까지의 넓이를 갱신한다. 그 후 역방향으로 계산하면서 가장 높은 기둥 뒷부분의 넓이를 갱신한다. import java.util.*; import java.io.*; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); ArrayList list = new ArrayList(); int N = Integer.parseInt(br.readLine()); StringTokenizer st; ..