민규의 흔적

2024년 9월 24일문제 링크 : 프로그래머스 - [PCCP 기출문제] 2번 / 퍼즐 게임 챌린지 문제 접근 현재 나의 숙련도에 따라 퍼즐을 푸는 시간이 달라진다. diffs의 각 요소는 최대 100000이므로, 나의 숙련도는 1 ~ 100,001일 것이다. 1 부터 100,001 까지 일일이 확인해보기엔 시간복잡도 측면에서 좋을 게 없다. (퍼즐의 개수 n의 최대 값은 300,000 이므로, 최악의 경우 100,001 * 300,000 ~= 10^10번 연산해야 한다.) 그러므로 우리는 효율적으로 숙련도의 최소값을 찾아야 한다. 어떻게? 이분 탐색으로! 내가 가질 수 있는 숙련도의 범위는 1 ~ 100,001 이므로 양 끝 값인 left, right는 각각 1, 100,001로 초기화 시켜준다. le..

2024년 7월 19일문제 링크 : 백준 2512번 - 예산문제  국가의 역할 중 하나는 여러 지방의 예산요청을 심사하여 국가의 예산을 분배하는 것이다. 국가예산의 총액은 미리 정해져 있어서 모든 예산요청을 배정해 주기는 어려울 수도 있다. 그래서 정해진 총액 이하에서 가능한 한 최대의 총 예산을 다음과 같은 방법으로 배정한다.모든 요청이 배정될 수 있는 경우에는 요청한 금액을 그대로 배정한다.모든 요청이 배정될 수 없는 경우에는 특정한 정수 상한액을 계산하여 그 이상인 예산요청에는 모두 상한액을 배정한다. 상한액 이하의 예산요청에 대해서는 요청한 금액을 그대로 배정한다. 예를 들어, 전체 국가예산이 485이고 4개 지방의 예산요청이 각각 120, 110, 140, 150이라고 하자. 이 경우, 상한액을..

2024년 4월 16일 LIS (최장 증가 부분 수열) 최장 증가 부분 수열(Longest Increasing Subsequence, LIS)이란, 주어진 배열 내에 존재하는 여러 부분 수열 중 오름차순을 준수하며 가장 길게 나열되어 있는 부분 수열을 의미한다. 예를 들어, { 2, 3, 8, 6, 4, 5, 9, 1 } 라는 배열의 LIS는 { 2, 3, 4, 5, 9 } 이며 길이는 5 이다. 오름차순을 준수하는 부분 수열은 { 2, 3 }, { 2, 3, 5 }, { 2, 3, 6, 9 } 등 많지만, 가장 긴 부분 수열은 { 2, 3, 4, 5, 9 } 이다. LIS의 길이를 알아내는 방법은 대표적으로 완전 탐색법과 DP(다이나믹 프로그래밍), 이분 탐색이 존재한다. 이 중, 완전 탐색을 통해 모..

2023년 5월 8일 문제 링크 : 1477번 - 휴게소 세우기 문제 다솜이는 유료 고속도로를 가지고 있다. 다솜이는 현재 고속도로에 휴게소를 N개 가지고 있는데, 휴게소의 위치는 고속도로의 시작으로부터 얼만큼 떨어져 있는지로 주어진다. 다솜이는 지금 휴게소를 M개 더 세우려고 한다. 다솜이는 이미 휴게소가 있는 곳에 휴게소를 또 세울 수 없고, 고속도로의 끝에도 휴게소를 세울 수 없다. 휴게소는 정수 위치에만 세울 수 있다. 다솜이는 이 고속도로를 이용할 때, 모든 휴게소를 방문한다. 다솜이는 휴게소를 M개 더 지어서 휴게소가 없는 구간의 길이의 최댓값을 최소로 하려고 한다. (반드시 M개를 모두 지어야 한다.) 예를 들어, 고속도로의 길이가 1000이고, 현재 휴게소가 {200, 701, 800}에 ..