👨💻📱✍️🎢314 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. 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. LeetCode 876 - Middle of the Linked List (Easy) 문제 LeetCode - 876번 풀이 과정 연결 리스트에서 중간 위치의 값을 찾는 문제입니다. 별도의 알고리즘을 요구하는 것이 아닌 단순 구현 문제로 리스트의 head 부터 포인터를 옮겨가며 리스트의 크기를 구한 뒤 중간 위치를 계산하여 구했습니다. 코드 /** * Definition for singly-linked list. * function ListNode(val, next) { * this.val = (val===undefined ? 0 : val) * this.next = (next===undefined ? null : next) * } */ /** * @param {ListNode} head * @return {ListNode} */ var middleNode = function (head).. 2021. 3. 2. 이전 1 ··· 43 44 45 46 47 48 49 ··· 53 다음
