본문 바로가기
반응형

알고리즘 문제/Leetcode185

[Leetcode] 437. Path Sum III 문제 : https://leetcode.com/problems/path-sum-iii/ 이진 트리와 targetSum이 주어지면 경로의 노드들 값의 합이 targetSum과 같은 경로들의 수를 구하라. 백트래킹. 트리를 탐색하면서 탐색한 노드들의 val의 합의 개수를 map에 저장한다. 탐색하면서 이때까지의 합(sum)에서 targetSum을 뺀 값의 개수들의 합이 정답이 된다. [그림 1]에서는 테이블들의 빨간색 셸들이 이에 해당하여 정답은 3이 된다. 시간복잡도는 O(N). N = 노드 수 소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/leetcode/medium/437.%20Path%20Sum%20III.cpp 2021. 10. 18.
[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.
반응형