Meluu_의 코딩 공부 일지

🧫 문제 분석 ✔️ 출처예산 실버 2 📖 문제 이진 탐색이다. 하지만 국가 예산이라는 제한이 걸려있다.때문에 무턱대고 이진탐색 범위를 0 ~ 10억 이렇게 설정하면 정말 쓴 맛을 느낄 수 있다.  필자는 저렇게해서 삽질을 엄청하고, 반례는 다 통과하는데 75퍼에서 자꾸 틀리는 문제가 발생했다. 생각해보면 탐색을 할 범위를 명확하게 알고 설정해야하는데 무턱대고 큰 값을 설정한 것이 화근이였고이진탐색을 할 줄만 알지 정확하게 이 알고리즘에 대해 이해하지 못함을 느꼈다. 따라서 이진탐색을 파볼 예정이다.  요청 예산중 최댓값을 max로 이진 탐색한다. mid값을 각 요청 예산에 연산하여 mid > 요청 예산[i] 면 요청 예산값을 합 변수에 더하고,크다면 mid값을 상한값으로 더한다.그리고 국가예산과 합을..

🧫 문제 분석✔️ 출처[PCCP 기출문제] 2번 / 퍼즐 게임 챌린지 level 2📖 문제 이진 탐색 문제다. 그런데 이진탐색을 했더니 시간초과나서 다른 방법을 찾아서 삽질을 하고 식을 제대로 세우고 이진탐색으로 풀었다. 문제에서 주어진 조건을 식으로 풀어보면 아래와 같다. limit >= (diff[i] - level) * (time_cur[i] + time_prev[i]) + time_cur[i] 이를 만족하는 level 최솟값을 찾으면 된다.  좀만 더 간단히하면문제에서 diff - level 번 만큼 이전 문제를 다시 풀고(time_prev) + 현재 문제를 다시 풀어야한다(time_cur) diff-level 번 틀린 후 다시 풀면 time_cur만큼 시간을 사용한다.  즉, limit - ..

🧫 문제 분석 ✔️ 출처나무 자르기 실버 2 📖 문제 이진 탐색 문제로나무를 잘랐을 때 적어도 M 미터의 나무를 집에 가져가기 위해 설정할 수 있는 높이의 최댓값을 구해야한다. 여기서 적어도 M미터의 의미는절단 높이가 최댓값을 가질때까지 찾되 적어도 M 미터 이상은 가져가야겠다는 의미이다. 예를 들어1~Int Max 의 절반으로 잘랐을 때 M미터를 넘겼다면 좀 더 그 위에를 잘랐을 때 M 미터 이상이면서 자르는 높이를 높여서 나무를 덜 자를 수 있는 경우가 있다.  푸는 방식 이진 탐색을 하되M 미터 이상이면 높이를 더 높여서 탐색해본다. 주의할 점자르는 높이 이하인 나무들은 무시해야한다.  반례 하나를 남기겠다.2 73 9정답 : 2오답 : 0 밑에 처럼 짜면 오답이 나온다. 이유를 생각해보자if ..