아주 유명한 분할 정복 문제입니다. Stack을 사용해서 풀 수 있는 문제이기도 하지만, 문제 테마가 분할정복이니 분할정복을 이용한 풀이로만 소개하겠습니다. 분할 정복 (Divide and Conquer)이란?문제를 같은 속성을 지닌 부분 문제로 쪼개서 각개격파 하는 방법으로, BruteForce(모든 경우의 수를 다 탐색하는 방법)로 푸는 것 보다 일반적으로 매우 빠릅니다. 그럼 이 문제는 어떻게 분할 정복을 해야할까요? 분할 정복을 사용할 부분 문제를 찾기 위해서는, 먼저 가장 큰 문제를 봐야합니다. 가장 큰 문제는 무엇일까요? "입력으로 주어진 히스토그램에서, 가장 큰 직사각형을 구하는 프로그램을 작성하시오" 입니다. 결국 우리가 풀어야 할 문제는 [0,n) 사이의 히스토그램에서 최대 넓이의 직사각..
주어진 수열에서, 가장 긴 증가하는 부분 수열을 구하는 문제입니다. 알고리즘 문제를 많이 접해 보지 못했던 사람들은, 이 문제를 보면 이걸 다이나믹 프로그래밍 풀어야지 하는 생각을 한번에 떠올리기란 쉽지 않습니다.보통 이러한 문제는 모든 경우의 수를 다 따져볼 수 있는 방법으로부터 접근하곤 합니다. 예제를 볼까요? 예제로 주어진 수열의 길이는 6이고, 주어진 수열은 {10, 20, 10, 30, 20, 50} 입니다. 이 수열에서 존재하는 부분 수열의 개수는 아무것도 없는 수열(공수열이라고 하겠습니다.)을 제외하고 6C0 + 6C1 + 6C2 + 6C3 + 6C4 + 6C5 + 6C6으로 이항정리에 의해 2^5-1 = 31개입니다. Brutforce로 해결하면, 총 2의 n-1승개의 부분수열이 존재하고,..
@markdownACM-ICPC 2016년 대한민국 인터넷 예선에 출제되었던 문제입니다. Q-Index라는 개념을 이용해 문제를 푸는 것이었는데요. 번역문보다 원문을 보는게 이해가 빠른 문제라 푸는데 조금 시간이 걸렸던 문제입니다. 문제를 해설해보면 "Q 인덱스가 k이다" 라는 말은 " n개중에 k개의 논문이 k번 이상 인용되었고 n-k의 논문이 k번 미만 인용되었다." 라는 의미입니다. 논문의 개수와 인용회수의 범위를 살펴보면,논문의 개수 n은 1 이상 1000이하,논문의 인용 회수(편의상 m)은 0이상 10000이하 라고 되어있습니다. 제가 생각하는 간단한 문제 풀이 방법은, 논문의 인용 횟수를 통해, 존재하는 논문을 전부 탐색해서, q-index의 최대값을 구하는 방법입니다. Psuedo Code를..