그리디 알고리즘과 우선순위 큐

그리디

그리디 알고리즘은 

현재 상태에서 볼 수 있는 선택지 중에 최선의 선택을 하는 알고리즘이다.

 

그리디 알고리즘은 동적 계획법보다 구현하기 쉽고 시간 복잡도가 우수하다.

하지만 항상 최적의 해를 보장하지 못한다...

 

그래서 코테에서는 그리디 알고리즘 사용 전에 항상 그리디 알고리즘을 적용할 때의 논리 유무를 충분히 살피라고 한다.

 

그리디 알고리즘의 핵심 이론

그리디 알고리즘 수행 과정

 

1. 해 선택: 현재 상태에서 가장 최선이라고 생각되는 해 선택

2. 적정설 검사: 현재 선택한 해가 전체 문제의 제약 조건에서 벗어나지 않는지 검사하기

3. 해 검사: 현재까지 선택한 해 집합이 전체 문제를 해결 가능한 지 검사

                  만약 전체 문제를 해결 못할거 같으면 1로 돌아가 과정 반복

 

문제 풀면서 익히는게 가장 좋다.

 

그리디 알고리즘에서 자주 사용하는 자료구조 : 우선순위 큐

그리디 알고리즘이 현재 상황에서 최선의 선택을 반복하는 알고리즘이라서

우선순위 큐 (Priority Queue)를 사용하여 문제 해결하는 경우가 흔하다.

 

파이썬에서는 우선순위 큐 자료구조를 아래와 같이 두 가지 방법으로 제공

 

Priority Queue

# <import>
from queue import PriorityQueue

# <생성 방법>
myque = PriorityQueue()		# myque를 우선순위 큐로 생성

# <기본 함수>
put(data)			# 원소 추가
get()				# 큐에서 데이터 꺼내기
qsize()				# 큐 사이즈 가져오기
empty()				# 큐가 비어 있는지 확인

 

headq

# <import>
import headq

# <생성 방법>
mylist = []				# 리스트 생성
headq.heappush(mylist, 1)		# 리스트에 데이터를 넣을 때 heappq를 이용하여 저장

# <기본 함수>
heappush(mylist. data)			# data를 list(heap 자료구조) 형태로 저장
heappop(mylist)				# list(heap 자료구조)에서 데이터 꺼내기
heapify(mylisy)				# 일반적인 list를 heap 자료구조로 변환

 

두 모듈 사용법에는 약간 차이가 있다.

PriorityQueue는 객체 자체를 우선순위 큐 형태로 만들어 사용

heapq는 기본적인 list 객체를 대상으로 원소 삽입, 삭제(꺼내기) 등의 제공 함수를 통해 우선순위 큐를 구현한다.

 

 

 

 

책 <Do It! 알고리즘 코딩테스트>_김종관 지음, 이지스퍼블리싱 출판사

학교 알고리즘 수업 강의자료 등 여러 자료 참고해서 공부함.