간단하게 배워보는 알고리즘 - 1. 알고리즘이란?

gyeryak (53)in #kr • 7 years ago (edited)

안녕하세요, 계략입니다.

스팀잇에 가입하고 한 주가 지났습니다.
무슨 주제로 글을 쓸까, 곰곰히 생각해보다가 제가 어느정도는 알고 있는 것에 대해 글을 쓰는게 좋을 것 같아서 알고리즘에 대한 글을 쓰기로 했습니다.
그렇다고 복잡한 내용을 다룰 생각은 전혀 없습니다.

어떤 알고리즘에 대해서 깊게 파고들기 위해서 글을 찾으시는 분들도 계시겠지만, 글을 보실 대부분의 분들은 관련 공부를 하지 않으셨을 겁니다.
그래서, 비전공자도 알아들을 수 있도록, 그리고 복잡한 내용이 아닌 이 알고리즘은 어떤 알고리즘인지만 알 수 있도록 설명드릴 계획입니다.

언제까지 연재하게 될지는 잘 모르겠습니다.
아마 제 지식이 바닥날 때까지일 것 같습니다.

이미지를 가급적 사용하기는 하겠지만, 표지에서 느껴지듯 그렇게 열심히 만들어지지는 않을 것입니다. 중앙이 맞지 않거나, 뭔가 이상하거나 해도 넓은 아량으로 넘어가주시면 감사하겠습니다.

또한, 앞서 말씀드렸듯 알고리즘이 어떤 방식으로 진행되는지만 간단히 다룰 예정입니다. 틀린 내용이 있어 알려주시면 작성 후 7일 내라면 바로 수정하겠습니다. 틀린 내용에 대해서는 책임지지 않습니다.

그러면, 잘 부탁드리겠습니다!

첫 번째로 다룰 내용은,

'알고리즘' 이란?

입니다.

이런 저런 알고리즘이 무엇인지 알기 전에,
알고리즘이 무엇인지부터 간단하게 이해하는게 맞겠죠.

그래서 알고리즘이 어떤 것인지, 알고리즘의 정의에 대해서 간단히 짚고 가겠습니다.

알고리즘은, 어떠한 문제를 해결하기 위해 사용하는 방식입니다.
그리고 이 알고리즘에는 여러 종류가 있습니다.
그리고 상황마다, 사람마다 사용하는 알고리즘이 달라지겠죠.

일상생활에서 문제를 마주했다고 생각해 봅시다.

같은 문제가 주어지더라도, 사람마다 접근하는 방식이 다를 것입니다.

만약 '30명의 승객이 타고 있는 버스를 운전하고 있다. 그런데 앞에 노인 한 분이 지나가고 있다. 브레이크가 고장나서 피하면 승객들과 자신이 크게 다치고, 피하지 않는다면 노인이 크게 다친다. 어떻게 할 것인가?' 라는 질문이 있을 때 피하겠다는 사람도, 피하지 않겠다는 사람이 있을 것입니다.

알고리즘도 마찬가지로 여러 가지가 있을 겁니다.
물론 저 예시보다는 조금 더 구체적이고 수치화되어있는 문제가 주어지겠죠.

알고리즘 얘기를 해 봅시다.
'1부터 100까지의 합을 구하라' 라는 고전적인 문제가 있습니다.
이 문제를 푸는 방법은 어떤 것이 있을까요?

1부터 100까지 모두 직접 더한다
1과 100을 더하면 101, 2와 99를 더하면 101, 이와 같이 합해서 101이 되는 쌍이 50개가 있음을 이용하여 구한다
공식을 사용하여 100*(100+1)/2 의 값을 구한다.

(2번과 3번은 사실 같은 것이긴 하지만, 약간의 차이점은 있습니다.)

컴퓨터에게 1부터 100까지 구하라는 문제를 주었을 때도, 컴퓨터에게 저런 방법으로 시킬 수 있겠죠.
모두 직접 더하라고 하던지, 양쪽 끝의 수를 짝을 지어 구하도록 하던지, 공식에 대입하라고 하던지요.
이것이 바로 알고리즘입니다. 각각의 방법이 하나의 알고리즘이 되는 것입니다.

어떤 방법이 가장 빠를까요?
어떤 방법이 사양이 낮은 컴퓨터로도 구해질 수 있을까요?
1번 방법보다는 3번 방법이 훨씬 빠를 겁니다.
100까지가 아니라, 100억까지라고 해 봅시다.
1번 방법은 100억번 계산해야 하지만, 3번 방법은 1번의 계산으로 됩니다.
그래서 알고리즘은 '효율'도 같이 생각해야 합니다.

알고리즘의 효율을 결정하는 것은