초심자를 위한 알고리즘과 자료구조 1편 - 알고리즘

- 해당 글은 비전공자 혹은 개발 초심자를 대상으로 하는 글입니다. 다소 비전문적이고 구어체에 가까운 표현이 등장하더라도 양해 부탁드립니다.

- 수학적으로 엄밀하지 않은 정의를 포함하고 있습니다. 

 

 

 

알고리즘이라는 단어는 누구나 한 번쯤 들어보셨을 겁니다.

컴퓨터 과학 관련 전공을 하신 분이나 개발 분야에서 일하시던 분은 물론이고, 유튜브를 즐겨보는 사람이라면 흔히들 "유튜브 알고리즘의 선택을 받았다"는 식의 드립으로 이야기합니다.

 

유튜브에서 이해할 수 없는 맞춤 동영상이 올라올 때 그런 말을 합니다. 내가 안 보던 분야의 동영상이 올라오기도 하고, 갑자기 한 번도 들어본 적도 없는 언어의 제목도 간혹 보입니다. 신기하게도 저는 동영상의 썸네일만 보고도 신기해서 곧잘 들어가곤 합니다. 그럴 때면 제가 유튜브의 동영상을 선택하는 것이 아니라 유튜브의 동영상에게 선택받은 것이라는 생각이 가끔씩 듭니다. 그렇게 제목에 이끌려 동영상을 클릭하면 덧글엔 "알고리즘의 선택을 받아서 왔습니다"라는 글이 쫙 깔려있곤 합니다.

사실 그건 알고리즘이라고 거창하게 말하기엔 조금 애매하지만 뭐, 재미있으니 됐잖아요?

 

이번 시리즈에서 알아볼 내용은 알고리즘과 자료구조입니다.

알고리즘과 자료구조는 개발에 있어서 가장 기본적이고 핵심적인 기술이자 능력입니다.

 

이제 막 전공을 듣기 시작한 학생뿐만 아니라 현역으로 5년 이상 뛴 선임 개발자도 입에 달고 살 정도로, 두 과목은 정말 중요합니다. 그러나 코딩을 막 시작하는 전공자들은 살인적인 과제와 시험 난이도로 인해, 비전공자 학생들에겐 특유의 익숙치 않은 느낌으로 인해 두려움을 사는 분야이기도 합니다.

 

오늘은 그리 어렵지 않게, 가볍게 알고리즘이 무엇인지에 대해 다뤄봅시다.

 

 

 

1. 알고리즘이란

우리에게 익숙한 이 알고리즘이라는 단어는 겉으론 거창해 보이지만 그리 대단한 말은 아닙니다.

알고리즘에는 명확한 정의가 존재하지 않습니다. 그래서 알고리즘은 부르는 사람마다 의미를 다르게 붙이곤 합니다. 우선 위키백과에 의하면 알고리즘은 다음과 같이 정의됩니다.

 

알고리즘이란 수학, 컴퓨터 과학, 언어학 또는 관련 분야에서 어떠한 문제를 해결하기 위해 정해진 일련의 절차나 방법을 공식화한 형태로 표현한 것, 계산을 실행하기 위한 단계적 절차를 의미합니다.

 

https://ko.wikipedia.org/wiki/알고리즘

알고리즘 - 위키백과, 우리 모두의 백과사전

복잡해 보이지만 쉽게 풀어서 말하면 간단합니다.

 

알고리즘이란 문제를 해결하기 위한 방법을 나타낸 것이다.

생각보다 간단하죠? 내가 지금 문제에 직면해 있을 때 그걸 어떻게 해결할지가 바로 알고리즘입니다.

문제 해결 방안을 이야기하면 우리는 말을 할 때 두서없이 생각나는 대로 이야기합니다. 이 또한 문제 해결을 위한 방법이니 알고리즘이 될 수도 있겠지요.

 

다만 알고리즘에는 명확한 절차와 단계가 존재합니다.

알고리즘은 문제를 해결하고 답을 얻기 위해서 일련의 단계를 거치게 됩니다. 여기서 거치는 단계는 명확한 순서가 존재하며, 순서가 틀리면 답 또한 틀릴 수도 있습니다.

 

 

알고리즘을 간단히 비유하면 오늘 학교 가는데 아침에 늦잠을 잤을 때 지각하지 않는 방법으로 이야기할 수 있습니다.

버스로 통학하는 학생이 있다고 가정해봅시다.

늦잠을 자지 않았다면 버스를 타고 학교로 가고, 늦잠을 잤다면 택시를 잡아서라도 제시간에 학교에 가야겠지요. 제시간에 도착하기 글렀다면 지각할 각오하고 돈 아낄 겸 버스를 타고 갈 수도 있겠죠.

물론 이건 사람마다 선택이 달라지겠지만, 위와 같이 기술한 것도 알고리즘이라고 말할 수 있습니다.

 

그래서 이 알고리즘은 무엇을 하기 위한 것일까요?

알고리즘은 궁극적으로 문제를 해결하기 위해 존재합니다. 특히 사람보다는 컴퓨터와 같은 기계에서 실행하기 위해서요.

 

인간이 문제를 해결하는 것보다는 기계가 계산하는 것이 훨씬 빠릅니다. 한 번 계산기에다가 30자리의 곱셈을 쳐보시면 1초도 채 되지 않아 답이 나옵니다.

이러한 컴퓨터의 계산 능력을 살려서 보다 효율적으로 문제를 해결하기 위해서, 우리는 알고리즘을 공부합니다.

 

실제 알고리즘은 보통 체계적인 형식을 갖습니다.

우리가 사용하는 언어로 표현하면 불확실할 수도 있습니다. 따라서 보다 확실하고 오해의 여지가 없는 수학 공식, 순서도(Flowchart), 의사 코드(Pseudocode) 등을 이용해 표현합니다.

 

 

 

 

2. 알고리즘의 효율성

수학 문제를 풀어보면 알겠지만 같은 문제라 하더라도 쉬운 풀이가 있고 어려운 풀이가 있습니다.

 

미지수 x에 관한 방정식 2x + 1 = 0가 주어져 있을 때, 미지수 x의 값을 구하는 문제가 있다고 쳐보죠. 우리는 이항을 통해 간단하게 x의 값이 -1/2 임을 알 수 있습니다. 정말 쉬운 문제죠!

하지만 이항을 이용한 풀이를 모르는 사람이라면 미지수 x에 값을 대입하며 답을 찾아가는 수밖에 없을 겁니다.

 

x = 0을 넣으면 좌항은 2 X 0 + 1 = 1이 되고, 우항은 0이니 0은 아니고,

x = -1을 넣으면 좌항은 2 X (-1) + 1 = -1, 우항은 0이니 아니고...

 

이항의 원리를 모르는 사람은 위처럼 모든 경우의 수를 고려하여 하나하나 수를 대입해서 해결해야 하죠.

 

마찬가지로 알고리즘에서도 효율적인 풀이가 있으면 비효율적인 풀이가 있습니다.

간단하게 생각해서 계산에 사용되는 자원이 적은 것은 '효율적인 알고리즘'이라고 부를 수 있겠고, 많은 자원이 든다면 비효율적인 알고리즘이라 부를 수 있겠습니다.

 

여기서 계산에 사용되는 자원은 시간적인 측면과 공간적인 측면으로 구분할 수 있습니다.

시간은 말 그대로 계산에 걸리는 시간인 거고, 공간은 메모리 상에서 잡아먹는 공간이죠. 알고리즘이 효율적이라는 것은 시간이 상대적으로 덜 걸리고 공간(메모리)도 상대적으로 덜 잡아먹는 알고리즘이라는 것이지요. 반대로 비효율적인 알고리즘은 시간이 많이 걸리고, 공간도 많이 잡아먹는 알고리즘이 되겠지요.

 

 

예를 들어 정렬이라는 문제가 있습니다. 정렬이란 주어진 수들을 크기에 따라 나열하는 걸 말합니다.

다음 주어진 수들을 오름차순으로 정렬한다고 생각해봅시다.

 

4, 2, 5, 1, 3

이렇게 수가 주어져 있으면 오름차순으로 나열하면

 

1, 2, 3, 4, 5

이렇게 되겠지요.

 

정렬 알고리즘에는 여러 가지가 존재합니다.

버블 정렬, 선택 정렬, 삽입 정렬, 퀵 정렬, 합병 정렬, 힙 정렬, 빈 정렬 등 다양하게 있고 이 사이에서도 속도가 천차만별로 갈립니다.

같은 컴퓨터라고 해도 수행하는 동작이 비효율적이면 그만큼 시간도 많이 걸리기 때문입니다.

 

정렬 알고리즘을 애니메이션으로 표현한 것. 여기서 막대기 하나가 하나의 값이고, 정렬은 막대기를 순서대로 놓는 것이라고 볼 수 있다.

(해당 GIF는 아래 사이트에서 가져왔습니다. 각 정렬 알고리즘 별로, 각 상황별로 정렬을 애니메이션으로 보여줍니다.)

https://www.toptal.com/developers/sorting-algorithms

Sorting Algorithms Animations

 

위 그림을 보면 알고리즘 별로 속도 차이가 많게는 2배가량까지 차이 나는 걸 볼 수 있습니다.

 

자료가 많아질수록 이 차이는 더 커져서 나중에는 10배, 20배 이상 차이가 생기게 됩니다.

 

이 속도 차이는 어떻게 해서 비교할 수 있을까요?

 

Sorting Algorithms Animations를 보시면, 버블 정렬(Bubble)과 퀵 정렬(Quick, Quick3) 간의 속도 차이는 극명합니다. 퀵 정렬이 모두 정렬을 마칠 동안에도 버블 정렬은 반도 해결하지 못하는 모습을 보여줍니다.

 

여기서 버블 정렬은 상대적으로 느린 정렬에 해당하고, 퀵 정렬은 상대적으로 빠른 정렬입니다.

 

그러면 퀵 정렬과 삽입 정렬(Insertion)을 비교해봅시다.

퀵 정렬은 삽입 정렬보다 빠른 정렬입니다.

 

경우에 따라 삽입 정렬이 빠를 때도 있지만 대체로 퀵 정렬이 빠릅니다.

(거의 정렬되어 있거나 Nearly sorted, 값이 몇 종류밖에 존재하지 않고 같은 값이 많을 때 Few Unique에는 삽입 정렬이 더 유리하기도 합니다.)

 

퀵 정렬, 삽입 정렬, 버블 정렬을 모두 비교하면 다음과 같습니다.

속도 : 퀵 정렬 > 삽입 정렬 > 버블 정렬
(자료가 충분히 큰 일반적인 경우)

 

퀵 정렬은 빠른 정렬이라고 치고, 버블 정렬은 느린 정렬이라 하면 삽입 정렬은 어떻게 표현할까요?

 

삽입 정렬은 퀵 정렬보다 빠르고, 버블 정렬보단 느린 정렬이 되겠죠.

 

위 표현에서 삽입 정렬이 효율이 좋다고 말할 수 있을까요?

위 문장에서 삽입 정렬의 효율성을 한눈에 알아볼 수 있나요?

 

우리가 사용하는 언어로는 알고리즘의 효율성을 표현하기는 어려워 보입니다.

그래서 알고리즘은 일반적으로 Big-O (빅-O) 표현법을 통하여 이야기하곤 합니다.

 

다음 포스팅에서는 자료의 크기와 알고리즘의 관계, 시간 복잡도, Big-O를 통한 알고리즘 효율성 표현에 관해 알아봅시다.

 

 

 

요약

• 알고리즘이란 주어진 문제를 해결하기 위한 방법을 말한다.
• 알고리즘에는 일련의 단계가 존재한다. 순서대로 이를 따르지 않으면 제대로 된 답을 얻지 못할 수도 있다.
• 알고리즘의 효율성은 시간(문제 해결에 필요한 시간)과 공간(문제 해결에 필요한 컴퓨터 메모리의 크기)에 따라 결정된다.
• 알고리즘의 효율성은 Big-O 표기법을 이용하여 표현한다.

 

 

 

 

 

출처 

김대수. 소프트웨어와 컴퓨팅 사고력. 생능 출판, 2016

Donald E. Knuth. The Art of Computer Programming. Addison-Wesley, 2006

"알고리즘", 위키백과, 2020년 7월 10일 수정, 2020년 8월 16일 접속, https://ko.wikipedia.org/wiki/알고리즘

"Algorithm Efficiency, Computational Complexity 알고리즘 효율성, 계산 복잡도", 정보통신기술용어해설, 2020년 6월 19일 수정, 2020년 8월 18일 접속, http://www.ktword.co.kr/abbr_view.php?m_temp1=5227

"Algorithm 알고리즘", 정보통신기술용어해설, 2020년 3월 3일 수정, 2020년 8월 18일 접속, http://www.ktword.co.kr/abbr_view.php?m_temp1=635