정렬과 탐색의 기초

dreamya (70)in #krsuccess • 6 days ago

정렬과 탐색, “찾아줘!”를 빠르게 만드는 법

이전 글에서 반복문으로 패턴을 찾는 감각을 잡았지? 이제는 그 패턴을 더 똑똑하게 써볼 차례야.
이번 4-4에서는 데이터 정렬하고, 그 다음에 필요한 값을 탐색(찾기)하는 기본 알고리즘을 배워볼게. 솔직히 말하면, “그냥 다 훑으면 되지”라고 생각할 수도 있는데… 데이터가 커지면 그게 은근히 멘붕이 오거든. 나도 예전에 “아, 어차피 금방 찾겠지” 했다가 로그 찍어놓고 멍 때린 적 있어 😂

1) 정렬이 뭐길래 이렇게 중요해?

정렬은 말 그대로 데이터를 순서대로 줄 세우는 것이야.

예를 들면 이런 리스트가 있다고 해볼게.

[7, 3, 9, 1]

이걸 정렬하면 보통은:

오름차순: [1, 3, 7, 9]
내림차순: [9, 7, 3, 1]

왜 중요하냐면, 정렬을 해두면 탐색이 훨씬 쉬워지거든.
“정렬 전”엔 그냥 앞부터 다 봐야 하지만, “정렬 후”엔 어느 쪽을 봐야 하는지 판단할 수 있어.

2) 선형 탐색: 그냥 한 칸씩 훑는 방법

탐색은 “찾기”야. 정렬을 안 해도 할 수 있는 가장 기본은 선형 탐색(Linear Search)이야.

배열 앞에서부터 하나씩 확인
내가 찾는 값이면 끝
아니면 계속

예시로 target = 3을 찾아보자.

def linear_search(arr, target):
    for i in range(len(arr)):
        if arr[i] == target:
            return i  # 찾은 인덱스 반환
    return -1  # 없으면 -1

arr = [7, 3, 9, 1]
print(linear_search(arr, 3))  # 1

아! 여기서 중요한 느낌만 잡자.
선형 탐색은 데이터가 작을 땐 그냥저냥 잘 돼. 근데 데이터가 엄청 커지면… 음… 나름 상상 가능한 그 속도 저하가 와.
“솔직히 말하면” 이런 방식은 정렬/최적화가 필요 없을 때 쓰는 편이야.

3) 정렬하면 탐색이 달라진다: 이진 탐색의 감각

이제 진짜 재미 포인트.
정렬된 배열에서 찾을 때는 이진 탐색(Binary Search)이 핵심이야.

아이디어는 이거:

가운데 값을 본다
찾는 값이 가운데보다 작으면 왼쪽만
찾는 값이 가운데보다 크면 오른쪽만
범위를 계속 줄여나간다

처음엔 좀 “어? 이게 진짜 빨라?” 싶을 수 있어. 나도 처음 배울 때 “반으로 나누는 거면 무슨 마법이지?” 했거든. 근데 사실은 되게 논리적이야.

이진 탐색 예시 코드

def binary_search(arr, target):
    left = 0
    right = len(arr) - 1

    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

arr = [1, 3, 7, 9]  # 정렬된 상태!
print(binary_search(arr, 3))  # 1

중요한 조건 1개!
이진 탐색은 정렬된 배열에서만 제대로 동작해.
정렬 안 돼 있으면 그냥… “반을 잘라서 운 맞추기”가 돼버려. 내가 예전에 이거 실수해서 결과가 자꾸 이상하게 나왔는데, 알고 보니 배열이 정렬이 안 돼 있더라. 아… 그때 한숨 한 번 크게 쉬었지 😂