AlgorithmBook

1. 도입 분할 정복(Divide & Conquer)은 가장 유명한 알고리즘 디자인 패러다임으로, 각개 격파라는 말로 간단히 설명할 수 있습니다. 분할 정복 패러다임을 차용한 알고리즘들은 주어진 문제를 둘 이상의 부분 문제로 나눈 뒤 각 문제에 대한 답을 재귀 호출을 이용해 계산하고, 각 부분 문제의 답으로부터 전체 문제의 답을 계산해 냅니다. 분할 정복이 일반적인 재귀 호출과 다른 점은 문제를 한 조각과 나머지 전체로 나누는 대신 거의 같은 크기의 부분 문제로 나누는 것입니다. 이 차이점은 아래 그림에서 알 수 있습니다. 첫 번째 그림은 항상 문제를 한 조각과 나머지로 쪼개는 일반적인 재귀 호출 알고리즘을 보여주고 두 번째 그림은 항상 문제를 절반씩으로 나누는 분할 정복 알고리즘을 보여줍니다. 분할 정..

1. 도입 프로그래밍 대회에서 대부분의 사람들이 가장 많이 하는 실수는 쉬운 문제를 어렵게 푸는 것입니다. 공부를 열심히 할수록 복잡하지만 우아한 답안을 만들고 싶은 마음이 커지기 마련이고, 그래서 바로 앞에 보이는 쉽고 간단하며 틀릴 가능성이 낮은 답안을 간과하기 쉽습니다. 이런 실수를 피하기 위해 문제를 마주하고 나면 가장 먼저 스스로에게 물어봅시다. 무식하게 풀 수 있을까? 흔히 전산학에서 '무식하게 푼다(brute-force)'는 말은 컴퓨터의 빠른 계산 능력을 이용해 가능한 경우의 수를 일일이 나열하면서 답을 찾는 방법을 의미합니다. 가능한 방법을 전부 만들어 보는 알고리즘들을 가리켜 흔히 완전 탐색(exhaustive search)이라고 부릅니다. 얼핏 보면 이런 것을 언급할 가치가 있나 싶을..

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..

1. 도입 앞에서 언급했듯이 프로그래밍 대회는 문제 해결 능력을 수련하기에 무척 좋은 환경입니다. 그러나 무작정 알고리즘을 외우고 문제를 푼다고 해서 문제 해결 실력이 쌓이는 것은 아닙니다. 문제 해결 능력은 프로그래밍 언어나 알고리즘처럼 명확히 정의된 실체가 없는 추상적인 개념이기 때문에 단순한 반복만으로 연마하기 어렵습니다. 실제로 우리는 초등학교 산수 시간부터 문제를 푸는 방법을 배우지만, 많은 경우 당장 주어진 문제를 풀기 위한 요령을 익히는 데 급급합니다. 결국 대다수 사람들의 문제 해결 기술이 기계적으로 문제를 풀면서 익힌 감과 막연한 시도에 머무르는 것이 현실입니다. 좋은 문제 해결자가 되기 위해서는 좀 더 높은 차원의 수련이 필요합니다. 이 수련의 목표는 문제를 푸는 것이 아니라 문제를 푸..

1. 도입 프로그래밍은 문제 해결이다.  프로그램이 사용할 수 있는 최대 메모리와 사용자가 답답해하지 않게 하기 위한 시간 제한을 유의하면서 가능한 한 재사용성이 높은 간결한 코드를 작성하여 요구사항을 이행하는 최선의 방법을 찾아내는 능력을 '문제 해결 능력'이라고 부릅니다. 그러나 문제 해결 능력을 훈련하기란 굉장히 어렵습니다. 문제 해결 능력은 추상적인 기술이기 때문입니다. 자기 계발을 하고 싶은 프로그래머들은 새로운 언어와 프레임워크, 개발 방법들을 계속 배워 나가지만 이들을 조합하는 방법에 대해서는 배울 곳이 없습니다. 단지 경험이 생기면서 나아질 것이라고 막연히 짐작할 뿐입니다. 좋은 프로그래머가 되기 위한 좀 더 나은 방법은 없을까요?