포스팅 목적 효율적인 탐색 알고리즘 중 하나인 이진 탐색을 코드 구현을 중심으로 알아봅니다. 이진 탐색의 정의 이진 탐색이란 데이터가 정렬되어 있는 배열에서 특정한 값을 찾아내는 알고리즘입니다. 예를 들어 특정 범위에 있는 숫자를 맞추는 UP & DOWN 게임을 할 때를 생각해 보면 가장 안정적이고 빠르게 답을 찾는 방법은 가장 한 숫자 범위 내에 있는 수 중에서 중간에 있는 숫자를 찍어서 그 숫자보다 큰지 작은지에 따라 다음 숫자를 결정하는 것 입니다. 이것이 이진 탐색입니다. 이진 탐색의 장단점 이진 탐색의 장점은 높은 효율성 입니다. 한 번 탐색할때 마다 탐색의 범위가 절반으로 줄어들기 때문에 시간 복잡도는 O(log N) 입니다. 앞의 정의에 나왔듯이 이진 탐색은 정렬되어 있는 배열에서만 사용할 ..

문제 정보 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] 를 비교하면서..

문제 정보 Leet Code 문제 링크 난이도 : Medium 해결 방법 첫 시도에 풀었던 방법은 단순히 이중 for loop 를 순회하면서 최대값을 찾는 방법이었습니다. O(n^2) 의 시간복잡도를 가져서 당연하게도, Time Limit Exceeded 가 발생했습니다. 그 다음 고려했던 방법은 nums[i] 요소의 제한 사항이 정수라는 것에 착안하여 0 을 제외하고는 절대값이 그 이전 값보다 같거나 클 수 밖에 없다는 점이었습니다. 답안을 보기 전에는 nums[i] 가 0 일 경우에 대해서만 고려해서 0 으로 초기화 되기 전의 값을 가져가면서 비교하는 방법이 있지 않을까 라는 생각을 했었는데 결국 구현하지는 못했습니다. 이 전에 있던 최소값이 이후에 나올 음수 값과 곱해지면서 최대값이 될 수 있도록,..

문제 정보 Leet Code 문제 링크 난이도 : Medium 해결 방법 아래와 같이 O(log n) 시간 내에 해결하라는 문제가 아니었다면 return Math.min(...nums); // O(n) 와 같이 한줄에 풀 수도 있지만 log n 이라는 시간 복잡도 자체에 Binary Search 등의 알고리즘으로 풀어야 한다는 힌트가 있습니다. You must write an algorithm that runs in O(log n) time. left 와 right 를 설정하여 위의 (잘 알아보기가 힘든) 그림과 같이 nums[mid] 가 nums[left] 보다 큰 경우는 mid 가 오른쪽으로 이동해야 하므로 left 값에 기존 mid + 1 값을 넣습니다. 첫 번째 구현에서는 예외 CASE 를 많이 ..

문제 정보 Leet Code 문제 링크 난이도 : Easy 해결 방법 이전에 풀었던 문제 중 #121. Best Time to Buy and Sell Stock 을 카데인 알고리즘 (Dynamic Programming) 으로 풀었을 때와 동일한 문제였습니다. dp[i] 를 i 번째 인덱스를 가장 오른쪽 끝으로 하는 subArray 의 최대값으로 정의 후 구현하면 기존 dp[i - 1] 에 현재 값인 nums[i] 를 더하거나 혹은 nums[i] 로 subArray 를 시작하는 경우로 나눌 수 있습니다. 이렇게 풀이할 경우 nums 의 길이만큼 for loop 를 1회 수행하므로 시간복잡도는 O(n) 이 됩니다. Follow up: If you have figured out the O(n) solution..

문제 정보 Leet Code 문제 링크 난이도 : Medium 해결 방법 문제의 답 자체는 모든 수를 for loop 나 reduce 메소드를 가지고 모든 수의 곱을 nums[i] divide 하고 0 으로 나누는 경우는 나머지를 모두 곱해서 구할 수 있습니다. 하지만 아래와 같이 제한 사항이 있기 때문에 for loop 를 순회하면서 나눗셈을 사용하지 않아야 합니다. You must write an algorithm that runs in O(n) time and without using the division operation. loop 를 두 번 순회하면서 왼쪽과 오른쪽으로 나누어 곱한 값을 result Array 에 저장하고 나머지 값을 곱해서 반환합니다. 소스 코드 // Leet Code // ..

문제 정보 Leet Code 문제 링크 난이도 : easy 해결 방법 첫 시도에는 하나의 수 라도 중복이 될 경우 true 이기 때문에 중복을 제거할 수 있는 수단 중 Set 을 사용해 구현했습니다. 코드는 간단했지만 생각보다 속도는 빠르지 않았습니다. Discuss 탭에 있던 글을 몇 가지 확인해 보니 Set 대신 Object 로 구현할 경우 모든 nums 에 대해 순회하지 않고 중복되는 수를 만났을 때 종료하는 하기 때문에 nums 의 크기가 커질 수록 Object 가 유리함을 알 수 있습니다. 1,000 elements (Set is 7x faster): Set: 0.15ms Object: 1.02ms 10,000 elements: Set: 0.87ms Object: 0.88ms 100,000 el..

포스팅 목적 개발자 면접과 관련된 영상을 몇 가지 시청하면서 질문에 대해 생각하지 못한 부분이 많았음을 알게 되었습니다. 면접관들이 무슨 질문을 왜 하는지 질문의 의도를 정리하고 어떤 부분에 포인트를 맞춰 답변을 해야 하는지 정리했습니다. 스타트업 개발자 면접 질문과 질문에 대한 의도 1. ( 포트폴리오나 코딩 테스트 등에서 ) 다양한 옵션 중 어떤 기술을 왜 선택했는가? 질문 의도 기술 관련 질문은 스스로 논리적 사고를 했는지 보기 위함입니다. 기술을 선택하게된 배경과 결과가 필요합니다. 선택이 가능한 다른 기술들과 비교했을 때 해당 기술의 장단점과 그로 인한 결과를 제시하는 논리적 근거가 필요합니다. 주의해야 할 것은 업무와 관련해서 의사소통이 되고 의견 개진이 가능한 사람인지를 보는 것이기 때문에 ..

문제 정보 Leet Code 문제 링크 난이도 : easy 해결 방법 첫 시도에는 단순히 이중 for loop 를 사용하여 O(n^2) 의 시간이 걸리게 구현하니 Time Limit Exceeded 을 판정되었습니다. 두 번째 시도에서는 prices 를 두번 순회하지 않기 위해 고민을 하던 중에 변화량을 기록하는 diff 라는 Array 를 만들고 최대 부분합을 구할 수 있는 Dynamic Programming 을 사용하여 값을 구했습니다. ( 참고로, 최대 부분합을 구하는 이 알고리즘을 카데인 알고리즘이라고 한다고 합니다. 기존 DP 와 내용은 같긴한데... 자주 등장하기 때문에 그런것 같습니다. ) 이렇게 풀고 나서 Solution 탭을 확인해보니 for loop 마다 minPrice 와 maxPro..

문제 정보 Leet Code 문제 링크 난이도 : easy 해결 방법 첫 시도에는 단순히 이중 for loop 를 사용하여 O(n^2) 의 시간이 걸리게 구현을 했습니다. Follow-up 에서 아래와 같이 더 빠른 풀이법을 요구했기 때문에 다른 방식의 풀이가 필요했습니다. Follow-up: Can you come up with an algorithm that is less than O(n2) time complexity? value 를 찾기 위해 index 를 모두 순회하여 O(n) 의 시간이 걸리는 Array 대신 맞는 key 값을 찾는데 O(1) 의 시간이 걸리는 Map 자료구조를 사용했습니다. key 는 덧셈에 사용할 숫자, value 는 index 입니다. map 에 두 개의 key 가 다 들..