문제 정보 프로그래머스 문제 링크 난이도 : level 2 해결 방법 멀쩡하지 않은 사각형은 나눈 줄에 의해 쪼개져야(?) 하므로 각 칸에서 위쪽 선의 위치와 아래쪽 선의 위치로 찾을 수 있습니다. 기울기가 w / h 로 고정적이므로 아래 그림과 같이 한 줄에 멀쩡하지 않은 사각형이 몇개나 나오는지 계산했습니다. 소스 코드 // 프로그래머스 // 코딩테스트 연습 > Summer/Winter Coding(2019) > 멀쩡한 사각형 function main(){ let answer = new Array(); let output = new Array(); // 입출력 예 입력 answer.push(solution(8, 12)); answer.push(solution(10000000, 10000000)); a..

포스팅 목적 코딩 테스트 유형을 알아보고 유형별로 문제를 풀어봐야 대응할 수 있기 때문에 자주 출제되는 유형을 알고 빠르게 알고리즘을 선택하기 위해 포스팅 했습니다. (알고리즘) 코딩 테스트 유형 중요도 순 정리 완전 탐색 Exhaustive Search ( Brute Force ) 깊이 우선 탐색 ( DFS ) 넓이 우선 탐색 ( BFS ) 동적 프로그래밍 ( Dynamic Programming ) 그리디 ( Greedy ) 이진 탐색 ( Binary Search ) 파라메트릭 서치 ( Parametric Search ) 투 포인터 ( Two Pointer ) 유니온 파인드 ( Union-Find ) 크루스칼 프림 다익스트라 GCD (최대공약수, 최소공배수) 순열/조합 Backtracking Divid..

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