얼마나 복잡한 문제인가?

경우의 수 확인하기

모든 알고리즘 책의 첫번째 시작은 문제의 복잡도를 분석하는 것입니다. 즉 경우의 수를 따져보는 것이지요.

 

현재 KBO 리그는 10개 팀으로 운영되고 있습니다. 그렇다면 한 경기에서 나올 수 있는 경우의 수는 어떻게 될까요?

10개 팀에서 2개 팀을 고르는 경우의 수는 90개입니다. (10개에서 2개를 고르는 조합이 아닌 순열 의 개수입니다. 순서가 변경되면 홈/어웨이의 차이가 발생하게 됩니다.) 그러면 남은 8개 팀에서 2개 팀을 고르는 경우의 수는 56입니다.

 

그렇다면 10개 팀에서 5개의 경기를 만드는 경우의 수는 3,628,800개가 됩니다. (10!입니다. 물론 Feasible한 것만 따져보면 경우의 수가 많이 줄어들겠지만, 일반적으로 알고리즘에서 문제의 복잡도를 따져볼 때는 처음부터 Feasible한 것까지 고려하지 않습니다.)

 

일반적으로 동일한 팀과 3경기를 연속하여 게임을 하게 됩니다. 아래 그림을을 보시면 4월 2일은 개막전이므로 토,일에 동일한 팀과 연속하여 2개의 경기를 치루고, 그 다음주 화요일인 4월 5일은 동일한 팀과 3개의 경기를 치룹니다. 이런 2게임, 3게임의 연속을 시리즈라 말하도록 하겠습니다.

 

그렇다면 총 몇 개의 시리즈를 치루는 것일까요? 아래 그림을 확인해보면 2022년 KBO 일정은 총 54개의 시리즈로 구성된 것을 알 수 있습니다.

 

2022년 시리즈 분석

시작일	요일	연속 경기	주말	휴일	휴일 상세
2022-04-02	토	2	1	0
2022-04-05	화	3	0	0
2022-04-08	금	3	1	0
2022-04-12	화	3	0	0
2022-04-15	금	3	1	0
2022-04-19	화	3	0	0
2022-04-22	금	3	1	0
2022-04-26	화	3	0	0
2022-04-29	금	3	1	0
2022-05-03	화	3	0	1	어린이날
2022-05-06	금	3	1	0
2022-05-10	화	3	0	0
2022-05-13	금	3	1	0
2022-05-17	화	3	0	0
2022-05-20	금	3	1	0
2022-05-24	화	3	0	0
2022-05-27	금	3	1	0
2022-05-31	화	3	0	1	지방선거
2022-06-03	금	3	1	0
2022-06-07	화	3	0	0
2022-06-10	금	3	1	0
2022-06-14	화	3	0	0
2022-06-17	금	3	1	0
2022-06-21	화	3	0	0
2022-06-24	금	3	1	0
2022-06-28	화	3	0	0
2022-07-01	금	3	1	0
2022-07-05	화	3	0	0
2022-07-08	금	3	1	0
2022-07-12	화	3	0	0
2022-07-22	금	3	1	0
2022-07-26	화	3	0	0
2022-07-29	금	3	1	0
2022-08-02	화	3	0	0
2022-08-05	금	3	1	0
2022-08-10	수	3	0	0
2022-08-13	토	2	1	0
2022-08-16	화	2	0	0
2022-08-18	목	2	0	0
2022-08-20	토	2	1	0
2022-08-23	화	2	0	0
2022-08-25	목	2	0	0
2022-08-27	토	2	1	0
2022-08-30	화	2	0	0
2022-09-01	목	2	0	0
2022-09-03	토	2	1	0
2022-09-06	화	2	0	0
2022-09-08	목	2	0	1	추석
2022-09-10	토	2	1	1	추석
2022-09-13	화	2	0	0
2022-09-15	목	2	0	0
2022-09-17	토	2	1	0
2022-09-20	화	2	0	0
2022-09-22	목	2	0	0

다만 2022년 프로야구 일정표를 확인하니 개막전과 어린이날은 고정이므로, 우리는 52개 시리즈에 대한 일정을 세워야 합니다. 이에 대한 경우의 수는 얼마나 될까요? 아까 한 경기의 경우의 수가 3,628,800개이므로 대략적으로 3628800^52 개가 됩니다.  어마어마하네요. (다시 말씀드리지만 그 모든 경우의 수가 feasible한 해가 아닙니다만 이를 걸러낸다면 그 경우의 수는 줄어들 것입니다. 그럼에도 불구하고 엄청난 숫자입니다.)

 

이 문제를 빠른 시간 내로 풀 수 있는 어떤 알고리즘도 없습니다.

모든 경우의 수를 다 시도해봐야 가장 좋은 해를 찾을 수 있습니다. 그러나 그러기에는 우리 인생은 너무나 짧습니다.

• 이 문제를 Brute-force 방식(모든 경우의 수를 다 접근해 보는 것)으로 접근한다면 계획을 수립하다가 시즌이 끝나버릴 것입니다. (어떤 복잡한 TSP문제는 한 평생 풀어도 시간이 부족하다고 하지요.)
• 혹 누가 자신있게 이것이 정답이라 말한더 하더라도 정답인지 확신할 수 없습니다. (어딘가 더 좋은 해가 있을지 누가 알까요?)
• 이런 문제를 대표적인 NP-Hard 문제 로 추정되는 문제로 볼 수 있습니다. (이산적인 조합최적화 관점에서는 NP-Hard가 맞다고 생각합니다. Decision 관점이 아니니까... )
• 보다 개념적인 정의를 원하신다면 아래 링크를 참조 부탁드립니다.
  • NP-Hard, NP-Complete
  • TSP는 NP-Complete.
  • P, NP문제와 co-NP, NP-난해(NP-Hard), NP-완전(NP-complete) 개념 정리 – Jang (wkdtjsgur100.github.io)

 

우리는 타협이 필요합니다.

• 현실적인 목표는 최적해일지 모르는 어떤 근사한 해를 찾는 것입니다.

 

과연 KBO는 이 복잡한 문제를 어떻게 풀었을까요?

• 문제의 복잡도를 파악하면서, 일정을 수립하는 KBO의 고충을 충분히 이해할 수 있었습니다.
• 다음 글에서는 지금까지 많은 논란이 있었던 일정 편성 문제를 2022년에는 어떻게 풀었을지 확인해보도록 하겠습니다.