[TIL-20260203] 코딩 테스트 - Linked List , 이진 탐색(Binary Search)

🍀 To Do List

 

✔️ 코테 알고리즘 강의 - LinkedList 문제, 이진탐색

✔️ 이력서 초안 작성

✔️ 사이드 프로젝트 - refresh token 발급 로직 수정

 

👩🏻‍💻 Today I Learned ...

 

Linked List

숫자 변환 패턴

초기값: sum = 0
1. 0 * 10 + 6 = 6      (6)
2. 6 * 10 + 7 = 67     (십의 자리로 밀고 7 추가)
3. 67 * 10 + 8 = 678   (백의 자리로 밀고 8 추가)

 

`[6] -> [7] -> [8]` 이렇게 이어진 링크드 리스트를 `678` 숫자 형태로 변환할 때

기존 숫자를 10배로 곱하고, 현재 숫자를 더해서 왼쪽으로 자릿수를 확장할 수 있다.

 

코드로 표현하면 아래와 같다.

 

sum = sum * 10 + cur.data
# 0 → 6 → 67 → 678

 

 

 

이진 탐색(Binary Search)

# 최소     탐색     타겟 최대
# [0, 3, 5, 6, 1, 2, 4]
# UP -> [1, 2, 4]
# DOWN -> [0, 3, 5]

def is_exist_target_number_binary(target, array):
    current_min = 0
    current_max = len(array) - 1
    current_guess = (current_min + current_max) // 2 # ⭐️ 가운데 기준점

    while current_min <= current_max:
        if array[current_guess] == finding_target:
            return True
        elif array[current_guess] < target:
            # UP
            current_min = current_guess + 1
        else: # array[current_guess] > target
            # DOWN
            current_max = current_guess - 1

        current_guess = (current_min + current_max) // 2

    return False

• 매번 탐색 범위를 절반으로 줄인다.  
  • 가운데 값부터 확인하여, 점점 탐색 범위를 줄인다. (오른쪽 or 왼쪽)
  • 업다운 게임을 예로 기억하면 쉽다.
• 일반 탐색
  • 1개씩 확인→ 최대 N번 
  • 시간 복잡도 : `O(N)`
• 이진 탐색
  • 입력 범위가 매번 감소
  • 시간 복잡도 : `O(log N)`

 

💡 python에서 숫자 내림

- `//` 연산자를 이용하면 소수점 이하의 수를 모두 버리고 몫만 나타낼 수 있다.

>>> print((4 + 5) / 2)
4.5
>>> print((4 + 5) // 2)
4

 

 

이진 탐색 전제 조건

• 정렬된 배열에서만 사용 가능하다.
• 정렬되지 않은 배열인 경우, 가운데 값 기준으로 어떤 부분을 탐색해야 하는지 알 수 없다.

 

🔍 이진 탐색 코테 문제 유형

1. 최대/최소 값 구하기

2. 정답 후보를 넣고 "가능" 여부 판단 ex)길이가 10이면 가능?

3. 범위가 엄청 큼

4. 정렬된 상태 or 정렬 가능한 데이터

5. 완전 탐색 할 경우 시간 초과될 것 같을 때