leetcode87 LeetCode 48 - Rotate Image (Medium) 문제 LeetCode - 48번 풀이 과정 주어진 배열을 90도 시계방향으로 회전하는 연산을 추가 메모리 없이 구현해야하는 문제입니다. 삼성 SW 역량 테스트 기출 문제에서도 비슷한 구현 요구사항이 존재하는 문제가 있었는데 그때는 임시값을 저장할 변수를 하나 둬서 회전 연산을 수행했습니다. 이번에는 배열의 모든 요소를 회전해야하기 때문에 비효율적인 거 같아서 다른 분의 구현 방법을 참고했습니다. 가장 간단한 방법으로는 전치 행렬을 만든 다음 각 행을 뒤집는 연산을 수행하는 것입니다. 조금만 생각해보면 되는 문제였는데 앞으로 비슷한 유형의 문제가 나오면 잊자말고 활용해야겠습니다. 코드 /** * @param {number[][]} matrix * @return {void} Do not return anyt.. 2021. 3. 4. 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. 이전 1 ··· 4 5 6 7 8 9 10 ··· 15 다음
