그리디 알고리즘은 최적화 문제를 대상을 하고 그리디 알고리즘은 그 문제를 해결하기 위한 최소한의 아이디어를 떠올릴 수 있는 능력을 요구한다.
즉, 특정한 문제를 직면했을 때, 단순히 현재 상황에서 최적으로 보이는 것만을 선택해도 문제를 풀 수 있는지 파악해야 한다.
또한, 그리디 알고리즘 문제는 정렬 알고리즘과 자주 짝을 이룬다. 정렬을 한 상태에서 기준을 만족시키는 경우가 많기 때문이다.
그리디 알고리즘에 대표적인 예시로 '거스름 돈' 문제를 이용해 그리디 알고리즘을 설명해 보겠다.
문제: 카운터에는 거스름돈으로 사용할 500원, 100원, 50원, 10원짜리 동전이 무한히 존재한다고 가정하고, 손님에게 거슬러 줘야 할 돈이 N원일 때 거슬러 줘야 할 동전의 최소 개수를 구하여라. 단, 거슬러 줘야 할 돈 N은 항상 10의 배수이다.
이 문제는 그리디 알고리즘을 이용해 풀 수 있는 대표적인 문제로 간단한 아이디어만 떠올릴 수 있으면 문제를 해결할 수 있다. 바로 '가장 큰 화폐 단위부터' 돈을 거슬러 주는 것이다.
N=int(input())
count = 0
# 큰 단위의 화폐부터 차례로 확인.
coin_types = [500 , 100, 50, 10]
for coin in coin_types:
count += n // coin #해당 화폐로 거슬러 줄 수 있는 동전의 개수
n %= coin
print(count)
화폐의 종류가 K라고 할 때 이 코드의 시간 복잡도는 O(K) 이다.
하지만 대부분의 그리디 알고리즘 문제는 이처럼 문제 풀이를 위한 최소한의 아이디어를 떠올리고 이것이 정당한지 검토할 수 있어야 정답을 도출할 수 있다.
리스트가 순서를 매긴 데이터를 나열하는 자료구조라면 , 트리는 데이터 사이의 계층 관계를 표현하는 트리 구조이다.
트리에 대해 이해를 하려면 먼저 트리의 구조와 관련된 용어를 알아야 한다.
트리의 구조
위 사진과 같이 트리는 노드와 가지(edge)로 구성된다. 각 노드는 가지를 통해 다른 노드와 연결이 된다.
루트 : 트리의 가장 위쪽에 있는 노드를 루트(root)라고 한다. 루트는 트리 하나에 1개만 존재한다.
리프 : 가장 아래쪽에 있는 노드를 리프(leaf)라고 한다. 리프는 단말 노드(terminal node), 외부 노드(external node)라고도 한다. (물리적으로 가장 밑에 위치한다는 의미가 아니라 가지가 더 이상 뻗어나갈 수 없는 마지막에 노드가 있다는 뜻이다.)
비단말 노드 : 리프를 제외한 노드(루트는 포함)를 비단말 노드라고 한다. 비단말 노드는 내부 노드(internal node)라고도 한다.
자식 : 어떤 노드와 가지가 연결되었을 때 아래쪽 노드를 자식(child)라고 한다. 노드는 자식을 몇 개라도 가질 수 있다. 하지만 가장 아래쪽 리프는 자식을 갖지 않는다.
부모 : 어떤 노드와 가지가 연결되었을 때 가장 위쪽에 있는 노드를 부모(parent)라고 한다. 노드의 부모는 하나뿐이다. 루트는 부모를 갖지 않는다.
형제 노드 : 부모가 같은 노드를 형제(sibiling)라고 한다.
레벨 : 루트에서 얼마나 멀리 떨어져 있는지를 나타내는 것이 레벨이다. 가장 위쪽에 있는 루트의 레벨은 0이고, 가지가 하나씩 아래로 뻗어 내려갈 때마다 레벨이 1씩 증가한다.
차수 : 각 노드가 갖는 자식의 수를 차수(degree)라고 한다. 모든 노드의 차수가 n이하인 트리를 n진 트리라고 한다.
순서 트리와 무순서 트리
트리는 형제 노드의 순서 관계가 있는지에 따라 2종류로 분리된다. 형제 노드의 순서 관계가 있으면 순서 트리(ordered tree)라 하고, 구별하지 않으면 무순서 트리(unordered tree)라고 한다.
순서 트리의 검색
순서 트리의 노드를 스캔하는 방법은 크게 2가지이다.
1. 너비 우선 검색 (breadth-first search)
2. 깊이 우선 검색(depth-first search)
너비 우선 검색
너비 우선 검색은 폭 우선 검색, 가로 검색, 수평 검색이라고도 한다. 너비 우선 검색은 낮은 레벨부터(루트) 왼쪽에서 오른쪽으로 검색하고, 한 레벨에서 검색을 마치면 다음 레벨로 내려가는 방법이다.
너비 우선 검색
검색 순서: A > B > C> D > E > F > G> H > I > J > K > L
깊이 우선 검색
깊이 우선 검색은 세로 검색, 수직 검색이라고도 한다. 깊이 우선 검색은 리프에 도달할 때까지 아래쪽으로 내려가면서 검색하는 것을 우선으로 하는 방법이다. 리프에 도달해 더 이상 검색할 곳이 없으면 일단 부모 노드로 돌아가고 그 뒤 다시 자식 노드로 내려간다.
깊이 우선 검색
어느 시점에서 실제로 노드를 방문하는지에 따라 깊이 우선 검색은 세 종류의 스캔 방법으로 구분한다.
1. 전위 순회 (preorder)노드 방문 -> 왼쪽 자식 -> 오른쪽 자식A > B > D > H > E > I >J > C> F > K > L >G
2. 중위 순회 (inorder)왼쪽 자식 > 노드 방문 >오른쪽 자식H> D > B > I > E> J > A > K > F> L > C > G
3. 후위 순회 (postorder)왼쪽 자식> 오른쪽 자식> 노드 방문H>D>I>J>E>B> K > L >F > G > C > A
데이터를 일정한 순서로 정렬하는 정렬 알고리즘이 있다. 예를 들어, 정렬은 이름, 학번, 학점 등의 key의 항목 값의 대소관계에 따라 데이터 집합을 일정한 순서로 바꾸어 늘어놓는 작업을 말한다.
데이터를 정렬하면 데이터를 더 쉽게 검색할 수 있다는 장점이 있다.
-오름차순 ascending order 정렬
-내림차순 descending order 정렬
정렬 알고리즘 가운데 대표적인 알고리즘 8가지가 있다. 정렬 알고리즘은 안정적인 알고리즘과 그렇지 않은 알고리즘으로 나눌 수 있다.
또한 정렬 알고리즘은 하나의 배열에서 작업할 수 있는 경우 내부 정렬(internal sorting)을 사용하고, 그렇지 않은 경우 외부 정렬 (external sorting)을 사용한다.
내부 정렬: 정렬할 모든 데이터를 하나의 배열에 저장할 수 있는 경우에 사용하는 알고리즘
외부 정렬: 정렬할 데이터가 많아서 하나의 배열에 저장할 수 없는 경우에 사용하는 알고리즘
*정렬 알고리즘의 핵심은 교환/선택/삽입 이다.
대부분의 정렬 알고리즘은 이 3가지를 응용하며, 앞서 말한 대표적인 8가지의 정렬 알고리즘에서도 자주 쓰이는 핵심 개념이다.
버블 정렬
버블 정렬(bubble sort)은 이웃한 두 원소의 대소 관계를 비교하여 필요에 따라 교환을 반복하는 알고리즘이다.
시간 복잡도 : O(n**2)
버블 정렬 예시
def bubbleSort(x):
"""버블 정렬 코드 """
length = len(x)-1
for i in range(length):
for j in range(length-i):
if x[j] > x[j+1]:
x[j], x[j+1] = x[j+1], x[j]
return x
선택 정렬 (selection sort)
선택 정렬은 가장 작은 원소부터 선택해 알맞은 위치로 옮기는 작업을 반복하며 정렬하는 알고리즘이다.
시간 복잡도 : O(n**2)
선택 정렬 교환 과정은 다음과 같이 이루어진다.
1. 아직 정렬하지 않은 부분에서 값이 가장 작은 원소 a[min]을 선택.
2. a[min]과 아직 정렬하지 않은 부분에서 맨 앞에 있는 원소를 교환.
#단순 선택 정렬 알고리즘 구현
def selection_sort(a):
"""단순선택 정렬"""
n= len(a)
for i in range(n-1):
min=i #정렬한 부분에서 가장 작은 원소의 인덱스
for j in range(i+1, n):
if a[j] < a[min]:
min= j
a[i] , a[min] = a[min], a[i] #정렬할 부분에서 맨 앞의 원소와 가장 작은 원소를 교환
삽입 정렬
삽입 정렬은 주목한 원소보다 더 앞쪽에서 알맞은 위치로 삽입하며 정렬하는 알고리즘이다.
단순 선택 정렬과 비슷해 보이지만 값이 가장 작은 원소를 선택하지 않는다는 점에서 차이가 있다.
시간 복잡도 : O(n**2)
이 글에서 다룬 단순 정렬(버블, 선택, 삽입) 알고리즘의 시간 복잡도는 모두 O(n**2)으로 프로그램 효율이 좋지 않다.
이진 검색 알고리즘을 사용하려면 배열의 데이터가 정렬되어 있어야 하고 이진 검색은 선형 검색보다 빠르게 검색할 수 있다는 장점이 있다.
*이진 검색은 원소가 오름차순이나 내림차순으로 정렬된 배열에서 좀 더 효율적으로 검색할 수 있는 알고리즘이다.
이진 검색 그림 예시
이진 검색의 검색 범위의 맨 앞, 맨 끝, 중앙의 인덱스를 각각 pl,pr,pc라고 하고 중앙 값부터 검색 범위를 계속 좁혀가면 된다.
# binary search 이진검색 알고리즘
from typing import Any,Sequence
def bin_search(a:Sequence, key:Any) -> int:
"""sequence a에서 key와 일치하는 원소를 이진검색"""
pl = 0 #검색 범위 맨 앞 원소의 인덱스
pr = len(a) - 1 # 검색 범위 맨 끝 원소의 인덱스
while True:
pc = (pl+pr) //2 #중앙 원소의 인덱스
if a[pc] == key:
return pc
elif a[pc] < key:
pl = pc+1 #검색 범위를 뒤쪽 절반으로 좁힘
else:
pr = pc-1 # 검색범위를 앞쪽 절반으로 좁힘
if pl>pr:
break
return -1 # fail search
if __name__=='__main__':
num=int(input('원소수를 입력하세요: '))
x = [None] * num
print('배열 데이터를 오름차순으로 입력')
x[0] = int(input('x[0]: '))
for i in range(1,num):
while True:
x[i] = int(input(f'x[{i}]: '))
if x[i] >= x[i-1]: #바로 직전에 입력한 원솟값보다 큰 값을 입력
break
ky=int(input('put the value: '))
idx = bin_search(x,ky)
if idx==-1:
print('검색값을 갖는 원소가 존재하지 않습니다.')
else:
print(f'검색값은 x[{idx}]에 있습니다.')
이 중 오늘 정리할 내용은 바로 '배열 검색'이며 구체적으로 다음과 같은 알고리즘이 있다.
1.선형 검색 : 무작위로 늘어놓은 데이터 집합에서 검색을 수행
2. 이진 검색: 일정한 규칙으로 늘어놓은 데이터 집합에서 아주 빠른 검색을 수행
3. 해시법: 추가, 삭제가 자주 일어나는 데이터 집합에서 아주 빠른 검색을 수행
-체인법: 같은 해시값 데이터를 연걸 리스트로 연결하는 방법
-오픈 주소법: 데이터를 위한 해시값이 충돌할 때 재해시하는 방법
데이터 집합이 있을 때 , 검색만 빠르게 하고싶다면 계산 시간이 짧은 알고리즘을 선택하면된다.
그러나 데이터 집합에서 검색뿐 아니라 데이터의 추가,삭제 등을 자주 수행해야 한다면 검색 이외의 작업에 들어가는 비용을 종합 평가하여 알고리즘을 선택해야 한다.
선형 검색 (linear search)
선형 검색은 무작위로 늘어놓은 데이터 집합에서 검색을 수행하며 배열에서 검색하는 방법중 가장 기본적인 알고리즘이다.
직선 모양으로(선형)으로 늘어선 배열에서 검색하는 경우에 원하는 키 값을 가진 원소를 찾을 때까지 맨 앞부터 스캔하여 순서대로 검색한다.
선형검색 설명 예시
선형 검색의 종료 조건에는 두가지가 있다.
1. 검색할 값을 찾지 못하고 배열의 맨 끝을 지나간 경우
2. 검색할 값과 같은 원소를 찾는 경우
*배열 원소의 개수가 n개라면 이 조건을 판단하는 횟수는 평균 n/2번이다.
#while 문으로 작성한 선형 검색 알고리즘
from typing import Any,Sequence
def seq_search(a: Sequence, key: Any) -> int:
"""sequence a에서 key와 값이 같은 원소를 선형 검색(while문)"""
i=0
while True:
if i==len(a):
return -1
if a[i]==key:
return i #검색에 성공하여 현재 검사한 배열의 인덱스를 반환
i+=1
if __name__=='__main__':
num = int(input('원소 수를 입력하세요: '))
x = [None] * num
for i in range(num):
x[i] = int(input(f'x[{i}]'))
ky= int(input('검색할 값: ')) #검색할 ky를 입력받음
idx = seq_search(x,ky) # ky와 값이 같은 원소를 x에서 검색
if idx == -1:
print('검색값을 갖는 원소가 존재하지 않습니다.')
else:
print(f'검색값은 x[{idx}]에 있습니다.')
#for문으로 작성한 선형 검색 알고리즘
#while 문과 비교해 배열의 스캔을 for문으로 구현하면 코드가 더 짧고 간결해짐.
from typing import Any,Sequence
def seq_search(a:Sequence, key:Any) -> int:
"""시퀀스 a에서 key와 값이 같은 원소를 선형검색"""
for i in range(len(a)):
if a[i] == key:
return i
return -1
* 배열 맨 앞부터 순서대로 원소를 스캔하는 선형 검색은 원소의 값이 정렬되지 않은 배열에서 검색할 때 사용하는 유일한 방법이다 .
재귀 알고리즘이란? 어떠한 event에서 자기 자신을 포함하고 다시 자기 자신을 사용하여 정의되는 경우 재귀(recrusion)이라고 함. 재귀를 효과적으로 사용하면 이러한 정의뿐만 아니라 프로그램을 간결하고 효율성 좋게 작성 가능. 재귀 알고리즘은 풀어야 할 문제나 계산할 함수 또는 처리할 자료구조가 재귀적으로 정의되는 경우 적용.
def hello(count):
if count == 0:
return
print("Hello",count)
count-=1
hello(count)
hello(5)
"""재귀 대표적인 예시"""
유클리드 호제법 Euclidean Algorithm
두 정수의 최대 공약수를 재귀적으로 구하기.
두 정수 x와 y의 최대 공약수 gcd(x,y)
ex) x=az 와 y=bz를 만족하는 정수 a,b와 최대의 정수 z가 존재할 때 z는 gcd(x,y) 라고 할 수 있음
- y==0 -> x
- y!=0 -> gcd(y,x%y)
<코드>
"""유클리드 호제법으로 최대공약수 구하기"""
def gcd(x:int,y:int) -> int:
"""정숫값 x와 y의 최대 공약수 반환"""
if y==0:
return x
else:
return gcd(y,x %y)
if __name__ == '__main__':
print('gcd 구하기')
x=int(input())
y=int(input())
print(f'두 정숫값의 최대 공약수는 {gcd(x,y)}.')
하노이의 탑
Towers of Hanoi는 쌓아 놓은 원반을 최소 횟수로 옮기는 알고리즘인 하노이의 탑.
● 작은 원반이 위에, 큰 원반이 아래에 위치
● 크기가 모두 다른 원반 첫번째 기둥에 쌓여있는 상태로 시작.
● 이 상태에서 모든 원반을 세 번째 기둥에 최소 횟수로 옮기기
● 원반은 1개씩 옮길 수 있으며 큰 원반은 작은 원반 위에 쌓을 수 없음.
#하노이의 탑 구현
def move(no: int, x: int, y:int) -> None:
"""원반 no개를 x기둥에서 y기둥으로 옮김"""
if no > 1:
move(no-1, x , 6-x-y)
print(f'원반 [{no}]를 {x}기둥에서 {y}기둥으로 옮깁니다.')
if no > 1:
move(no-1,6-x-y,y)
print('하노이의 탑 구현')
n=int(input('원반의 개수 입력: '))
move(n, 1, 3) #1기둥에 쌓인 원반 n개를 3기둥으로 옮김
