0. Introduction

0. Introduction

안녕하세요! 자료구조와 알고리즘 주제로 연재를 하게 된 공우 13기 이성찬입니다. 반갑습니다!

여러분은 만약 구글이나 네이버에 로그인하는데 1분이 넘게 걸린다면 어떤 생각이 드실 것 같나요? 빠른 인터넷과 놀라운 성능을 가진 컴퓨터의 계산 속도에 익숙해진 분들이라면, 아마 참지 못할 정도로 답답해하실 것입니다. 저라면 10초가 지나기도 전에 왜 로그인이 안되는지 의아해하며 바로 새로고침 버튼을 누른 뒤 다시 시도해볼 것 같습니다.

구글의 로그인 화면

로그인이 빨리 되는 것이 왜 중요할까요? 다양한 답을 생각할 수 있을 것 같습니다. 기다리기 힘들어서, 현대인은 바쁘기 때문에 빠르면 빠를수록 좋아서 등등... 다 맞는 말입니다. 이 현상을 서비스 제공자(구글/네이버)의 관점에서 본다면, 느린 로그인 시간은 곧 부정적인 사용자 경험(UX)을 의미하게 됩니다. 서비스 제공자의 입장에서는 서비스가 성장하기 위해 사용자들을 모아야 하고, 많은 사용자들이 불편함을 느끼고 있다면 이를 빠르게 해결해야 사용자들의 이탈을 막을 수 있게 됩니다.

비즈니스적인 이유 이외에 기술적인 이유들도 찾을 수 있습니다. 이용자가 적당히 많은 서비스이고, 로그인이 1분 걸린다고 가정해 보겠습니다. 만약 여러 명의 사용자가 로그인을 시도하게 된다면 어떤 일이 벌어질까요? 첫 번째로 시도한 사람의 로그인을 처리하는 1분이 지나기 전에 다음 사람이 또 로그인을 시도할 수도 있습니다. 두 번째 사람은 얼마나 기다려야 로그인을 할 수 있을까요?^[1] 간단하게 생각해보면 앞사람의 로그인이 끝나야 자신의 로그인이 처리되기 시작할 것입니다. 그러니 1분이 넘는 시간을 기다려야 하게 될 수도 있습니다.

만약 Gmail과 같은 글로벌 서비스라면 적어도 수백만 이상의 사용자를 보유하고 있을 것입니다. 전 세계에서 로그인을 시도하는 사람이 많을 것이기 때문에, 이 속도의 로그인으로는 서비스가 기술적으로 불가능합니다. 한 사람의 입장에서 보면 짧은 1분이겠지만, 수 만 명이 동시에 서비스를 사용하는데 로그인이 느리다면 이는 수 만 명의 시간을 낭비하게 되는 결과를 낳게 됩니다. 조금만 빨라져도, 이용자가 많기 때문에 엄청난 양의 시간과 컴퓨팅 자원을 아낄 수 있게 됩니다. 실제로, 넷플릭스의 '오프닝 건너뛰기'(Skip Intro) 버튼은 수 십 초를 건너뛰게 해 주지만, 사용자가 매우 많기 때문에 하루에 무려 195년에 해당하는 시간을 절약해 준다고 합니다. 늘 반복되는 오프닝을 보지 않고 더 빨리 콘텐츠를 볼 수 있도록 건너뛰기 버튼을 만들어서 사용자의 시간을 절약해준 사례이죠.^[2]

결국 컴퓨터는 빠르고 정확하게 작업을 처리하는 것이 중요합니다. 결과의 정확성을 해치지 않는 선에서, 빠르면 빠를수록 좋습니다. 시간은 금이기 때문입니다!

1: 이런 서비스는 없겠지만, 서버가 1개의 CPU 코어로 운영되고 있으며, queue 방식으로 요청을 처리한다고 가정했습니다. 하지만 멀티 코어를 사용한다고 해도 처리가 오래 걸리는 작업은 서버 입장에서 부담되는 것은 마찬가지입니다.↩

2: '오프닝 건너뛰기' 도입 5년, 그 기원을 돌아보다↩

---

최적화

위 사례에서 알 수 있듯이, 컴퓨터의 세계에서는 프로그램이 소비하는 자원(시간, 메모리 등)을 줄이는 것이 굉장히 중요합니다. 이렇게 프로그램이 소비하는 자원을 줄여서 프로그램을 더욱 효율적으로 만드는 과정을 최적화(optimization)라고 합니다.

역사적으로 수많은 학자들이 다양한 최적화 기법을 고안해 냈고, 지금도 더욱 효율적인 프로그램을 만들기 위해 끊임없이 연구하고 있습니다. 업계에서는 수많은 엔지니어들이 보다 더 효율적인 프로그램을 만들기 위해 고민하고 또 고민합니다. 이러한 과정들을 모두 거쳤기 때문에 현대의 우리는 과거에는 상상하지도 못했을 컴퓨터의 빠른 성능을 경험할 수 있게 되었습니다.

그렇다면 최적화는 어떻게 하는 것일까요? 크게 두 가지 방법이 있는데, 실생활에서의 예시를 소개해 보겠습니다.

자료구조

여러분이 수 천 권의 책이 있는 도서관에서 특정 책 1권을 찾는다고 해봅시다. 일반적으로 도서관에 가면 도서 검색용 컴퓨터가 있어 책 제목 검색을 통해 해당 도서의 번호를 알아낼 수 있고, 이 번호를 사용해서 원하는 책이 어디에 있는지 금방 찾아낼 수 있습니다.

000	총류
100	철학
200	종교
300	사회과학
400	자연과학
500	기술과학
600	예술
700	언어
800	문학
900	역사

번호를 사용해서 원하는 책을 쉽게 찾을 수 있는 이유가 무엇인지 곰곰이 생각해 보면, 책들이 분류되어 도서 번호 순서대로 정렬되어 있기 때문입니다. 만약 책들의 순서가 정리되지 않은 채로 뒤죽박죽이라면, 도서 검색용 컴퓨터를 이용해 도서 번호를 검색했다고 하더라도 책이 몇 층 어느 책꽂이에 있는지 찾으려면 하루 종일 걸릴 것입니다.

도서관에서 책 찾기와 같은 현실의 문제를 해결하기 위해 자료의 검색, 삽입, 삭제 등의 연산이 효율적으로 수행될 수 있도록 자료구조(data structure)를 사용합니다. 도서관에서는 도서의 번호가 자료(data)이며, 자료(도서 번호)가 정렬된 구조(structure)의 형태로 정리되어 있는 것입니다. 이와 같이 자료구조를 이용해서 자료의 검색에 걸리는 시간을 최적화할 수 있습니다. 이 분야를 더욱 깊이 공부하다 보면 다양한 현실의 문제를 효율적으로 해결하기 위해 고안된 다양한 자료구조를 만나게 될 것입니다. 약간의 억지를 부려보자면, 수학에서 사용하는 벡터와 행렬도 연산을 효율적으로 하기 위한 일종의 자료구조로 볼 수도 있습니다!

물론 자료구조를 사용하는 것이 절대 공짜는 아닙니다. 도서관의 예시만 봐도 수많은 책들이 번호순으로 정렬된 상태를 유지하기 위해 누군가는 책을 올바른 위치에 꽂아 정리해야 합니다. 저는 중학교 3년 내내 도서관에서 책을 정리하는 봉사활동을 했었습니다. 다양한 책을 접하는 것은 정말 좋아했고 책 꽂는 것도 쉬웠지만 머리로 도서 번호를 비교하는 작업은 결코 쉽지 않았던 것 같습니다. 그럼에도 이 비용을 들여 정리를 하는 이유는 정리를 잘해둬야 나중에 다시 찾기 쉽기 때문입니다. 조금 더 기술적으로 말해보면, 정렬된 자료구조를 유지하도록 도서관에서 정리를 하는데 드는 비용이 정렬을 포기한 상태에서 책을 검색하는데 드는 비용보다 훨씬 작기 때문입니다.^[3]

알고리즘

다음으로는 어떤 계산이나 연산을 조금 더 효율적으로 수행해서 최적화를 할 수도 있습니다. 앞서 언급한 도서관의 예시에서 도서 번호를 알았을 때 어떤 방식으로 책을 찾아가는지 생각해보고자 합니다.

우선 가장 간단하게 생각할 수 있는 방법으로는 000 총류에 있는 도서부터 하나씩 찾아가는 방법이 있을 것입니다. 이 방법을 사용한다면 000 총류 쪽에 있는 도서를 찾을 때는 금방 찾을 수 있겠지만, 400번대의 책을 찾는다면 000 ~ 300 분야의 책을 모두 확인해야 하기 때문에 굉장히 시간이 오래 걸릴 것입니다. 우리의 시간은 소중하니, 조금 더 효율적인 방법이 필요할 것 같습니다.

현실의 우리는 도서관의 책들이 정렬되어 있다는 사실을 이용해서 보다 효율적인 방법으로 책을 찾습니다. 예를 들어 425번 책을 찾는다고 하면 우선 400번대 책이 있는 곳으로 간 다음, 아무 책이나 하나 집어서 번호가 425보다 크면 더 앞쪽으로 가서 책을 찾을 것이고, 425보다 작으면 더 뒤로 가서 책을 찾을 것입니다. 이 과정을 반복해서 최종적으로 원하는 책을 찾습니다.

이 과정은 우리가 책에서 특정 페이지를 펼 때 하는 동작과 굉장히 유사하고, 숫자게임(업다운 게임)^[4]에서도 비슷한 원리를 사용해서 게임을 진행합니다. 이 두 경우 모두 자료구조(숫자)가 정렬되어 있다는 사실을 의식적으로 혹은 무의식적으로 이용한 것입니다.

이렇게 우리는 연산을 하거나 문제를 해결할 때 이를 위한 과정이나 방법을 사용합니다. 컴퓨터공학에서는 이를 알고리즘(algorithm)이라고 부릅니다. 상황이나 문제에 따라 조금 더 효율적인 알고리즘을 고안해서 최적화를 할 수도 있습니다.

번외 - 계산을 효율적으로 하는 알고리즘

누군가 1부터 100까지 더하라고 한다면 실제로 더할 수도 있겠지만, 아래의 공식을 이용해서 덧셈을 직접 하는 것보다 효율적으로 답을 구할 수 있습니다. 우리는 경험적으로 공식을 이용하는 편이 월등히 빠르다는 것을 알고 있습니다.

\[ \sum_{k=1}^{n} k = \frac{n(n+1)}{2} \implies \sum_{k=1}^{100} k = \frac{100 \cdot 101}{2} = 5050\]

심지어 이 공식과 함께 자주 일화로 등장하는 수학자 가우스조차 공식을 사용해 계산하는 것이 빠르다고 판단한 것 같습니다.

3: 책의 개수가 적다면 비용 차이가 유의미하지 않지만, 책의 수가 늘어날수록 비용 차이는 점점 커질 것입니다.↩

4: 1부터 100까지의 숫자 중 상대방이 생각하고 있는 숫자를 맞히는 게임으로, 숫자 하나를 불렀을 때 상대방은 그 숫자가 자신이 생각한 숫자와 비교했을 때 큰지, 작은지, 혹은 같은지 알려주는 방식으로 진행합니다.↩

---

이처럼 자료구조와 알고리즘은 실생활 속에서, 또 우리가 사용하는 전자기기, 애플리케이션, 그리고 각종 서비스 속에서 연산을 효율적으로 수행하고 자원을 아끼기 위해 곳곳에서 이미 사용되고 있습니다. 우리의 시간과 자원이 소중한 만큼, 매우 깊이 있게 연구되고 있는 분야이며 저는 개인적으로 매우 중요한 분야라고 생각합니다!

본 정기 연재를 통해서 다양한 자료구조와 알고리즘을 소개하고자 합니다. 학부 알고리즘 수업 시간에는 이론을 소개하고 의사 코드(혹은 특정 언어로 구현한 구현체)를 작성하고 넘어가지만, 여기서는 더 나아가 알고리즘을 활용해서 풀어볼 수 있는 문제도 함께 소개하고자 하고, 가능하다면 실제로 그 알고리즘이 현실에서 어떻게 쓰이고 있는지 소개하는 것을 목표로 해볼 예정입니다.

사전 지식

• 주제에 따라 깊은 수학이 필요할 수도, 아닐 수도 있습니다. 고등학교 수학 지식 혹은 대학교 교양 미적분학의 내용은 설명하지 않고 넘어갈 예정입니다.
• C/C++ 또는 Java 언어에 대한 이해, 객체지향(OOP) 프로그래밍을 어느 정도 이해하고 있으면 좋습니다.

다음 글에서 만나요!