[묘공단] 코딩테스트 스터디 13주차
[묘공단] 코딩테스트 스터디 13주차
2024.03.02이 글은 골든래빗 코딩 테스트 합격자 되기 파이썬 편의 16장 문제풀이입니다 16. 그리디 개념 그리디 -> 문제 해결 과정에서 순간마다 최선의 선택을 하며 선택을 번복하지 않는 알고리즘 다시 말해서 지역 최적해를 추구한다라고 말할 수 있다 그리디 알고리즘이 최적해를 보장하려면 최적 부분 구조 (Optimal substructure): 부분해를 푸는 과정이 최적해를 구하는 과정과 일치 그리디 선택 속성 (Greddy selection property): 선택 과정이 다른 과정에 영향을 주지 않음 이런 특징때문에 항상 최적해를 구할 수 있다는 보장은 못하지만, 빠르게 근사해를 제공하는 효과는 누릴 수가 있다 앞에서 공부했던 Union-Find를 활용하여 최소 신장 트리를 구하는 알고리즘도 그리디 알고리즘의..