세상에이런알고리즘이있다니

이세상의 알고리즘을 알아보자

• 합이 10인 조합이 남았는지 판정하기 (연결 부분집합 열거)

  왜 공부했나

  블로그에 사과게임(17×10 판에서 인접한 칸을 긁어 합이 정확히 10이면 사라지는 게임)을 만들었다. 2분 제한인데, 판에 조합이 하나도 안 남았는데도 남은 시간 동안 멍하니 긁고 있어야 하는 게 답답했다.

  그래서 “더 이상 만들 수 있는 조합이 없으면 즉시 종료"를 넣기로 했다. 문제는 그 판정이다. 지금 판에 합이 10이 되는 연결 부분집합이 하나라도 있는가?

  순진하게 접근하면

  170칸의 모든 부분집합을 보는 건 당연히 불가능하다. 2¹⁷⁰이다.

  하지만 조건이 두 개 있어서 실제 탐색 공간은 훨씬 작다.