Algorithm/동적 계획법
-
[Java]최장 공통 부분 수열(LCS, Longest Common Subsequence)Algorithm/동적 계획법 2021. 7. 11. 18:49
*최장 공통 부분 수열(LCS, Longest Common Subsequence) ->최장 공통 부분 수열이란, 주어진 두 수열이 주어졌을 때 두 수열 모두의 부분 수열이 되는 수열 중 가장 긴 것을 말한다. ->LCS를 구하는 문제는 역시 백준 Gold5 9251 LCS 문제를 기반으로 알고리즘을 설명하도록 하겠다. ※ 문제 주소 : https://www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net ->해당 테스트 ..
-
[Java]최장 증가 부분 수열(LIS, Longest Increasing Subsequence)Algorithm/동적 계획법 2021. 7. 11. 17:19
*최장 증가 부분 수열(LIS, Longest Increasing Subsequence) ->최장 증가 부분 수열이란, 주어진 수열에서 오름차순으로 정렬된 가장 긴 부분 수열을 찾는 문제이다. 여기서 부분 수열은 연속적이거나, 유일할 필요는 없다. ->아래 그림을 참고하여 이해하도록 하자. 해당 예시로 주어진 배열에서는 가장 긴 증가하는 부분 수열(이하 LIS)은 1, 2, 3, 7임을 직관적으로 알 수 있다. ->LIS를 구하는 문제는 Knapsack, LCS와 더불어 다이나믹 프로그래밍의 기초를 다지는데 자주 사용되는 예제 중 하나이다. 이 문제 역시 백준 Silver2 11053 가장 긴 증가하는 부분 수열 문제를 기반으로 알고리즘을 설명하도록 하겠다. ※ 문제 주소 : https://www.acm..
-
[Java]배낭 문제(Knapsack Problem)Algorithm/동적 계획법 2021. 7. 11. 02:32
*배낭 문제(Knapsack Problem) ->배낭 문제는 조합 최적화의 유명한 문제로, 배낭에 담을 수 있는 무게의 최댓값이 정해져 있는 경우, '일정 가치'와 '무게'가 있는 짐들을 배낭에 넣을 때 가치의 합이 최대가 되로록 짐을 고르는 방법을 찾는 문제이다. ※ 조합 최적화란 쉽게 말해 모든 조합의 경우의 수를 고려하지 않고, 최적화하여 조합의 경우의 수를 줄이는 것을 말한다. ->배낭 문제는 두 가지로 나눌 수 있다. (1) 분할가능 배낭문제(Fractional Knapsack Problem) ->짐을 쪼갤 수 있다는 가정을 둔다. 예를 들어, 물건이 4kg이고 가치가 8이라면 물건을 2kg으로 나눠 가치가 4인 경우로 분할 해 배낭에 담을 수 있다고 생각하면 된다. ->해당 문제는 그리디 알고..
-
[Java]동적 계획법(Dynamic Programming)Algorithm/동적 계획법 2021. 7. 10. 22:37
*동적 계획법(Dynamic Programming) ->동적 계획법이란 특정 범위까지의 최적해(상위 문제)를 구하기 위하여 다른 범위까지의 최적해(하위 문제)를 이용하여 효율적으로 해를 구하는 알고리즘 설계 기법이다. ->쉽게 말해, 이전에 구한 값을 기반으로 규칙성을 파악하여 다음 값을 구하는 것이라고 생각하면 된다. ->알고리즘 설계 기법(패러다임) 중 하나이다. 하위 문제의 최적해를 적절히 사용하여 상위 문제를 해결함으로써, 불필요한 계산을 줄일 수 있다. ※ 어떤 문제를 해결할 때, 기본적인 방법은 모든 경우의 수를 고려하는 것(완전 탐색)이다. 어떤 문제를 해결할 때, 그 문제에 대한 모든 경우의 수를 고려할 수 있는 설계가 가능하다면, 그 문제는 시간과 자원이 매우 많이 들지는 몰라도 언젠가 ..