DP52 [leetcode][139] Word Break 문제 : https://leetcode.com/problems/word-break/ 문자열 s, 단어 리스트가 주어질 때 단어 리스트들로 문자열 s를 만들 수 있는지 구하는 문제. 단어는 사용하지 않아도 되고 여러번 사용해도 된다. DP로 해결했다. dp[i] = s[i..]를 단어 리스트로 만들 수 있는지 여부(true, false) 저장. index를 기준으로 s[index]와 문자[0]가 같다면 s[index~] prefix가 문자와 같은지 비교하고 같다면 index+문자길이를 index로 다시 탐색한다. 만약 탐색중 dp[index]가 이미 있다면 이를 반환한다. (이미 s[index..]를 탐색했다는 것을 의미) 시간복잡도는 O(|s| x |wordDict|). 문자가 같은지 비교해야 되기 때문.. 2020. 3. 18. 동전 교환(CC: Coin Change) 동전 교환(CC: Coin Change)은 다이나믹 알고리즘 중 하나입니다. CC는 동전의 종류들로 특정 금액을 만드는 경우의 수를 구하는 알고리즘입니다. 예를 들어서 1원, 2원, 5원, 10원 4가지 종류의 동전으로 10원을 만드는 경우의 수를 구해보겠습니다. 동전의 가치는 cost 배열에 넣었다고 생각하겠습니다. 즉, cost[] = {0, 1, 2, 5, 10} 입니다. 모든 경우의 수를 구하기 위해서는 2차원 배열이 필요합니다. d[i][j] = i가지 종류의 동전을 사용해서 j금액을 만드는 모든 경우의 수 입니다. 따라서 우리가 구하고자 하는 경우의 수는 d[4][10]이 됩니다. 이제 배열을 채워봅시다. 0행은 0원으로 j금액을 만드는 경우의 수라고 생각하변 됩니다. 0금액을 만드는 방법은 .. 2020. 2. 23. [codeup][3740] 0/1 배낭 문제(Knapsack Problem) 문제 : http://codeup.kr/JudgeOnline/problem.php?id=3740 다이나믹 프로그래밍 DP의 대표 문제 중 하나인 물건을 넣느냐 빼느냐를 선택하는 0/1 배낭문제. 물건의 개수가 N이고 배낭에 담을 수 있는 최대 무게가 W이다. 물건은 종류별로 1개씩 있다. d[i][j] = 물건을 i번째 까지 배낭에 넣는다고 가정했을 때, 무게 j를 초과하지 않으면서 배낭에 넣을 수 있는 물건들의 가격의 총합의 최대값 d[i][j] = d[i - 1][j] (j = w[i]인 경우, i번째 물건을.. 2020. 2. 22. 다이나믹 프로그래밍(Dynamic Programming) 다이나믹 프로그래밍은 동적계획법이라고도 불리며 짧게 DP라고 많이 사용합니다. DP의 중점은 "작은 문제를 해결하고 이를 이용해 큰 문제를 해결하자 / 큰 문제를 작은 문제로 쪼개서 해결하자."입니다. DP를 배우지는 않으셨더라도 피보나치 수를 재귀로 구하는 방법은 한번쯤 들어보셨을 거라 생각합니다. 이를 DP를 사용하는 방법으로 한 번 바꿔보겠습니다. int fibo(int n){ if(n==1 || n==0) return n; return fibo(n-1) + fibo(n-2); } 일단 기존 방법의 재귀 소스코드는 위와 같습니다. 4번째 피보나치 수를 구하려면 위와 같이 함수를 호출하게 되는데 2번째 피보나치 수를 구하는 함수를 중복해서 호출하게 됩니다. 2번째 피보나치 수는 상황에 따라서 변하는 .. 2020. 2. 22. [hackerrank] Largest Pyramid 문제 : https://www.hackerrank.com/contests/hourrank-23/challenges/largest-pyramid/problem int arr[351][351]; //arr[i][j] : (i,j) 요소 값. (입력값) int max_down[400][351][351] = {0}; //max_down[size][i][j] : j열의 arr[i][j] 부터 arr[i+size-1][j] 중 최대 값 int max_right[400][351][351] = {0}; //max_right[size][i][j] : i행의 arr[i][j] 부터 arr[i][j+size-1] 중 최대 값 int sum[351][351] = {0}; //sum[i][j] : (1,1) ~ (i,j) 까지.. 2020. 2. 15. [leetcode][368] Largest Divisible Subset 문제 : https://leetcode.com/problems/largest-divisible-subset/ 중복되지 않는 양수 정수 배열이 주어질 때, (A, B) pair가 A%B = 0 이거나 B%A = 0 인 경우, 즉, 나누어떨어지는 수들로만 이루어진 subset들 중 가장 긴 subset을 하나 구하는 문제이다. dp로 풀었다. dp[i] = 부분문자열[i~]에서 i 번째 정수를 반드시 포함하면서 조건에 만족하는 subset들 중 최장 길이. (길이를 저장) nextInd[i] = dp[i]가 저장될 때, 2번째로 저장되는 정수의 인덱스. (1번째는 i번째 정수로 고정). 나중에 subset 문자열을 구할 때 추적용도로 사용한다. 초기값은 -1 [1,2,4,5]을 예로 들어보자. 인덱스 0,1.. 2020. 1. 26. 이전 1 ··· 3 4 5 6 7 8 9 다음
