👨💻📱✍️🎢314 LeetCode 236 - Lowest Common Ancestor of a Binary Tree (Medium) 문제 LeetCode - 236번 풀이 과정 이진 트리가 주어질 때 가장 가까운 공통 조상을 찾는 문제입니다. 여기서 가장 가까운 조상 노드가 되기 위해서는 두 가지 경우의 형태를 가집니다. q (A) a (A) / / \ b b q / / p p위 그림에서 p & q 의 공통 조상 중 가장 가까운 노드는 전자의 경우 q 이고 후자의 경우 a 가 됩니다. 이를 통해 우리가 찾는 조상 노드 A 는 왼쪽과 오른쪽 서브트리에 각각 p 혹은 q 가 존재하거나 조상 노드 A 를 포함하고 나머지 한 노드가 왼쪽 혹은 오른쪽 서브트리에 존재하는 형태를 가집니다. 따라서 DFS 를 수행하며 우리가 찾는 타켓 노드 p, q 의 존재 유무를 판단하고 현재 루트 노드를 포함해서 자식들 중 p 혹은 q 가 모두 발견되는 첫 .. 2021. 3. 4. LeetCode 494 - Target Sum (Medium) 문제 LeetCode - 494번 풀이 과정 양의 정수들로 이루어진 배열이 주어질 때 + 와 - 를 적절히 사용해서 특정 합 S 를 만들 수 있는 경우의 수를 찾는 문제입니다. 배열의 길이가 최대 20 이고 + 와 - 두 가지만 존재하기 때문에 최대 2^20 의 경우의 수만 탐색하면 됩니다. 따라서 DFS 를 이용해서 모든 경우의 수를 따져봐도 되지만 DFS 과정에서 중복이 발생할 수 있고 최적 부분 구조를 따르기 때문에 동적 계획법 을 사용해서 문제를 해결했습니다. dp(x, sum) = 배열의 x 위치부터 선택해서 그 합이 sum을 만족시키는 경우의 수 라고 한다면 다음과 같은 점화식을 세울 수 있습니다. dp(x, sum) = dp(x+1, sum + x) + dp(x+1, sum - x) 코드 /.. 2021. 3. 4. LeetCode 187 - Repeated DNA Sequences (Medium) 문제 LeetCode - 187번 풀이 과정 주어진 문자열에서 10자 이상의 부분 문자열 중 2번 이상 반복되는 모든 부분 문자열의 종류를 찾는 문제입니다. 해시 테이블 를 사용하면 O(N) 에 모든 경우를 탐색할 수 있습니다. 이외에도 두 개의 Set 을 사용하면 동일한 로직을 수행할 수도 있습니다. (구현은 이게 더 깔끔한 것 같습니다 😄) 코드 /** * @param {string} s * @return {string[]} */ var findRepeatedDnaSequences = function (s) { if (s.length = 1) .. 2021. 3. 3. LeetCode 3 - Longest Substring Without Repeating Characters (Medium) 문제 LeetCode - 3번 풀이 과정 중복된 문자가 없는 부분 문자열 중에서 가장 길이가 긴 것을 찾는 문제입니다. 두 개의 포인터 head, tail 를 활용해서 윈도우를 나타내고 중복된 문자가 발견되면 현재 윈도우에서 중복된 문자의 위치로 head 를 이동시키면 됩니다. 코드 /** * @param {string} s * @return {number} */ var lengthOfLongestSubstring = function (s) { const cache = new Map(); let head = 0; let tail = 0; let answer = 0; for (; tail < s.length; tail++) { if (cache.has(s[tail])) { const duplicateInd.. 2021. 3. 3. LeetCode 89 - Gray Code (Medium) 문제 LeetCode - 89번 풀이 과정 n 자리의 gray code 를 생성하는 문제입니다. gray code 는 인접한 비트 1개를 바꾸는 방식으로 만들어갑니다. 4자리의 gray code 를 보면 특정한 규칙성이 존재하는 것을 알 수 있습니다. 따라서 재귀 호출 로 가능한 모든 gray code 를 생성하고 10 진수롤 변환해서 반환하면 됩니다. 코드 /** * @param {number} n * @return {number[]} */ var grayCode = function (n) { if (n === 0) return [0]; function code(bit) { if (bit > n) return [""]; const subsets = code(bit + 1); const zeroStart.. 2021. 3. 3. LeetCode 118 - Pascal's Triangle (Easy) 문제 LeetCode - 118번 풀이 과정 파스칼 삼각형을 구현하는 문제입니다. 1번째 행과 2번째 행은 각각 [1] 과 [1, 1] 로 따로 처리해주고 나머지 경우는 마지막 행의 인접한 요소들을 더해서 새로운 행을 만들면 됩니다. 코드 /** * @param {number} numRows * @return {number[][]} */ var generate = function (numRows) { const answer = []; let walker = 1; while (walker 2021. 3. 3. 이전 1 ··· 36 37 38 39 40 41 42 ··· 53 다음
