다이나믹 프로그래밍

[python3] 백준 7579 (앱 , DP)

우선 A,B,C,D,E 프로세스가 존재할때 메모리크기와 코스트가 존재하기 때문에 언제 최소한의 코스트를 사용하며 60이상의 메모리가 확보되는지 확인하기 위해서는 모든 경우의 수를 확인해야한다. A 활성화 비활성화 B 활성화 비활성화 C 활성화 비활성화 D 활성화 비활성화 E 활성화 비활성화 그럼 결과적으로 2**5의 경우의 수가 존재한다. 그런데 N값이 100이므로 2**100의 경우가 존재하는데 이걸 전부 확인하는 것은 말이 안된다. 따라서 백트래킹이나, DP 처럼 쳐낼수 있는 경우를 쳐내는 방식으로 진행해야한다. 그런데 이 문제는 냅색문제처럼 무게와 가중치가 존재하는 문제이다. 따라서 냅색의 알고리즘을 활용하면 되겠다는 생각이 들었다. 냅색의 경우는 무게 제한이 있었기 때문에 dp[i][w]로 2차원..

[dp] 모듈러 분배법칙

코딩테스트를 풀다보면 결과 값이 매우 큰 경우 값의 나머지를 구하라는 문제가 자주 출제된다. 단순히 결과 값에 모듈러 연산을 수행하면 이미 결과값이 너무 커져서 오버플로우가 발생하거나 연산에 시간이 오래 걸리는 경우바 발생한다. 따라서 이럴때 연산 과정 중간에 모듈러 연산을 적용해야 한다. 연산 과정중에 모듈러 연산을 적용하기 위해서는 모듈러 연산의 분배법칙에 대해 알아야한다. 각 피연산자에 모듈러 연산을 취하고 계산 결과에 다시한번 모듈러 연산을 취하면 된다. ( dp[i] + dp[j] ) % C = ( dp[i]%C + dp[j]%C ) %C와 같다. 모듈러 연산의 분배법칙은 덧셈+, 뺄셈-, 곱셈* 에만 적용이 가능하고 나머지 연산에 대해서는 분배법칙을 적용할 수 없다.

[python3] 백준 2293 풀이 ( 동전 1, 다이나믹 프로그래밍 )

아주 상당히 헤매면서 풀었다. 실버 1이라 어려울 것이라 생각했는데 정답비율이 높았다. 난이도는 높지만 알고리즘만 이해하면 코드 구현을 쉬웠기 때문인거 같다. 우선 나는 노가다를 해가며 풀었다. k가 1일때부터 1,2,5가 가능한 조합을 전부 때려 넣어가며 숫자를 보았는데 규칙 일랑 하나도 보이지 않았다. 그래서 덩어리를 생각하며 풀어보기로 했다. 그래서 생각한 것이 이차원 배열로 나타내는 것이었다. 문제에서 주어진 예제가 아닌 다른 예제로 생각해 보겠다. 2 10 2 3 K 0 1 2 3 4 5 6 7 8 9 10 2 1 0 1 0 1 0 1 0 1 0 1 3 coin이 2인경우 k값에 따라 만들 수 있는 경우는 2로 나누어 떨어지는 경우이다. 이때는 2만 들어 가기 때문에 한가지 경우만 존재한다. 따..

[python3] 백준 10844 풀이 ( 쉬운 계단 수, 다이나믹 프로그래밍, 이차 배열)

이번 문제 너무 어려웠다. 이것저것 해보다가 결국 해설을 봐버렸지만 그냥 외워서 체득시켜 놓아야 겠다. 솔직히 이거 못풀었다. 그래서 해설을 보고 이해하고 풀게 되었다. 처음에는 노가다로 갯수를 구해보았다. 9, 17, 32, 61까지 구했고 먼가 규칙이 있는듯 했지만 결과만으로는 규칙을 찾을 수 없었다. 그래서 끝자리를 배열에 넣어 개수를 확인하는 방식을 사용해보았다. 그러나 이렇게 풀면 시간초과가 났다. 알고보니 배열을 2차원 배열을 만들어 각 숫자별 개수를 저장하여 푸는 방법이 존재했다. 예를 들어 끝자리가 가능한 숫자는 0~9까지 이다. 따라서 이에 대한 배열을 만든다. 그리고 N=1일때 가능한경우에 1을 채워준다. 0은 시작부분에 나올수 없기 때문에 0이 되고 나머지는 가능하므로 1을 채울 수 ..

백준 9251 풀이 (LCS, 다이나믹 프로그래밍)

LCS는 Longest Common Subsequence라고 한다. 최장 공통 부분 수열.....이름부터 먼가 심상치 않다. 두 수열이 주어질때 공통으로 가장 긴 부분 수열을 찾는 알고리즘이다. C와 ACAYKP를 비교한다고 생각하고 2차원 배열을 만든다. 이후에 CA, CAP, CAPC....등으로 확장해나간다. 그러면 아래와 같은 2차원 배열이 생성된다. 0 A C A Y K P 0 0 0 0 0 0 0 0 C 0 0 1 1 1 1 1 A 0 1 1 2 2 2 2 P 0 1 1 2 2 2 3 C 0 1 2 2 2 2 3 A 0 1 2 3 3 3 3 K 0 1 2 3 3 4 4 이때 확인 할 수 있는 것은 다음과 같다.(파랑색은 증가한 경우, 빨강색은 알파벳이 같아도 증가하지 않는경우) 1. 알파벳이 ..

백준 11054 풀이 (가장 긴 바이토닉 부분 수열, 다이나믹 프로그래밍)

이번에는 저번 시간에 풀었던 11053을 응용한 문제를 풀어보자. 처음 보면 솔직히 나야 역시나 무슨 말인지 몰라서 2~3번은 더 읽어보았다. 간단히 요약하자면 S1 Sk+1 > ... SN-1 > SN 과 같은 수열의 형태인 바이토닉 부분 수열을 찾되 가장 긴 부분 수열을 찾아보자는 것이다. 11053번에서 나는 오름차순으로 가장 긴 부분 수열을 찾을 수 있었다. 11054는 내림차순을 구해보라는 문제이다. 일단 문제를 풀기에 앞서 표를 그리며 생각해본다. number 1 5 2 1 4 3 4 5 2 1 dp (->) 1 2 2 ... ..... ... 4 5 2 1 dp2 ( dp[target]: dp[target] = dp[i] + 1 target2 = le..

다이나믹 프로그래밍(동적 계획법)

다이나믹 프로그래밍이란 동적 계획법이라고 한다. 간단히 설명하자면 어떠한 문제를 한번에 해결하기 어렵기 때문에 작은 문제로 쪼개어 작은것 부터 하나씩 해결하여, 마지막에 문제를 해결하는 것이다. 솔직히 무슨 말인지 바로 와닿지 않는다. 그러나 원래 모를때는 일단 들으면서 알때까지 자료를 찾아보면 얼추 이해가 되기 마련이다. 다이나믹 프로그래밍에는 2가지가 존재한다. 1. Bottom-up : 작은 문제를 처음부터 풀어가는 방식이다. 주로 점화식을 세우고 for 구문으로 빠르게 해결해준다.(리스트나 배열에 직관적으로 구할 수 있는 값들이 넣어넣고 for 구문을 시작한다.) 2. Top-down : 재귀함수로 주로 구현하기 때문에 큰 문제를 풀기위해 작은 문제로 파고들어가서 작은 문제를 해결하면서 큰문제를 ..