본문 바로가기
반응형

분류 전체보기533

[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.
adsense 100 달러~! 드디어! 이사한다고 바빠서 블로그 신경 못썼는데 다시 열심히 해봐야겠다. 행복하니 오늘은 맛있는거 먹어야지~ 2021. 10. 5.
2021 pycon 인증샷 게더타운 처음 써보는데 신기하다. 2021. 10. 3.
[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.
반응형