DP

[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] 백준 1005 풀이 ( ACM Craft, 위상정렬, 다이나믹 프로그래밍, DP )

상당히 헤맸던 문제다. 갈피를 못 잡다가 문제의 알고리즘 분류를 힌트로 보고 방향성을 잡을 수 있었다. 그럼 문제를 보자 문제를 읽어보면 건물의 순서가 주어진다. 이때 목표하는 건물을 만들기까지 걸리는 최소 시간을 출력한다. 보면 건물의 순서가 그래프로 주어지기 때문에 사이클이 존재하지 않는다. 즉, DAG그래프처럼 보인다. 그럼 당연히 자연스럽게도 위상정렬이 떠오른다. 그럼 생각을 해본다. 위상정렬은 BFS처럼 동작한다. 큐에서 노드를 뽑고, 노드의 out degree접선을 제거하면서 진행한다. 그리고 만약 한 노드의 in degree접선이 0이라면 큐에 넣는다. 위상정렬의 원리는 아래의 글을 읽으면 된다. [python3] 백준 2252 풀이 ( 줄세우기, 위상정렬, DAG, 그래프 ) 위상정렬 어떤..

[python3] 백준 1520 풀이 ( 내리막길, DP, DFS, 그래프 )

이번 문제 풀이 사실 봐버렸다. 거의 풀었다고 생각했는데 내가 생각한 방법으로는 도저히 풀리지가 않아서 그냥 풀이를 봤다. 바로 문제를 보자 문제를 읽어보면 낮은 방향으로만 진행한다고 한다. -> 사이클이 존재하지 않는 그래프이다. 가장 빠른게 도착하는게 아닌 도착하는 경우의 수를 구한다. -> BFS가 아닌 DFS를 여러 번 써야한다. 문제를 통해 2가지를 확인할 수 있다. 그런데 DFS만을 쓰는 경우에는 너무 많은 케이스가 존재한다. 실제로 DFS만으로 제출한다면 시간초과가 뜬다. 따라서 DFS만이 아닌 DP를 함께 활용해 주어야한다. 그럼 DP를 어떻게 활용해야 할지 고민을 해본다. DFS만 써서 시간초과가 나는 것은 빙빙 돌아 목적지에 도착하는 경우까지 기다려야 하기 때문이다. 그렇다면 빙빙 돌아..

[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] 백준 9465 풀이 ( 스티커, 다이나믹 프로그래밍, 이차원 배열 )

문제를 쓱 읽어 보면 DP의 냄새가 솔솔솔~ 난다. 딱 봐도 그리디로 풀 수 없고 완전 탐색을 진행해야만 풀 수 있는 상황이다. 그렇다면 역시 DP로 풀어야한다. DP로 풀기 위해서는 다음 단계에 영향을 미쳐야 한다. 즉, 선택한 스티커의 상하좌우에 위치한 다른 스티커를 선택할 수 없다. 우선 dp를 이차원배열이라 한다. 또한 dp에는 각 행별로 열까지의 최댓값을 가진다. 따라서 천천히 생각해보자 만약 0열의 i를 뽑을 것이라면 0열의 dp[0][i-1]을 뽑을 수 없다. 따라서 0열이 아닌 1열의 i-1까지인 dp[1][i-1]을 더할 수 있다. 그러면 식은 dp[0][i] = dp[1][i-1] 이다. 또한 한가지를 더 생각해 보아야 한다. i-1의 열의 스티커의 값이 형편 없다면 이걸 무시하고 i-..

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

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

[c++] 백준 1753 풀이 ( 최단 경로, 다익스트라, 그래프, 우선순위 )

다익스트라 다익스트라는 다이나믹 프로그래밍을 활용한 최단경로 탐색 알고리즘이다. 단일 시작점 알고리즘에 속하여 시작점을 기준으로 각 노드까지의 최단 거리를 알 수 있다. 이때 시간 복잡도를 줄이기 위해 우선순위 큐를 활용하면 좋다. 음수 간선이 없을때 사용 (음수가 있으면 벨만-포드나 플로이드를 사용하는게 좋다) 우선순위 큐를 활용 단일 시작점 알고리즘 다익스트라 알고리즘은 BFS처럼 동작한다. 시작점에서부터 BFS탐색을 진행한다. 단, 우선순위 큐에서 노드를 뽑을때는 간선의 가중치가 가장 낮은 노드를 뽑는다.(우선순위 큐에 {-가중치,노드} 형태로 넣으면 된다.) 해당 노드와 접한 노드를 뽑아서 dp에 최단경로를 메모이제이션한다. 이후 최단경로 가중치를 노드와 함께 큐에 넣고 루프를 돌며 반복한다. 문..