문제 https://www.acmicpc.net/problem/10265 10265번: MT 남규는 동기들과 엠티를 가기 위해 버스를 대절했다. 그런데 과사의 실수로 대절버스의 인원이 잘못되어 남규의 동기들을 모두 태울 수 없었다. 이 와중에 동기들은 화를 내며 다음과 같은 www.acmicpc.net 풀이 solved.ac 난이도: Platium 4 SCC로 새롭게 구성한 컴포넌트 별로 최대, 최소 인원을 파악해 배낭 문제로 값을 구해야 했던 문제로 굉장히 어려웠다.. 일단 인원 마다 같이 가고 싶은 인원(pick)을 가리키도록 그래프로 표현해보자. 1번 인원이 2번 인원과 가고 싶다면 다음과 같이 표현된다. 관계를 이런식으로 나타냈을 때 예제의 입력인 12 3 2 3 4 5 6 7 4 7 8 8 12..

Boolean 변수들에 대해서 참, 거짓의 결정을 여러 번 해야 하는 문제를 충족 가능성 문제(Satisfiability Problem, SAT)라고 합니다. 특히 그중에 선 괄호 안의 각 절(clause)에 최대 두 가지 변수만이 존재하는 경우를 2-SAT 문제라고 합니다. 예를 들어 다음과 같은 식은 각 절에 두 가지 변수를 가지고 있습니다. (A || B) && (B || C) && (C || D) (이처럼 각 절들이 && 로 연결된 수식을 논리곱 정규형(Conjunctive normal)이라고 합니다.) 이제 2-SAT로 해결해야 하는 문제인 알고스팟 회의실 배정(MEETINGROOM) 문제를 풀면서 2-SAT에 대하여 알아봅시다. 문제 https://algospot.com/judge/proble..

문제 https://www.acmicpc.net/problem/3977 3977번: 축구 전술 World Soccer Championship이 다가오고 있다! 천재적인 전술을 창조하는 플랜 아티스트 감독 도현이는 자신의 팀이 승리하도록 만반의 준비를 가하고 있다. 도현이의 전략은 경기장을 여러 개의 구역 www.acmicpc.net 풀이 solved.ac 난이도: Platium 4 강한 결합 컴포넌트(SCC,Strongly Connected Component)로 해결해야 하는 문제. SCC를 모른다면 굉장히 풀기 힘드니 먼저 공부하고 오자. 방향 그래프에서 두 정점이 서로 이동 가능한 경로가 있는 경우 해당 정점들은 같은 강한 결합 컴포넌트에 속한다. 예를 들어 아래의 방향 그래프에서 같은 SCC끼리를 ..