WEEK02 - 컴퓨팅사고로의 전환 2
이번 2주차에는 이분탐색 분할정복법 스택 큐 우선순위큐 에 대한 내용들을 공부하고 관련 문제들을 풀어보았다. 간단하게 개념 및 구현코드로 정리해보려고 한다.
이분탐색 (Binary Search)
정렬되어있는 리스트에서 원하는 값을 빠르게 찾기 위한 알고리즘으로, 리스트를 절반으로 나누고 중간에 위치한 값과 원하는 값을 비교하여 범위를 좁혀가는 과정으로 진행된다.
# while문 활용
def binary_search(arr, key) :
left = 0
right = len(arr) - 1
while True :
chk_idx = (left + right) // 2
if arr[chk_idx] == key :
return chk_idx
if arr[chk_idx] > key :
right = chk_idx-1
else :
left = chk_idx+1
if left > right : return -1
# 재귀 적용
def binary_search_recul(arr, key, left, right) :
chk_idx = (left + right) // 2
if arr[chk_idx] == key : return chk_idx
if arr[chk_idx] > key :
if left > chk_idx-1 : return -1
return binary_search_recul(arr, key, left, chk_idx-1)
else :
if chk_idx+1 > right : return -1
return binary_search_recul(arr, key, chk_idx+1, right)분할정복법 (Devide and Conquer)
문제를 2개 이상의 작은 문제로 분할하고 작은 문제들을 해결함으로써 큰 문제를 정복해내는 방법이다.
대표적인 한가지 예로 A의 N제곱을 구한다고 하면, A의 N/2제곱을 먼저 구한 뒤 이를 제곱함으로써 최종 결과를 얻을 수 있다.
# A의 B제곱을 구하는 함수
def cal(A,B) :
# B가 1이라면 A 그대로 반환
if B == 1 :
return A
# B가 짝수라면 A의 B//2 제곱을 먼저 구한뒤 이의 제곱을 반환
if B%2 == 0 :
return (cal(A,B//2) ** 2)
# B가 홀수라면 A의 B//2 제곱을 먼저 구한뒤 이의 제곱에 A를 곱한 값을 반환
else :
return (cal(A,B//2) ** 2) * A
print(cal(A,B,C))스택 (Stack)
마지막에 저장한 값을 먼저 빼내는 후입선출(LIFO: Last In First Out) 방식의 자료구조이다.
리스트의 append / pop으로 간단하게 구현할 수 있다.
# 리스트의 가장 오른쪽에 데이터를 추가
list.append()
# 리스트의 가장 오른쪽 데이터를 반환하고 제거
list.pop()큐 (Queue)
먼저 저장한 값을 먼저 꺼내는 선입선출(FIFO: First In First Out) 방식의 자료구조이다.
리스트와 포인터를 사용한 class를 정의하여 구현할 수 있으며, deque 라이브러리를 사용하여 간단하게 구현할 수도 있다.
from collections import deque
que = deque()
# 큐의 오른쪽에 데이터 삽입
que.append(data)
# 큐의 가장 왼쪽에 있는 데이터를 반환하고 제거
que.leftpop()우선순위큐 (Priority Queue)
가장 크거나 작은 값을 먼저 꺼내는 방식의 자료구조이다.
heapq 라이브러리를 사용하여 구현할 수 있다.
import heapq
heapq.heapify(list)
# 데이터를 리스트에 최소힙 방식으로 추가
heapq.heappush(list,data)
# 리스트에서 최소값을 반환 후 제거
heapq.heappop()heapq는 최소힙으로 구현되어있어 최대힙으로 사용하려면 -를 붙여주면 된다.
# 데이터를 리스트에 최소힙 방식으로 추가 - (-를 넣었기 때문에 pop하고 -를 붙이면 최대힙이 됨)
heapq.heappush(list,-data)
# 리스트에서 최소값을 반환 후 제거
-heapq.heappop()정리
이번 주차에는 자료구조를 어떻게 잘 활용할 수 있을지 생각해볼 수 있었다.
문제들을 그냥 해결하려고 달려들면 어떤 개념을 어떻게 적용해야할지 감이오질 않았다.
하여 문제를 파악할 때, 어떤 자료구조와 어떤 알고리즘이 필요할지 문제정의를 잘 하고 접근해야겠다고 느꼈다.
