답은 알고리즘 뿐이야!

출처 : https://www.acmicpc.net/problem/2094 풀이 : y, x가 주어졌을때 y~x 사이의 범위에서 최댓값이 x이고 두번째로 큰 값이 y인지 묻는 문제입니다. y~x 사이의 범위의 최댓값은 세그먼트 트리로 구하면 되고 그거완 별개로 모든 연도의 강수량 정보가 주어지는 것은 아니기 때문에 y와 x의 강수량이 주어졌는지 확인해주셔야합니다. 따라서 3가지의 케이스를 검사해야합니다. case 1: x년도의 강수량이 있을때 y+1 ~ x-1 사이의 최댓값이 x년도의 강수량보다 작은가 case 2: y년도의 강수량이 있을때 y+1 ~ x-1 사이의 최댓값이 y년도의 강수량보다 작은가 case 3: x년도의 강수량이 있고, y년도의 강수량이 있을때 y ~ x 사이의 모든값이 주어져있는가 ..

문제 출처 : https://www.acmicpc.net/problem/7453 풀이 : 네 정수의 합을 0으로 만드는 문제입니다. 이 문제는 [BOJ 16287] Parcel (ICPC 2018) 과 비슷한 개념을 사용하여 풀면 됩니다. a,b의 합을 ab라는 배열로 묶고, c,d의 합을 cd라는 배열로 묶어서 각각 정렬한다음 ab를 기준으로 cd중 -ab와 같은 값을 이분탐색을 통해 찾으면 됩니다. 저는 어퍼바운드를 구현하여 끝에서부터 내려오면서 중복 체크를했습니다. ab의 값이 같다면 계산을 생략해주어야 시간초과가 나지 않습니다. 해쉬로도 풀수있는거 같으니 다음에 한번 풀어보겠습니다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 2..

문제 출처 : https://www.acmicpc.net/problem/2343 풀이 : 이분 탐색 문제입니다. 블루레이의 길이를 기준으로 이분탐색을 돌아 가능한 모든 경우의수를 다 시도해봅니다. 이분 탐색을 돌 때 left와 right를 기준으로 도는데, 1. Mid 값이 문제조건을 만족 할 때, (즉, Mid값을 블루레이의 길이로 잡고 M을 채울때 M개 안에 다 채워 질 때) - binary( left , Mid - 1 ) 2. Mid 값이 문제 조건을 만족 시키지 못 할 때, - binary( Mid + 1, right ) 위와 같이 탐색하시면 됩니다. O(n) * O(logn) 으로 총 O(nlogn)의 시간복잡도를 가집니다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 ..

문제 출저 : https://www.acmicpc.net/problem/2805 풀이 : 이분 탐색 문제입니다. 절단기 높이의 최댓값은 나무 높이 들 중 최댓값이 됩니다. 기본적인 이분 탐색은 [2512] 예산 과 같으니 참고 하시면 감사하겠습니다. 그리고 나무의 최대 높이가 20억이니 꼭 결과값 저장할 때 long long int 같이 큰 정수 써주셔야합니다. 처음에 아무생각 없이 안썼다가 틀렸었습니다 .ㅠㅠ 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 #include int n, m, arr[1000000], Max, result; void parametricSearch(int s, int e) { i..

문제 출저 : https://www.acmicpc.net/problem/2512 풀이 : 이분 탐색 문제입니다. 배정 될 수 있는 예산들 중 최댓값은 요청의 최댓값을 넘을 수 없기 때문에 e를 요청중 최댓값으로 설정합니다. mid를 요청 당 최대로 배정할 예산으로 두고 아래와 같이 계산합니다. 1. 요청 당 배정할 예산 >= 요청 : 요청만큼 배정 2. 요청 당 배정할 예산 < 요청 : 배정할 예산만큼 배정 그 후 현재 배정된 총 예산과 총 예산과 비교하고 아래와 같이 이분탐색을 실행합니다 1. 배정된 총 예산 총 예산 : parametricSearch(s, mid - 1); 배정된 총 예산이 총 예산보다 작다면 예산을 조금 더 배정 할 수 있다는 말이 되므로 예산을 더 늘려서 이분 탐색을 진행하고, 반..