[항해99 취업 리부트 코스 학습일지] Day 15 - 알고리즘 : 이분 탐색

오늘 목표

• TIL 작성
• 필수 과제 모두 풀기

---

학습한 것

이진 탐색이란?

정렬이 이미 되어 있는 리스트에서 탐색의 범위를 절반씩 줄여나가며 데이터를 탐색하는 방법을 의미한다. 다음과 같은 특징을 가진다.

• 변수 3개를 사용해 탐색한다.(start, mid, end or left, mid, right)
  • start: 시작 범위
  • mid : 중간 위치에 있는 데이터
  • end : 끝 범위
• 탐색의 범위를 절반 단위로 줄이기 때문에 시간 복잡도는 O(log₂N) 이다.

다음과 같은 예시를 통해서 이해해보자.

코드 및 실행 예시

# 시작 데이터
arr = [1,2,3,4,5,6,7,9,10]

# 찾으려는 값
target = 8

# 1회 탐색(start = 1, mid = 5, end = 10)
# mid의 값보다 찾으려는 값이 작은지 큰지 확인.
# 찾으려는 값이 만약 더 크다면 start를 mid보다 한 칸 큰 수로 이동
# 이미 mid가 target보다 작기 때문

# 2회 탐색(start = 6, mid = 8, end = 10)
# 다시 target과 mid의 값을 비교
# 찾았으면 탐색과정 종료.

def binary_search(arr: list[int], target: int):
    left = 0
    right = len(arr) - 1
    arr = sorted(arr)

    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1 # not found
    
 print(binary_search(arr,target))

정렬

이진 탐색은 탐색 알고리즘 중에서 가장 간단하고 좋은 알고리즘이지만 전제 조건은 반드시 탐색하려는 자료구조가 정렬되어 있어야 한다. 파이썬에서는 정렬을 위해 2가지 함수를 제공한다.

• a.sort() : a를 정렬해서 값을 변경해준다.(원본 데이터 변경)
• sorted(a) : a를 정렬한 값을 복사해서 만들어준다.(원본 데이터 유지)

두 함수 모두 내부적으로 reverse와 key 매개변수를 활용해 다양한 정렬이 가능하다.

• reverse : 별도의 조건이 없으면 오름차순 정렬이지만, reverse = true로 사용할 경우 내림차순 정렬
• key : 특정 키워드 값을 기준으로 정렬하며, lambda 함수를 활용해서 많이 지정한다.
  • ex) a.sort(key = lambda x : x*x)  # x^2을 기준으로 값을 정렬

위와 같은 정렬 함수를 활용해 값을 정렬한 뒤 사용한다면 충분히 좋은 탐색 알고리즘이라 할 수 있겠다.

투포인터

투포인터는 2개의 포인터를 기준으로 범위를 점차 줄여 나가면서 진행을 하는 알고리즘이다. 이진 탐색과 유사해 보이지만 이진 탐색은 처음과 끝을 기준으로 하지만, 투포인터의 경우 2개의 포인터를 시작지점에서 같이 출발해도 되고, 양끝에서 와도 되고 그건 본인이 결정할 문제이다.

투포인터와 이진탐색

	이진탐색	투포인터
시간복잡도	O(log n)	O(n)
기법	mid를 지정하여 탐색범위를 절반으로 탐색	문제에서 주어진 조건을 맞추는 방향 양끝단 혹은 좌에서 우로 탐색
조건	데이터 정렬 sort 필요	필요 x, 있으면 좋음.

 

---

좋았던 점

멘토링 때 정렬은 풀 때 사용하는 것보다 면접을 대비해서 정렬 알고리즘의 종류나 각각의 이론에 대해서 아는 것이 더 중요하다고 말씀하셨다. 문제를 풀 때는 그냥 sort 함수를 쓰면 되지만, 면접에서는 정렬의 이론적인 내용에 대해서 인지하고 사용하고 있는지에 대해서 물어볼 수 있다고 말씀하셨다. 뿐만 아니라 자신의 주력 언어가 어떤 정렬 알고리즘 기반으로 만들어진 정렬 함수인지도 인지한다면 더 도움될 것이라 생각한다.

---

아쉬웠던 점

알고리즘 실력이 단기간에 늘어난다고 생각하는 것은 욕심이지만 그래도 꾸준히 하는 것 잘하고 있다고 생각한다. 다만 주력 언어와 개발 실력이 부족한데 알고리즘만 붙잡고 있어도 되는지 하는 불안은 조금씩 들긴 한다. 내일부터 조금씩이라도 주력 언어와 스프링 부트 학습도 해야겠다.

---

항해99 취업 리부트 코스를 수강하고 작성한 콘텐츠입니다.

IT 커리어 성장 코스 항해99, 개발자 취업부터 현직자 코스까지