parametricsearch2 [leetcode][441] Arranging Coins 문제 : https://leetcode.com/problems/arranging-coins/ n 개의 동전이 있으면 이를 계단 모양으로 배열하려고 한다. i번째 계단에는 i개의 동전이 있어야 한다. n개의 동전으로 조건을 충족시키는 계단의 최대 행 수를 구하라. 1부터 1씩 증가시키면서 i번째 행의 계단을 만들 때 필요한 동전 수를 구해서 정답을 구할수도 있다. 이렇게 풀면 O(N)으로 문제를 해결할 수 있을 것이다. 더 빠른 방법을 알아보자. 계단은 등차 수열이니까 i개의 행을 가진 계단을 만들고자 할 때 등차수열의 합 공식( i * (i + 1) / 2 )을 이용하면 필요한 동전 수를 O(1)만에 구할 수 있다. 이를 이용해서 parametric search 방식으로 문제를 다시 생각해보자. i 행의.. 2020. 7. 2. [leetcode][275] H-Index II 문제 : https://leetcode.com/problems/h-index-ii/오름차순으로 정렬된 양의 정수 배열이 주어진다고 하자. (let, 배열 크기 = N)이 배열은 논문들이고, 각 배열 값은 i번째 논문이 몇 개의 논문을 인용했는지를 나타낸다. 즉, arr[2] = 3이라면 2번째 논문은 3개의 논문을 인용하여 작성되었음을 의미한다.N개의 논문중 h개의 논문이 h개 이상의 논문을 인용하고 N-h개는 h개 이하를 인용하는 경우 h-인덱스라고 한다.배열의 가능한 h-인덱스 값 중 최대값을 구해라.이분 탐색으로 풀어보자. 어쨌든 h의 범위는 논문의 개수이다.l, r 은 배열의 시작인덱스, 종료인덱스로 잡자.m = (l+r)/2이다.h = N - m라고 하고 h가 정답이 가능한지 판단한다.문제 초반.. 2020. 6. 18. 이전 1 다음