Algorithm202 LeetCode 322 - Coin Change (Medium) 문제 LeetCode - 322번 풀이 과정 오랜만에 풀어보는 동적 계획법 문제입니다. dp[x] = x 원을 만들기 위한 최소 동전의 개수 라고 정의한다면 다음과 같은 점화식을 얻을 수 있습니다. dp[x] = for all coins, min{ dp[x - coins[i]] } 이때 i 는 i 번째 동전을 의미합니다. 코드 /** * @param {number[]} coins * @param {number} amount * @return {number} */ var coinChange = function (coins, amount) { const dp = new Array(amount + 1).fill(Infinity); // 초기값 dp[0] = 0; for (let money = 1; money 2021. 3. 3. LeetCode 21 - Merge Two Sorted Lists (Easy) 문제 LeetCode - 21번 풀이 과정 병합 정렬 의 병합 과정을 직접 구현해보는 문제입니다. 병합 정렬 은 각각의 배열 요소를 균등하게 나누고 나누어진 배열을 정렬하여 합치는 분할정복 을 사용하는 정렬 알고리즘입니다. 두 배열이 모두 정렬된 상태이기 때문에 배열의 가장 앞 요소부터 서로 비교해주며 작은 요소들을 하나씩 추가해나가면 됩니다. 만약 둘 중 하나의 배열이 비어있을 경우에는 비어있지 않은 배열을 그대로 이어붙이면 됩니다. 입력으로 둘 중 한 배열이 비어있는 것이 존재할 수 있으므로 이 부분에 대해 별도의 예외처리를 진행해줬습니다. 코드 /** * Definition for singly-linked list. * function ListNode(val, next) { * this.val = .. 2021. 3. 2. LeetCode 240 - Search a 2D Matrix II (Medium) 문제 LeetCode - 155번 풀이 과정 이차원 배열에서 목표값이 존재하는지 판단하는 문제입니다. 그냥 브루트 포스 로 접근한다면 O(MN) 의 시간 복잡도로 해결할수도 있지만 좀 더 효율적인 탐색을 위해 이분 탐색 을 적용했습니다. 각 행이 오름차순으로 정렬되어 있다는 점을 이용해서 각 행마다 이분 탐색 을 수행해 원하는 값이 존재하는지 판단합니다. 코드 /** * @param {number[][]} matrix * @param {number} target * @return {boolean} */ var searchMatrix = function (matrix, target) { for (let row of matrix) { if (bisect(row, target)) return true; } r.. 2021. 3. 2. LeetCode 155 - Min Stack (Easy) 문제 LeetCode - 155번 풀이 과정 스택 을 사용해서 min stack 을 구현하는 문제입니다. 단순하게 구현하면 최소값을 찾을 때마다 Math.min 을 사용할 수도 있지만 문제 조건과 같이 상수 시간에 최소값을 찾기 위해서는 다른 방법이 필요합니다. 이를 위해 두 개의 스택을 사용하여 값을 저장하도록 합니다. 하나는 들어온 순서대로 쌓아 올리는 스택이고 다른 하나는 이에 대응하여 현재까지의 최소값을 저장하는 스택으로 사용합니다. 예를 들어 1, 2, 0, 3 이 순서대로 입력된다고 한다면 두 개의 스택은 다음과 같은 상태를 가지게 됩니다. | 3 | | 0 | | 0 | | 0 | | 2 | | 1 | | 1 | | 1 | A 스택 B 스택따라서 minValue 를 통해 현재까지의 최소값을 .. 2021. 3. 2. LeetCode 787 - Cheapest Flights Within K Stops (Medium) 문제 LeetCode - 787번 풀이 과정 최대 K 개의 경유지를 포함한다는 조건 아래에서 한 정점에서 목표 정점까지의 최단 경로를 구하는 문제입니다. 따라서 단일 정점 - 모든 쌍 최단 경로 알고리즘인 다익스트라 알고리즘 을 변형해서 문제를 해결하였습니다. 사실 간선 선택을 위해 우선순위 큐 도 사용하지 않아서 애매한 부분이 있지만 BFS + Dijkstra 의 유형이라고 생각하면 될 것 같습니다. 이 문제의 핵심은 k 개의 경유지를 어떻게 처리할 것인가 입니다. 기존의 다익스트라 알고리즘 은 이전에 발견되어 큐에 저장되어 있는 경로 중 더 짧은 경로가 발견되어 dist 가 갱신 되었을 경우 큐에서 이전에 발견된 경로가 pop 되어 처리할 차례가 되면 그냥 무시를 해주는 방식으로 처리를 해줬습니다. .. 2021. 3. 2. LeetCode 417 - Pacific Atlantic Water Flow (Medium) 문제 LeetCode - 417번 풀이 과정 입력으로 주어진 격자판에서 가장자리에 도달할 수 있는 좌표를 찾는 BFS 문제였습니다. 문제 조건에 따라 x 죄표 혹은 y 좌표 가 0보다 작아질 경우는 pacific 에 해당하고 그 반대의 경우에는 atlantic 에 해당합니다. 따라서 matrix 의 각 지점마다 BFS 를 수행하며 pacific 과 atlantic 에 모두 도달 가능한 경우에만 해당 죄표값을 기록하여 답을 구할 수 있습니다. 이때 인접한 지역에 대해서 값이 같거나 작을 경우에만 이동할 수 있다는 것에 유의하도록 합니다. 코드 /** * @param {number[][]} matrix * @return {number[][]} */ var pacificAtlantic = function (m.. 2021. 3. 2. 이전 1 ··· 26 27 28 29 30 31 32 ··· 34 다음
