My life story

1. 문제 링크 www.acmicpc.net/problem/4013 4013번: ATM 첫째 줄에 교차로의 수와 도로의 수를 나타내는 2개의 정수 N과 M(N, M ≤ 500,000)이 차례로 주어진다. 교차로는 1부터 N까지 번호로 표시된다. 그 다음 M개의 줄에는 각 줄마다 각 도로의 시작 교차 www.acmicpc.net 2. 문제 개요 모든 도로들이 일방통행으로 되어 있다. 도로들이 만나는 모든 교차로에는 ATM기가 설치되어 있다. 또, 일부 교차로에는 레스토랑이 있는데, ATM에 들릴 때마다 돈을 인출한다. 이때, 시작점에서 아무 레스토랑까지 최대한 많은 돈을 인출하여 레스토랑에 가려고 하는데, 이때 최대 얼마를 가지고 갈 수 있는지 구하는 프로그램을 작성. 3. 문제 힌트 문제를 보아하니.. ..

1. 문제 링크 www.acmicpc.net/problem/3977 3977번: 축구 전술 World Soccer Championship이 다가오고 있다! 천재적인 전술을 창조하는 플랜 아티스트 감독 도현이는 자신의 팀이 승리하도록 만반의 준비를 가하고 있다. 도현이의 전략은 경기장을 여러 개의 구역 www.acmicpc.net 2. 문제 개요 경기장을 여러 개의 구역으로 나누고, 어떤 선수가 A구역에서 B구역으로 이동하게 하는 움직임을 (A,B)로 표현한다. 다른 모든 구역에 도달할 수 있는 시작 구역을 찾은 뒤 지시한 움직임만을 따라가라고 했다. 그런데 이러한 시작 구역을 찾는 것이 어려웠다. 적절한 시작 구역을 찾는 프로그램을 작성하시오 3. 문제 힌트 어떠한 시작점을 찾아서 그래프를 전부 순회할 ..

1. 문제 링크 www.acmicpc.net/problem/2150 2150번: Strongly Connected Component 첫째 줄에 두 정수 V(1 ≤ V ≤ 10,000), E(1 ≤ E ≤ 100,000)가 주어진다. 이는 그래프가 V개의 정점과 E개의 간선으로 이루어져 있다는 의미이다. 다음 E개의 줄에는 간선에 대한 정보를 나타내는 두 정 www.acmicpc.net 2. 문제 개요 방향 그래프가 주어졌을 때, 그 그래프를 SCC들로 나누는 프로그램을 작성하시오. 3. 문제 힌트 코사라주 알고리즘(kosaraju's algorithm), 타잔 알고리즘(Tarjan's algorithm)을 사용하여 SCC를 선형시간에 구함. 4. 문제 풀이 결국 알고리즘을 알아야 풀 수 있는 문제이다. ..