DP52 [leetcode][140] Word Break II 문제 : https://leetcode.com/problems/word-break-ii/ DFS를 돌리면 TLE가 발생해서 memoization을 추가했다. dp[lastInd] = s[0 ~ lastInd] 로 만들 수 있는 정답 가능 문자열의 리스트이다. 즉 우리가 구할 건 dp[ |str| - 1 ]. 문자열의 뒤에서부터 탐색을 하므로 wordDict의 문자열들의 마지막 문자를 key로 하는 dictionary를 하나 만들었다. ex) wordDict = ["ab", "b", "ac"] -> dict ={ {'b', ["ab", "b"]}, {'c', ["c"]}} dict에서 lastInd를 key로 하는 단어들을 가져온 뒤, 문자열의 서브 문자열이 가능한지 체크한다. ex) banana a가 l.. 2019. 12. 19. [leetcode][1186] Maximum Subarray Sum with One Deletion 문제 : https://leetcode.com/problems/maximum-subarray-sum-with-one-deletion/ DP로 해결했다. 연속되는 subarray의 최대합을 구하는 문제인데, 최대 하나의 요소를 삭제해도 된다고 한다. 이 말은 즉, 연속합 혹은 한 칸 떨어진 2개의 subarray의 합들 중 최대값을 구하는 문제이다. 2개를 구해야하므로 2차원 배열이 필요하다. dp[0][i] = i번째 요소를 시작기점으로 contiguous max sum. dp[1][i] = i~끝 범위에서 구한 subarray에서 하나의 요소를 삭제했을 때 max sum. 채워야 되는 배열은 위와 같다. // now = arr[i] // 최대값(now, now를 포함하고 (i+1)을 시작점으로 가지는 .. 2019. 10. 5. [codeground] 98. 소수 수열 codeground - Practice - SCPC 5회 예선 - 98. 소수 수열 문제 : https://www.codeground.org/practice/practiceProblemList 먼저 에라토스테네스의 체로 소수인지 여부를 저장하는 배열을 구한다. 127을 입력으로 받으면 12, 17, 27로 얻을 수 있는 점수를 구한다음 이 중 가장 큰 점수 + 1이 127로 얻을 수 있는 최대 점수가 된다. -> 점화식 이미 구한 숫자의 점수를 다시 탐색할수도 있으므로 배열을 만들어 memoization 한다. 만약 점수를 구하고자 하는 숫자가 소수가 아닌경우 0을 반환한다. (불가능) 숫자가 일의 자리라면 1을 반환한다. (점수 획득 가능) A, B 숫자로 점수를 구한다음 A == B (3), A > .. 2019. 9. 19. [codeground] 9. 화학자의 문장 codeground - Practice - 연습문제 - 9. 화학자의 문장 문제 : https://www.codeground.org/practice/practiceProblemList vector alph(26, vector (27, false)); vector check;//-1: 방문 x. 0: 불가능. 1: 가능 화학원소 기호들로 위 배열 2개를 채웁니다. alph 배열은 원소 기호들로 문자를 만들 수 있는지 여부를 저장합니다. 예를 들어 alph[0('a')][0] 은 a를 만들 수 있는지를 뜻하고 alph[0('a')][1('a')]은 aa를 만들 수 있는지를 뜻합니다. check 배열은 입력받은 문자열을 s라고 했을 때 check[ind] 는 s[ind~끝]에 해당하는 부분 문자열을 화학 원소.. 2019. 9. 15. [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. [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. 이전 1 ··· 4 5 6 7 8 9 다음