79brue의 PS 블로그

그리디 알고리즘은 그 발상에 따라 난이도가 천차만별이기로 유명하다. 회의실 배정과 같이 기초적인 그리디 문제는 실버에서 시작하는 반면, Scenery 같은 문제는 루비까지 올라가기도 한다. (사실 난 Scenery의 풀이를 잘 모르기 때문에 단순 그리디가 아닐 수도 있다.) 그리디 전략을 증명할 때 사용하는 방법 중 하나가 플로우를 이용하는 것이다. 플로우는 분명 OI 범위 밖이지만, 그리디 알고리즘은 OI 범위 안이고, 플로우를 이용한 증명은 플로우 없이도 할 수 있는 경우가 많아 OI에서 심심찮게 볼 수 있었다. 난 이러한 증명 방식에 대해 잘 몰랐기 때문에 이런 문제를 만날 때마다 힘들었는데, 이제는 공부해 볼 때가 되었다고 생각해 공부를 시작해 보았다. 이 글은 이해하는 데 초점을 맞추었기 때문에..

그리디 알고리즘은 그 발상에 따라 난이도가 천차만별이기로 유명하다. 회의실 배정과 같이 기초적인 그리디 문제는 실버에서 시작하는 반면, Scenery 같은 문제는 루비까지 올라가기도 한다. (사실 난 Scenery의 풀이를 잘 모르기 때문에 단순 그리디가 아닐 수도 있다.) 그리디 전략을 증명할 때 사용하는 방법 중 하나가 플로우를 이용하는 것이다. 플로우는 분명 OI 범위 밖이지만, 그리디 알고리즘은 OI 범위 안이고, 플로우를 이용한 증명은 플로우 없이도 할 수 있는 경우가 많아 OI에서 심심찮게 볼 수 있었다. 난 이러한 증명 방식에 대해 잘 몰랐기 때문에 이런 문제를 만날 때마다 힘들었는데, 이제는 공부해 볼 때가 되었다고 생각해 공부를 시작해 보았다. 이 글은 이해하는 데 초점을 맞추었기 때문에..