이 정확히 뭔가요?
지금 개념이 막 혼란함.
인트로덕숀투앨거리듬스 보다가 딱 18쪽에서 \"루프불변성\"이 갑자기 튀나오는데 못알아먹겠습니다.

책에

INSERTION-SORT(A)//삽입정렬 의사코드
1  for j <- 2 to length[A]
2    do key <- A[j]
3      //A[j]를 정렬된 수열 A[1..j-1]속에 삽입하기
4      i <- j-1
5      while i>0 and A[i] > key
6        do A[i+1] <- A[i]
7          i <- i-1
8      A[i+1] <- key
<중략>
A[1..j-1]은 처음에 배열에 저장된 순서대로 처음부터 j-1번째까지의 값들이었지만, 이제 그것들이 정렬되어 자장되어 있는 것이다. A[1..j-1]의 이러한 특성을 엄밀하게 표현하면 \"루프불변성\"이라 한다.
<중략>
루프불변성을 보일라면 다음 세 성질을 만족해야 한다.
초기조건 : 루프시작직전 루프불변성은 참
유지조건 : 루프 반복 직전의 루프불변성이 참이었다면 그 다음 반복이 시작되기 직전까지 계속 참
종료조건 : 루프 종료시, 불변식이 알고리즘의 타당성을 보이는데 도움될 어떤 유용한 성질을 가져야 한다.
<중략>
이는 수학적 귀납법과 유사하다.
<중략>
위의 삽입정렬에서 이런 성질이 어떻게 만족되는가 보자.
초기조건 : j=2일때 A[1..j-1]은 A[1] 하나라 이미 정렬되어있으므로 루프불변성이 참이다.
유지조건 : 바깥 for루프의 몸체부분은 A[j]가 위치를 찾을때까지 A[j-1],A[j-2]...를 오른쪽으로 한자리씩 이동시키다가 적절한데 삽입한다(8행). 안쪽루프에 대한 불변성 증명은 생략한다.
종료조건 : 바깥 for루프는 j=n+1일때 종료된다. 앞의 루프불변성의 기술에서 j에 n+1을 넣어보면 부분수열 A[1..n]은 원래의 A[1..n]의 원소들로 구성되지만 정렬된 순서로 저장됨을 알수있다. 근데 a[1..n]은 전체수열이고, 이게 정렬되어있으니 알고리즘이 타당함을 알수있다.

그니까
루프 시작직전에 만족하고 그다음 중간 루프에서도 만족하는게 루프불변성이고,
루프가 끝나자면 유용한 성질을 갖는게 루프불변식이다.

뭐 이런식으로 저 문장을 이해를 했습니다.

근데 그이상은 모르겠습니다.

그니까 \"루프불변성\"의 정의가 뭡니까? \"불변식\"은 또 뭐고.
지금 3시간째 책을 뚫어져라 쳐다보고, 구글링을 해봐도 두루뭉술한 개념만 어설프게 잡힐듯 안잡힐듯.
최소한 반은 이해하고 넘어가야된다는 강박증때문에 더이상 못넘어가겠습니다.

좀 도와주세요


P.S. 구글에서 인트로덕숀 투 알고리듬스 pdf문서를 구했을때에는 슈도코드는 깔끔하게 고정폭글꼴인데
한글 완역판은 가변폭글꼴이라 살짝 초보자로썬 눈아픈감이...