알고리즘 개론

그렇다. 여러분도 아시다시피 전화번호부에 있는 사람들의 이름은 가나다 순으로 정렬이 되어있다. `정동섭`이라는 인물을 찾고자 할 경우 전화번호부의 `ㅈ`항목을 찾은 다음, `정`으로 시작하는 사람들의 이름을 찾고, `동`이라는 글자가 이어지는 이름을 찾아낸 후, 마지막으로 `섭`을 찾으면 `정동섭`이라는 사람의 전화번호를 알 수 있게 되는 것이다. 물론 사람마다 약간의 차이는 있겠지만. 위에서 말한 두가지 방법. 즉 무식한 방법과 유식한(?)방법. 이 두가지 방법 모두다 알고리즘으로 볼 수 있다. `정동섭이라는 이름을 가진 사람의 전화번호 을 찾아라` 라고 하는것이 우리에게 주어진 문제이고, 위에 주절주절 써놓은 것들이 해답을 찾아주는 절차, 즉 알고리즘이다. 그리고 이런 알고리즘을 사용해서 주어진 문제를 해결하는 것을 문제를 푼다(solve)라고 한다. 하지만 전화번호부에서 특정한 사람의 전화번호를 찾는것은 꼭 저 위의 두가지 방법만 있는것은 아니다. 저 두 방법외에 엄청나게 많은 방법이 존재할 수 있다. 이러한 방법들도 모두 알고리즘이라고 할 수 있는 것들이다. 앞으로 이 강좌에서는 여러가지 알고리즘들을 사용해 컴퓨터로 주어진 문제를 푸는 방법에 대에 설명하게 될 것이다. 여러분이 앞으로 공부할 내용들은 모두 이 `알고리즘`에 대한 것들이다. 2. 알고리즘의 중요성 앞에서 말했듯이 전화번호부에서 사람을 찾는 방법.. 즉 알고리즘은 여러가지가 있을 수 있다. 하지만 이 중에서 어떤 것을 선택해야 할까? 역시 `유식한 방법`을 선택하는 것이 좋을 것이다. 유식한 방법이 무식한 방법보다 더 빠르기 때문이다. 하지만 앞으로 우리는 이러한 일들을 컴퓨터에게 시킬것이다. 컴퓨터는 연산속력이 인간과는 비교가 안 될 정도로 빠르다. 그러면 컴퓨터는 무지 빠르니까 그냥 무식한 방법으로 풀게 해도 답은 금방 나오지 않을까? 대답은 `No`다. 만약에 찾는 전화번호부에 실린 이름들의 수가 1,000,000,000,000…
대답은 `No`다. …