본문 바로가기

👨‍💻📱✍️🎢314

LeetCode 416 - Partition Equal Subset Sum (Medium) 문제 LeetCode - 416번 풀이 과정 주어진 배열에서 두 그룹으로 나누었을 때 두 그룹의 합이 같은 경우가 존재하는지 찾는 문제입니다. 0-1 knapsack 문제와 비슷하게 특정 인덱스의 숫자를 선택할지 안할지를 따져서 문제를 해결하면 됩니다. 우선 목표 합 target = total / 2 이며 나누어 떨어지지 않는 경우는 해가 존재하지 않으므로 이를 따로 예외처리합니다. 그 다음 dp[i, k] = i 이후 숫자들을 선택해서 합이 k 가 되는 경우가 존재하는지 라고 정의한다면 다음과 같은 점화식을 얻을 수 있습니다. dp[i, k] = dp[i+1, k-num[i]] or dp[i+1, k] 코드 /** * @param {number[]} nums * @return {boolean} */ v.. 2021. 3. 4.
LeetCode 560 - Subarray Sum Equals K (Medium) 문제 LeetCode - 560번 풀이 과정 특정 구간의 합이 k 이 되는 총 개수를 구하는 문제입니다. 원래 투 포인터 를 사용해서 구하려고 했는데 음수가 존재하기 때문에 올바른 값을 구할 수 없었습니다. 따라서 1차원 배열에 누적 합을 계속 기록하면서 계산을 수행합니다. 여기서 합이 k 가 되는 구간을 찾기 위해서는 다음과 같이 생각해볼 수 있습니다. a, b, ... e, f ... 만약 f 까지의 합이 30이고 우리가 찾는 k = 20 일 때 a ~ f 까지 숫자 중에서 합이 10 인 지점을 찾으면 됩니다. 그 이유는 a ~ b = 10 이라면 c ~ f 의 구간이 30 - 10 = 20 이 되기 때문입니다. (구간 합 알고리즘) 코드 /** * @param {number[]} nums * @pa.. 2021. 3. 4.
LeetCode 752 - Open the Lock (Medium) 문제 LeetCode - 752번 풀이 과정 문자열을 기준으로 특정 숫자에 도달하기 위한 최소 회전수를 구하는 문제입니다. 각 숫자에 대해서 증가하거나 감소할 수 있으며 deadends 에 포함되지 않는 숫자에 대해서만 탐색을 진행합니다. 따라서 조건에 맞도록 BFS 를 수행하며 목표 숫자에 도달하기 위한 최소 횟수를 구하면 됩니다. 코드 /** * @param {string[]} deadends * @param {string} target * @return {number} */ var openLock = function (deadends, target) { const digits = ["0", "1", "2", "3", "4", "5", "6", "7", "8", "9"]; function bfs(st.. 2021. 3. 4.
LeetCode 11 - Container With Most Water (Medium) 문제 LeetCode - 11번 풀이 과정 두 막대기를 기준으로 가장 많은 물을 담을 수 있는 방법을 찾는 문제입니다. 완전 탐색 으로 접근할 경우 O(N^2) 에 문제를 해결할 수 있지만 투 포인터 를 사용하면 O(N) 에 가능합니다. 두 막대가 다음과 같이 존재한다고 하겠습니다. 편의상 2, 1, 4 크기의 막대를 각각 다른 위치에 그렸지만 사실은 가장 왼쪽과 오른쪽 막대 중간의 어느 특정 위치 X 에 위치할 수 있는 막대의 3 종류를 나타낸 것입니다. 위와 같이 가장 왼쪽에 위치한 막대를 L 그 반대를 R 이라고 했을 때 어느 포인터를 옮겨야 최대 적재 컨테이너를 구할 수 있을까요? 만약 R 의 포인터를 왼쪽으로 옮길 경우 2, 1, 4 막대 모두 R 보다 작기 때문에 절대 더 큰 컨테이너를 구할 .. 2021. 3. 4.
LeetCode 763 - Partition Labels (Medium) 문제 LeetCode - 763번 풀이 과정 투 포인터 와 그리디 알고리즘 을 사용하는 문제입니다. partition 이 특정 문자들의 집합으로 이루어져 있을 때 가장 많은 partition 으로 나누기 위해서는 우선 다음과 같이 생각해볼 수 있습니다. 먼저 partition A 의 가장 첫 문자가 a 라고 한다면, 해당 partition 에는 문자열 S 에 존재하는 모든 a 를 포함해야합니다. 따라서 문자열 S 에서 가장 마지막에 존재하는 a 를 포함해야합니다. 그러므로 partition 의 기준이 되는 포인터 right 와 각 partition 의 문자들을 검사하기 위한 포인터 left 를 선언해서 탐색을 수행하면 됩니다. 코드 /** * @param {string} S * @return {numbe.. 2021. 3. 4.
LeetCode 48 - Rotate Image (Medium) 문제 LeetCode - 48번 풀이 과정 주어진 배열을 90도 시계방향으로 회전하는 연산을 추가 메모리 없이 구현해야하는 문제입니다. 삼성 SW 역량 테스트 기출 문제에서도 비슷한 구현 요구사항이 존재하는 문제가 있었는데 그때는 임시값을 저장할 변수를 하나 둬서 회전 연산을 수행했습니다. 이번에는 배열의 모든 요소를 회전해야하기 때문에 비효율적인 거 같아서 다른 분의 구현 방법을 참고했습니다. 가장 간단한 방법으로는 전치 행렬을 만든 다음 각 행을 뒤집는 연산을 수행하는 것입니다. 조금만 생각해보면 되는 문제였는데 앞으로 비슷한 유형의 문제가 나오면 잊자말고 활용해야겠습니다. 코드 /** * @param {number[][]} matrix * @return {void} Do not return anyt.. 2021. 3. 4.

티스토리툴바