전체 글

1. 도입 알고리즘의 정확한 증명을 위해서는 각종 수학적인 기법이 동원되어야 합니다. 전 세계 99%의 프로그래머는 알고리즘을 새로 만들기보다 배워서 써먹는 쪽에 지대한 관심을 가지고 있습니다. 그래서 대개 알고리즘의 증명에 관해서는 일찌감치 잊어버리는 게 어떨까 하는 유혹을 받기가 쉽고요. 하지만, 알고리즘의 증명을 이해하지 않고서는 알고리즘을 제대로 공부했다고 할 수 없습니다. 알고리즘의 증명을 공부해야 하는 가장 큰 이유는 많은 경우 증명이 알고리즘을 유도하는 데 결정적인 통찰을 담고 있기 때문입니다. 모든 알고리즘은 사실 치열한 고민과 개선 과정을 거쳐 태어납니다. 이 과정에서 결정적으로 필요한 깨달음이 증명에 담겨 있는 경우가 많습니다. 따라서 의사 코드를 달달 외우기만 해서는 알고리즘에 담겨 ..

1. 도입반복문이 지배한다.여기 자동차 두 개가 있습니다. 서울에서 부산까지 서둘러 가야 하는데, 어느 쪽을 타고 가야 더 빨리 도착할 수 있을지를 알고 싶습니다. 다음은 두 자동차에 대한 정보입니다.항목자동차 A자동차 B시동 거는 데 걸리는 시간3분5초문 열었다 닫는 데 걸리는 시간1분0초운전석 등받이 조절에 걸리는 시간5분0초앞 유리 닦는 데 걸리는 시간4분0초최대 시속200km/h40km/h 네, 사실 자동차 B는 자전거입니다. 문이 없으니 문을 열었다 닫을 필요도 없고, 등받이가 없으니 등받이를 조절할 필요도 없지요. 하지만 그렇다고 해서 서울에서 부산까지 자전거를 타는 사람은 아마 별로 없을 겁니다. 자동차에서 더 오래 걸리는 항목들은 출발할 떄 한 번만 적용되는 반면, 최대 시속은 서울에서 부..

1. 실수 자료형의 이해 실수 연산의 어려움아래 코드는 [1, n] 범위의 모든 자연수 중 1/x * x = 1 인 x의 수를 세는 countObvious()의 구현을 보여줍니다. 누가 보더라도 이 식은 항상 성립해야 하니, countObvious(n)을 호출하면 당연히 n이 반환되어야 할 것입니다. 그런데 이 함수를 직접 실행해보면 결과는 그렇지 않다는 것을 알게 됩니다. 대표적으로 제 컴퓨터에서는 countObvious(50) = 48 라고 나옵니다. 설마 우리 프로그램에 버그가 있는 것일까요? 아니면 CPU에 문제가 있는 것일까요? 이 의문을 해결하려면 컴퓨터가 사용하는 실수 표현 방식에 대해 알아야 합니다.// 잘못된 실수 연산의 예제int coundObvious(int n) { int sa..