Programming Contest Challenging8 최장 공통 부분열(DP) 문자열 S1, S2, ... , Sn과 T1, T2, ... , Tn이 주어져 있습니다. 이 둘의 공통 부분 문자열의 길이의 최대 값을 구하세요. 단 문자열 S1S2...Sn의 부분 문자열이란 Si1, Si2, ... Sim(i1 < i2 < ... < im)로 표현 가능한 문자열을 말합니다. 제약 1 2017. 8. 4. 0/1Knapsack Problem(DP) DP(Dynamic Program, 동적계획법)을 이용하여 해결가능한 문제중 가장 기본적인 문제인 Knapsack Problem. 배낭문제의 유형으로는 0/1, bounded, unbounded, fractional 등이 있다. 무게와 가격이 각각 Wi, Vi,인 n개의 물건이 있습니다. 무게의 총합이 W를 초과하지 않도록 물건을 선택했을 때의 가격 총합의 최대치를 구하세요. 위 문제를 완전탐색을 이용하여 풀면 아래와같다. 각 물건 i를 선택하느냐 마느냐의 경우의 수가 존재한다. 1. i번째 물건을 배낭에 담지 않을 것이다. 2. 담을 수 있을경우 배낭에 담을 것이다. int n; int w[], v[]; //무게, 가격 //now부터 n -1까지 의 물건들을 용량이 capacity인 배낭에 담을때 //.. 2017. 8. 4. 탐욕(Greedy) 탐욕 알고리즘은 한가지 규칙에 의해 눈 앞에 보이는 최선만을 반복적으로 선택하여 최선의 결과를 얻어내는 알고리즘이다. 긴 널빤지를 N토막 내려고한다. L1, L2, ... , Ln이 자르려고 하는 널빤지의 길이이며 널빤지의 길이는 토막들의 합과 같다. 널빤지를 자를때에는 비용이 든다. 21을 13과 8로 자르는 비용은 21이다. 13을 5와 8로 자르는 비용은 13이다. N과 N개의 배열L이 주어질때 널빤지를 자를 수 있는 최소비용을 구하여라. 위 문제는 그리디를 이용하여 해결이 가능하다. 널빤지를 우리가 원하는 토막이 되게끔 자르다보면 마지막 토막이 나는 널빤지 조각이 있을 것이다. 여기에 주목하는 것이 이문제를 그리디로 풀 수 있는 요점이다. 예를들어 마지막 톱질로인해 널빤지조각이 a와b로 분리되었다.. 2017. 8. 3. 전탐색(Full Search) 모든 것의 기본이자 뼈대는 전 탐색이라고 생각한다. 전탐색을 고려해보고 전탐색이 불가하다면 그때부터 다른 어떠한 알고리즘과 자료구조를 적용 시켜서 문제를 제한된 시간과 메모리내에 해결가능할지를 모색한다. 이러한 전탐색을 할 수 있는 방법으로는 크게 -for문을 통한 탐색 -깊이 우선 탐색 -너비 우선 탐색 이 있다고 생각한다. 각 경우에 따라 효율이 좋은 방법을 채택하여 사용하면 될것이다. 특히 너비 우선 탐색은 queue를 사용하기 때문에 탐색의 깊이와 넓이가 커지면 커질 수 록 그에 비례하는 메모리가 필요하다. 반면에 깊이우선 탐색은 깊이에만 비례하는 메모리가 필요하므로 너비 우선 탐색에 비해 메모리 제약이 적다. (최단거리는 너비우선탐색 ㅋ) 2017. 8. 3. 이전 1 2 다음