
1. 오늘의 학습 키워드 : 이분 탐색(Binary Search)
이진탐색이라고도 하는 이분탐색입니다.
- 이분 탐색
정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법
*정렬이 포인트!!
변수 3개(start, mid, end)를 사용해 탐색한다. 찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교해 원하는 데이터를 찾는 것이 이분탐색의 과정
- 시간 복잡도
O(log N)
2. 오늘의 문제 : Search Insert Positon
https://leetcode.com/problems/search-insert-position/
이진탐색의 아주아주 기본 문제입니다!!
3. 풀이
class Solution {
public int searchInsert(int[] nums, int target) {
int left = 0;
int right = nums.length - 1;
while(left <= right){
int mid = (right+left)/2;
if(target == nums[mid])
return mid;
else if(target > nums[mid])
left = mid + 1;
else
right = mid - 1;
}
return left;
}
}
처음에 오류가 나서... 왜이러지 이게 맞는데 하고보니까 while문에 left와 right를 반대로 쓴거있죠... 이렇게라도 오류를 고쳐 해결한 점에 아주 저 자신을 칭찬합니다!
3. 회고
이진 탐색 얼마전에 알고리즘 강의를 들으며 풀었던 문젠데 금방 기억이 나지 않았어요... 하지만 이렇게 발전하다 보면 할 수 있겠죠? 오늘 클럽장님께서 모든 문제를 완전탐색으로 접급해보고 DP로 풀지 정한다고 하셨는데 시간 복잡도가 10억 이렇게 되면 이진 탐색을 도전한다고 하셔서 그 점 명심하고 코테 문제에 적용하려고 합니다.
참고 사이트
https://jaime-note.tistory.com/161
[LeetCode - Daily Challenge] 35. Search Insert Position
소스 코드는 여기 있습니다. 문제는 여기 있습니다. Problem Given a sorted array of distinct integers and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order. You
jaime-note.tistory.com
이분은 코드뿐만아니라 테스트코드까지 작성해서 올려주셨더라구요. 자기주도프로젝트할 때 교수님께서 테스트코드 작성이 아주 중요하다 해서 보며 공부하는게 좋을 것 같아 가져왔습니다!
이진 탐색(Binary Search) 알고리즘 개념
😀우리가 일상생활에서 나이맞추기 퀴즈? 같은 것을 하거나 주변인과 소통을 하면서 특정 수에 대해서 나는 결과를 알고있고, 상대방이 못 맞췄을 때 힌트를 주기위해서 up & down으로 특정 수를
velog.io
'항해99_코테스터디' 카테고리의 다른 글
[항해99]99클럽 코테 스터디 16일차 TIL + 그래프 (1) | 2024.06.13 |
---|---|
[항해99]99클럽 코테 스터디 15일차 TIL + 이분탐색 (1) | 2024.06.11 |
[항해99]99클럽 코테 스터디 13일차 TIL + 동적계획법 (1) | 2024.06.10 |
[항해99]99클럽 코테 스터디 12일차 TIL + 동적계획법 (0) | 2024.06.08 |
[항해99]99클럽 코테 스터디 11일차 TIL + 동적계획법 (1) | 2024.06.07 |