문제 정보 Leet Code 문제 링크 난이도 : Medium 해결 방법 pay[val] 을 val 가격을 지불하는데 필요한 최소 코인 갯수 라고 정의한다면 Dynamic Programming 를 사용할 수 있습니다. pay[코인 중 1개의 가격] = 1 이고 pay[코인1 가격 + 코인2 가격] = 2 이므로 가능한 가격들 중 최소값을 구할 수 있기 때문입니다. Dynamic Programming 을 사용하면서 묘하게 불필요한 연산이 들어가는 것 같이 느꼈었는데, 지금까지는 거의 DP 풀이를 Top-Down 방식을 사용했고 Memoization 으로 구현했었습니다. 그런데 이번 문제는 Bottom-Up 방식을 사용했고 Tabulation 으로 구현했습니다. Memoization 은 재귀를 이용하기 때문..

문제 정보 Leet Code 문제 링크 난이도 : Medium 해결 방법 처음에는 회로도 처럼 AND, OR, XOR 게이트 등을 상요하면 구현할 수 있을 거라고 생각을 했었는데 결국 구현이 힘들어서 Discuss 탭에 있는 답안들을 참고했습니다. a & b 와 a ^ b 를 구분해서 a & b 는 Carry 로

문제 정보 Leet Code 문제 링크 난이도 : Easy 해결 방법 bitwise 연산인 >>> 을 반복적으로 사용하면서 i 번째 자리에 숫자가 존재하는지 여부를 확인하고 2^(n-i) 를 반복해서 더해주는 방법으로 구현했습니다. 다른 제출된 답안들을 확인해 봐도 한 두 가지 방법을 제외하고는 (실제 구현하는 방법은 조금씩 다르겠지만) 컨셉은 비슷했습니다. 소스 코드 // Leet Code // #190. Reverse Bits // Success // Runtime: 103 ms, faster than 33.55% of JavaScript online submissions for Reverse Bits. // Memory Usage: 40.6 MB, less than 49.41% of JavaScri..

문제 정보 Leet Code 문제 링크 난이도 : Easy 해결 방법 문제 자체가 기본적인 Dynamic Programming 의 꼴을 하고 있어서 그렇게 구현했습니다. dp 함수를 따로 사용하지 않고 배열에 for loop 를 순회하면서 데이터를 채워 넣어도 구현이 가능합니다. 소스 코드 // Leet Code // #70. Climbing Stairs // Success // Runtime: 72 ms, faster than 74.80% of JavaScript online submissions for Climbing Stairs. // Memory Usage: 38.6 MB, less than 58.88% of JavaScript online submissions for Climbing Stairs..

문제 정보 Leet Code 문제 링크 난이도 : Easy 해결 방법 문제 자체는 쉬운 편이어서 곧바로 Follow up 의 조건을 포함해서 구현하려고 했습니다. 이런 저런 알고리즘을 생각하다 보니 어느 순간 '다 더해서 빼면 되겠다' 라는 생각이 들었습니다. Follow up: Could you implement a solution using only O(1) extra space complexity and O(n) runtime complexity? Discuss 탭을 보던 중 한줄만에 구현한 댓글도 있었습니다. 컨셉은 동일하나 reduce 를 자주 사용하진 않아 문제를 고민할 때는 미처 생각이 나지 않는 것 같습니다. return -nums.reduce((acc,num,i)=> acc+num-i-1..

문제 정보 Leet Code 문제 링크 난이도 : Easy 해결 방법 첫 번째로 시도한 방법은 1 의 개수를 구하는 방법은 n >> 1 을 반복해서 첫번째 bit 에서 갯수를 세는 것 입니다. n >> 1 의 시간복잡도가 log n 이기 때문에 총 시간복잡도는 O(n log n) 입니다. 두 번쨰로 시도한 방법은 Dynamic Programming 으로 점화식은 getOnes(n) = 1 + getOnes(n - maxBitNum(n)) 입니다. 세 번째는 Discuss 탭에 있던 글을 참고했는데 두 번째와 비슷한 방법이지만 반대로 maxBitNum 을 따로 구하지 않고 >> 1 로 비트를 shift 한 뒤 첫 번째 자리의 갯수를 세는 방법입니다. Follow up 조건을 만족합니다. Follow up:..

문제 정보 Leet Code 문제 링크 난이도 : Easy 해결 방법 해결 하는 방법 자체는 n 이 0이 아닐 때까지 >>> bitwise 연산을 해주면서 1의 개수를 셌습니다. 문제는 이진법의 수를 표현하는 방법이었는데 Leet Code 에 나온 입력과는 다르게 자바스크립트 (를 포함한 다른 언어) 에서 사용하는 표현 법으로 앞에 '0b'를 붙여 주었습니다. 소스 코드 // Leet Code // #191. Number of 1 Bits // Success // Runtime: 130 ms, faster than 13.39% of JavaScript online submissions for Number of 1 Bits. // Memory Usage: 40.3 MB, less than 54.56% of..

문제 정보 Leet Code 문제 링크 난이도 : Medium 해결 방법 최악의 경우 막대 중 2개를 선택해서 최대 Area 를 비교할 수 있기 때문에 시간은 O(N^2) 보다 효율적으로 풀어야 합니다. 우선 O(N log N) 을 먼저 고려했을 때 대표적으로 Binary Search 같은 알고리즘을 생각할 수 있는데 정렬이 되지 않아 컨셉에 맞지 않았습니다. 풀이에 중점을 둬야할 부분이 넓고 낮은 Area 와 좁고 높은 Area 를 비교하는 것 입니다. 최대 높이를 기준으로 for loop 를 돌면서 계산할 경우 height 가 10의 4승까지 가능했기 때문에 최대 너비를 기준으로 left 와 right 를 비교하는 two-pointers 알고리즘으로 풀이 방향을 정했습니다. 핵심적인 부분은 left ..

문제 정보 Leet Code 문제 링크 난이도 : Medium 해결 방법 첫 번째로 풀었을 때는 특별히 다른 생각이 나지 않아서 가능한 경우의 수를 모수 구한 뒤 중복처리만 하도록 구현했습니다. O(N^3) 시간이 걸리기 때문에 당연히 Time Limit Exceeded 가 발생했고 해결을 위해서 몇 가지를 생각했습니다. // #1. 이중 for loop 를 순회하여 가능한 num[i] 값을 찾고 // 해당 값이 nums 배열에 존재하는지 여부 확인 nums[i] = - nums[j] - nums[k] // #2. 정렬에 O(N^2) 의 시간이 소요되므로 우선 정렬 후에 // 0 을 기준으로 case 를 나누어 가능한 값들을 Binary Search 로 탐색 // CASE 1. 0 0 0 // CASE ..

문제 정보 Leet Code 문제 링크 난이도 : Medium 해결 방법 이전에 풀었던 #153. Find Minimum in Rotated Sorted Array 문제와 비슷한데 Minimum 이 아닌 target 값을 찾는 문제입니다. 처음에는 이전 문제처럼 minimum 을 먼저 찾은 뒤 구간을 왼족 구간 ( nums[0] ~ nums[minIdx - 1] ) 과 오른쪽 구간 ( nums[minIdx] ~ nums[nums.length - 1] ) 으로 나누어 Binary Search 를 하려고 했었지만 Min 값 대신 target 값을 구하는 것으로 컨셉을 잡았습니다. 핵심은 rotate 된 정렬된 left side, right side 로 나누어서 target 과 nums[mid] 를 비교하면서..