본문 바로가기

leetcode87

LeetCode 112 - Path Sum (Easy) 문제 LeetCode - 112번 풀이 과정 루트 노드부터 시작해서 잎 노드까지의 경로 중 합이 S 인 경우가 존재하는지 찾는 문제입니다. DFS 를 활용해서 모든 경우를 탐색할 수 있으며 루트 노드 배열이 비어있는 경우에 유의하면 쉽게 해결할 수 있습니다. 코드 /** * Definition for a binary tree node. * function TreeNode(val, left, right) { * this.val = (val===undefined ? 0 : val) * this.left = (left===undefined ? null : left) * this.right = (right===undefined ? null : right) * } */ /** * @param {TreeNode} .. 2021. 3. 4.
LeetCode 63 - Unique Paths II (Medium) 문제 LeetCode - 63번 풀이 과정 시작 지점에서 목표 지점에 도달할 수 있는 경우의 수를 찾는 문제입니다. dp(x, y) 를 (x, y) 에서 오른쪽 하단 모서리에 도달하는 경우의 수라고 한다면 다음과 같은 점화식을 정의할 수 있습니다. dp(x, y) = dp(x + 1, y) + dp(x, y + 1) 이때 dp(x, y) 에는 장애물이 없어야 하며 격자를 벗어나면 안됩니다. 코드 /** * @param {number[][]} obstacleGrid * @return {number} */ var uniquePathsWithObstacles = function (obstacleGrid) { const m = obstacleGrid.length; const n = obstacleGrid[0]... 2021. 3. 4.
LeetCode 1011 - Capacity To Ship Packages Within D Days (Medium) 문제 LeetCode - 1011번 풀이 과정 화물들의 무게 weights 가 주어질 때 D 일에 모든 화물을 배송하기 위한 화물선의 최소 무게를 찾는 문제입니다. 사실 문제 분류는 이분 탐색 으로 되어 있지만 입력의 크기를 고려 했을 때 완전 탐색 으로도 해결할 수 있을 것 같았습니다. 그래도 이분 탐색 을 활용해보면 화물선의 최소 및 최대 무게를 정하고 모든 화물을 운반하기 위해 필요한 최소 일수를 구해서 비교하면 됩니다. 회물선의 최소 무게는 모든 화물 중 가장 무거운 것이며 최대 무게는 모든 화물을 하루만에 배송하기 위한 무게(즉, 모든 화물 무게의 합) 입니다. 코드 /** * @param {number[]} weights * @param {number} D * @return {number} *.. 2021. 3. 4.
LeetCode 881 - Boats to Save People (Medium) 문제 LeetCode - 881번 풀이 과정 최대 2명이 탈 수 있는 보트를 이용해서 모든 사람들을 옮기는 최소 왕복 이동 횟수를 구하는 그리디 문제입니다. 우선 사람들의 몸무게로 내림차순 정렬해서 보트에 순서대로 태우도록 합니다. 여기서 생각해볼 점은 people[head] < limit 일 때 남은 사람은 limit - people[head] 보다 적은 몸무게 중 가장 큰 무게 A 를 가지는 사람을 선택할 것인지 혹은 남은 사람들 중 가장 무게가 적게 나가는 사람 B 을 선택할 것인지 입니다. 이때 A 를 선택하든 B 를 선택하든 선택되지 않은 다른 하나를 위해 보트가 하나 필요하다는 사실은 변하지 않습니다. 따라서 가장 무게가 많이 나가는 사람을 가리키는 포인터 head 와 가장 무게가 적은 사람을.. 2021. 3. 4.
LeetCode 234 - Palindrome Linked List (Easy) 문제 LeetCode - 234번 풀이 과정 주어진 링크드리스트가 팰린드롬 인지 판단하는 문제입니다. 시간 복잡도가 O(N) 이면서 공간 복잡도가 O(1) 으로 구현하기 위해서 재귀 함수를 사용했습니다. 이를 위해 먼저 링크드 리스트의 길이를 구한 다음, 중앙 위치까지 이동해서 팰린드롬 유무를 판단합니다. 이는 a[i] ~ a[j] 까지의 링크드 리스트가 팰린드롬이기 위해서는 a[i+1] ~ a[j-1] 까지가 팰린드롬이고 a[i] == a[j] 이기 때문입니다. 그러므로 각각의 재귀 호출 과정에서 반환값으로 팰린드롬 유무 와 tail 노드 를 반환해서 재귀 호출 과정에서 각각의 서브 리스트의 양 끝 노드를 비교해줍니다. 코드 /** * Definition for singly-linked list. * .. 2021. 3. 4.
LeetCode 309 - Best Time to Buy and Sell Stock with Cooldown (Medium) 문제 LeetCode - 309번 풀이 과정 특정 날에 주식을 매도 혹은 매수하여 얻을 수 있는 최대 이윤을 계산하는 동적 계획법 문제입니다. 문제 조건에서 주식을 구매 전에는 판매를 먼저 해야한다는 것이 명시되어 있다는 점에 유의합니다. 만약 dp(i, buy) = i 번째 날 주식의 판매 상태가 buy 일 때 i 이후 얻을 수 있는 최대 이윤 이라고 정의한다면 다음과 같은 점화식을 얻을 수 있습니다. dp(i, buy) = max(dp(i+1, true) - stock[i], dp(i+1, false)), if buy == false else(buy == true), dp(i, buy) = max(dp(i+2, false) + stock[i], dp(i+1, true)) 즉, `i` 번째 날 주식을 .. 2021. 3. 4.

티스토리툴바