1. 문제 https://www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 2. 최적 부분 구조(optimal substructure) 최장 공통 부분 수열에서는 시작점이 중요하다 다음과 같은 함수를 만들어보자 solve(aidx, bidx) = a 문자열은 aidx 에서 , b문자열은 bidx에서 시작해서 각각 문자열 끝까지 만들어질 수 잇는 최장 공통 부분 수열의 최대 길이 임의의 문자열 a와 b가 있고 이들의 ..

1. 문제 https://www.acmicpc.net/problem/2629 2629번: 양팔저울 첫째 줄에는 추의 개수가 자연수로 주어진다. 추의 개수는 30 이하이다. 둘째 줄에는 추의 무게들이 자연수로 가벼운 것부터 차례로 주어진다. 같은 무게의 추가 여러 개 있을 수도 있다. 추의 무 www.acmicpc.net 2. 완전탐색 이 문제에서 구슬을 비교하는 추의 개수와 종류는 전부 동일하다. 따라서 주어진 추를 사용해서 만들 수 있는 모든 경우의 무게를 만들고나면 구슬의 무게를 확인할 수 있다. 추는 한번만 사용할 수 있으므로 각각의 추에대해서 3가지 선택을 해야한다 1. 추를 구슬쪽에 올릴 경우 (w - weight[idx]) 2. 추를 올리지 않는 경우 (w) 3. 추를 반대편에 올릴 경우 (w..

1. 완전 탐색 이 문제는 다음으로 재생될 곡은 바로 이전 곡에만 영향 받기때문에 마르코프 모델이라고 할 수 있다. 이 문제는 주어진 k분 30초에 좋아하는 노래들이 각각 나올 확률을 구하는 문제이다. 좋아하는 곡들의 번호들과 i다음으로 j가 재생될 확률을 담고있는 행렬 T가 주어지고 각 곡의 길이가 주어진다 number 음악이 min분에 재생될 확률을 구하려면 일단 0 ~min 에 number 음악이 시작되는 확률을 먼저 구해야한다. 해당 음악이 min분에 재생될 확률은 해당 음악이 min - number.len + 1에서부터 min까지 시작되는 확률을 전부 더한것과 같기때문이다. play(min, number) = min에서 number가 재생될 확률 play(min, number) = Σ ( pla..

1. 완전 탐색 이 문제는 packing 문제에서 중복가능한점을 제외하고 전부 같다 따라서 이문제는 다음과 같이 쓸수있다. menu(price) = price로 시킬 수 있는 메뉴의 최대 선호도 이에 모든 메뉴를 for문으로 탐색하면서 price를 넘어가지 않도록 선택하는 재귀함수를 구현하면 답을 구할 수 있다. 2. 반복적 동적 계획법 하지만 이 문제의 price의 최대 값은 10억이다. 총 n메뉴가 있을때 값이 2만을 넘지 않으므로 n^50000시간 이상 걸릴 수 있을 것이다. 이렇게 큰 수를 메모이제이션 하려면, 슬라이딩 윈도 기법을 사용해야한다. 이 기법은 반복적 동적 계획법을 이용해야만 쓸 수 있다. menu(price) = price로 시킬 수 있는 메뉴들의 최대 선호도 합 이 식이 의미하는 ..

1. 완전 탐색 이 문제는 BOARDCOVER에서 문제를 풀었듯이 완전 탐색으로 해결 할 수 있다. 각 차례마다 사용 가능한 모든 블록들을 모든 위치에 넣어보면서 한번이라도 짝수 차례일때 블록을 못넣으면 함수를 종료시키면 된다. 2. 비트 마스크를 사용한 동적 계획법 이 문제는 주어진 게임판의 상태에 따라 승패가 좌우된다. 이전 까지의 블록의 배치와 지금이 누구 차례인지 알 필요 없다는 것이다. 게임판은 5*5배열로 '#' 과 '.' 두 상태가 있으므로 비트마스크로 배열을 하나의 정수로 표현할 수 있다. 이 정수 하나로 메모이제이션이 가능해지고 완전 탐색에서 더욱 수행시간을 최적화 시킬 수 있다. 3. 비트마스크를 사용한 블록 배치 가능 유무성 판단 이 문제에서 블록의 형태는 L자 형과 | 형 ㅡ 형 이..

1. 항상 최선을 다해 게임을 플레이한다. 이 문제는 자신의 차례일 때 항상 최선을 다한다. 다음 차례인 상대의 선택을 고려하면서 선택해야한다는 것이다. 어떻게 해야 최선일까? 자신의 선택한 점수 - 다음턴에 상대방이 선택한 점수 가 최대일때가 최선의 선택이 된다. 2. 재귀 함수 한번 위에 가정한것을 식으로 표현해보자. i는 0~3까지이며 뭘 선택 할 것인지를 나타낸다 0: 맨 왼쪽 선택 => myTurn = board[lo] dlo => +1, dhi => 0 1: 맨 오른쪽 선택 => myTurn = board[hi] dlo => +0, dhi => -1 3: 맨 왼쪽 두개 삭제 => myTurn = 0 dlo => +2, dhi => 0 4. 맨 오른족 두개 삭제 => myTurn = 0 dlo ..