알고리즘 문제408 [leetcode][920] Number of Music Playlists 문제 : https://leetcode.com/problems/number-of-music-playlists/ DP로 풀었다.dp[N][L] = N개의 노래로 L개의 노래가 있는 플레이 리스트를 만드는 경우의 수. 만약 i개의 노래로 j개의 노래가 있는 플레이 리스트를 만들었다고 할 때(dp[i][j]) 다음에 추가하는 노래는 플레이리스트에 없는 노래거나 플레이리스트에 이미 있는 노래. 이렇게 2가지 경우가 있다. 플레이리스트에 없는 노래를 추가한다면 만들어지는 dp배열은 dp[i+1][j+1]이다. (노래가 하나 추가되고 플레이리스트도 하나 느므로)dp[i][j]가 추가될 수 있는 노래의 개수(N - i = 전체 - 이미 들은 노래)만큼 추가되므로 dp[i+1][j+1] += dp[i][j] * (N .. 2018. 11. 6. [leetcode][66] Plus One 문제 : https://leetcode.com/problems/plus-one/ 가산기를 만들어보자.carry(올림수) 변수를 하나 두고 1로 세팅한다. 원래는 0으로 시작하지만 1을 더하는 값을 구하는 것이기 때문에 1을 세팅한다.배열의 뒤에서부터 carry와 수를 더해가면서 정답 배열의 뒤에서부터 채운다.carry는 더한 값에 / 10한 값이다. (10을 넘겨야만 다음 수에 1을 더해주므로)정답 배열에 들어가는 수는 더한 값에 % 10을 한 값이다.배열을 모두 탐색이 끝났을 때(배열을 전부 탐색해도 되고 carry가 0이 나올때까지만 탐색해도 됨) carry가 1이라면 정답 배열의 가장 앞에 1을 추가해준다. 시간 복잡도는 O(N). 소스 코드 : https://gist.github.com/fpdjs.. 2018. 11. 5. [leetcode][918] Maximum Sum Circular Subarray 문제 : https://leetcode.com/problems/maximum-sum-circular-subarray/ 최대 부분 문자열과 최소 부분 문자열을 구한다.최대 부분 문자열의 합과 배열의 모든 총합 - 최소 부분 문자열 중에 큰 값이 정답이 된다.모든 수가 음수인 경우는 음수 중에 가장 큰 값이 정답이 된다. 시간복잡도는 O(N). 소스코드 : https://gist.github.com/fpdjsns/fa784f6bf9e9296b8670fc07759ff466 2018. 11. 5. [leetcode][53] Maximum Subarray 문제 : https://leetcode.com/problems/maximum-subarray/ 문자열을 앞에서부터 더해간다.더한 값이 양수라면 앞으로의 탐색 값에 더했을 때 더 큰 합을 기대할 수 있다.하지만 음수라면 무슨 수를 더해도 더 작은 합이 나올 것이다.따라서 더한 값이 음수가 나오면 부분합을 0으로 초기화시키고 다시 배열 값을 더해간다.이렇게 구한 부분합들 중 최대값이 정답이 된다. 시간복잡도는 O(N). 소스코드 : https://gist.github.com/fpdjsns/157788123006e2e518e352129645b170 2018. 11. 4. [leetcode][91] Decode Ways 문제 : https://leetcode.com/problems/decode-ways/ DP로 풀었다.알파벳이 될 가능성이 있는 수는 한자리 수(1~9)이거나 두 자리 수(10~26)다.문자열을 앞에서부터 탐색하면서 한자리 수와 현재 탐색중인 문자보다 하나 작은 문자를 합쳐서 두 자리 수를 구해 이들이 알파벳이 될 수 있는지 체크한다. ex) "12" -> 1, 2, 12 체크.탐색 중인 문자열 인덱스를 ind라 하고 ind번째 문자열까지 만들 수 있는 알파벳문자열의 경우의 수를 저장하는 d[ind] 배열을 만든다. 한 자리 수가 숫자가 될 수 있는 경우 ind-1 번째 문자열까지 만들 수 있는 알파벳 배열의 수(d[ind-1])를 d[ind]에 더한다. (d[ind-1]로 만들 수 있는 알파벳 문자열 뒤.. 2018. 11. 2. [leetcode][423] Reconstruct Original Digits from English 문제 : https://leetcode.com/problems/reconstruct-original-digits-from-english/ Note 2번에 집중해보면 코드를 더 간결하게 짤 수 있다. 2. Input is guaranteed to be valid and can be trasformed to its original digits. That means invalid inputs such as "abc" or "zerone" are not permitted. 모든 문자는 숫자로 변경될 수 있는 문자라는 뜻이다. 즉, 0~9 숫자의 알파벳 중에 자신만 고유하게 가지고 있는 문자가 입력 문자열에 있다면 해당 문자는 반드시 나온다는 뜻이다. 그렇지 않으면 2번 조건에 어긋나기 때문이다.ex) z~~ -.. 2018. 11. 1. 이전 1 ··· 64 65 66 67 68 다음