CLRS 썸네일형 리스트형 [Introduction to Algorithms] 2. 시작하기 2. 시작하기 많은 알고리즘에서는 루프를 사용하여 문제를 해결하곤 한다. 우리는 코드가 문제없이 작성 되었다면, 그 루프가 정상적으로 작동하여 문제를 해결할 것을 알고 있다. 그러나 이를 논리적으로 증명하기는 어려웠다. 이때 사용할 수 있는 것이 루프 불변성(Loop Invariant)이다. 루프 불변성은 루프를 사용한 알고리즘이 타당(correct)한지 증명하기 위해 사용된다. 루프 불변성임을 확인하기 위해서는 세 가지 특성이 만족되어야 한다. 초기조건 : 루프가 첫 번째 반복을 시작하기 전에 루프 불변성이 참이어야 한다. 유지조건 : 루프의 반복이 시작되기 전에 루프 불변성이 참이었다면, 다음 반복이 시작되기 전까지도 계속 참이어야 한다. 종료조건 : 루프가 종료될 때 그 불변식이 알고리즘의 타당성을.. 더보기 [Introduction to Algorithms] 1. 알고리즘의 역할 1. 알고리즘의 역할 1.1 알고리즘 이 장에서는 우리가 알고리즘을 배우는 이유와 배워서 어떻게 사용할 수 있는지에 대해 간략하게 설명해준다. 먼저, 알고리즘이란 한 값을 입력받아 다른 값으로 출력하는 계산 절차라고 한다. 가장 대표적으로는 임의의 수열을 정렬시키는 정렬 기법이 있다. 여러 알고리즘을 익히고, 사용할 수 있게 된다면 더 훌륭한 프로그래머가 될 수 있을 것이다. 마치 요리사 지망생이 요리사가 되기 위해 많은 레시피를 배워가는 것처럼. 1.2 기술로서의 알고리즘 어떤 문제를 풀기 위해서 여러 개의 알고리즘을 구현했다고 했을 때, 가장 최적의 알고리즘을 선택하는 기준은 무엇이 있을까? 나는 효율성이 대표적인 기준이 될 수 있다고 생각한다. 효율이라는 것은 시간과 메모리 두 차원에서 생각해볼 수.. 더보기 이전 1 다음
