728x90 반응형 백준 21381 [백준 1080, 2138][파이썬] 행렬, 전구와 스위치 (그리디 알고리즘) 백준 1080번과 2138번 모두 그리디 알고리즘으로 풀이가 비슷해서 같이 가져와보았다. 그리디 알고리즘은 욕심쟁이 알고리즘이라고도 하는데 현재 최선의 선택을 하는 것이다. 미래를 생각하지 않고 현재 선택할 수 있는 경우의 수 중 최선의 선택을 하는 것인데 반드시 최적의 해를 구할 것이라는 보장이 없다. 최적의 해를 구하지 못하더라도 근사값은 구할 수 있기 때문에 유용한 알고리즘이다. 그리디 알고리즘을 사용했을 때 최적의 해를 보장할 수 있으려면 다음과 같은 조건이 필요하다. 탐욕 알고리즘이 잘 작동하기 위한 조건은 탐욕스런 선택 조건(greedy choice property)과 최적 부분 구조 조건(optimal substructure)이다. 탐욕스런 선택 조건은 앞의 선택이 이후의 선택에 영향을 주지.. 2023. 6. 30. 이전 1 다음 728x90 반응형
