About Dev

https://www.acmicpc.net/problem/1450 1450번: 냅색문제 첫째 줄에 N과 C가 주어진다. N은 30보다 작거나 같은 자연수, C는 109보다 작거나 같은 음이 아닌 정수이다. 둘째 줄에 물건의 무게가 주어진다. 무게도 109보다 작거나 같은 자연수이다. www.acmicpc.net 알고리즘 : 이분탐색 or 투포인터, 재귀 풀이 날짜 : 2023.08.15. 물건의 개수는 N, 가능한 가방 무게는 C 로 입력이 주어질 때 처음에 물건들을 모두 같은 크기의 무게로 생각해서, 그 무게로 C 를 나누었을 때 개수를 R (C / 무게 = R) 이라고 했을 때 N 개 중 R ~ 0 개의 조합들 합으로 잘못 구했었다. 더보기 import java.io.Buffered..

https://www.acmicpc.net/problem/7453 7453번: 합이 0인 네 정수 첫째 줄에 배열의 크기 n (1 ≤ n ≤ 4000)이 주어진다. 다음 n개 줄에는 A, B, C, D에 포함되는 정수가 공백으로 구분되어져서 주어진다. 배열에 들어있는 정수의 절댓값은 최대 228이다. www.acmicpc.net 알고리즘 : 투 포인터 or 이분 탐색 풀이 날짜 : 2023.08.10. 배열 A, B, C, D 의 모든 조합을 완전 탐색(브루트 포스) 을 하면 약 O(N⁴) 의 시간이 걸린다. N이 최대 4000 까지 나올 수 있고, 시간 제한이 12초 이므로 시간 초과가 난다. 그럼 최악으로 O(N² * logN) = 약 4000 * 4000 * 12 = 약 2억 번까..

https://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 알고리즘 : 매개변수 탐색 (이분 탐색) 풀이 날짜 : 2023.05.26., 2023.08.09. 리뷰 어떤 범위의 값이 가능하고, 그 중 어떤 조건을 충족해야 하는 값을 찾는 문제는 매개변수 탐색을 이용한다. 매개변수 탐색이란, 조건(매개변수) 를 따져가며 구하려는 대상(거리) 를 이분 탐색하는 것이다. 해당 문제는 가능한 ..

https://www.acmicpc.net/problem/3079 3079번: 입국심사 첫째 줄에 N과 M이 주어진다. (1 ≤ N ≤ 100,000, 1 ≤ M ≤ 1,000,000,000) 다음 N개 줄에는 각 심사대에서 심사를 하는데 걸리는 시간인 Tk가 주어진다. (1 ≤ Tk ≤ 109) www.acmicpc.net 알고리즘 : 매개변수 탐색(이분 탐색) 풀이 날짜 : 2023.05.25. 처음에 누적 합으로 이분 탐색을 하려고 했는데, 조건을 처리할 논리가 이어지지 않는다. 또한, 최대 십 억 명의 상근이 칭구들을 각각 심사할 수도 없다. 따라서, 한 명이 심사를 몇 초 기다렸는지, 몇 번째로 받았는지는 중요하지 않고 총합(마지막 심사 종료 시각) 이 중요하다. 상근이의 칭구..