알고리즘 정리 🏃♂️
1월에 있을 코딩테스트를 대비해서 복습한다는 마음으로 Leetcode의 14일 알고리즘 스터디를 진행한 내용을 정리합니다!
Day 1 (Binary Search - 이분 탐색)
간단한 이분 탐색의 정의
이분 탐색은 정렬된 배열이나 리스트에서 원하는 값을 찾을때 사용하는 탐색 기법입니다.
기본적으로 방대한 길이의 최대 길이가 주어지는것이 일반적으로,
만약 O(N)으로 풀이가 불가능하지만 정렬되어 있는 공간에서의 탐색 문제가 나온다면
이분 탐색을 적용해보는것을 고려해볼 수 있습니다.
704. Binary Search
이분 탐색의 개념을 익히고 넘어갈 수 있는 가장 기본적인 문제입니다.
보시는것과 같이 정렬되어 있는 배열에서의 타겟값을 구하는 문제로 출제가 됬습니다.
문제 조건에서 반드시 O(logN)으로 구현해야 하는것을 볼 수 있습니다.
var search = function(nums, target) {
let left = 0;
let right = nums.length - 1;
while (left <= right) {
const index = Math.floor((left + right) / 2);
if (target === nums[index]) {
return index;
}
if (target > nums[index]) {
left += 1;
}
else {
right -= 1;
}
}
return -1;
};이분 탐색은 가장 왼쪽의 인덱스와 가장 오른쪽의 인덱스를 선언하고
둘을 합친 값을 2로 나눈 몫을 새로운 인덱스로 만들어 값을 찾는 과정을 진행합니다.
위 문제는 target이 유니크하기 때문에 만약 찾은 경우 바로 값을 return해 줍니다.
만약 target 보다 현재 index의 값이 작은경우 index를 높이기 위해 left의 값을 증가시킵니다.
반대의 경우 index를 낮히기 위해(값을 낮추기 위해) right의 값을 감소시킵니다.
이러한 과정을 반복하고 탐색을 진행하며 target을 찾아나가는 방법입니다.
278. First Bad Version
이분 탐색 문제 풀이의 중요한점은
- 정렬되어있는지 스스로 알아내야 한다는 점
- 범위를 정할 수 있어야 한다는 점입니다.
첫번째 문제와 다르게 이번 문제에서는 배열의 인덱스가 주어져 있지 않기때문에
left, right 값을 어떻게 정해야할까? 라는 점을 생각해봐야 합니다.
이때 자연스럽게 주어져있는 n, 즉 1~n이 범위가 된다는 점을 파악할 수 있습니다.
var solution = function(isBadVersion) {
/**
* @param {integer} n Total versions
* @return {integer} The first bad version
*/
return function(n) {
let left = 1;
let right = n;
while (left < right) {
const mid = Math.floor((left + right) / 2);
if (isBadVersion(mid)) {
right = mid;
}
else {
left = mid + 1;
}
}
return right;
};
};첫 번째 문제와 동일한 코드 양식인것은 비슷하다고 볼 수 있습니다.
하지만 조건을 통해 return 해주지 않고 반복문이 끝난 뒤 right 값을 return 해주고 있습니다.
이번 문제의 포인트는 정확한 값이 아닌
값이 될 수 있는 경우에서의 최소값을 구하는 문제라는 점입니다.
즉 조건에 맞는 값을 찾았다고 해도, 그 값을 그대로 return 하지 않고
계속해서 값을 찾아 나간다는 점이 다른 포인트라고 할 수 있습니다.
최소값을 찾기 위해 right는 계속 -1 될것이고
더 이상 조건에 맞지 않는다면 left는 증가하면서 결국 while문을 벗어나게 될것입니다.
이때의 right 값은 조건에 맞는 값 중에서 가장 작은 값일겁니다.
35. Search Insert Position
이번 문제는 만약 target이 존재하면 return 하되
없다면 오름차순 순서를 기준으로 몇 번째 index에 들어가야 하는지를 묻는 문제였습니다.
var searchInsert = function(nums, target) {
let left = 0;
let right = nums.length - 1;
while (left <= right) {
const index = Math.floor((left + right) / 2);
if (target === nums[index]) {
return index;
}
if (target < nums[index]) {
right -= 1;
}
else {
left += 1;
}
}
return left;
};역시나 같은 양식의 코드가 보입니다.
몇번째 index에 들어가야 하는가? 는 결국에는
target에 가장 가깝지만 작은 값을 가진 인덱스를 구하는것과 같습니다.
즉 이때 left 값은 계속해서 target과 값이 가까워지도록 증가할것이고
만약 배열내부에 target보다 작은값만 존재한다면
배열의 길이를 넘어선 left 값이 while문을 빠져나올것입니다.
오늘 배운점 🤓
이분 탐색을 복습하면서 잃어버린 감을 찾을 수 있었다..!!
