[코테 스터디] 1주차 : 자료구조 / 이진탐색

📌스택 ( Stack )

선입후출( FILO ; First In Last Out ) 방식 = 먼저 들어온 데이터가 나중에 나가는 방식

Stack 이 '쌓다' 라는 의미라는 것을 상기하면 이해하기 편함

🤚🏻파이썬으로 구현하기 

파이썬에서는 별도의 라이브러리 없이 List 자료형을 사용하여 스택 구현 가능

# Stack 
stack = [] # list()

# 데이터 삽입
stack.append(1)  # [1]
stack.append(2)  # [1,2]
stack.append(3)  # [1,2,3]

# 데이터 추출
stack.pop()     # [1,2]
stack.pop()     # [1]

 

📌큐 ( Queue )

선입선출( FIFO ; First In First Out ) 방식 = 먼저 들어온 데이터가 먼저 나가는 방식

🤚🏻파이썬으로 구현하기

몇 가지 방법이 있지만 collections 모듈의 deque를 가장 많이 사용

큐와 스택 둘 다 구현 가능하며 큐는 popleft()  , 스택은 pop()  사용

from collections import deque

queue = deque()
stack = deque()

queue.append(1)
queue.append(2)
queue.append(3)
stack.append(1)
stack.append(2)
stack.append(3)

queue.popleft() # deque([2, 3])
queue.popleft() # deque([3])

stack.pop()  # deque([1, 2])
stack.pop()  # deque([1])

 

📌이진탐색 ( Binary Search ) 

정렬된 배열에서 특정한 값을 효율적으로 찾는 탐색 알고리즘

탐색 범위를 반으로 줄여가며 데이터를 찾는 과정을 반복하여 탐색 효율성 극대

분할정복(Divide and Conquer) 방식의 대표적인 예시

💡작동 로직

1. 데이터가 정렬되어 있어야 함.
   이진 탐색은 데이터가 정렬되어 있지 않은 경우 올바른 결과를 보장할 수 없음
2. 중간점 선택하기 
   탐색 범위 내에서 중간 위치의 요소를 선택 
3. 탐색 조건 비교하기
   중간점의 데이터와 찾고자 하는 값(target)을 비교.
   • 중간점 = target  
     탐색 종료
   • 중간점 < target
     탐색 범위의 왼쪽 부분을 버리고 오른쪽 부분을 새로운 탐색 범위로 설정
   • 중간점 > target 
     탐색 범위의 오른쪽 부분을 버리고 왼쪽 부분을 새로운 탐색 범위로 설정
4. 반복 수행 
   2번, 3번 과정 반복 

 

💡이진 탐색 장/단

[장점]

• 효율성 : O(log n)의 시간 복잡도. 대규모 데이터셋에서도 탐색 시간이 로그 시간으로 증가하기 때문에 매우 빠름
• 간결함 : 알고리즘 구현이 간결하고 이해 쉬움

[단점]

• 정렬된 데이터 : 데이터가 미리 정렬되어 있어야 하는 전제조건이 있음. 
• 동적 데이터셋 : 데이터셋이 자주 변경되어 재정렬이 필요한 경우 이진탐색의 효율성 떨어짐

 

💡이진 탐색 활용

배열에서의 값 탐색, 범위 내의 특정 조건 만족하는 요소 찾기 (최소 최대 값 경계 찾기 ) , 알고리즘 문제 해결 시 탐색 범위  좁혀나가는 과정 등

🤚🏻파이썬으로 구현하기 

1️⃣재귀적인 방법 ( binary_search_recursive )

def binary_search_recursive(arr, target, left, right):
    if left > right:
        return -1  # 조건 성립 안됨

    mid = (left + right) // 2

    if arr[mid] == target:
        return mid
    elif arr[mid] < target:
        return binary_search_recursive(arr, target, mid + 1, right)
    else:
        return binary_search_recursive(arr, target, left, mid - 1)

# 사용 예시
arr = [1, 3, 5, 7, 9, 11, 13, 15]
target = 13
result = binary_search_recursive(arr, target, 0, len(arr) - 1)
print(f"Target {target} found at index {result}")  # Target 13 found at index 6

만약, 배열이 오름차순이 아닌 내림차순의 형태로 주어진다면 if - elif - else 조건 구문만 다음과 같이 수정하면 된다.

    if arr[mid] == target:
        return mid
    elif arr[mid] > target:
        return binary_search_recursive(arr, target, mid + 1, right)
    else:
        return binary_search_recursive(arr, target, left, mid - 1)

 

2️⃣반복문을 사용한 방법 ( binary_search_iterative )

def binary_search_iterative(arr, target):
    left, right = 0, 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  # Target not found

# 사용 예시
arr = [1, 3, 5, 7, 9, 11, 13, 15]
target = 13
result = binary_search_iterative(arr, target)
print(f"Target {target} found at index {result}")  # Target 13 found at index 6

배열이 오름차순이 아닌 내림차순일 경우 재귀방식과 동일하게 if-elif-else 구문만 수정하면 된다.

        if arr[mid] == target:
            return mid
        elif arr[mid] > target:
            left = mid + 1
        else:
            right = mid - 1