d라이브러리

알고리듬만 있으면 세상에 못 풀 문제가 없는 줄 알았던 견우가 충격에 빠진 모양이에요. 어떤 문제는 유한한 시간 안에 답을 구하는 방법이 아직 존재하지 않거든요. 이럴 때 우리 알고리듬 요정은 손 놓고 가만히 있어야 할까요? 아니, 실망하긴 일러요!

밸런타인데이 기념으로 제가 여러분에게 줄 초콜릿을 잔뜩 준비했어요! 간단한 문제를 맞히면 전부 다 드릴게요. 여기 높이가 10인 상자가 있어요. 제가 준비한 초콜릿 상자는 6개고 각각 높이는 5, 6, 3, 7, 5, 4예요. 모든 초콜릿 상자를 큰 상자에 담되, 큰 상자를 최대한 적게 쓰려면 어떻게 채워야 할까요?

답은 아래 그림처럼 담는 거예요. 그러면 큰 상자를 3개만 써서 모든 초콜릿 상자를 담을 수 있죠. 쉽다고요? 하지만 물건의 수와 가짓수가 컸다면 지금처럼 쉽게 구할 수 없었을 거예요. 언뜻 간단해 보이는 상자 채우기 문제는 유한한 시간 안에 항상 문제를 해결하는 효율적인 알고리듬이 아직 발견되지 않은 ‘NP-완전 문제’거든요.

수학적으로 풀린 문제는 컴퓨터가 알고리듬을 따라 정확한 답을 쉽게 구할 수 있지만 NP-완전 문제는 아직 정확한 답을 구하기 어려워요. 그렇다고 당장 실생활에 NP-완전 문제를 해결해야 할 상황들이 있는데 마냥 풀리기만 기다릴 순 없죠. 이럴 때 사용하는 것이 답에 아주 가까운 답을 찾아주는 ‘근사 알고리듬’이에요!

근사 알고리듬은 긴 시간과 복잡한 단계를 거쳐 정확한 답을 찾는 대신, 일정한 단계 안에 최대한 정확한 답에 가까운 답을 찾는 알고리듬이에요. 실제 답에 가까울수록 좋은 근사 알고리듬이라고 할 수 있죠.

외판원 문제, 정점 커버 문제, 작업 스케줄링 문제, 클러스터링 문제 등 아직 해결되지 않은 문제로부터 우리 삶을 편리하게 해주는 몇 가지 근사 알고리듬을 배워볼게요.

그림으로 보는 알고리듬 ⑥ - 클러스터링

클러스터링은 많은 데이터가 있을 때 ‘비슷한 것’들을 묶어 집합으로 분류하는 작업으로, 클러스터링 문제는 근사 알고리듬의 한 종류예요. 데이터의 수가 많으면 정보를 일일이 비교하기 힘드니 어떤 기준을 정해서 분류하는 것이 좋아요. 한 방법으로 아래 그림과 같이 데이터를 점으로 표현해 평면에 나타낼 수 있죠. 예를 들어 견우네 반 친구들을 수학, 영어 실력이 비슷한 친구들끼리 한 조에 묶어 방학 보충수업 반을 짜려고 할 때, 영어 성적과 수학 성적을 평면에 나타내 클러스터링하는 거예요.

‘클러스터링 문제’는 클러스터를 나누는 방법을 찾는 알고리듬이에요. 전체 점을 원하는 개수의 집합으로 나누고 집합마다 중심이 되는 점을 선택하는 문제죠. 다만 점을 선택할 때 가장 큰 집합의 지름이 최소가 되도록 점을 골라야 해요.

클러스터링 개념을 충분히 이해했다면 다음 시간에는 클러스터링 알고리듬이 어떻게 최소 지름을 찾는지 알려드릴게요. 그럼 전 견우를 도와주러 이만!