알고리즘 문제408 [codeground] 31. 프리랜서 codeground - Practice - SCPC 2회 예선 - 31. 프리랜서 문제 : https://www.codeground.org/practice/practiceProblemList DP를 Top-down(탑다운) 방식으로 채워나가면서 문제를 해결합니다. D[0][ind] = ind주에 P사 작업했을 때 얻을 수 있는 최대 이익 D[1][ind] = ind주에 Q사 작업했을 때 얻을 수 있는 최대 이익 go(int ind) = ind주까지 작업했을 때 얻을 수 있는 최대 이익 반환 만약 ind주에 P사를 작업했을 때 얻을 수 있는 최대 이익은 D[0][ind] = go(ind-1) + P[ind] 입니다. ind주에 Q사를 작업했다면 그 전주에도 Q사 작업을 해야 하므로 D[1][ind] = g.. 2019. 9. 13. [codeground] 52. 최대 직사각형 codeground - Practice - 연습문제 - 52. 최대 직사각형 문제 : https://www.codeground.org/practice/practiceProblemList 2차원 배열에서 만들 수 있는 모든 직사각형들의 배열 합 중 최대값을 구하는 문제다. 직사각형을 [그림 1] 순서로 탐색하였다. 그런데 실제로는 1,2를 합친 것, 3,4를 합친 것, 5,6을 합친 것 또한 직사각형도 탐색을 해야 하므로 추가적인 알고리즘이 더 필요하다. 이를 위해 변수 2개를 사용한다. tmp는 현재 탐색 중인 직사각형(빨간색)의 배열 합을 의미한다. row는 현재까지 탐색한 열 범위([그림 2]에서 열 범위는 1~2)로 만들 수 있는 직사각형들 중 가장 큰 배열의 합을 의미한다. 즉, [그림 3] 처럼.. 2019. 9. 12. [leetcode] 1048. Longest String Chain 문제 : https://leetcode.com/problems/longest-string-chain/ 먼저 words 배열을 문자열 길이 오름차순으로 정렬한다. 이제 반드시 [words[i], words[j]] (i < j) 식으로 string chain이 만들어진다. longest length를 저장하는 map을 하나 만든다. map dp; 위 map에는 key : words[i], value : longest length of a word chain 이 들어간다. 이제 words를 앞에서부터 탐색한다. 탐색 중인 words 문자열을 word2라고 했을 때 word2에서 문자를 하나씩 빼면서 string chain을 만드는 word1인지 확인한다. 만약 string chain을 만들 수 있는 word1.. 2019. 9. 11. [leetcode] 1155. Number of Dice Rolls With Target Sum 문제 : https://leetcode.com/problems/number-of-dice-rolls-with-target-sum/ DP 문제. int dp[d+1][target+1]; // dp[d][sum] = d개의 dice로 sum을 만들 수 있는 경우의 수 점화식은 위와 같다. 먼저 dp[1][1~target]을 1로 초기화 시킨다. (다이스 1개로 만들 수 있는 경우의 수 세팅) dp 배열을 행우선탐색으로 탐색하면서 배열을 채운다. (dice, sum) dp 요소를 채운다고 할 때, for(int face=1; face 2019. 9. 8. [leetcode] 904. Fruit into Baskets 문제 : https://leetcode.com/problems/fruit-into-baskets/description/ 슬라이딩 윈도우 문제. 인덱스를 가리키는 변수 l(왼쪽), r(오른쪽)을 둔다. tree[l]을 포함하여 수집할 수 있는 최대 범위를 r로 구한다. tree[l ~ r]이 과일종류가 3개 이상이 되기전까지 r을 증가시킨다. r을 구했으면 tree[l]을 포함할 때 수집할 수 있는 최대 과일 수를 구할 수 있다. (l~r 범위) ex) l = 0. r = 4 -> r - l + 1 = 5(0번째 인덱스를 포함하여 수집할 수 있는 최대 과일 수) 다음 탐색 시 tree 배열을 다시 탐색하지 않으려면 구한 범위에서 tree[l]이 아닌 과일의 종류가 무엇인지 알아야하고 이 과일이 가장 나중에.. 2019. 9. 3. [codeground] 8. 블럭 없애기 codeground - Practice - 연습문제 - 8. 블럭 없애기 문제 : https://www.codeground.org/practice/practiceProblemList 1. i번째 블럭 높이(h) a h b -> 높이가 h인 블럭 없어지는데 걸리는 시간 = h 2. i번째 블럭(h)의 양쪽 블럭이 없어지는데 걸리는 시간 중 최소값 + 1 a h b -> 높이가 h인 블럭 없어지는데 걸리는 시간 = (a, b 중 작은 값) + 1 i번째 블럭이 없어질 때까지 걸리는 시간은 1, 2번 중 최소값이다. int d[n + 2];//d[i] = i번째 블럭이 없어질 때까지 걸리는 시간 즉, d[i] = min(d[i-1] + 1 , d[i+1] + 1, i번 블럭 높이) i 번째 블럭이 모두 없어지.. 2019. 9. 2. 이전 1 ··· 50 51 52 53 54 55 56 ··· 68 다음
