그리디 알고리즘 : 최적화 문제(가능한 해들 중 가장 좋은 해를 고르는)를 해결하는 알고리즘

 

◆그리디 알고리즘의 특징

 

1)데이터 간의 관계를 고려하지 않고 부분적인 최적해를 찾고, 이들을 모아서 문제의 최적해를 얻는다.

 

2)일단 한번 선택하면 그 데이터를 버리고 다른 것을 취하지 않는다.

 

 

 

◆그리디 알고리즘으로 해결 가능한 대표적인 문제들

 

1)동전 거스름돈

:거스름돈을 받을 때 가장 적은 수의 동전으로 주는 문제

 

#유사코드

 

 

#파이썬 소스

 

 

 

2)최소 신장 트리

:주어진 가중치 그래프에서 사이클이 없이 모든 점들을 연결시킨 트리들 중 선분들의 가중치 합이 최소인 트리

 

최소 신장 트리를 찾는 대표적인 그리디 알고리즘으로는 크러스컬프림 알고리즘이 있음.

 

#크루스컬 유사코드

 

 

#프림 유사코드

 

 

#파이썬 소스

 

*크러스컬과 프림 둘 다 제 파이썬 숙련도로는 무리인 것 같습니다 지송합니다 ㅠㅠ

3)선택 문제 알고리즘

 

k번째 작은 수를 찾는 문제로서, 입력에서 퀵 정렬에서와 같이 피봇을 선택하여 피봇보다 작은 부분과 큰 부분으로 분할한 후에 k 번째 작은 수가 들어있는 부분을 재귀적으로 탐색한다. 평균 경우 시간복잡도는 O(n)이다.

 


#유사코드

 

 

#파이썬 소스

 

*퀵 정렬 참고해서 작성해주시기 바랍니다!!

주의 : 피봇을 왼쪽으로 옮겼다가 중앙으로 옮길 때 (1~p)인덱스를 하나씩 앞으로 땡겨주고 p자리에 피봇을 넣어줘야 합니다

 

 

 

4)최근접 점의 쌍 문제

 

n개의 점들을 1/2로 분할하여 각각의 부분 문제에서 최근접 점의 쌍을 찾고, 2개의 부분해 중에서 짧은 거리를 가진 점의 쌍을 일단 찾는다. 그리고 2개의 부분해를 취합할 때, 반드시 중간 영역 안에 있는 점들 중에 최근접 점의 쌍이 있는지도 확인해보아야 한다. 시간복잡도는 O(nlogn)이다.

 

 

#유사코드

 

 

#파이썬 소스

 

이건 파이썬 2차원 배열 좀더 배우고 올리겠습니다 스미마셍...

 

분할 정복 알고리즘 = 주어진 문제의 입력을 분할하여 문제를 해결하는 방식의 알고리즘

 

◆대표적인 분할 정복 알고리즘

 

1)합병 정렬

 

문제를 계속해서 반으로 잘르고 다시 합병시키는 정렬. 자를 수 없을 때까지 자른 후 합병 과정에서 sorting함

 

#유사코드

 

 

#파이썬 소스

 

 

※파이썬은 들여쓰기 꼭 지켜주시기 바랍니다.

 

2)퀵 정렬

 

피봇이라 일컫는 배열의 원소를 기준으로 피봇보다 작은 숫자들은 왼편으로, 피봇보다 큰 숫자들은 오른편에 위치하도록 분할하고, 피봇을 그 사이에 놓고 정렬이 될 때까지 반복하는 sorting이다.

 

#유사코드

 

 

 

#파이썬 소스

 

+ Recent posts