기록보관소

가장 긴 증가하는 부분 수열 2는 이분법을 사용하여(솔직히 이 문제의 핵심은 이분법이 아닌 것 같습니다. 이분법만 아는 것으로는 조금 부족할 수도 있을 것 같습니다.;) 풀 수 있는 문제입니다. 원래 문제인 가장 긴 증가하는 부분 수열(LIS)문제는 동적계획법(완전탐색 + 메모이제이션)으로 해결할 수 있으나 N의 개수가 100만이 되어서 더 빠른 방식의 알고리즘을 고안해야 합니다. 문제를 곰곰히 생각해보면 다음과 같은 통찰을 얻을 수 있습니다. 수열의 어떠한 위치를 탐색하고 있다고 가정하면 우리는 그 이전의 수들로만 구성된 수열들을 상상할 수 있습니다. 어떤 수열은 1개의 숫자로만 이루어질 수도 있고, 어떤 수열을 2개, 3개 혹은 그 이상의 숫자로 만들어질 수 있을 것입니다. 우리가 구하고자 하는 것은..

K번째 수 문제는 최적화 문제를 결정 문제로 바꾸어 푸는 유형의 문제로 볼 수 있습니다. K번째 수를 X로 가정하면 X보다 작거나 같은 수는 K개 이상이라는 사실을 알 수 있습니다. 그보다 작으면 K번째 수가 될 수 없기 때문입니다. 작거나 같은 수가 K개 이상인 수 중 가장 작은 값을 찾는 문제로 생각해볼 수 있습니다. 이와 같은 최적화 문제를 X이상의 수에 대해 자기 자신보다 작거나 같은 수를 K개이상 가지고 있는지 확인하는 결정문제로 바꿀 수 있습니다. 이러한 결정문제는 이분법을 이용하여 해결할 수 있습니다. 작성한 코드는 다음과 같습니다. #include #pragma warning(disable : 4996) //https//ark-hive.tistory.com int N, K; int min(..

공유기 설치는 최적의 값을 찾는 문제를 참과 거짓을 결정하는 문제로 변환하여 이분법을 통해 해결할 수 있는 문제입니다. 문제의 지문을 그대로 해석하면 가장 인접한 공유기의 거리의 최대값을 구하는 문제로 생각할 수 있습니다. 이러한 최적화 문제를 참과 거짓을 결정하는 결정 문제로 변환하여 이분법을 이용하여 쉽게 해결할 수 있습니다. 위의 최적화 문제를 다음과 같은 결정 문제로 변환할 수 있습니다. "가장 인접한 공유기의 거리가 x이상이 되도록 공유기를 설치할 수 있을까" 이 질문에 대해서는 참 또는 거짓으로만 답을 할 수 있습니다. 만약 이 질문의 답이 참이라고 가정하면 가장 인접한 공유기의 거리가 x 이하인 모든 값으로 설치가 가능하다는 자명한 사실을 알 수 있습니다. 따라서 x이하의 값에 대해서는 더 ..

나무 자르기 문제는 최적화 문제를 결정 문제로 변환하여 푸는 기법을 통해 해결할 수 있는 문제입니다. 적어도 ~이상의 나무를 가져가기 위해 전기톱을 최대한으로 설정할 수 있는 높이를 구하는 최적화 문제를 참, 거짓의 결정 문제로 변환하여 이분법으로 빠르게 해결할 수 있습니다. 최대의 값을 구하기를 결정 문제로 변환하면 "나무를 어떠한 값 이하로 잘랐을 때 적어도 ~만큼 가져갈 수 있는가?"라는 질문을 할 수 있습니다. 이 질문에 대해 참, 거짓으로 답을 하게 되면 그 값을 기준으로 이하나 이상에 대해서는 더 이상 질문을 할 필요가 없어지게 됩니다. 이분법의 논리와 같다는 사실에서 이분법을 그대로 적용하여 결국에는 최적의 값을 찾을 수 있게 됩니다. 작성한 코드는 다음과 같습니다. #include #pra..