WannaBeDeveloper

12015번: 가장 긴 증가하는 부분 수열 2 www.acmicpc.net 이 문제는 dynamic programming을 사용해 풀 수 있는 대표적인 유형의 문제 중 하나다. 하지만 dynamic programming을 사용하면 O(N^2)의 시간 복잡도를 가지는데, N이 작으면 괜찮으나 위 문제의 경우 N이 10^6까지 커질 수 있기 때문에 이러한 알고리즘을 사용할 경우 시간이 매우 오래 걸린다는 단점이 있다. 그런데 가장 긴 부분 수열의 '길이'만을 구한다는 조건에 한하면 특별히 다른 알고리즘으로 문제를 풀 수 있다. 이 문제에서는 '가짜' 부분수열을 담는 배열을 이용한다. 먼저 이 배열은 비어있으면 안 되기 때문에 A의 첫 번째 원소를 넣는다. 그리고 A의 각 원소에 대해 배열의 마지막 원소보다 ..

1300번: K번째 수 www.acmicpc.net 위 문제는 만약 행렬의 크기 N이 작은 문제였다면 크게 어렵지 않은 문제다. 왜냐하면 N이 작은 경우에는 행렬을 직접 만들 수 있고, 이에 따라 배열 B 역시 쉽게 만들 수 있기 때문이다. 그러면 배열 B를 정렬하기만 하면 끝나는 문제라 큰 의미가 없는 문제였을 것이다. 하지만 이 문제의 핵심은 행렬의 크기 N이 10^5까지 커질 수 있다는 점이다. 이 때문에 배열 B를 만드는 것이 불가능하다. 그래서 직접 배열을 만들어 정렬하는 것은 불가능하고, 대신 다른 방법을 찾아야 한다. 이 문제를 다른 관점으로 봤을 때 이 문제 역시 k번째 수를 '찾는' 문제다. 즉 search를 해야 하는데 이때 binary search를 할 수만 있다면 쉽게 풀 수 있을 ..