06-1 그리디 알고리즘
현재 상태에서 가능한 선택지 중에 최선의 선택지가 전체 선택지 중에 최선의 선택지라고 가정하는 알고리즘
- 각각의 상황에서 best를 선택하다 보면 전체의 best 값이 나올거다
but, 최적의 해를 보장하는 것은 아님
그리디 알고리즘의 핵심 이론
수행과정
1. 해 선택: 현재 상태에서 가장 최선이라고 생각되는 해를 선택한다.
2. 적절성 검사: 현재 선택한 해가 전체 문제의 제약 조건에 벗어나지 않는지 검사한다.
3. 해 검사: 현재까지 선택한 해 집합이 전체 문제를 해결할 수 있는지 검사한다. 전체 문제를 해결하지 못한다면 1로 돌아가 같은 과정을 반복한다. (해결하면 멈춤)
반응형
'ALGORITHM' 카테고리의 다른 글
알고리즘 강의 | Do it! 알고리즘 코딩테스트 with Python - 오일러 피 (0) | 2023.12.09 |
---|---|
알고리즘 강의 | Do it! 알고리즘 코딩테스트 with Python - 소수 구하기 (0) | 2023.12.09 |
알고리즘 강의 | Do it! 알고리즘 코딩테스트 with Python - 이진 탐색 (2) | 2023.12.08 |
알고리즘 강의 | Do it! 알고리즘 코딩테스트 with Python - BFS (0) | 2023.12.08 |
알고리즘 강의 | Do it! 알고리즘 코딩테스트 with Python - DFS (1) | 2023.12.08 |