boj, 백준) 4013. ATM (C/C++)
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. 문제 힌트 문제를 보아하니.. ..
boj, 백준) 3977. 축구전술(C/C++)
1. 문제 링크 www.acmicpc.net/problem/3977 3977번: 축구 전술 World Soccer Championship이 다가오고 있다! 천재적인 전술을 창조하는 플랜 아티스트 감독 도현이는 자신의 팀이 승리하도록 만반의 준비를 가하고 있다. 도현이의 전략은 경기장을 여러 개의 구역 www.acmicpc.net 2. 문제 개요 경기장을 여러 개의 구역으로 나누고, 어떤 선수가 A구역에서 B구역으로 이동하게 하는 움직임을 (A,B)로 표현한다. 다른 모든 구역에 도달할 수 있는 시작 구역을 찾은 뒤 지시한 움직임만을 따라가라고 했다. 그런데 이러한 시작 구역을 찾는 것이 어려웠다. 적절한 시작 구역을 찾는 프로그램을 작성하시오 3. 문제 힌트 어떠한 시작점을 찾아서 그래프를 전부 순회할 ..
boj, 백준) 2150. SCC(Strongly Connected Component)
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. 문제 풀이 결국 알고리즘을 알아야 풀 수 있는 문제이다. ..
boj, 백준) 17404. RGB거리 2 (C/C++)
1. 문제 링크 www.acmicpc.net/problem/17404 17404번: RGB거리 2 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 2. 문제 개요 RGB거리에는 집이 N개 있다. 거리는 선분으로 나타낼 수 있고, 1번 집부터 N번 집이 순서대로 있다. 집은 빨강, 초록, 파랑 중 하나의 색으로 칠해야 한다. 각각의 집을 빨강, 초록, 파랑으로 칠하는 비용이 주어졌을 때, 아래 규직을 만족하면서 모든 집을 칠하는 비용의 최솟값을 구하는 프로그램을 작성. 1번 집의 색은 2번, N번 집의 색과 같지..
boj, 백준) 1086. 박성원 ( C / C++)
1. 문제 링크 www.acmicpc.net/problem/1086 1086번: 박성원 첫째 줄에 정답을 기약분수 형태로 출력한다. p/q꼴로 출력하며, p는 분자, q는 분모이다. 정답이 0인 경우는 0/1로, 1인 경우는 1/1로 출력한다. www.acmicpc.net 2. 문제 개요 서로 다른 정수로 이루어진 집합이 있다. 이 집합의 순열을 합치면 큰 정수 하나를 만들 수 있다. 합친 수가 정수 K로 나누어 떨어지는 순열을 구하는 프로그램을 작성하시오. 박성원이 우연히 정답을 맞출 확률을 분수로 출력하는 프로그램을 작성하시오. 3. 문제 힌트 (1) 숫자의 길이가 최대 50 - 입력을 string으로 받아서 나머지를 계산해야 함. 손으로 직접 나머지를 구하는 방법 그대로 적용하자. -> O(L), ..
boj, 백준) 3584. 가장 가까운 공통 조상 (C/C++)
1. 문제 링크 www.acmicpc.net/problem/3584 3584번: 가장 가까운 공통 조상 루트가 있는 트리(rooted tree)가 주어지고, 그 트리 상의 두 정점이 주어질 때 그들의 가장 가까운 공통 조상(Nearest Common Anscestor)은 다음과 같이 정의됩니다. 두 노드의 가장 가까운 공통 조상은, 두 www.acmicpc.net 2. 문제 개요 루트가 있는 트리가 주어지고, 트리의 간선들이 주어진다(부모 자식 관계). 그리고 마지막으로 LCA를 찾을 두 노드가 주어진다. 주어지는 두 노드의 LCA를 출력하는 프로그램을 작성하시오. 3. 문제 힌트 첫 번째로 루트를 찾자. 부모 -> 자식 방향으로 간선이 존재한다고 했을 때, 루트는 어떻게 찾을 수 있을까? 두 번째로 L..