dynamicprogramming 【개인 메모】초초심자적 동적 계획법～피보나치 수열～ 정적 최적화로 문제를 해결했지만 처리하는 데이터 크기가 커지면 계산이 불가능 해지기 때문에 동적 계획법을 도입하고 싶다. MATLAB에서 할 것입니다. 이번에는 가장 간단한 곳에서 피보나치 수열을 구현하려고합니다. 근처에서 공부한 피보나치 수열. 피보나치 수열의 점화식에 따라 솔직하게 실장하면 다음과 같다. 위의 솔직한 방법에서는 n 번째를 계산하기 위해 n-1 번째와 n-2 번째를 계산해야... 동적 계획법dynamicprogrammingmatlab Kadane의 알고리즘을 사용한 최대 하위 배열 합계 문제 설명 FAANG이나 대기업에 취직하고 훌륭한 프로그래머가 되기 위해 동적 프로그래밍 관련 문제를 해결하는 것 외에 다른 대안은 없습니다. 우리 개발자들은 종종 문제 해결을 무시하고 개발에만 집중하려고 하지만 실생활의 큰 생산 문제를 해결하거나 무언가를 최적화하려면 아주 좋은 문제 해결사가 되어야 한다는 것을 기억해야 합니다. 그래서 이 점을 염두에 두고 동적 프로그래밍 관련 문제를 해결하기 시작했... kadanealgorithmdynamicprogrammingproblemsolving LEETCode 21일간의 동적 프로그래밍 ** 13일차** 최소 낙하 경로 해시맵 사용 10일차 Airtmetic 슬라이스 디코드 방법: 우리는 subString Intger.Parseint(s.substring(i-1, i+1)을 사용할 수 있습니다. i-1에서 i+1까지 주목해야 할 지점은 i-1과 1의 범위를 포함합니다. 예:(2,5 )-> 2,3,4 5일차 4일차 3일차 2일차: 1일차 문제 1: 피보나치 수열 문제 2: n... leetcodejavacodingdynamicprogramming 점프 게임 리트코드 문제 정수 배열 숫자가 제공됩니다. 처음에는 배열의 첫 번째 인덱스에 위치하며 배열의 각 요소는 해당 위치에서의 최대 점프 길이를 나타냅니다. 마지막 인덱스에 도달할 수 있으면 true를 반환하고 그렇지 않으면 false를 반환합니다. 예 1: Input: nums = [2,3,1,1,4] Output: true Explanation: Jump 1 step from index 0 to 1, the... javadynamicprogrammingleetcode 점프 게임 II leetcode 문제 음수가 아닌 정수 nums의 배열이 주어지면 초기에 배열의 첫 번째 인덱스에 배치됩니다. 배열의 각 요소는 해당 위치에서의 최대 점프 길이를 나타냅니다. 귀하의 목표는 최소 점프 횟수로 마지막 인덱스에 도달하는 것입니다. 항상 마지막 색인에 도달할 수 있다고 가정할 수 있습니다. 예 1: Input: nums = [2,3,1,1,4] Output: 2 Explanation: The minim... javadynamicprogrammingdp Cherry Pickup II Leetcode 문제 체리 필드를 나타내는 행 x 열 매트릭스 그리드가 제공되며 여기서 grid[i][j]는 (i, j) 셀에서 수집할 수 있는 체리 수를 나타냅니다. 체리를 수집할 수 있는 두 대의 로봇이 있습니다. 로봇 #1은 왼쪽 상단 모서리(0, 0)에 있으며 로봇 #2는 오른쪽 상단 모서리에 있습니다(0, 열 - 1). 아래 규칙에 따라 두 로봇을 사용하여 체리 수집의 최대 수를 반환합니다. 셀 (i, ... javaalogorithmdynamicprogramming 문자열 회문을 만드는 데 필요한 최소 삽입 단계(LCS와 동일) 문제: 주어진 문자열 s . 한 번에 문자열의 모든 인덱스에 모든 문자를 삽입할 수 있습니다. s 회문을 만들기 위한 최소 단계 수를 반환합니다. Palindrome 문자열은 앞뒤로 같은 문자열을 읽는 것입니다. 예 1: 해결책: 표 방식 시간복잡도 : O(n*m), 공간복잡도 : o(n*m) for dp array... javadynamicprogrammingalgorithms 최소 비용 등반 계단 비용[i]이 계단에서 i번째 단계의 비용인 정수 배열 비용이 주어집니다. 비용을 지불하면 한 단계 또는 두 단계를 오를 수 있습니다. 인덱스가 0인 단계에서 시작하거나 인덱스가 1인 단계에서 시작할 수 있습니다. 바닥에 도달하기 위한 최소 비용을 반환합니다.... cppleetcodedynamicprogramming 0-1 배낭 문제 형제인 fractional knapsack과 달리, greedy는 이 문제에 대한 최적의 솔루션을 보장하지 않습니다. 여기서 우리는 물건을 집어들거나 그냥 둘 수 있습니다. 물체의 일부를 선택할 수 없습니다. 우리의 목표는 maxWeight를 초과하지 않는다는 점을 염두에 두면서 가장 가치가 높고 가중치가 가장 적은 개체를 선택하여 이러한 개체에서 최대 이익을 얻는 것입니다. 이 경우 가중치... algorithmsdynamicprogrammingdatastructuresknapsack <Baekjoon> #1520 Dyamic Programming, DFS_내리막 길 c++ 처음 칸에서 상하좌우 이웃한 곳을 탐색해서 제일 아래 칸으로 내려간다는 점에서 dfs를 이용해 풀어야 한다는 것을 알 수 있다 처음에 dfs만을 이용해 풀었다가 시간 초과가 났다. map의 크기가 최대 500*500이므로 완전탐색 dfs 방법으로 풀면 최악의 경우 4^(500*500)의 탐색을 해야한다 => DFS + DP 방법으로 해결한다 Initialize dp 동적 계획법 알고리즘을 만... DFSdynamicprogrammingbaekjoonalgorithmDFS DynamicProgramming_1_02_피보나치 수2(2748) 피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다. 이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 된다. n=17일때 까지 피보나치 수를 써보면 다음과 같다. n이 주어졌을 때, n번째 피보나치 수를 구하는 프로그램을 작성하시오. 첫째 줄에 n이 주어진다. n은 20... iron1dynamicprogrammingbaekjoonalgorithmalgorithm DynamicProgramming_1_03_다리놓기(1010) 재원이는 한 도시의 시장이 되었다. 이 도시에는 도시를 동쪽과 서쪽으로 나누는 큰 일직선 모양의 강이 흐르고 있다. 하지만 재원이는 다리가 없어서 시민들이 강을 건너는데 큰 불편을 겪고 있음을 알고 다리를 짓기로 결심하였다. 강 주변에서 다리를 짓기에 적합한 곳을 사이트라고 한다. 재원이는 강 주변을 면밀히 조사해 본 결과 강의 서쪽에는 N개의 사이트가 있고 동쪽에는 M개의 사이트가 있다는 ... silver5dynamicprogrammingbaekjoonalgorithmalgorithm Leetcode 70. Climbing Stairs Python3 풀이 계단수가 0 일때, 0 1일때, 1 2일때, 2 3일때, 3 4일때, 5 5일때, 8 이다. 현재 n의 전과 전전의 결과를 더하면 현재 가능한 경우의 수이다.... leetcodePython3dynamicprogrammingPython3 DynamicProgramming_1_04_돌 게임(9655) 돌 게임은 두 명이서 즐기는 재밌는 게임이다. 탁자 위에 돌 N개가 있다. 상근이와 창영이는 턴을 번갈아가면서 돌을 가져가며, 돌은 1개 또는 3개 가져갈 수 있다. 마지막 돌을 가져가는 사람이 게임을 이기게 된다. 두 사람이 완벽하게 게임을 했을 때, 이기는 사람을 구하는 프로그램을 작성하시오. 게임은 상근이가 먼저 시작한다. 첫째 줄에 N이 주어진다. (1 ≤ N ≤ 1000) 상근이가 ... algorithmsilver5baekjoondynamicprogrammingalgorithm DynamicProgramming_1_05_Four Squares(17626) 라그랑주는 1770년에 모든 자연수는 넷 혹은 그 이하의 제곱수의 합으로 표현할 수 있다고 증명하였다. 어떤 자연수는 복수의 방법으로 표현된다. 예를 들면, 26은 52과 12의 합이다; 또한 42 + 32 + 12으로 표현할 수도 있다. 역사적으로 암산의 명수들에게 공통적으로 주어지는 문제가 바로 자연수를 넷 혹은 그 이하의 제곱수 합으로 나타내라는 것이었다. 1900년대 초반에 한 암산가... algorithmbaekjoonsilver4dynamicprogrammingalgorithm DynamicProgramming_1_06_1로 만들기(1463) 정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다. X가 3으로 나누어 떨어지면, 3으로 나눈다. X가 2로 나누어 떨어지면, 2로 나눈다. 1을 뺀다. 정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오. 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. 첫째 줄에 연산을 하... algorithmbaekjoondynamicprogrammingsilver3algorithm <Baekjoon>#1699 제곱수의 합 (Sum of square number) c++ 문제만 봐서는 아무런 아이디어도 떠오르지 않아서 표에 채워 넣어가면서 규칙을 찾아보려 했다. 여기서 얻었던 몇 개의 단서는 dp[1]=1 dp[i*i]=1 (어떤 수의 제곱 수는 1) dp[3]=dp[3-1*1]+1 dp[5]=dp[5-2*2]+1 dp[6]=dp[6-2*2]+1 이런 규칙을 찾을 수 있다 (여기서 +1이란 1*1 의미가 아니라 1개를 의미한다) 하지만 항상 dp[N]에서 N... dynamicprogrammingalgorithmbaekjoonalgorithm <Baekjoon>#14002가장 긴 증가하는 부분 수열4 (Longest increasing subsequence 4) c++ 바로 앞에서 풀었던 문제가 부분 수열의 길이만 출력하는 거라면, 이번에는 가장 긴 증가하는 부분수열도 출력해야 한다. dp의 값이 가장 큰 A의 값부터 시작해서 하나씩 작아지게 역순으로 B에 push_back 한다. (처음에 dp의 값이 가장 작은 A값부터 B에 push를 했다가 한참을 헤맸다..) dp[5]=4 A[5]=50의 값을 B에 push dp[3]=3 A[3]=30의 값을 B에 p... baekjoonalgorithmLISdynamicprogrammingLIS <종만북> 08. 동적계획법_비대칭 타일링 (Asymmetric Tiling) c++ 먼저 비대칭 타일링 문제를 풀기 위해서는 앞에서 공부했던 타일링 방법의 수 세는 알고리즘을 복습할 필요가 있다. 2xn 사각형을 채우는 방법들은 맨 오른 쪽이 어떻게 채워져 있느냐로 나눌 수 있다. a는 마지막 타일의 가로길이가 1인 경우, b와 c는 마지막 타일의 가로 길이가 2인 경우이다. a와 c는 본질적으로 동일 하기 때문에 tiling(n)=1xtiling(n-1) + 1xtilin... Tiling종만북algorithmalgospotdynamicprogrammingTiling <Baekjoon>#1149 RGB 거리 (RGB street) c++ 먼저 dp[N][3] 이렇게 만들어 줄거다. 행에는 n번째 집, 열에는 RGB의 값을 넣어준다. dp[0][0]= 1번 집이 R를 색칠했을 경우 비용의 최솟값, dp[0][1]= 1번 집이 G를 색칠했을 경우 비용의 최솟값, dp[0][2]= 1번 집이 B를 색칠했을 경우 비용의 최솟값... 을 차례로 저장한다 먼저 처음 dp에 각 집을 R,G,B로 칠하는 비용을 입력받으면서 저장한다. 그 ... baekjoonalgorithmdynamicprogrammingalgorithm
【개인 메모】초초심자적 동적 계획법～피보나치 수열～ 정적 최적화로 문제를 해결했지만 처리하는 데이터 크기가 커지면 계산이 불가능 해지기 때문에 동적 계획법을 도입하고 싶다. MATLAB에서 할 것입니다. 이번에는 가장 간단한 곳에서 피보나치 수열을 구현하려고합니다. 근처에서 공부한 피보나치 수열. 피보나치 수열의 점화식에 따라 솔직하게 실장하면 다음과 같다. 위의 솔직한 방법에서는 n 번째를 계산하기 위해 n-1 번째와 n-2 번째를 계산해야... 동적 계획법dynamicprogrammingmatlab Kadane의 알고리즘을 사용한 최대 하위 배열 합계 문제 설명 FAANG이나 대기업에 취직하고 훌륭한 프로그래머가 되기 위해 동적 프로그래밍 관련 문제를 해결하는 것 외에 다른 대안은 없습니다. 우리 개발자들은 종종 문제 해결을 무시하고 개발에만 집중하려고 하지만 실생활의 큰 생산 문제를 해결하거나 무언가를 최적화하려면 아주 좋은 문제 해결사가 되어야 한다는 것을 기억해야 합니다. 그래서 이 점을 염두에 두고 동적 프로그래밍 관련 문제를 해결하기 시작했... kadanealgorithmdynamicprogrammingproblemsolving LEETCode 21일간의 동적 프로그래밍 ** 13일차** 최소 낙하 경로 해시맵 사용 10일차 Airtmetic 슬라이스 디코드 방법: 우리는 subString Intger.Parseint(s.substring(i-1, i+1)을 사용할 수 있습니다. i-1에서 i+1까지 주목해야 할 지점은 i-1과 1의 범위를 포함합니다. 예:(2,5 )-> 2,3,4 5일차 4일차 3일차 2일차: 1일차 문제 1: 피보나치 수열 문제 2: n... leetcodejavacodingdynamicprogramming 점프 게임 리트코드 문제 정수 배열 숫자가 제공됩니다. 처음에는 배열의 첫 번째 인덱스에 위치하며 배열의 각 요소는 해당 위치에서의 최대 점프 길이를 나타냅니다. 마지막 인덱스에 도달할 수 있으면 true를 반환하고 그렇지 않으면 false를 반환합니다. 예 1: Input: nums = [2,3,1,1,4] Output: true Explanation: Jump 1 step from index 0 to 1, the... javadynamicprogrammingleetcode 점프 게임 II leetcode 문제 음수가 아닌 정수 nums의 배열이 주어지면 초기에 배열의 첫 번째 인덱스에 배치됩니다. 배열의 각 요소는 해당 위치에서의 최대 점프 길이를 나타냅니다. 귀하의 목표는 최소 점프 횟수로 마지막 인덱스에 도달하는 것입니다. 항상 마지막 색인에 도달할 수 있다고 가정할 수 있습니다. 예 1: Input: nums = [2,3,1,1,4] Output: 2 Explanation: The minim... javadynamicprogrammingdp Cherry Pickup II Leetcode 문제 체리 필드를 나타내는 행 x 열 매트릭스 그리드가 제공되며 여기서 grid[i][j]는 (i, j) 셀에서 수집할 수 있는 체리 수를 나타냅니다. 체리를 수집할 수 있는 두 대의 로봇이 있습니다. 로봇 #1은 왼쪽 상단 모서리(0, 0)에 있으며 로봇 #2는 오른쪽 상단 모서리에 있습니다(0, 열 - 1). 아래 규칙에 따라 두 로봇을 사용하여 체리 수집의 최대 수를 반환합니다. 셀 (i, ... javaalogorithmdynamicprogramming 문자열 회문을 만드는 데 필요한 최소 삽입 단계(LCS와 동일) 문제: 주어진 문자열 s . 한 번에 문자열의 모든 인덱스에 모든 문자를 삽입할 수 있습니다. s 회문을 만들기 위한 최소 단계 수를 반환합니다. Palindrome 문자열은 앞뒤로 같은 문자열을 읽는 것입니다. 예 1: 해결책: 표 방식 시간복잡도 : O(n*m), 공간복잡도 : o(n*m) for dp array... javadynamicprogrammingalgorithms 최소 비용 등반 계단 비용[i]이 계단에서 i번째 단계의 비용인 정수 배열 비용이 주어집니다. 비용을 지불하면 한 단계 또는 두 단계를 오를 수 있습니다. 인덱스가 0인 단계에서 시작하거나 인덱스가 1인 단계에서 시작할 수 있습니다. 바닥에 도달하기 위한 최소 비용을 반환합니다.... cppleetcodedynamicprogramming 0-1 배낭 문제 형제인 fractional knapsack과 달리, greedy는 이 문제에 대한 최적의 솔루션을 보장하지 않습니다. 여기서 우리는 물건을 집어들거나 그냥 둘 수 있습니다. 물체의 일부를 선택할 수 없습니다. 우리의 목표는 maxWeight를 초과하지 않는다는 점을 염두에 두면서 가장 가치가 높고 가중치가 가장 적은 개체를 선택하여 이러한 개체에서 최대 이익을 얻는 것입니다. 이 경우 가중치... algorithmsdynamicprogrammingdatastructuresknapsack <Baekjoon> #1520 Dyamic Programming, DFS_내리막 길 c++ 처음 칸에서 상하좌우 이웃한 곳을 탐색해서 제일 아래 칸으로 내려간다는 점에서 dfs를 이용해 풀어야 한다는 것을 알 수 있다 처음에 dfs만을 이용해 풀었다가 시간 초과가 났다. map의 크기가 최대 500*500이므로 완전탐색 dfs 방법으로 풀면 최악의 경우 4^(500*500)의 탐색을 해야한다 => DFS + DP 방법으로 해결한다 Initialize dp 동적 계획법 알고리즘을 만... DFSdynamicprogrammingbaekjoonalgorithmDFS DynamicProgramming_1_02_피보나치 수2(2748) 피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다. 이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 된다. n=17일때 까지 피보나치 수를 써보면 다음과 같다. n이 주어졌을 때, n번째 피보나치 수를 구하는 프로그램을 작성하시오. 첫째 줄에 n이 주어진다. n은 20... iron1dynamicprogrammingbaekjoonalgorithmalgorithm DynamicProgramming_1_03_다리놓기(1010) 재원이는 한 도시의 시장이 되었다. 이 도시에는 도시를 동쪽과 서쪽으로 나누는 큰 일직선 모양의 강이 흐르고 있다. 하지만 재원이는 다리가 없어서 시민들이 강을 건너는데 큰 불편을 겪고 있음을 알고 다리를 짓기로 결심하였다. 강 주변에서 다리를 짓기에 적합한 곳을 사이트라고 한다. 재원이는 강 주변을 면밀히 조사해 본 결과 강의 서쪽에는 N개의 사이트가 있고 동쪽에는 M개의 사이트가 있다는 ... silver5dynamicprogrammingbaekjoonalgorithmalgorithm Leetcode 70. Climbing Stairs Python3 풀이 계단수가 0 일때, 0 1일때, 1 2일때, 2 3일때, 3 4일때, 5 5일때, 8 이다. 현재 n의 전과 전전의 결과를 더하면 현재 가능한 경우의 수이다.... leetcodePython3dynamicprogrammingPython3 DynamicProgramming_1_04_돌 게임(9655) 돌 게임은 두 명이서 즐기는 재밌는 게임이다. 탁자 위에 돌 N개가 있다. 상근이와 창영이는 턴을 번갈아가면서 돌을 가져가며, 돌은 1개 또는 3개 가져갈 수 있다. 마지막 돌을 가져가는 사람이 게임을 이기게 된다. 두 사람이 완벽하게 게임을 했을 때, 이기는 사람을 구하는 프로그램을 작성하시오. 게임은 상근이가 먼저 시작한다. 첫째 줄에 N이 주어진다. (1 ≤ N ≤ 1000) 상근이가 ... algorithmsilver5baekjoondynamicprogrammingalgorithm DynamicProgramming_1_05_Four Squares(17626) 라그랑주는 1770년에 모든 자연수는 넷 혹은 그 이하의 제곱수의 합으로 표현할 수 있다고 증명하였다. 어떤 자연수는 복수의 방법으로 표현된다. 예를 들면, 26은 52과 12의 합이다; 또한 42 + 32 + 12으로 표현할 수도 있다. 역사적으로 암산의 명수들에게 공통적으로 주어지는 문제가 바로 자연수를 넷 혹은 그 이하의 제곱수 합으로 나타내라는 것이었다. 1900년대 초반에 한 암산가... algorithmbaekjoonsilver4dynamicprogrammingalgorithm DynamicProgramming_1_06_1로 만들기(1463) 정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다. X가 3으로 나누어 떨어지면, 3으로 나눈다. X가 2로 나누어 떨어지면, 2로 나눈다. 1을 뺀다. 정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오. 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. 첫째 줄에 연산을 하... algorithmbaekjoondynamicprogrammingsilver3algorithm <Baekjoon>#1699 제곱수의 합 (Sum of square number) c++ 문제만 봐서는 아무런 아이디어도 떠오르지 않아서 표에 채워 넣어가면서 규칙을 찾아보려 했다. 여기서 얻었던 몇 개의 단서는 dp[1]=1 dp[i*i]=1 (어떤 수의 제곱 수는 1) dp[3]=dp[3-1*1]+1 dp[5]=dp[5-2*2]+1 dp[6]=dp[6-2*2]+1 이런 규칙을 찾을 수 있다 (여기서 +1이란 1*1 의미가 아니라 1개를 의미한다) 하지만 항상 dp[N]에서 N... dynamicprogrammingalgorithmbaekjoonalgorithm <Baekjoon>#14002가장 긴 증가하는 부분 수열4 (Longest increasing subsequence 4) c++ 바로 앞에서 풀었던 문제가 부분 수열의 길이만 출력하는 거라면, 이번에는 가장 긴 증가하는 부분수열도 출력해야 한다. dp의 값이 가장 큰 A의 값부터 시작해서 하나씩 작아지게 역순으로 B에 push_back 한다. (처음에 dp의 값이 가장 작은 A값부터 B에 push를 했다가 한참을 헤맸다..) dp[5]=4 A[5]=50의 값을 B에 push dp[3]=3 A[3]=30의 값을 B에 p... baekjoonalgorithmLISdynamicprogrammingLIS <종만북> 08. 동적계획법_비대칭 타일링 (Asymmetric Tiling) c++ 먼저 비대칭 타일링 문제를 풀기 위해서는 앞에서 공부했던 타일링 방법의 수 세는 알고리즘을 복습할 필요가 있다. 2xn 사각형을 채우는 방법들은 맨 오른 쪽이 어떻게 채워져 있느냐로 나눌 수 있다. a는 마지막 타일의 가로길이가 1인 경우, b와 c는 마지막 타일의 가로 길이가 2인 경우이다. a와 c는 본질적으로 동일 하기 때문에 tiling(n)=1xtiling(n-1) + 1xtilin... Tiling종만북algorithmalgospotdynamicprogrammingTiling <Baekjoon>#1149 RGB 거리 (RGB street) c++ 먼저 dp[N][3] 이렇게 만들어 줄거다. 행에는 n번째 집, 열에는 RGB의 값을 넣어준다. dp[0][0]= 1번 집이 R를 색칠했을 경우 비용의 최솟값, dp[0][1]= 1번 집이 G를 색칠했을 경우 비용의 최솟값, dp[0][2]= 1번 집이 B를 색칠했을 경우 비용의 최솟값... 을 차례로 저장한다 먼저 처음 dp에 각 집을 R,G,B로 칠하는 비용을 입력받으면서 저장한다. 그 ... baekjoonalgorithmdynamicprogrammingalgorithm