다이나믹프로그래밍
-
알고리즘: 되추적(BackTracking)을 이용한 0 - 1 배낭채우기 문제(0- 1 knapsack problem) 공부하기알고리즘 2020. 11. 15. 00:33
이전에는 동적계획법을 이용하여 0-1 knapsack 문제에 대해 다루었다. 알고리즘: 배낭채우기(knapsack problem) 공부하기!(0-1 knapsack problem) 탐욕 알고리즘과 동적계획법은 최적화 문제를 푸는 두가지 방법이다. 둘 중 어떤 방법을 사용해도 문제를 풀 수 있다. 단일 출발점 최단경로 문제에서는 동적계획법은 모든 마디를 출발점으로 seungjuitmemo.tistory.com 이번 포스팅은 좀 더 효율적인 0-1 knapsack problem 알고리즘에 대해 알아본다. 기존의 0-1 knapsack problem은 상태공간트리에서 되추적을 이용하였다. 이 문제는 최댓값을 구하는 최적화 문제이기때문에 검색이 완전히 끝나기 전까지는 마디가 해답을 포함하고 있는지 알지 못한다...
-
알고리즘: 백준 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..
-
알고리즘: 백준 11048번 이동하기 (feat. python)알고리즘/백준(BaekJoon) 2020. 8. 27. 22:42
백준 11048번 링크입니다. 11048번: 이동하기 준규는 N×M 크기의 미로에 갇혀있다. 미로는 1×1크기의 방으로 나누어져 있고, 각 방에는 사탕이 놓여져 있다. 미로의 가장 왼쪽 윗 방은 (1, 1)이고, 가장 오른쪽 아랫 방은 (N, M)이다. 준규는 �� www.acmicpc.net DFS 인줄 알았지만 시간초과가 나길래 다시 보니 다이나믹프로그래밍이였던 문제 dp를 이차원 리스트로 만들어서 dp[N][M] = (N, M)까지 오기까지의 합이라고 한다면 dp[N][M] = max(dp[N - 1][M], dp[N][M - 1], dp[N - 1][M - 1]) + maze[N][M] 라고 할 수 있다. import sys input = sys.stdin.readline N, M = map(in..
-
알고리즘: 백준 2293번 동전 1 (feat. python)알고리즘/백준(BaekJoon) 2020. 8. 25. 20:51
백준 2293번 링크입니다. 2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net 결론부터 말하면 dp를 이용해 풀어야 풀린다. 시간제한이 0.5초로 dp를 제외한 다른 방법을 쓰기가 까다롭다. 처음에는 dfs를 이용해 풀었지만 시간초과가 나길래 결국은 다른 분의 답을 참고하였다. import sys class Node: # 방문처리를 위해 노드 클래스를 만들었다. def __init__(self, data): self.data = data def dfs(start, tar..
-
알고리즘: 백준 11052번 카드 구매하기(feat.c++)알고리즘/백준(BaekJoon) 2020. 8. 23. 18:13
백준 11052번 링크입니다. 11052번: 카드 구매하기 첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000) www.acmicpc.net 다이나믹 프로그래밍을 이용하면 쉽게 해결할 수 있다. 우선 코딩하기 전에 dp[n]을 말로 정의하는 게 중요하다. dp[n] = n개의 카드를 구매했을 때 최댓값 라고 하자 dp[n]을 구하기 위해서는 다음과 같은 과정을 거친다. (편의상 k번째 dp[n]을 dpk[n]라고 하자) dp1[n] = dp[n - 1] + packs[1] dp2[n] = dp[n - 2] + packs[2] dp3[n] = dp[n - 3] + packs[3] ..
-
알고리즘: 백준 1932번 정수 삼각형 (feat. Python)알고리즘/백준(BaekJoon) 2020. 7. 22. 07:21
최적 부분 구조와 중복되는 부분이 보인다. 다이나믹 프로그래밍으로! 점화식: n 번째 줄 0번째까지의 합 = n - 1번째 줄 0번째까지의 합 + n 번째 줄 0번째 값 n 번째 줄 1번째까지의 합 = max(n - 1번째 줄 0번째까지의 합, n - 1번째 줄 1번째까지의 합) + n번째 줄 1번째 값 n 번째 줄 2번째까지의 합 = max(n - 1번째 줄 1번째까지의 합, n - 1번째 줄 2번째까지의 합) + n번째 줄 2번째 값 ... n 번째 줄 n - 1번째까지의 합 = max(n - 1번째 줄 n - 2번째까지의 합, n - 1번째 줄 n - 1번째까지의 합) + n번째 줄 n - 1번째 값 n 번째 줄 n번째까지의 합 = n - 1번째 줄 n - 1번째까지의 합 + n 번째 줄 n번째 값..
-
알고리즘: 다이나믹 프로그래밍(dynamic programming) 공부하기! (Memorization, Tabulation, 공간최적화)알고리즘 2020. 7. 10. 19:34
다이나믹 프로그래밍(Dynamic Programming)이란? 다이나믹 프로그래밍은 부분 문제들의 답을 중복되지 않게 최적의 방법으로 구하고 이를 통해 기존의 답을 구하는 방식이다. 정리하자면 어떤 한 문제가 최적부분구조와 중복되는 부분 문제가 있을 때 동적 프로그래밍을 사용하면 효율적이다. (두 조건을 만족하지 않아도 다이나믹 프로그래밍을 할 수 있다.) → 최적부분구조(Optimal substructure) 어떤 문제가 최적 부분구조로 이루어져 있을 때, 부분 문제들의 최적의 답을 구해서 기존 문제의 최적의 답을 구할 수 있다. 예를 들면, 최단경로를 찾는 문제가 있다. → 중복되는 부분 문제(Overlapping subproblems) 주로 재귀(recursion)을 사용하는 경우, 중복되는 문제들..