위키득계정 ↗
기술

불변식과 루프 종료

불변식과 루프 종료기술
불변식
반복 경계에서 유지할 조건
검증 단계
초기 성립과 유지 및 종료 후 의미
종료 근거
감소하는 양과 하한
주요 용도
탐색과 누적 계산의 정확성
루프 불변식은 반복의 정해진 지점에서 계속 성립해야 하는 조건이다. 불변식이 유지된다는 사실과 반복이 끝난다는 사실은 별도로 확인해야 알고리즘의 올바른 종료 결과를 설명할 수 있다.

변하지 않는 값만 뜻하지 않는다

불변식은 변수의 숫자가 항상 같다는 뜻만은 아니다. 반복마다 값이 바뀌어도 변수들 사이의 관계가 계속 참일 수 있다. 배열의 앞쪽 처리 구간이 이미 검사되었다는 조건처럼 진행 상황을 설명할 수 있다. 어느 반복 지점에서 조건을 주장하는지 먼저 정해야 유지 여부를 정확히 확인할 수 있다.

합계를 구하는 사례

앞의 i개 원소를 처리했을 때 합계 변수가 그 i개의 합이라는 조건을 생각하자. 처음 i가 0일 때 빈 합계를 0으로 두면 성립한다. 다음 원소를 더하고 i를 하나 늘리면 같은 관계가 유지된다. 모든 원소를 처리한 시점에는 그 조건이 전체 합계라는 결론을 준다. 이 설명은 계산 코드와 검증 조건의 연결을 보여 준다.

유지해도 끝나지 않을 수 있다

항상 참인 조건을 유지하면서 같은 상태를 영원히 반복하는 프로그램도 만들 수 있다. 따라서 불변식만으로 종료가 증명되지는 않는다. 처리하지 않은 원소 수나 남은 탐색 구간 크기처럼 매번 줄어들고 아래로 한계가 있는 양을 확인할 수 있다. 감소가 실제로 일어나는지 모든 분기에서 검토한다.

경계 조건과 연결

이진 탐색에서는 답의 후보가 남은 구간 안에 있다는 관계를 유지할 수 있다. 동시에 그 구간이 줄어들어야 같은 중간 위치를 무한히 반복하지 않는다. 빈 구간이 허용되는지와 마지막 후보가 무엇인지도 종료 후 결론에 영향을 준다. 구간의 끝 포함 규칙을 바꾸면 불변식과 갱신식을 함께 바꾸어야 한다.

구현을 검토하는 도구

복잡한 반복을 읽을 때 각 줄의 의도를 추측하기보다 반복 전후에 무엇이 보장되어야 하는지 적으면 도움이 된다. 조건이 처음부터 성립하는지, 각 분기가 유지하는지, 종료 조건과 합쳐 필요한 결과가 나오는지 확인한다. 입력 범위를 벗어난 접근이나 산술 표현의 한계도 별도로 살핀다. 논리적인 관계와 실제 실행의 안전 조건을 함께 검토한다.

관련 문서

알고리즘 / 이진 탐색의 경계 조건 / 동적 계획법