컴퓨터공학부: 알고리즘

유튜브 알고리즘은 아는데, 컴퓨터공학에서는 어떤 알고리즘을 배우나요? 알고리즘이 궁금한 사람들에게 추천하는 강의!

 

1.  강의에서 배울 수 있는 내용

1)  과목의 전반적인 개요

본 과목에서는 과목의 이름 그대로 여러가지 알고리즘에 대해 학습하고, 각각의 알고리즘들을 비교하는 방법을 학습합니다. 알고리즘을 평가하는 데 가장 중요한 것은 바로 소요 시간입니다. 주어진 문제를 빠르게 해결하는 알고리즘을 사용하는 것이 중요합니다. 대부분 알고리즘의 소요 시간은 알고리즘의 입력 값에 의해 결정되기 때문에, 소요 시간이 알고리즘의 입력 값과 어떤 관계를 가지는지 표현하는 “시간 복잡도” 개념을 배웁니다. 그런 다음 정렬, 동적 프로그래밍, 집합 처리, DFS/BFS, 그리디 알고리즘 등 여러 알고리즘을 배우게 됩니다. 이번 글에서는 알고리즘의 핵심 개념인 시간복잡도와 가장 간단한 알고리즘인 이진 탐색에 대해 알아봅시다.

2)  시간 복잡도

시간 복잡도는 알고리즘을 수행하는 데 걸리는 시간입니다. 어떤 진주 목걸이가 있을 때, 진주를 한 알씩 살펴보는 데에는 전체 진주의 개수에 비례하는 시간이 소요되겠죠? 알고리즘의 시간 복잡도를 계산하는 방법도 이와 비슷합니다. 어떤 숫자 리스트가 있을 때, 리스트에서 가장 큰 숫자를 찾기 위해서는 리스트에 있는 숫자를 처음부터 끝까지 살펴보면서, 가장 큰 숫자를 기억해야 할 것입니다. 리스트에 있는 숫자의 개수(즉, 리스트의 길이)가 n이라면, 리스트에서 가장 큰 숫자를 찾는 이 알고리즘의 시간 복잡도는 n에 비례하므로 O(n)이라고 할 수 있습니다. 어떤 알고리즘의 시간복잡도가 O(n)이라는 것은, 이 알고리즘의 시간 복잡도가 O(n)이라는 집합에 속한다는 뜻입니다. O(n)은 n과 비례하거나 더 작은 함수들의 모임입니다. 예를 들어 n-5나 n+sqrt(n), 99*n, 0.01*n은 모두 O(n)에 속하게 됩니다. 

99*n와 0.01*n를 하나로 묶어서 표현한다니, 뭔가 낯설게 느껴지시나요? 이렇게 O-표기법(big-O 표기법)을 사용해서 얻는 이점이 뭘까요? 다시 아까의 큰 숫자 찾기 알고리즘으로 돌아가봅시다. 전체 리스트의 길이(n)가 10^99라면 살펴보아야 할 원소의 개수가 많아서 99*n이나 0.01*n이나 비슷하게 느껴지죠? 이처럼 결국 시간 복잡도를 좌우하는 것은 n 앞에 붙은 상수들이 아니라, n의 크기입니다. 그러니 우리는 경향성을 보기 쉽게 n이나 8n이나 n-9999나 모두 O(n)으로 표기하는 것입니다.

(알고리즘] 시간복잡도(Time Complexity)와 Big-O표기법(Big-O Notation))

 

3) 이진 탐색 알고리즘

가장 간단한 알고리즘 중 하나인 이진 탐색 알고리즘에 대해 알아봅시다. 

아까의 문제를 살짝 바꾸어 이번에는 전체 리스트에 6이라는 숫자가 있는지 찾는 문제를 해결해봅시다. 가장 쉽게 생각할 수 있는 해결책은 이전과 유사하게 리스트의 처음부터 끝까지 리스트에 있는 모든 숫자를 살펴가며 6인지 확인하는 것입니다. 이러한 알고리즘의 시간 복잡도는 리스트 길이에 비례하는 O(n)이 걸립니다. 

자 그렇다면, 여기서 문제! O(n)보다 빠르게 가장 큰 숫자를 찾는 방법은 없을까요? 더 빠른 컴퓨터를 써서 10*n이던 소요 시간을 3*n으로 바꾼다 - 이런 해결책은 어떨까요? 눈치채신 분들도 있겠지만, 컴퓨터를 아무리 빠른 슈퍼컴퓨터를 쓰더라도 결국 처음부터 끝까지 리스트를 모두 살펴본다면 시간복잡도는 결국 O(n)입니다. 그러니 처음부터 끝까지 탐색하는 알고리즘 자체를 바꾸어야 합니다.

대표적인 탐색 알고리즘은 바로 정렬된 리스트에서 사용하는 이진 탐색입니다. 내림차순으로 정렬된 리스트를 생각해봅시다. 리스트 정중앙의 값이 4이라면 리스트의 오른쪽에는 4보다 작은 숫자뿐이니 6과 같은 숫자가 있을 수 없습니다. 그러므로 4의 왼쪽 숫자만 살펴보면 됩니다. 이로써 탐색해야할 범위가 절반으로 줄었습니다. 이제 4의 오른쪽의 숫자들에 대해 같은 과정을 반복하면 됩니다. 4 오른쪽 숫자들 중 정중앙의 값이 7이라면 이제 7과 4 사이의 숫자들만 살펴보면 되고, 7 왼쪽의 숫자들은 볼 필요가 없습니다. 탐색할 범위가 이제 1/4로 줄었습니다. 이러한 과정을 반복하다 보면 결국 탐색 범위가 1개로 줄어듭니다. 이 숫자가 6과 같은지 확인하면, 리스트 안에 6이 있는지 판단할 수 있겠죠? 이러한 이진 탐색에서는 이전과 달리 리스트 원소를 전부 살펴보지 않았습니다. log_2(n)개의 원소만 살펴보았으므로, 이진 탐색의 시간 복잡도는 O(log n)입니다. 이진 탐색은 여러가지 알고리즘과 자료 구조의 기초가 되는 아이디어이므로 알고리즘에서 매우 중요한 개념 중 하나입니다. 

(이진 탐색 (Binary Search))

 

 

2. 선배의 조언

1) 선수과목

알고리즘 과목에서는 특정 자료구조에서만 사용할 수 있는 알고리즘을 배우기도 하고, 어떤 알고리즘을 사용하기 위한 특별한 자료구조를 만들기도 합니다. 이처럼 자료구조와 알고리즘은 떼려 해도 뗄 수 없는 관계입니다. 실제로 컴퓨터공학부 과목 흐름도에서 알고리즘은 자료구조의 상위 과목에 해당합니다. 따라서 자료구조를 선수강하고 알고리즘 과목을 수강하는 것을 추천합니다. 하지만 엇학기로 수강하여 알고리즘을 자료구조보다 먼저 수강하더라도 문제는 없습니다. 컴퓨터공학부의 알고리즘 수업은 자료구조를 수강하지 않았더라도 따라갈 수 있는 속도로 짜여져 있으니까요!

2) 관련 책 추천

도움이 되는 책은 우리 학교 컴퓨터공학부 교수님이 직접 저술하신 “쉽게 배우는 알고리즘”입니다. 컴퓨터공학부에서 공부하는 책들은 영어로 된 원서가 많은데요, “쉽게 배우는 알고리즘”은 한글로 쓰여 있으면서도 그림으로 설명이 잘 되어 있어서 공부하는데 굉장히 편리합니다. 저는 고등학생 때 이 책으로 처음 알고리즘을 공부하였는데요, 이때부터 컴퓨터 공학에 본격적인 관심을 가지게 되었을 정도로 굉장히 재미있게 쓰여진 책입니다. 알고리즘 수강 계획이 없지만, 컴퓨터 과학에 대해 관심이 있는 타 학과 친구들에게도 자신있게 추천할만한 책입니다.

 

3. 맺음말

컴퓨터 공학 분야에서 하루가 다르게 새로운 연구가 쏟아지는 가운데,  몇십년 전에 만들어진 알고리즘들을 배우는 ‘알고리즘’ 수업이 흥미롭지 않게 느껴질 수도 있을 것 같습니다. 하지만 ‘알고리즘’ 수업에서 배우는 알고리즘들은 단순히 가장 빠른 경로를 찾거나, 리스트를 정렬하는 방법이 아니고, 그 이상의 의미가 있습니다. 알고리즘 수업을 통해 우리는 재귀적으로 사고하는 방법을 배우게 되고, 이러한 사고의 방식은 후에 컴퓨터 공학을 공부하는 데 있어서 큰 자산이 될 것 입니다. 모두 저처럼 알고리즘을 공부하면서 컴퓨터 과학의 재미를 찾으실 수 있기를 바랍니다!