📌스택 ( 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) 방식의 대표적인 예시
💡작동 로직
- 데이터가 정렬되어 있어야 함.
이진 탐색은 데이터가 정렬되어 있지 않은 경우 올바른 결과를 보장할 수 없음 - 중간점 선택하기
탐색 범위 내에서 중간 위치의 요소를 선택 - 탐색 조건 비교하기
중간점의 데이터와 찾고자 하는 값(target)을 비교.- 중간점 = target
탐색 종료 - 중간점 < target
탐색 범위의 왼쪽 부분을 버리고 오른쪽 부분을 새로운 탐색 범위로 설정 - 중간점 > target
탐색 범위의 오른쪽 부분을 버리고 왼쪽 부분을 새로운 탐색 범위로 설정
- 중간점 = target
- 반복 수행
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
'🏷️CS > Algorithm' 카테고리의 다른 글
[코테 스터디] 2주차 : 시간복잡도 (0) | 2024.06.17 |
---|---|
[코테 스터디] 2주차 : DFS/BFS (1) | 2024.06.17 |
[백준] 1966 (프린터 큐) (2) | 2023.07.26 |
[백준] 구현 2941 / 1193 / 2775 (1) | 2023.05.13 |
[백준] 구현 1157 / 4673 / 1316 (0) | 2023.05.09 |