'공부'가 아니라 '해보라'는 제안
수학 분야 중에 그래프 이론만큼 개발자와 가까운 게 또 있을까 싶어요. vertex.degree라는 사이트가 'Start Doing Graph Theory', 그러니까 그래프 이론을 시작해보라는 메시지를 내걸었는데요. 도메인 이름부터 재밌어요. vertex는 정점, degree는 차수라서 그래프 이론의 가장 기본 개념인 '정점의 차수'를 그대로 주소로 쓴 거거든요.
이 제목에서 눈에 띄는 단어는 '공부(study)'가 아니라 '해보기(doing)'예요. 교과서를 처음부터 끝까지 읽으라는 게 아니라, 직접 문제를 붙잡고 그려보고 증명해보라는 거죠. 그래프 이론은 대학 수학 중에서도 진입 장벽이 낮은 편이라 이런 접근이 특히 잘 통하는 분야예요. 오늘은 그래프 이론이 뭔지, 왜 개발자에게 유용한지, 그리고 어떻게 '해보기'를 시작할 수 있는지 이야기해볼게요.
그래프가 뭐냐면
여기서 말하는 그래프는 엑셀 차트가 아니에요. 점과 선으로 이루어진 구조, 즉 정점(vertex)과 그 정점들을 잇는 간선(edge)으로 만든 구조를 말해요. 지하철 노선도를 떠올리면 딱이에요. 역이 정점이고, 역과 역을 잇는 구간이 간선이죠. 한 정점에 연결된 간선의 개수를 차수(degree)라고 하는데, 환승역은 차수가 높은 정점인 셈이에요.
그래프 이론의 맛을 보여주는 간단한 사실이 하나 있어요. 모든 정점의 차수를 더하면 항상 간선 개수의 두 배가 된다는 건데요, 흔히 '악수 정리'라고 불러요. 이유는 단순해요. 간선 하나는 양 끝에 정점이 두 개 있으니까, 차수를 셀 때 정확히 두 번씩 세어지거든요. 여기서 재밌는 결론이 바로 따라 나와요. 파티에서 홀수 명과 악수한 사람의 수는 항상 짝수라는 거죠. 그림 몇 개와 짧은 논리로 '아하' 하는 순간을 만날 수 있다는 게 그래프 이론의 매력이에요.
역사적으로는 1736년 오일러가 쾨니히스베르크의 일곱 다리 퍼즐, 즉 모든 다리를 한 번씩만 건너서 다 지나갈 수 있느냐는 문제를 풀면서 시작됐어요. 답은 '불가능'이었고, 그 근거가 바로 차수였어요. 홀수 차수인 지점이 너무 많았던 거죠.
개발자는 이미 매일 그래프를 쓰고 있어요
의식하지 못할 뿐, 우리는 이미 그래프 위에서 일하고 있어요.
- 패키지 의존성: npm이나 Gradle이 설치 순서를 정할 때는 의존 관계를 방향 그래프로 보고 위상 정렬을 해요. 순환 의존성 에러는 그래프에 사이클이 생겼다는 뜻이고요.
- Git 커밋 히스토리: 커밋은 부모 커밋을 가리키는 방향 비순환 그래프(DAG)예요. merge와 rebase를 그래프로 이해하면 훨씬 덜 헷갈려요.
- 길찾기: 지도 앱은 도로망을 가중치 그래프로 보고 최단 경로 알고리즘을 돌려요.
- 컴파일러: 변수들을 한정된 CPU 레지스터에 배정하는 문제는 그래프 색칠 문제로 바뀌어요. 동시에 살아 있는 변수끼리는 같은 색, 즉 같은 레지스터를 쓰면 안 되거든요.
- 매칭: 배달 기사와 주문을 짝지어주는 문제는 이분 그래프 매칭의 가까운 친척이에요.
- Python의 networkx로 작은 그래프를 만들어 차수, 경로, 색칠을 직접 실험해 보세요. 그림으로 그려보는 것만으로도 감이 확 와요.
- 백준이나 프로그래머스의 그래프 문제를 풀되, 정답을 맞히는 데서 멈추지 말고 '왜 이 알고리즘이 맞는지' 한 줄이라도 증명해 보세요.
- 입문서로는 Richard Trudeau의 『Introduction to Graph Theory』처럼 얇고 친절한 책이 좋고, 더 깊이 가고 싶다면 Reinhard Diestel의 『Graph Theory』가 정석이에요.
코딩 테스트에 BFS, DFS 문제가 빠지지 않는 것도 이 때문이에요. 그래프는 현실의 '관계'를 표현하는 가장 범용적인 언어거든요.
왜 '해보기'가 가능한 분야냐면
그래프 이론의 독특한 점은 설명은 중학생도 이해하는데 아직 아무도 못 푼 문제가 많다는 거예요. 대표적인 예가 Hadwiger–Nelson 문제예요. 평면 위에서 거리가 정확히 1인 두 점이 항상 다른 색이 되도록 칠하려면 최소 몇 가지 색이 필요할까요? 오랫동안 답이 4에서 7 사이라는 것만 알려져 있었는데, 2018년 전문 수학자가 아닌 생물학자 오브리 드 그레이가 컴퓨터를 활용해 '최소 5색은 필요하다'는 걸 보여 수학계를 놀라게 했어요. 이후 온라인 공동 연구 프로젝트인 Polymath16이 그 그래프의 크기를 줄여나가기도 했고요.
1976년에 증명된 4색 정리도 컴퓨터로 수많은 경우를 확인해서 완성됐죠. 바로 이 지점이 개발자에게 유리해요. 작은 경우를 코드로 전부 탐색하고, 반례를 찾고, SAT 솔버(주어진 조건을 모두 만족하는 해를 찾아주는 프로그램)로 가능성을 검증하는 일은 우리가 이미 잘하는 일이니까요.
한국 개발자에게 주는 시사점
시작은 생각보다 가벼워도 돼요.
마무리
한줄 정리: 그래프 이론은 개발자가 이미 매일 쓰는 수학이고, 코드라는 무기가 있는 우리야말로 '직접 해보기'에 가장 유리한 사람들이에요.
여러분은 실무에서 '이거 사실 그래프 문제였네!' 하고 깨달았던 순간이 있나요? 의존성 지옥, 권한 체계, 추천 로직 등 어떤 경험이든 나눠주세요.
🔗 출처: Hacker News