알고리즘 문제408 [leetcode] 279. Perfect Squares 문제 : https://leetcode.com/problems/perfect-squares/ 정수 n이 입력으로 주어지면 완전제곱수들의 합으로 n을 만들 때 사용되는 완전제곱수들의 최소 개수를 반환하라. DP로 풀 수 있다. dp[i] = i를 만들 때 사용되는 완전제곱수들의 최소 개수 = dp[i - j*j] + 1 들 중 최소값 (j*j 2021. 10. 14. [leetcode] 2028. Find Missing Observations 문제 : https://leetcode.com/problems/find-missing-observations/ 1~6까지 수가 새겨진 주사위가 (n+m)개가 있다. 모든 주사위를 굴린 값들 중 m개 주사위에 대한 정보를 가지고 있고 (n + m)개의 주사위의 평균값 mean 값도 알고 있다고 할 때, 가능한 n개의 주사위 결과를 반환하라. 만일 가능한 정답이 없다면 빈 배열을 반환하라. mean 값에 (n + m)을 곱하면 모든 주사위 값들을 더한 값이 된다. 이 값에 입력값으로 주어진 m개 주사위들의 값들을 뺀다면 n개의 주사위 눈들의 합(let, sum)이 된다. sum = mean * (n+m) - m개의 주사위 눈들의 합 = n개의 주사위 눈들의 합 sum / n 을 초기화 값으로 n 배열을 만들.. 2021. 10. 5. [leetcode] 1293. Shortest Path in a Grid with Obstacles Elimination 문제 : https://leetcode.com/problems/shortest-path-in-a-grid-with-obstacles-elimination/ m x n 정수 2차원 배열이 주어진다. 각 셸은 0(비어있음) 혹은 1(장애물) 이다. 최대 k개의 장애물을 제거할 수 있다고 할 때, (0, 0) -> (m-1, n-1)로 이동할 수 있는 최소 걸음 수를 구하라. 배열에서 1칸 이동을 1 걸음수로 본다. 상하좌우로 한 칸씩 이동할 수 있다. 불가능한 경우 -1을 반환하라. BFS로 풀었다. 탐색했는지 여부를 저장하기 위해 visits[x][y][k] 배열을 하나 만든다. visits[x][y][k] = 장애물 제거가능 횟수가 k번 남았을 때, grid[x][y]를 탐색한 적이 있는지 여부. BFS.. 2021. 9. 26. [leetcode] 1328. Break a Palindrome 문제 : https://leetcode.com/problems/break-a-palindrome/ 소문자 영어로 이루어진 펠린드롬 문자열이 주어지면 한 문자만 다른 소문자 알파벳으로 변경하여 펠린드롬이 아닌 문자열로 만들고자 한다. 이 때, 사전순으로 가장 작은 문자열을 구하라. 만일 조건을 만족하는 변경 가능한 문자열이 없는 경우 빈 문자열을 반환하라. 펠린드롬이므로 1/2 개만 탐색해도 된다. (앞뒤 문자가 같으므로) 문자열이 홀수인 경우 가운데 문자는 펠린드롬 여부와 관계가 없으므로 변경하는 문자에서 제외시켜야 한다. -> 문자열 길이가 1인 경우 빈문자열을 반환한다. (어떤 문자를 바꿔도 펠린드롬이 되므로) 앞에서 1/2개의 문자들 중 ‘a’가 아닌 문자가 있으면 이를 ‘a’로 바꾼다. (앞에 문.. 2021. 9. 25. [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. 이전 1 ··· 15 16 17 18 19 20 21 ··· 68 다음