동적프로그래밍
-
알고리즘: Dynamic programming을 이용한 이항계수(Binomial Coefficient) (feat.c++)알고리즘 2020. 10. 2. 15:39
이항계수는 다음과 같이 표현되며 다음과 같은 성질을 따른다. int binomial(int n, int k) { if (k == 0 || k == n) { return 1; } return binomial(n - 1, k) + binomial(n - 1, k - 1); } 이렇게 간단하게 구현 가능하지만, 효율적이지는 않다. 알고리즘을 재귀호출하면서 이미 했던 계산을 반복해서 수행하기 때문이다 하지만 동적프로그래밍을 이용하면 중복되는 부분을 커버하여 효율적인 알고리즘을 만들 수 있다. Divide and conquer가 top-down 방식이였다면 dyna..
-
알고리즘: 백준 2565번 전깃줄 (feat. c++) 최장증가수열문제(LIS)알고리즘 2020. 8. 31. 22:41
백준 2565번 문제입니다. 2565번: 전깃줄 첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결되는 www.acmicpc.net 좀 꼬아놓은 최장증가 수열 문제 (사실 최장증가수열문제는 처음 접해보았다...) 처음에는 파이썬으로 스택을 이용해서 풀었지만 무슨 이유인지 틀렸다고 나왔다... (틀린 코드) n = int(input()) line_list = [] for i in range(n): line_list.append(list(map(int, input().split()))) del_count = 0 while True: cross = [] for i in ran..
-
알고리즘: 백준 11057번 오르막 수 (feat. c++)알고리즘/백준(BaekJoon) 2020. 8. 24. 11:45
백준 11057 링크입니다. 11057번: 오르막 수 오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다. 예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다. 수� www.acmicpc.net 다이나믹 프로그래밍을 이용하면 쉽지만 어떤 구조를 이용하면 좋을지가 가장 어렵다. dp를 이차원리스트로 해서 dp[i][j] = 길이가 i인 끝자리수가 j인 오르막 수 라고 하면 쉽게 해결할 수 있다. (끝자리수를 기준으로 나누는게 포인트) i는 1 ~ 1000 j는 0 ~ 9까지 가능하다 예를 들어 dp[2][3]을 구한다고 하면 dp[2][3] = dp[1][2] + dp[1][1] + dp[1..
-
알고리즘: 다이나믹 프로그래밍(dynamic programming) 공부하기! (Memorization, Tabulation, 공간최적화)알고리즘 2020. 7. 10. 19:34
다이나믹 프로그래밍(Dynamic Programming)이란? 다이나믹 프로그래밍은 부분 문제들의 답을 중복되지 않게 최적의 방법으로 구하고 이를 통해 기존의 답을 구하는 방식이다. 정리하자면 어떤 한 문제가 최적부분구조와 중복되는 부분 문제가 있을 때 동적 프로그래밍을 사용하면 효율적이다. (두 조건을 만족하지 않아도 다이나믹 프로그래밍을 할 수 있다.) → 최적부분구조(Optimal substructure) 어떤 문제가 최적 부분구조로 이루어져 있을 때, 부분 문제들의 최적의 답을 구해서 기존 문제의 최적의 답을 구할 수 있다. 예를 들면, 최단경로를 찾는 문제가 있다. → 중복되는 부분 문제(Overlapping subproblems) 주로 재귀(recursion)을 사용하는 경우, 중복되는 문제들..