본문 바로가기

전체 글657

[leetcode] 1137. N-th Tribonacci Number 문제 : https://leetcode.com/problems/n-th-tribonacci-number/ T(0) = 0, T(1) = 1, T(2) = 1, T(n) = T(n-1) + T(n-2) + T(n-3) n이 주어질 때, T(n) 값을 구해라. n크기의 배열을 만들어서 문제에서 주어진 점화식으로 구할 수 있다. 이 경우, 시간/공간 복잡도는 모두 O(n)이 된다. 점화식을 보면 결국 필요한 값들은 최신 값 3개 이므로 크기가 3인 배열(let, arr)을 만들고 arr[n%3] = arr[0] + arr[1] + arr[2] 위 식으로 arr을 채워나간 뒤 n번째까지 모두 채우면 arr[n%3] 가 정답이 된다. 이 경우 시간복잡도는 동일하게 O(n)이지만 공간복잡도는 O(1)이 된다. 소스.. 2021. 9. 25.
[leetcode] 115. Distinct Subsequences 문제 : https://leetcode.com/problems/distinct-subsequences/ 문자열 s, t가 주어지면 t와 동일한 s의 고유한 하위 시퀀스 수를 반환하라. 답은 32비트 부호있는 정수임을 보장한다. DP로 풀었다. dp[i][j] = t[0~j]와 동일한 s[0~i]의 고유한 하위 시퀀스 수. dp[i][j] = dp[i-1][j] + dp[i-1][j-1] (s[i]가 t[j]인 경우) dp[i][j] (s[i] 가 t[j]가 아닌 경우) 점화식은 위와 같다. s[i] == t[j]인 경우 s[0~i-1] 문자열의 고유 하위 시퀀스들 문자 뒤에 s[i]를 붙이면 t[0~j]가 되므로 dp[i-1][j]에 dp[i-1][j-1]을 더해준다. ex) s = "rabbbit", .. 2021. 9. 19.
투포인터 (Two pointer) 투포인터란 이름 그대로 두 개의 포인터를 사용하여 문제를 풀어나갑니다. 2개의 포인터로 배열이나 문자열을 탐색할 때 탐색 위치를 저장하고 있습니다. 말로 하는거보다는 예를 들어서 한 번 살펴봅시다. 수들의 합. N개의 자연수 배열이 주어질 때, i~j 번째 수들의 합이 M이 되는 경우의 수를 구하는 문제입니다. 1 1 1 1 배열은 위와 같고, M = 2 라고 했을 때 투포인터로 정답을 구해봅시다. 두 개의 포인터를 두고 이들을 left, right라 합시다. left는 i, right는 j 번째 수의 위치를 가리킵니다. left는 범위를 줄이고자 할 때 증가시키고, right는 범위를 증가시키고자 할 때 증가시킵니다. 시작 인덱스는 둘 다 0입니다. left right 부분 배열합 0 0 1 0 1 2.. 2021. 9. 12.
[leetcode] 446. Arithmetic Slices II - Subsequence 문제 : https://leetcode.com/problems/arithmetic-slices-ii-subsequence/ 정수 배열 nums가 주어지면 모든 arithmetic subsequences 의 수를 구하라. 시퀀스들의 숫자가 3개 이상이고 연속되는 두 요소의 차이가 동일한 경우 arithmetic subsequences라 한다. i:j->(j-i)가 차이이고 i, j를 포함하는 subsequences 수 (i>j) 4:2->1 [4,2] 6:2->1 [6,2] 6:4->2 [6,4,2] [6,4] 8:2->1 [8,2] 8:4->1 [8,4] 8:6->3 [8,6,4,2] [8,6,4] [8,6] 10:2->1 [10,2] 10:4->1 [10,4] 10:6->2 [10,6,2] [10,6].. 2021. 9. 11.
[leetcode] 764. Largest Plus Sign 문제 : https://leetcode.com/problems/largest-plus-sign/ 왼쪽 -> 오른쪽. 오른쪽 -> 왼쪽. 위 -> 아래. 아래 -> 위 로 탐색하면서의 subSum을 모든 위치에서 구한다. (x,y)를 + 부호의 가운데 지점이라 할 때, (x,y)를 좌표로한 4가지 subSum들의 최소값이 + 부호의 최대 크기이다. 모든 (x,y)을 + 부호의 가운데라 가정하고 subSum들을 이용하여 + 부호의 크기들을 구했을 때 최대값이 정답이 된다. 시간복잡도는 O(N^2) 공간복잡도는 4가지 subSum들을 구해둬야 하기 때문에 O(4N^2). 소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/leetcode/medium/764.%2.. 2021. 9. 9.
[LeetCode] 899. Orderly Queue 문제 : https://leetcode.com/problems/orderly-queue/ 문자열 s, 정수 k가 주어진다. 문자열 s의 앞에서부터 k개의 문자들 중 하나를 s문자열의 가장 뒤로 이동시킬 수 있다. 이동횟수와 상관없이 s 문자열의 문자를 이동시켰을 때 얻을 수 있는 문자열들 중 사전순으로 가장 빠른 문자열을 구하라. K가 2이상인 경우, s문자열의 문자들로 만들 수 있는 사전순으로 가장 빠른 문자열이 정답이 될 수 있다. (정렬된 문자열이 정답) 왜냐하면 K가 2이상의 경우 문자들의 개수가 달라지지 않는 한에서 어떤 문자열들도 만들 수 있기 때문이다. 증명해보자. 한 번에 많은 것을 하지 않고 하나의 문자만 올바른 위치로 옮긴다고 생각하면 쉽다. 옮겨야 될 문자를 가장앞에 keep해뒀다가 .. 2021. 9. 5.

티스토리툴바