본문 바로가기

🏃 algorithm/leetcode93

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.

LeetCode 17 - Letter Combinations of a Phone Number (Medium) 문제 LeetCode - 17번 풀이 과정 휴대폰 자판을 이용해서 만들 수 있는 문자열을 모두 찾는 백트래킹 문제입니다. 각 숫자별로 할당된 문자들을 표현해주는 다양한 방법들 (Map, Object 등) 이 있지만 저는 배열에 인덱스로 접근하는 방법을 사용했습니다. 숫자로 이루어진 주어진 입력 문자열을 한 자리씩 순회하며 만들 수 있는 모든 문자열을 재귀호출로 생성하면 됩니다. 코드 /** * @param {string} digits * @return {string[]} */ const buttons = [ 0, 0, "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz", ]; var letterCombinations = function (digits) {.. 2021. 3. 2.

LeetCode 230 - Kth Smallest Element in a BST (Medium) 문제 LeetCode - 230번 풀이 과정 이진 검색 트리 에서 k번째 원소를 찾는 문제입니다. 이진 검색 트리 는 루트 노드가 해당 노드의 왼쪽 자식 노드보다 크고 오른쪽 노드보다 작은 값을 가집니다. 따라서 이를 중위 순회 할 경우 키 값이 정렬된 순서대로 방문한다는 것을 알 수 있습니다. 이를 활용하여 중위 순회를 하는 함수를 만들고 k 번째 노드에 방문했을 때를 기록하여 답을 구하도록 하였습니다. 코드 /** * @param {number[]} nums * @return {number} */ var rob = function (nums) { const memo = new Array(nums.length).fill(-1); function dp(i) { if (i >= nums.length) re.. 2021. 3. 2.

LeetCode 198 - House Robber (Easy) 문제 LeetCode - 198번 풀이 과정 도둑질을 통해 얻을 수 있는 최대 수익을 구하는 동적 계획법 문제입니다. 만약 dp(house) = house 에서부터 마지막 집까지 도둑질을 통해 얻을 수 있는 최대 수익 이라고 한다면, 다음과 같은 점화식을 세울 수 있습니다. dp(house) = max(dp(house+1), dp(house + 2) + cost[house]) 여기서 두 가지로 나누어지는 이유는 현재 house 위치에서 도둑질을 하는 것과 안하는 것 이렇게 두 가지 경우가 있기 때문입니다. 코드 /** * @param {number[]} nums * @return {number} */ var rob = function (nums) { const memo = new Array(nums.le.. 2021. 3. 2.

LeetCode 22 - Generate Parentheses (Medium) 문제 LeetCode - 22번 풀이 과정 주어진 괄호쌍의 개수에 맞는 올바른 괄호 배치를 생성하는 백트래킹 문제입니다. 이때 해당 괄호배치가 올바르게 위해서는 양 끝의 괄호가 각각 ( 와 ) 여야 한다는 점을 유의하도록 합니다. 또한 괄호쌍이 올바르기 위해서는 ( 가 존재하지 않늦데 ) 가 ( 보다 먼저 할당되면 안됩니다. 따라서 각각의 재귀 호출마다 ( 의 여유분이 있다면 ) 를 시도해보는 방식으로 진행하였습니다. 다만 ( 또한 최대 n 번 만큼만 등장할 수 있으므로 left 와 leftCount 를 각각 구분하여 전자는 ( 의 여유분으로 ) 가 등장할때마다 감소시켜줬고, 후자는 현재까지 선택된 ( 의 개수를 나타내도록 하였습니다. 코드 /** * @param {number} n * @return {.. 2021. 3. 2.

이전 1 ··· 10 11 12 13 14 15 16 다음

티스토리툴바