1. 매칭 문제 N명을 둘씩 짝으로 묶으려고한다. 단 사이가 좋은 사람끼리만 짝을 지어준다고 할때 모든 학생에게 짝을 지어 줄 수 있는지, 불가능하다면 최대 몇 쌍이나 만들 수 있는지 계산하는 문제가 매칭 문제의 예시이다. 이런 문제들은 그래프로 간단하게 표현할 수 있다. 각 사람을 표현하는 정점을 만든 뒤, 사이 좋은 학생들을 간선으로 연결한다. 이 때 서로 짝을 이룬 학생들을 연결하는 간선들을 모아 보면, 이들은 끝점을 공유하지 않는 간선의 집합이 된다. 이런 간선의 집합을 이 그래프의 매칭(matching)이라고 한다. 이때 가장 큰 매칭을 찾아내는 문제를 최대 매칭 문제(maximum matching), 매칭 문제라고 부른다. 매칭 문제는 직관적인 정의를 가진 중요한 문제이다. 하지만 모든 그래프..

1. 문제 N명의 선수를 승부 조작에 참여시켰다. 결승 리그는 여러번의 1:1 경기이다 무승부 없이 항상 승부가 나며 모든 경기가 끝난 후 승수가 가장 많은 선수가 우승한다. 만약 가장 승수가 많은 선수가 둘 이상 있을 겨우 공동 우승을 하게 된다 대부분 우승하지 못할 것으로 여겨지는 X 를 단독 우승하도록해서 이득을 취하려고한다 의심을 피하기위해 가능한 X가 적은 승수로 우승하도록 하고싶다 현재 각 선수의 승수와 남아 있는 경기 목록이 주어질 때. 승부를 적절히 조작해 X가 우승하도록 할 수 있는지 여부를 계산하고, 우승할 수 있다면 필요한 X의 최소 승수는 얼마인지 계산하는 프로그램을 작성하여라. 이때 단독 우승이 불가능할 경우 -1을 출력한다. 그리고 모든 선수가 같은 수의 경기를 치르도록 보장되어..

1. 문제 A나라와 B나라가 경기를 한다고 한다. 이때 종목들과 종목마다 두 나라 선수의 예상 기록이 주어질때 두 나라를 무승부로 만들려고한다. 이때 가장 짧은 기록을 구하는 문제이다. 만약 무승부가 될 수 없으면 IMPOSSIBLE을 출력한다. 2. 책의 풀이: 그래프의 생성 만들수 있는 코스는 무한히 많다. 따라서 완전 탐색으로 이 문제를 풀기 불가능하지만 모든 코스를 다 만들어 봐야하는 것은 아니다. 힌트는 종목들 간의 순서가 상관이 없다는 것이다. 이 문제에서 종목들의 종류나 순서는 중요하지 않다. 의미 있는 것은 두 선수의 예상 시간 차이 뿐이다. 코스에 종목을 하나 추가하면, 그 종목에 따라 차이는 변화한다. 이와 같은 정보를 그래프로 표현하려면 A국 선수의 예상 시간에서 B국 선수의 예상 시..

1. 네트워크 모델링 네트워크 유량 문제를 풀 때는 특히나 주어진 문제를 어떻게 그래프로 표현할 것인가가 중요하다. 예제를 통해 그래프를 어떻게 표현할 것인지를 알아보자 2. MILEAGE 마일리지로 여행하기: 자원 분배 신용카드 포인트와 항공사 마일리지 포인트, 이동 통신사 멤버십 포인트 등을 모아서 여행중 쓰려고 한다. 한 종류의 마일리지를 여러 개의 결제 항목에 나눠서 쓸 수 있으며, 한 가지 항목을 여러 개의 마일리지와 현금을 합쳐 결제 하는 것도 가능하다. 단 각 마일리지마다 사용할 수 있는 항목에 제한이 있기 때문에, 어느 마일리지로 무엇을 결제할지 신중해야한다. 결제해야하는 항목들의 가격과 각 마일리지에 쌓인 금액, 각 결제 항목마다 사용할 수 있는 마일리지의 목록이 주어질 때, 사용해야하는..

1. 그래프의 용량(Network Flow) 네트워크를 이용해 아주 큰 파일을 다운로드하는 중이라고 하자. 이렇게 존송받을 자료의 양이 많을 때 관심을 갖는 부분은 서버가 보낸 패킷이 내 컴퓨터에 몇 밀리초 만에 도착하느냐가 아니라 1초에 몇 MB의 자료를 전송받을 수 있느냐이다. 네트워크를 구성하는 케이블들에는 일정한 대역폭이 있기 때문에, 단위 시간당 일정량 이상의 자료를 전송할 수 없다. 따라서 패킷을 여러 경로로 나누어 보내 그 중 일부가 좀더 먼 길을 돌아오더라도 초당 10MB를 전송받는 것이 훨씬 이득이다. 이렇게 각 간선이 용량을 갖는 그래프에서 두 정점 사이에 얼마나 많은 '흐름' 혹은 '유량'을 보낼 수 있는지를 계산하는 문제를 네트워크 유량 문제(Network Flow)라고한다. 네트워..

1. 문제 한 도시에서 다른 도시까지 여행을 하고싶다. 철도망은 여러 개의 역들과 그들을 잇는 노선으로 구성되어 있다. 각 구간별로 철도의 운행 속도가 정해져 있다. 가속과 감속을 반복하면 멀미때문에 괴롭다. 따라서 항상 비슷한 속도로 여행하고싶다. 철도망이 주어질때 여행 구간 중 최대 운행 속도와 최소 운행 속도의 차를 최소화하는 경로를 찾는 프로그램을 작성하라 시작 철도역은 항상 0 번이고 도착할 철도역은 항상 N-1번이다. 2. 책의 풀이1 어떤 경로에서 모든 간선의 가중치가 어떤 값 U이거나 그보다 작을 때, U를 '상한'이라고 하고 반대로 모든 간선의 가중치가 어떤 값 L이거나 그보다 클 때, L을 이 경로의 '하한'이라고 하자. 경로의 최소 상한과 최대 하한의 차이를 경로의 '너비'라고 하면 ..