dynamicprogramming 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 문자열 회문을 만드는 데 필요한 최소 삽입 단계(LCS와 동일) 문제: 주어진 문자열 s . 한 번에 문자열의 모든 인덱스에 모든 문자를 삽입할 수 있습니다. s 회문을 만들기 위한 최소 단계 수를 반환합니다. Palindrome 문자열은 앞뒤로 같은 문자열을 읽는 것입니다. 예 1: 해결책: 표 방식 시간복잡도 : O(n*m), 공간복잡도 : o(n*m) for dp array... javadynamicprogrammingalgorithms 최소 비용 등반 계단 비용[i]이 계단에서 i번째 단계의 비용인 정수 배열 비용이 주어집니다. 비용을 지불하면 한 단계 또는 두 단계를 오를 수 있습니다. 인덱스가 0인 단계에서 시작하거나 인덱스가 1인 단계에서 시작할 수 있습니다. 바닥에 도달하기 위한 최소 비용을 반환합니다.... cppleetcodedynamicprogramming <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 <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 LeetCode 509. Fibonacci Number Python3 풀이 Dynamic Programming Day 1. DP의 memoization 방법을 사용한다. n이 0일때는 fibo 배열 0번째에 0을 저장 n이 1일때는 fibo 배열 0번째에 0을 저장, 1번째에 1을 저장한다. 이후 index에 해당하는 값은 fibo[_] = fibo[_-1] + fibo[_-2] 를 진행한다.... dynamicprogrammingPython3fibonaccileetcodePython3 Dynamic Programming_1_01_설탕배달(2839) 상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그램 봉지와 5킬로그램 봉지가 있다. 상근이는 귀찮기 때문에, 최대한 적은 봉지를 들고 가려고 한다. 예를 들어, 18킬로그램 설탕을 배달해야 할 때, 3킬로그램 봉지 6개를 가져가도 되지만, 5킬로그램 3개와 3... baekjoonalgorithmdynamicprogrammingiron1algorithm <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 <Baekjoon>#1309 동물원 (Zoo) c++ 이 문제는 앞에서 풀었던 RGB문제와 흡사하게 풀 수 있다. 먼저 동물원의 크기가 가로2 세로1인 경우를 생각해본다. 사자를 한 마리도 배치하지 않는 경우 + 왼쪽 우리에 배치하는 경우 + 오른쪽 우리에 배치하는 경우= 총 3가지가 있다. 다음 동물원의 크기가 가로2 세로2인 경우를 생각해본다. 두 번째 행만 봤을 때 사자를 한 마리도 배치하지 않는 경우는 가로2, 세로1일 때 사자를 배치하... baekjoonalgorithmdynamicprogrammingalgorithm <종만북> 08. 동적계획법_비대칭 타일링 (Asymmetric Tiling) c++ 먼저 비대칭 타일링 문제를 풀기 위해서는 앞에서 공부했던 타일링 방법의 수 세는 알고리즘을 복습할 필요가 있다. 2xn 사각형을 채우는 방법들은 맨 오른 쪽이 어떻게 채워져 있느냐로 나눌 수 있다. a는 마지막 타일의 가로길이가 1인 경우, b와 c는 마지막 타일의 가로 길이가 2인 경우이다. a와 c는 본질적으로 동일 하기 때문에 tiling(n)=1xtiling(n-1) + 1xtilin... Tiling종만북algorithmalgospotdynamicprogrammingTiling <Baekjoon>#2133 3n 타일 채우기 (3n Tiling) c 처음 타일링 문제를 접했을 때는 이게 도대체 뭐지? 하는 생각이 들었다. 동적 프로그래밍을 처음 접한 문제가 타일링 이었기 때문에 더욱 더 낯설고 이상(?)했다. 이 문제를 풀기 전에 #11726, #11727 2n 타일링을 먼저 공부해야 이해가 더 잘 된다. 타일링만으로도 엄청 많은 문제를 응용해서 낼 수 있을 것 같다. 타일링 문제의 경우 끝을 기준으로 나눠서 생각해야 한다. 3 x k ... TilingbaekjoonalgorithmdynamicprogrammingTiling <종만북> 08. 동적계획법_합친 LIS (JLIS, Joined Longest Increasing Subsequence 문제는 정수 수열 A, B가 주어질 때 JLIS의 길이를 계산하는 프로그램이다. list()는 S(start)에서 시작하는 증가 부분 수열 중 최대 길이를 반환하는 함수이다. ret 의 값을 바꾸면 cache[a][b]의 값도 변하기 때문에 매번 귀찮게 cache[a][b]라고 쓰지 않고, 실수를 줄여주기 위해 사용한다. ret=1 로 설정하는 이유는 항상 S[start]는 있기 때문에 길이... 종만북dynamicprogrammingLISalgospotLIS
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 문자열 회문을 만드는 데 필요한 최소 삽입 단계(LCS와 동일) 문제: 주어진 문자열 s . 한 번에 문자열의 모든 인덱스에 모든 문자를 삽입할 수 있습니다. s 회문을 만들기 위한 최소 단계 수를 반환합니다. Palindrome 문자열은 앞뒤로 같은 문자열을 읽는 것입니다. 예 1: 해결책: 표 방식 시간복잡도 : O(n*m), 공간복잡도 : o(n*m) for dp array... javadynamicprogrammingalgorithms 최소 비용 등반 계단 비용[i]이 계단에서 i번째 단계의 비용인 정수 배열 비용이 주어집니다. 비용을 지불하면 한 단계 또는 두 단계를 오를 수 있습니다. 인덱스가 0인 단계에서 시작하거나 인덱스가 1인 단계에서 시작할 수 있습니다. 바닥에 도달하기 위한 최소 비용을 반환합니다.... cppleetcodedynamicprogramming <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 <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 LeetCode 509. Fibonacci Number Python3 풀이 Dynamic Programming Day 1. DP의 memoization 방법을 사용한다. n이 0일때는 fibo 배열 0번째에 0을 저장 n이 1일때는 fibo 배열 0번째에 0을 저장, 1번째에 1을 저장한다. 이후 index에 해당하는 값은 fibo[_] = fibo[_-1] + fibo[_-2] 를 진행한다.... dynamicprogrammingPython3fibonaccileetcodePython3 Dynamic Programming_1_01_설탕배달(2839) 상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그램 봉지와 5킬로그램 봉지가 있다. 상근이는 귀찮기 때문에, 최대한 적은 봉지를 들고 가려고 한다. 예를 들어, 18킬로그램 설탕을 배달해야 할 때, 3킬로그램 봉지 6개를 가져가도 되지만, 5킬로그램 3개와 3... baekjoonalgorithmdynamicprogrammingiron1algorithm <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 <Baekjoon>#1309 동물원 (Zoo) c++ 이 문제는 앞에서 풀었던 RGB문제와 흡사하게 풀 수 있다. 먼저 동물원의 크기가 가로2 세로1인 경우를 생각해본다. 사자를 한 마리도 배치하지 않는 경우 + 왼쪽 우리에 배치하는 경우 + 오른쪽 우리에 배치하는 경우= 총 3가지가 있다. 다음 동물원의 크기가 가로2 세로2인 경우를 생각해본다. 두 번째 행만 봤을 때 사자를 한 마리도 배치하지 않는 경우는 가로2, 세로1일 때 사자를 배치하... baekjoonalgorithmdynamicprogrammingalgorithm <종만북> 08. 동적계획법_비대칭 타일링 (Asymmetric Tiling) c++ 먼저 비대칭 타일링 문제를 풀기 위해서는 앞에서 공부했던 타일링 방법의 수 세는 알고리즘을 복습할 필요가 있다. 2xn 사각형을 채우는 방법들은 맨 오른 쪽이 어떻게 채워져 있느냐로 나눌 수 있다. a는 마지막 타일의 가로길이가 1인 경우, b와 c는 마지막 타일의 가로 길이가 2인 경우이다. a와 c는 본질적으로 동일 하기 때문에 tiling(n)=1xtiling(n-1) + 1xtilin... Tiling종만북algorithmalgospotdynamicprogrammingTiling <Baekjoon>#2133 3n 타일 채우기 (3n Tiling) c 처음 타일링 문제를 접했을 때는 이게 도대체 뭐지? 하는 생각이 들었다. 동적 프로그래밍을 처음 접한 문제가 타일링 이었기 때문에 더욱 더 낯설고 이상(?)했다. 이 문제를 풀기 전에 #11726, #11727 2n 타일링을 먼저 공부해야 이해가 더 잘 된다. 타일링만으로도 엄청 많은 문제를 응용해서 낼 수 있을 것 같다. 타일링 문제의 경우 끝을 기준으로 나눠서 생각해야 한다. 3 x k ... TilingbaekjoonalgorithmdynamicprogrammingTiling <종만북> 08. 동적계획법_합친 LIS (JLIS, Joined Longest Increasing Subsequence 문제는 정수 수열 A, B가 주어질 때 JLIS의 길이를 계산하는 프로그램이다. list()는 S(start)에서 시작하는 증가 부분 수열 중 최대 길이를 반환하는 함수이다. ret 의 값을 바꾸면 cache[a][b]의 값도 변하기 때문에 매번 귀찮게 cache[a][b]라고 쓰지 않고, 실수를 줄여주기 위해 사용한다. ret=1 로 설정하는 이유는 항상 S[start]는 있기 때문에 길이... 종만북dynamicprogrammingLISalgospotLIS