본문 바로가기

Algorithm202

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 62 - Unique Paths (Medium) 문제 LeetCode - 62번 풀이 과정 전형적인 동적 계획법 을 활용한 경로 찾기 문제입니다. 시작 지점에서 이동할 수 있는 방향이 오른쪽과 아래쪽으로 고정되어 있기 때문에 dp(x, y) = (x, y) 지점에서 finish에 도달하는 경로의 개수 라고 정의한다면 다음과 같은 점화식을 세울 수 있습니다. dp(x, y) = dp(x+1, y) + dp(x, y+1) 이때 격자를 벗어나거나 finish 지점에 도착하는 기저 사례를 처리해준다면 쉽게 문제를 해결할 수 있습니다. 코드 /** * @param {number} m * @param {number} n * @return {number} */ var uniquePaths = function (m, n) { const memo = new Array.. 2021. 3. 2.
LeetCode 121 - Best Time to Buy and Sell Stock (Easy) 문제 LeetCode - 121번 풀이 과정 시세가 주어진 배열에서 주식을 사고 팔았을 때 가장 큰 이윤을 남기는 방법을 찾는 문제입니다. 직관적으로 주식이 가장 낮을 때 사서 가장 높을 때 파는 것이 가장 큰 이윤을 남긴다는 것을 알 수 있습니다. 따라서 배열의 각 요소를 순회하며 최소 비용 값을 갱신해주는 것과 동시에 각 상품마다 현재 인덱스까지 탐색한 최소 비용 과의 차이값을 통해 최대 판매 수익 을 O(N)의 시간 복잡도로 얻을 수 있습니다. 정당성 증명 최소 비용을 선택하는 우리의 탐욕 알고리즘 은 자명하기 때문에 간단히 증명하고 O(N) 에 탐색을 수행할 수 있다는 정당성을 따져보겠습니다. 우선 매 시세마다 최소비용을 갱신한 결과 최적해를 찾지 못했다고 하겠습니다. 이 경우 실제 최적해(가정).. 2021. 3. 2.
LeetCode 101 - Symmetric Tree (Easy) 문제 LeetCode - 101번 풀이 과정 주어진 트리가 최상위 루트를 중심으로 서로 대칭구조를 이루고 있는지 판단하는 문제입니다. 이를 위해서 대칭구조를 가지고 있는 트리를 하나 예시로 그려서 알고리즘을 설계하였습니다. 위와 같이 대칭 구조를 가지고 있는 트리를 어떤 방법으로 판단해줄 수 있을까요? 여러가지 방법이 있겠지만 저는 트리의 순회를 응용하여 구현하였습니다. 대칭적인 구조를 가진 트리는 최상위 루트를 기준으로 왼쪽 서브트리와 오른쪽 서브트리의 배치가 서로 반대이기 때문에 왼쪽 서브트리에서는 일반적인 전위 순회 를 수행하였고, 오른쪽 서브트리에서는 대칭되어 있다는 가정하에 왼쪽 자식보다 오른쪽 자식을 먼저 방문하게하여 탐색을 수행했습니다. 만약 해당 트리가 대칭구조를 가지고 있다면 두 순회 결.. 2021. 3. 2.

티스토리툴바