본문 바로가기

Computer/Etc

Loop Invariant

알고리즘과 관련된 문제를 풀고 있는데...

기억하면 좋을만한 내용이 있어서 정리해본다.


Loop Invariant

  • 루프안에서 원하는 속성이 유지되는지 확인해보는 방법
  • 3가지를 통해서 속성이 유지되는지 확인해 볼 수 있다.
    • Initialization : 루프를 돌기전 true 상태이다.
    • Maintenance : 루프를 반복 후에도 true 상태이다.
    • Termination : 루프는 종료될 수 있다.
이렇게 정리할 수 있는데... 이것을 InsertionSort에서 확인해본다면...?

for(int i = 1; i < A.length; i++){
//insertion sort code


여기에서 //insertion sort code 들어가는 것은

  • sorting에서 시작되는 subarray는 정렬되어 있다.(i = 0, 정렬되어 있다)
  • 루프를 돌고 나서는 subarray는 정렬되어 있는 상태이다.
  • i = length -1 이 되면 종료된다.
이렇게 정리가 된다.


관련 url : https://www.hackerrank.com/challenges/correctness-invariant


끝.

'Computer > Etc' 카테고리의 다른 글

3way handshaking  (0) 2015.01.11
github gist  (0) 2015.01.03
Loop Invariant  (0) 2015.01.01
LCS, longest common subsequence vs longest common substring  (0) 2014.12.09
Excel에서 조건부 수식을 사용해서 줄단위 색 입히기  (0) 2014.12.05
long-tail vs short head  (0) 2014.12.03