문제 정보 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..

나의 카카오 뷰 채널 이야기 IT로그 라는 채널 이름답게 IT 관련된, 제가 요즘 관심이 있는 지식을 발행합니다. 채널을 만들자 마자 친구가 5 명이 되었는데 ( 본인 포함 ) 그 이후에도 쭉 5명이었습니다. 단순히 1일 1보드 발행만으로는 클릭율을 떠나서 노출이 거의 없다시피해서 조회 수나 친구가 없었는데 보드 관계자 분이 우연히 친구 추가를 해주신 건지 친구가 3명이나 늘었습니다. 물론 친구를 늘리고 수익을 창출하려고 채널을 개설한 것은 아니지만... 진전이 없는데도 열심히 하는 게 정말 힘든것 같습니다. PC 에서는 채널에 있는 컨텐츠를 볼 수가 없고 모바일은 카카오톡 어플에서 접속이 가능합니다. http://pf.kakao.com/_BeRsb 쫑인스 IT로그 IT 와 관련된 다양한 내용을 매일 발..

문제 정보 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 ..