변하지 않는 값만 뜻하지 않는다
불변식은 변수의 숫자가 항상 같다는 뜻만은 아니다. 반복마다 값이 바뀌어도 변수들 사이의 관계가 계속 참일 수 있다. 배열의 앞쪽 처리 구간이 이미 검사되었다는 조건처럼 진행 상황을 설명할 수 있다. 어느 반복 지점에서 조건을 주장하는지 먼저 정해야 유지 여부를 정확히 확인할 수 있다.
합계를 구하는 사례
앞의 i개 원소를 처리했을 때 합계 변수가 그 i개의 합이라는 조건을 생각하자. 처음 i가 0일 때 빈 합계를 0으로 두면 성립한다. 다음 원소를 더하고 i를 하나 늘리면 같은 관계가 유지된다. 모든 원소를 처리한 시점에는 그 조건이 전체 합계라는 결론을 준다. 이 설명은 계산 코드와 검증 조건의 연결을 보여 준다.
유지해도 끝나지 않을 수 있다
항상 참인 조건을 유지하면서 같은 상태를 영원히 반복하는 프로그램도 만들 수 있다. 따라서 불변식만으로 종료가 증명되지는 않는다. 처리하지 않은 원소 수나 남은 탐색 구간 크기처럼 매번 줄어들고 아래로 한계가 있는 양을 확인할 수 있다. 감소가 실제로 일어나는지 모든 분기에서 검토한다.
경계 조건과 연결
이진 탐색에서는 답의 후보가 남은 구간 안에 있다는 관계를 유지할 수 있다. 동시에 그 구간이 줄어들어야 같은 중간 위치를 무한히 반복하지 않는다. 빈 구간이 허용되는지와 마지막 후보가 무엇인지도 종료 후 결론에 영향을 준다. 구간의 끝 포함 규칙을 바꾸면 불변식과 갱신식을 함께 바꾸어야 한다.
구현을 검토하는 도구
복잡한 반복을 읽을 때 각 줄의 의도를 추측하기보다 반복 전후에 무엇이 보장되어야 하는지 적으면 도움이 된다. 조건이 처음부터 성립하는지, 각 분기가 유지하는지, 종료 조건과 합쳐 필요한 결과가 나오는지 확인한다. 입력 범위를 벗어난 접근이나 산술 표현의 한계도 별도로 살핀다. 논리적인 관계와 실제 실행의 안전 조건을 함께 검토한다.
관련 문서
알고리즘 / 이진 탐색의 경계 조건 / 동적 계획법