YJ_Scribbles

★ 그리디 알고리즘 - 최적화 문제를 해결하는 알고리즘 - 욕심쟁이 방법, 탐욕적 방법, 탐욕 알고리즘 등으로 불림 ㅇ 최적화 (optimization) 문제 - 가능한 해들 중에서 가장 좋은 (최대 또는 최소) 해를 찾는 문제 ㅇ 특징 - 데이터 간의 관계를 고려하지 않고 수행 과정에서 ‘욕심내어’ 최소값 또는 최대값을 가진 데이터를 선택 (‘근시안적’인 선택) - 일단 한 번 선택하면, 이를 절대로 번복하지 않음 -> 매우 단순하며, 또한 제한적인 문제들만 해결 가능 ★ 예시1. 동전 거스름돈 문제 - 남은 액수를 초과하지 않는 조건하에 ‘욕심내어’ 가장 큰 액면의 동전을 취하는 것 ㅇ 알고리즘 -> CoinChange 알고리즘은 항상 최적의 답을 주지 못함 (따라서 실제로는 거스름돈에 대한 그리디 ..

★ 분할-정복 알고리즘 - 주어진 문제를 분할하여 해결(정복)하는 방식의 알고리즘 -> 문제 분할 -> 분할한 입력에 대해 동일한 알고리즘 적용 -> 해 계산 -> 계산된 해 취합 -> 문제의 해 구함 ☆ 부분문제와 부분해 • 부분문제 (subproblem) : 분할된 입력에 대한 문제 (부분문제는 더 이상 분할할 수 없을 때가지 계속 분할) • 부분해 : 부분문제의 해 ★ 퀵정렬 - Partition()으로 큰 문제를 2개의 작은 문제로 분할(절반으로 나누지 않을 수 있음) - 분할할 때 작은 부분, 큰 부분으로 분할함으로써 정복(해결)과정이 따로 필요없음 ★ 합병정렬 - 무조건 절반으로 분할 - 분할된 문제를 Merge()로 정복 ★ 분할정복의 효과 ex)O(n²) 알고리즘 - N = 100일 때, ..