본문 바로가기

👨‍💻📱✍️🎢314

LeetCode 39 - Combination Sum (Medium) 문제 LeetCode - 39번 풀이 과정 중복 조합 을 만들어서 숫자들의 합이 target 이 되는 모든 경우를 찾는 문제입니다. 여기서 중복 조합 이란 서로 다른 n개를 중복을 허용하여 r 개를 선택하는 경우 를 말합니다. 이를 위해서는 백트래킹 을 활용해서 모든 조합을 탐색해주는 과정이 필요합니다. 기존 조합에서는 i 번쩨 숫자를 선택했을 경우 그 다음 숫자인 i + 1 번째 부터 하나씩 골라야하지만 중복을 허용하기 때문에 선택 시작점을 i 번째 부터 해주면 됩니다. 코드 /** * @param {number[]} candidates * @param {number} target * @return {number[][]} */ var combinationSum = function (candidates,.. 2021. 3. 2.
LeetCode 20 - Valid Parentheses (Easy) 문제 LeetCode - 20번 풀이 과정 스택 을 활용하는 대표적인 괄호 쌍 맞추기 문제입니다. 닫는 괄호 가 나타났을 때 스택의 가장 위에 짝이 맞는 여는 괄호 가 존재하는지 판단하면 되는 문제입니다. 이번 문제를 통해 javascript 의 includes 메서드를 활용하는 방법을 알 수 있게 되었습니다. || 연산자로 or 처리 해주는 것이 코드도 길어지고 번거로웠는데 원하는 요소가 존재하는지 판단하는 includes 를 활용해서 쉽게 조건을 판단할 수 있었습니다. 코드 /** * @param {string} s * @return {boolean} */ function top(stack) { return stack[stack.length - 1]; } var isValid = function (s.. 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.
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.

티스토리툴바