[▒] 알고리즘
분류 : 다이나믹 프로그래밍 시간복잡도 : O(K^2) 다이나믹 프로그래밍의 해결 과정은 다음과 같다. DP를 정의한다. 정의한 DP에 대해 점화식을 세운다. DP를 계산해야 하는 순서에 대해 생각한다. 시간 복잡도를 검증하고 구현한다. 위 문제로 해당 풀이법을 적용해보자. 1. DP를 정의한다. 이 문제에서의 DP는 다음과 같다. DP[i][j] = (i 번째 파일부터 j 번째 파일까지를 하나로 합치는데 드는 최소 비용) 2. 점화식 세우기 시간복잡도를 계산해보자. 먼저, 첫 함수 호출에서 검사해야하는 값은 {(1, 1) + (2, K)}, {(1, 2) + (3, K)}, ... , {(1, K - 1), (K, K)} 로 1 ~ K - 1의 범위를 확인해야하므로 K - 1개를 확인해야한다. 두 번째..
분류 : 이분 탐색 시간복잡도 : O(nlogn) https://qhdks.tistory.com/134 [12015] 가장 긴 증가하는 부분 수열 2 분류 : 이분 탐색 시간복잡도 : O(nlogn) 다이나믹 프로그래밍(DP) 문제이다. DP인 만큼 어떻게 이전 상태의 정보를 저장하고 사용할지가 핵심이다. 다음의 경우를 보자. {1, 2, 3}, {5, 6, 7} 이 수열 A의 qhdks.tistory.com 위 문제의 풀이 방식에서 경로 추적 코드를 넣어주면 된다. 경로 추적은 어떻게 할까? 보통은 way[10]이 있을 때, 1-3-4-2-5-8-7-9-6 의 순서를 가진다면, i 1 2 3 4 5 6 7 8 9 way -1 4 1 3 2 9 8 5 7 과 같이 이전 위치를 저장한다. 이를 이용해서 해..
분류 : 이분 탐색 시간복잡도 : O(nlogn) 다이나믹 프로그래밍(DP) 문제이다. DP인 만큼 어떻게 이전 상태의 정보를 저장하고 사용할지가 핵심이다. 다음의 경우를 보자. {1, 2, 3}, {5, 6, 7} 이 수열 A의 부분 수열이라고 할 때, 길이가 3으로 동일하다. 이 두 부분 수열의 다음으로 4가 주어졌을 때, 길이가 4가 되는 부분 수열은 {1, 2, 3} 이다. 이처럼 길이가 같을 때, 맨 마지막 숫자가 작을수록 효율적이다. (관찰) 그렇다면, 어떻게 마지막에 작은 숫자가 오도록 만들 수 있을까? 이진 탐색을 이용하면 된다. 이진 탐색을 이용한 최소값 갱신은 각 길이 (i + 1)에 대한 마지막 값이다. 즉, 경로가 아니라는 뜻이다. 따라서, 갱신 시에 길이에 관련하여 다음 숫자, 이..
