👨💻📱✍️🎢314 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. LeetCode 283 - Move Zeroes (Medium) 문제 LeetCode - 283번 풀이 과정 정렬을 수행한 뒤에 같은 키 값을 가지는 원소들의 순서가 뒤바뀌지 않는 것을 stable sort 라고 합니다. 이번 문제에서는 주어진 배열에서 0을 배열의 끝쪽으로 옮겨주되 그 순서가 뒤바뀌면 안되는 로직을 구현하였습니다. 이때 별도의 array 를 복사하여 구현하면 안되고 배열 내에서 정렬이 in-place 로 수행되어야하므로 삽입정렬을 활용하여 구현했습니다. 삽입 정렬 은 배열의 끝 원소부터 하나씩 자신의 위치를 찾아 삽입 해주는 방식을 사용하는데, 여기서는 0을 발견할 때마다 0이 위치할 수 있는 위치를 반복해서 찾음으로서 O(N^2) 의 시간 복잡도로 문제를 해결하였습니다. 코드 /** * @param {number[]} nums * @return {.. 2021. 3. 2. LeetCode 678 - Valid Parenthesis String (Medium) 문제 LeetCode - 678번 풀이 과정 주어진 문자열에서 괄호쌍이 올바르게 짝지어졌는지 판단하는 문제입니다. 다만 이 문제에서는 와일드카드(*) 가 존재하여 약간의 다른 방식의 접근이 필요합니다. 우선 이 와일드카드를 어떤 식으로 처리할지 결정해야합니다. 각각의 와일드 카드는 ( 혹은 ) 혹은 빈칸 으로 사용될 수 있으므로 현재 괄호 스택을 가지고는 어떤 방식으로 사용해야할지 알 수 없습니다. 따라서 해당 와일드 카드는 다음 세 가지 경우로 사용 방법을 나눌 수 있습니다. * 보다 앞서 발견된 ( 문자의 ) 역할 * 보다 늦게 발견된 ) 문자의 ( 역할 아무 역할도 하지 않는 빈칸 다시 말해 ) 문자에 대응되는 ( 가 이전에 스택에 존재하지 않을 경우 * 를 대신 사용하도록 하면 됩니다. 따라서 큐.. 2021. 3. 2. LeetCode 1094 - Car Pooling (Medium) 문제 LeetCode - 1094번 풀이 과정 문제 분류는 탐욕 알고리즘 이지만 입력 값의 범위가 크지 않기 때문에 브루트 포스 로도 충분히 해결할 수 있는 문제였습니다. 우리가 찾아야 하는 것은 한 시점에 필요한 최대 capacity 입니다. 따라서 시간을 0.5 단위로 증가시키며 겹치는 최대 구간을 찾도록 합니다. 이때 0.5씩 증가시켜준 이유는 거리가 1 단위이기 때문입니다. (저와 같은 방법으로 구현한 분의 코드를 보니 시작 지점을 포함하고 종료 시간을 제외하여 1씩 증가시켜도 되도록 구현한 방법이 있었는데 그게 더 간단해보입니다.) 코드 /** * @param {number[][]} trips * @param {number} capacity * @return {boolean} */ var car.. 2021. 3. 2. LeetCode 49 - Group Anagrams (Medium) 문제 LeetCode - 49번 풀이 과정 주어진 입력에서 Anagram을 찾는 문제입니다. Anagram은 순서에 상관없이 두 단어를 구성하는 문자의 종류와 개수가 동일한 관계를 말합니다. Anagram을 판단하는 직관적인 방법은 두 단어를 정렬한 뒤 같은 지 비교하는 것입니다. Javascript 에서 String 을 정렬하기 위해서는 spread 연산을 통해 Array로 바꿔준 이후 sort 함수를 사용합니다. 코드 /** * @param {string[]} strs * @return {string[][]} */ var groupAnagrams = function (strs) { const anagram = new Map(); for (let word of strs) { let sorted = [... 2021. 3. 2. 이전 1 ··· 44 45 46 47 48 49 50 ··· 53 다음
