포스테키안

2019 여름호 / 포스텍 에세이

2019-07-18 184

포스텍 에세이 / 알고리즘 Algorithm 최적의 길에서 한계 뛰어넘기

안희갑 컴퓨터공학과 교수

인공지능과 알고리즘

인공지능은 학술이나 산업 분야의 관심을 넘어 이제 우리의 일상생활에 큰 변화와 편리함을 가져다주는 데까지 이르고 있다. 컴퓨터 기반으로 실제 사고하고 문제를 해결하는 지능적인 행동을 하는 강인공지능 strong AI에 대한 논의는 철학적인 찬반 단계를 넘어 이제 곧 기술적인 도약을 바라보는 단계에 이른 듯하다. 최근 신문에서 세계 최대 전자상거래 업체인 아마존이 발표한 드론은 전깃줄이나 빨랫줄 같은 복잡한 장애물을 피하며 최대 약 2.3kg 무게를 최대 24km까지 30분 이내에 배달할 수 있다고 한다. 이렇듯 인간의 사고방식과 지능을 흉내 내어 복잡한 문제를 해결하려는 시도에서 시작된 인공지능기술은 수십 년 동안 기술적 발전과 암흑기를 반복해 오면서 점점 더 삶의 질을 향상시키고 있고 난제를 해결하는 단계에 한 걸음씩 다가가고 있다.

인공지능과 함께 알고리즘에 대한 관심 또한 커지고 있다. 알고리즘의 논리에 따라 주식을 거래하는 알고리즘 매매 algorithmic trading에서부터 Google의 PageRank 검색 알고리즘과 개인별 취향과 선호도에 따라 맞춤형 검색 결과를 제시하고 추천하는 추천 시스템에 이르기까지, 알고리즘이라는 용어는 우리의 일상생활과 밀접한 용어가 되었다. 컴퓨터 알고리즘은 인공지능과 머신러닝의 핵심이 되는 기술로, 복잡하고 계산이 어렵거나 많은 계산량이 필요한 문제 해결에 대한 순차적이며 논리적인 해결 절차이다. 기원전 300년경에 만들어진 유클리드 최대공약수 알고리즘부터 숫자들을 빠르게 정렬하는 다양한 정렬 알고리즘들, 점집합의 공간적 분포를 인식하고 계산하는 최적화 알고리즘에 이르기까지 수많은 계산 문제들이 최적의 알고리즘 방식으로 해결되고 구현되어 검색과 추천, 그래픽스, 컴퓨터 비전기술 그리고 게임에 이르기까지 핵심 구현 요소로 사용되고 있다.

최적화 난제

하지만 아직도 효율적인 알고리즘을 찾지 못한 수많은 문제가 우리 앞에 놓여 있다. 컴퓨터 알고리즘과 계산 이론에서 효율적으로 해결하기 어렵다고 알려진 외판원 문제는 이러한 최적 계산의 어려움을 잘 보여준다.

포스텍의 문서수발실에서 일하는 K씨는 매일 오전과 오후에 한 번씩 캠퍼스에 흩어진 건물들을 돌아다니며 문서를 수합하고 전달하는 일을 한다. 어느 날 문득 K씨는 지금까지 캠퍼스 건물들을 순회 방문하는 경로가 가장 효율적인, 즉 가장 짧은 길이의 경로인지에 대해 의문이 생겼다. 다섯 개의 건물 A, B, C, D, E가 캠퍼스에 흩어져 있는데 문서수발실이 있는 A에서 출발해서 나머지 건물들을 모두 방문한 후에 다시 A로 돌아오는 방법은 모두 4!=24가지이다. 건물들 사이의 거리를 모두 알고 있을 때 길이가 가장 짧은 경로는 24가지의 서로 다른 경로를 하나씩 고려해서 계산하면 구할 수 있다. 만약 건물이 50개가 있다면 49! 개의 서로 다른 경로가 있는데, 이것은 63자리의 아주 큰 수다. 건물이 100개가 넘는다면, 해변의 모래알과 같이 천문학적인 수의 가능성을 살펴봐야 하고 최고 성능의 GPU를 여러 개 갖춘 컴퓨터 클러스터를 동원한다고 해도 수년 내에 가장 짧은 경로를 구하기는 어려울 것 같다. 이처럼 최고 성능의 컴퓨터를 사용하거나 혹은 프로그램을 얼마나 잘 짜든 간에 본질적으로 최적의 해결책을 구할 수 없는 문제들이 많이 있다.

최적 알고리즘 추구 노력과 한계

컴퓨터과학자들은 이러한 최적화 난제들을 해결하기 위해서 부단히 노력했지만 어느 누구도 실질적인 진척을 이룰 수 없었다. 대신 그 노력의 결과로 난제들이 서로 비슷한 이유로 어렵다는 점을 발견하였다. 그들은 다항시간 Reduction이라고 알려진 방법을 사용해 최적화 난제들이 비슷한 어려움을 갖는 문제들이라는 것을 밝혔고, 이러한 문제들을 모아 NP-Complete라고 이름을 붙였다. 입력의 크기에 대해 지수적으로 많은 수의 후보들 가운데 최적의 답 하나를 찾는 문제들 가운데 가장 어려운 문제들을 모아둔 것이 바로 NP-Complete이다. 컴퓨터과학 혹은 컴퓨터공학의 최대 난제로 알려진 NP와 P의 동등성 문제는 바로 NP-Complete 문제 하나를 다항시간에 해결하는 알고리즘이 존재하는지 여부를 증명하여 해결할 수 있다. 하지만 현재까지 다항시간 알고리즘을 찾은 NP-Complete 문제는 하나도 없으며, 그렇기 때문에 대부분 컴퓨터과학자는 모든 NP-Complete 문제는 다항시간에 해결 불가능하다고, 따라서 P와 NP는 동등하지 않다고 확신하고 있다. 현재 우리가 가진 컴퓨팅 능력으로는 정확한 답을 효율적으로 구할 수 없는 어려운 문제들이 아주 많다.

한계 뛰어넘기

그렇다고 포기할 필요는 없다. 잠시 생각해 보면 우리는 일상생활에서 NP-Complete처럼 가장 어려운 문제들을 끊임없이 대면하면서 해결해 가고 있다. 물론 제대로 해결 못 해 엉망이 되는 경우도 자주 일어난다. NP-Complete 문제를 해결하기 위해 컴퓨터과학자들은 오랜 기간의 연구를 통해 해결책을 찾고자 노력해 왔다. 때로는 인간의 직관이나 새와 곤충의 군집 생활에서 해결책을 찾기도 하고 때로는 비상식적이고 무질서한 방식을 통해서도 어느 정도의 성과를 거두었다. 물론 다항시간의 완벽한 알고리즘 대신, 무작위적으로 정답을 찾거나 알파고와 같이 정답이 될 수 없는 조건이나 경우를 미리 발견해 많은 후보를 일찌감치 제외하는 방식으로 빠른 시간에 정답을 찾을 가능성을 높이는 기법을 사용하였다. 또는 정답을 찾는 대신 정답일 가능성이 높은 국소 최적값 local optima을 반복적으로 찾거나, 정답에 가까운 정도가 보장되는 근사 답을 찾는 방식이 제안되어 왔다. 인공지능은 인간의 사고방식을 흉내 내어 문제를 해결하려는 노력에서 시작하였고, 기계학습에서는 인간 두뇌를 단순하게 모방한 신경망을 구성하여 어려운 문제를 해결하고자 노력하고 있으며, 더 나아가 신경망을 여러 층으로 복합 구성한 심층신경망을 통해 더 복잡한 사고가 가능하도록 연구하고 있다. 이처럼 어려운 계산 문제를 해결하려는 노력은 결국 일상의 문제를 해결하며 살아가는 인간의 두뇌 구조와 사고방식에서 해결책을 발견한 셈이다.

중요한 건 사람이다

컴퓨터과학자들이 어려운 문제의 계산 한계를 넘기 위해 끊임없이 도전하는 이유는 무엇일까? 아마 무엇보다도 학문에 대한 호기심과 성취 욕구 때문일 것이다. 20여 년 동안 해결되지 못했던 알고리즘 난제를 해결했을 때 필자가 느꼈던 희열은 잊을 수가 없다. 그리고 또 한 가지 이유는 이러한 성과를 통해 기술과 산업이 발전하여 과학기술과 인간 사회의 거리를 좁히고, 궁극적으로 인간 삶의 질을 향상시킬 것이라는 믿음 때문이다. 단기간의 성과를 생각하면 당장 활용되어 조금이라도 성능을  향상시킬 소프트웨어의 개발이 중요하지만 보다 장기적으로 고려하면 문제를 면밀히 분석하여 근본 구조와 성질을 규명하고 궁극적으로 문제를 해결하는 효율적인 알고리즘을 설계하고 구현하는 것이 훨씬 중요하고 가치 있는 일이다. 그리고 환경의 변화와 새로운 하드웨어의 등장, 해결해야 하는 새로운 문제들에 대해 능동적으로 대처하며 이를 해결하는 최적의 알고리즘 개발은 수학적 지식과 탐구 능력, 그리고 알고리즘 문제 해결 역량을 갖춘 인재들에 의해 이루어진다. 그렇다, 가장 중요한 건 사람이다.

안희갑 컴퓨터공학과 교수와 학생과의 인터뷰 후 기념 사진

난제에 도전하는 인고의 시간

난제의 계산 한계를 넘어 보다  빠른 시간에 문제를 해결하는 알고리즘 연구는 필자를 포함한 컴퓨터과학자들에게는 무척이나 매력적이다. 컴퓨터 알고리즘이 단순한 학문을 넘어 삶에서 부딪히는 문제를 직접 해결하고 삶의 질을 높이는 데 도움이 되는 알고리즘 해결 방식을 제공하고 있기 때문일 것이다. 하지만 난제를 해결하는 것은 결코 쉬운 일이 아니다. 문제를 면밀히 분석하여 기존의 방식과는 다른 새로운 접근 방법을 시도하기도 하고, 전혀 관련 없어 보이는 현대 수학의 원리를 적용하기도 하며, 인간의 사고방식을 모방하기도 하면서 며칠이 아니라 여러 해를 손에 잡히는 성과 없이 보내기도 한다. 마음은 점점 더 초조해지지만, 난제를 해결하겠다고 하는 도전 의지와 문제 해결의 희망을 잃지 않고 인고의 시간을 견뎌야 한다. 노력 끝에 마침내 문제를 해결하게 되어 큰 기쁨을 누리기도 하지만, 문제가 해결되지 않더라도 그 시간은 문제 해결 역량을 한 단계 더 높이는 값진 기간이 된다. 때로는 문제 해결의 과정에서 다른 문제를 해결하는 성과를 얻기도 하고, 더욱 실용적인 해법을 찾아 현실에 적용하여 큰 성공을 거두기도 한다.

모죽같은 포스테키안

포스테키안은 NP-Complete처럼 가장 어려운 문제들과 끊임없이 대면하고 있다. 시간은 부족한데 배워서 익혀야 할 내용은 매주 기하급수적으로 늘어나고 힘든 과제와 프로젝트를 수행하기 위해 밤을 지새우며 마치 끝이 보이지 않는 깜깜한 터널을 계속 지나며 지친 몸과 마음을 겨우 추스르고 있는지도 모르겠다.

대나무 중에서도 최고라고 하는 모죽은 씨를 뿌린 후 물을 주고 정성을 다해 가꾸어도 5년 동안은 작은 순만 나올 뿐 거의 변화가 나타나지 않다가, 어느 순간부터 하루 수십 센티미터씩 자라 25m 정도 높이로 자란다고 한다. 5년이란 기간 동안 뿌리를 내리고 넓히며 성장을 위한 기초 역량을 충분히 갖춘 후 그 후에 기적같이 당당한 모습으로 자라난다. 현재와 미래의 포스테키안들이 모죽과 같이 인고의 터널을 지나 마침내 인류의 삶에 기여하고 세상을 변화시키는 인재로 거듭나 더욱 가치 있는 삶을 살아가기를 기대한다.

글/ 안희갑 컴퓨터공학과 교수