본문 바로가기

🏃 algorithm/leetcode93

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.

LeetCode 221 - Maximal Square (Medium) 문제 LeetCode - 221번 풀이 과정 주어진 martix 안에서 가장 큰 정사각형을 찾는 문제입니다. 각각의 정사각형은 또다른 정사각형으로 구성되어 있다는 점을 통해 동적 계획법 으로 풀이가 가능한 문제입니다. 따라서 dp(x, y) = (x, y)를 왼쪽 모서리로 하는 최대 정사각형의 한 변의 길이 라고 정의한다면 다음과 같은 점화식을 세울 수 있습니다. dp(x,y) = 0 if board[x][y] == 0 else min(dp(x+1, y), dp(x+1, y+1), dp(x, y+1)) + 1 이때 board 의 각 지점을 순회하며 1이 발견될때마다 dp 를 호출하며 최대값을 갱신하면 원하는 결과를 얻을 수 있습니다. 코드 /** * @param {character[][]} matrix .. 2021. 3. 2.

LeetCode 543 - Diameter of Binary Tree (Easy) 문제 LeetCode - 543번 풀이 과정 이진트리의 지름을 구하는 문제입니다. 이진트리 혹은 일반적인 트리의 지름을 찾기 위해서는 임의의 두 정점 사이의 간선의 개수가 가장 많은 경로를 알아내야합니다. 우선 root 를 루트 노드로 가지는 트리가 다음과 같이 두 가지가 존재할 수 있습니다. 1 / \ 2 3 /\ 4 5 1 / 2 / \ 4 5 위 그림에서는 이진 트리를 가정했지만 일반적인 트리에서도 동일하게 적용됩니다. 따라서 하나의 서브트리에서 가장 긴 경로(지름)는 잎노드 - 잎노드 혹은 루트노드 - 잎노드 의 형태를 가지게 됩니다. 루트노드 - 잎노드 의 경우 트리의 높이를 구하면 되지만 잎노드 - 잎노드 의 경우 내부 노드 사이에서 가장 긴 경로가 형성될 수 있기 때문에 다른 아이디어가 필요.. 2021. 3. 2.

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

티스토리툴바