JAVA - 백준 [BAEK JOON]/이분 탐색
[백준] 12015번 : 가장 긴 증가하는 부분 수열 2 - JAVA [자바]
[백준] 12015번 : 가장 긴 증가하는 부분 수열 2 - JAVA [자바]
2022.04.25https://www.acmicpc.net/problem/12015 12015번: 가장 긴 증가하는 부분 수열 2 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000) www.acmicpc.net 문제 알고리즘 [접근 방법] 이 문제를 풀기 전에 가장 긴 증가하는 부분 수열(LIS)에 대해 모르고 있다면, 아래 문제를 먼저 풀면서 접해보는 것을 권장한다. https://st-lab.tistory.com/137 [백준] 11053번 : 가장 긴 증가하는 부분 수열 - JAVA [자바] www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 ..
[백준] 1300번 : K번째 수 - JAVA [자바]
[백준] 1300번 : K번째 수 - JAVA [자바]
2021.12.27https://www.acmicpc.net/problem/1300 1300번: K번째 수 세준이는 크기가 N×N인 배열 A를 만들었다. 배열에 들어있는 수 A[i][j] = i×j 이다. 이 수를 일차원 배열 B에 넣으면 B의 크기는 N×N이 된다. B를 오름차순 정렬했을 때, B[k]를 구해보자. 배열 A와 B www.acmicpc.net 문제 알고리즘 [접근 방법] 필자도 이 번 문제는 접근 방법을 이해하는데 조금 애를 먹은 문제다. 혹여나 필자가 포스팅 하는데, 잘못 접근하진 않았을까 검색도 해보았지만 생각보다 한 번에 이해가 팍 되는 글은 개인적으로 없는 것 같았다. 그래서 최대한 쉽게 풀이하여 이해 할 수 있도록 최대한 노력해보겠다. 일단, 이분 탐색으로 접근한다는 생각은 잠시 뒤로하고 문제부터..
[백준] 2110번 : 공유기 설치 - JAVA [자바]
[백준] 2110번 : 공유기 설치 - JAVA [자바]
2021.12.08https://www.acmicpc.net/problem/2110 2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 www.acmicpc.net 문제 문제를 정확히 파악만 한다면 매우 쉬운 문제다. 알고리즘 [접근 방법] 그동안 숫자 카드, 랜선 자르기, 나무 자르기를 순서대로 풀어왔다면, 이 번 문제는 그리 어렵지는 않았을 것이다. 그럼에도 정답률이 낮은 이유라 한다면, 아마 이분탐색 구현을 제대로 하지 않았기 때문일 가능성이 매우 높지 않을까 생각을 해본다만.. 그렇기 때문에 필자가 ..
[백준] 2805번 : 나무 자르기 - JAVA [자바]
[백준] 2805번 : 나무 자르기 - JAVA [자바]
2021.09.12https://www.acmicpc.net/problem/2805 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보 www.acmicpc.net 문제 이 전의 랜선 자르기 문제와 매우 유사한 문제다. 만약 직전 문제를 안풀어보셨다면 먼저 풀고오는 것을 추천한다. 그러면 이 문제도 자연스럽게 바로 풀릴 것이다. 알고리즘 [접근 방법] 이 번 문제는 앞서 언급했듯 랜선 자르기 문제와 풀이 방식이 거의 같은 문제다. 이 문제를 풀기 전에 되도록이면 아래 글을 먼저 보고 오시는 것을 추천한다. 모두 다 연계..
[백준] 1654번 : 랜선 자르기 - JAVA [자바]
[백준] 1654번 : 랜선 자르기 - JAVA [자바]
2021.08.31https://www.acmicpc.net/problem/1654 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 www.acmicpc.net 문제 이분 탐색의 응용 문제다. 알고리즘 [접근 방법] 일단, 이 번 문제를 풀기 전에 이분 탐색 중 Upper Bound 에 대해 이해하고 있어야 한다. 그러니, 해당 원리를 이해하기 위해 아래 포스팅을 먼저 보시고 오시기를 바란다. https://st-lab.tistory.com/267 [백준] 10816번 : 숫자 카드 2 - JAVA [자바] https://ww..
[백준] 10816번 : 숫자 카드 2 - JAVA [자바]
[백준] 10816번 : 숫자 카드 2 - JAVA [자바]
2021.08.06https://www.acmicpc.net/problem/10816 10816번: 숫자 카드 2 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10, www.acmicpc.net 문제 직전 문제랑 비슷하지만, 이분 탐색을 활용해야 할 경우 조금 고려해야 할 부분이 있는 문제다. 알고리즘 [접근 방법] 이 문제 자체는 그리 어렵지 않다. 사실 이분 탐색을 쓰지 않고도 카운팅 정렬 형식을 사용하여 풀 수도 있다만, 그래도 이분 탐색 카테고리에 있는 만큼 한 번 이분 탐색 풀이 방식을 통해 풀이를 해보도록 하자. 일단, 이분 탐색의 경우 구간의..
[백준] 1920번 : 수 찾기 - JAVA [자바]
[백준] 1920번 : 수 찾기 - JAVA [자바]
2021.07.16https://www.acmicpc.net/problem/1920 1920번: 수 찾기 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들 www.acmicpc.net 문제 새 카테고리인 이분 탐색의 첫 번째 문제인 수 찾기다. 알고리즘 [접근 방법] 일단, 풀이 방법을 알아보기 전에 이분 탐색(Binary Search)에 대해 알아보자. 이 전 문제까지 우리가 분할 정복을 살펴보았다. 분할 정복 방식의 경우에는 문제가 주어지면 해당 문제를 둘 이상으로 나누면서 나눠진 부분문제에 대해 풀렸다면 해당 부분은 끝내고,..