반응형 [PCCP] 알고리즘 - 그리디 1. 이론- Greedy: 지역 최적해를 구함. 전역 최적해 장담 불가- 특정한 상황에서 사용 가능 - Optimal Substructure(최적 부분 구조): 부분해 과정이 최적해 과정과 일치 - Greedy Selection Property(그리디 선택 속성): 선택과정이 다른 과정에 영향을 주지 않음- Minimum Spanning Tree(최소신장트리) 1) 모든 정점이 간선으로 연결 2) 간선의 개수는 (정점의 개수 - 1)과 동일 3) 간선의 가중치의 합이 최소일 경우 성립- 알고리즘 종류: Prim's Algorithm / Kruskal Algorithm- 예제 - 거스름 돈 문제 - Knapsack Problem(배낭문제): 부분 배낭문제 / 01배낭문.. 2024. 12. 15. [알고리즘] 4. 그리디 && 구현 Index 1. 그리디 2. 구현 3. 추천 문제 4. 참고자료1. 그리디Greedy Algorithm- 현재 상황에서 지금 당장 좋은 것만 고르는 방법- 정당성 분석, 반복적 선택시 최적의해 보존되는지 검토 (Exam)- 거스름 돈: 가장 큰 동전의 단위가 항상 작은 단위의 배수이므로 작은 단위의 동전들을 종합해 다른 해가 나올 수 없음 2. 구현Implementation- 머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정(problem->thinking->solution)- 2차원 공간을 다룰 경우 Matirx(행렬)을 사용- 시뮬레이션 및 완전 탐색의 경우 2차원 공간에서의 방향 벡터가 활용dx = [0, -1, 0, 1]dy = [1, 0, -1, 0]for i in range(4): nx =.. 2024. 7. 19. 이전 1 다음 반응형
