자구/알고리즘(algorithm)이란? - 쓰는중

1. 개요

지난번에 아버지와 같이 카페에 갔는데 아버지께서 "알고리즘이 대체 정확히 뭐냐?"라고 물어보셨다. 간단히 대답하긴 했는데, 아무래도 좀 더 자세한 답변을 원하셨던 것 같아서 이 참에 정리해본다. 알고리즘의 정의는 어떻게 되고, 어떤 성질을 가지며, 어떻게 공부해야 할까?

2. 정의와 성질

알고리즘은 문제를 해결하는 방법이나 과정을 말한다. '문제(probleem)'라는 건 처리해야 하는 일을 말한다.  엄청 간단한 말이다. 그런데 그냥 대충 해결하지 뭐 이런 건 알고리즘이 될 수 없다. 어떤 방법이 알고리즘이 되기 위해서는 다음의 다섯 가지 성질을 가지고 있어야 한다. 읽어보면 다 당연히다고 납득할 수 있는 말이다.

1. 정확해야 한다. 즉, input - output이 정확해야 한다. 각각의 input을 의도한 것과 같이 정확하게 output으로 바꿀 수 있어야 한다.

2. 구체적인 단계들로 이루어져 있어야 한다. 구체적이라는 건 완전히 이해 가능한 동작들이란 뜻이다. 각 단계는 유한한 시간 안에 수행할 수 있어야 한다.

3. 모호성이 없어야 한다. 어떤 많은 것들 중에 하나를 선택하는 문법(if문 등)이 바로 이것을 위해 있다고 하더라.

4. 유한개의 단계로 이루어져 있어야 한다. 문제 해결의 단계가 무한하다면 도저히 어디에 적을 수가 없다. 반복 같은 경우는 for문이나 while 문 등을 통해 해결한다.

5. 끝나야 한다. 무한 루프에 빠지면 안된다.

3. 알고리즘 분석

알고리즘을 만들거나 사용하려면 어떤 알고리즘이 좋은지 아닌지부터 판단할 수 있어야 한다. 알고리즘이 좋다는 것은 효율적이고 빠르게 동작한다는 말이다. 그럼 알고리즘의 성능을 어떻게 파악할 수 있을까?
점근적 알고리즘 분석(asymptotic algorithm analysis)을 사용하면 알고리즘의 대략적인 성능을 파악할 수 있다. 알고리즘의 성능은 자원을 얼마나 효율적으로 사용하는지에 달렸는데, 자원이라고 하면 시간과 공간을 말한다. 그런데 알고리즘에서 필요한 것은 얼마나 빨리, 즉 얼마나 적은 시간 안에 과제를 수행할 수 있느냐이다. 자료구조에서는 공간을 얼마나 적게 차지하면서 데이터를 담느냐가 관건이 된다. 아무튼 알고리즘의 성능 분석은 시간 복잡도 계산이다. 이 시간 복잡도를 계산하는 방법은 점근적 알고리즘 분석인데, 대표적으로 빅-오 등이 있다. 검색하면 좋은 글들 많이 나오지만 이건 내 글이니까 아래는 내 글 링크.

점근적 알고리즘 분석과 빅-오에 대하여 : https://silverskystudyandworkout.blogspot.com/2018/08/bigo.html#more

4. 알고리즘 분석 예시 - 몇 가지 정렬 알고리즘들의 빅-오

4.1. 거품 정렬(bubble sort)
거품 정렬은 정렬의 과정에서 근접한 두 데이터가 바뀌는데, 그 모양이 거품이 일어나는 것과 비슷하다고 해서 거품 정렬이란 이름이 붙었다.
빅-오는 \(O(n^2)\)이다.

4.2. 선택 정렬(selection sort)
하나씩 선택해서
빅-오는 \(O(n^2)\)

4.3. 병합 정렬(merge sort)

빅-오는 \(O(n\log n)\)이다.

4.4. 퀵 정렬(quick sort)
빅-오는 \(O(n\log n)\)이다.

4.5. 기수 정렬(radix sort)

5. 어떻게 공부하면 좋을까?

알고리즘을 어떻게 공부하면 좋을까? 일단 나 같은 경우는 학부 3학년 커리큘럼에 알고리즘 과목이 전공필수로 들어가 있다. 그런데 알고리즘의 선행 과목으로 먼저 자료구조를 들어야 한다. 자료구조에 대한 기본적인 이해가 있어야 알고리즘을 원활하게 배울 수 있다.

생활코딩이나 백준 강의 같은 온라인 사이트 등을 보면 알고리즘 강의 목차에 자료구조와 겹치는 부분이 상당수 보인다. 가령 정렬(sorting)이나 탐색(searching)과 관련해서는 어떤 자료구조에 있는 데이터를 찾느냐에 따라서 사용할 수 있는 알고리즘이 달라지기 때문에 잘 알아야 한다. 리스트, 스택, 큐, 덱, 우선순위 큐, 트리, 그래프, 테이블(맵) 등에 대해 배우면서 이 자료구조들을 활용해서 어떻게 문제를 풀 수 있느냐 하는 알고리즘까지 같이 배우게 된다. 그러니까 알고리즘을 잘 배우려면 우선 자료구조를 잘 배워야 한다.

알고리즘은 이론과 구현을 둘 다 공부해야 하는데, 책도 있고 문제풀이 사이트도 있는 듯하다. 이걸 내가 언제 다 공부할까 싶기는 한데... 아무튼 이론서적으로 알고리즘 책은 <Introduction to Algorithm>이 가장 유명한 것 같다. 또 실제 코딩에 대해서는 생활코딩이나 백준, 혹은 해커랭크 같은 사이트를 참고하자. C++로 정리해놓은 사이트 중에서는 http://ehpub.co.kr/ 여기가 알기 쉽게 정리한 것 같다.

내가 아직 자료구조도 다 배우지 못한 상태니까 "알고리즘을 어떻게 공부하면 좋을까?"라는 질문에 대해서는 우선 "자료구조를 열심히 공부하자"라는 말로 끝내기로 하자.



6. 마무리