[알고리즘] 루프 불변성

루프 불변성은 반복문 또는 루프가 실행될 때 특정 조건이 항상 참으로 유지되는 것을 의미하는 것으로, 알고리즘이 타당한 이유를 쉽게 이해할 수 있도록 하기 위해 사용된다. 루프 불변성을 보이려면 다음 세 가지 특성을 만족해야 한다.

 

초기조건: 루프가 첫 번째 반복을 시작하기 전에 루프 불변성이 참이어야 한다.

유지조건: 루프의 반복이 시작되기 전에 루프 불변성이 참이었다면 다음 반복이 시작되기 전까지도 계속 참이어야 한다.

종료조건: 루프가 종료될 때 그 불변식이 알고리즘의 타당성을 보이는 데 도움이 될 유용한 특성을 가져야 한다.

 

초기조건과 유지조건을 만족하면 루프가 반복을 시작할 때 루프 불변성은 항상 참이다. 종료조건은 알고리즘의 타당성을 보이는 것과 같기 때문에 가장 중요한다.

728x90