문제 www.acmicpc.net/problem/18250 18250번: 철도 여행 한국에는 N개의 도시 C1, C2, ..., CN가 있고, 두 개의 도시를 양방향으로 잇는 M개의 철도 노선이 있다. 철도를 좋아하는 가희는 철도 여행을 하려고 한다. 철도 여행이란 시작 도시에서 도착 도시까 www.acmicpc.net 풀이 solved.ac 난이도: Platium 4 오일러 서킷(Eulerian curcit)과 오일러 경로(Eulerian trail)를 알아야 해결 가능한 문제. 분류를 알고 풀어서 풀만 했지만 분류를 모르면 정말 풀기 힘들었을 듯한 문제였다. 일단 오일러 서킷과 경로를 집고 넘어가자. 오일러 서킷(Eulerian curcit) 오일러 서킷은 모든 그래프의 간선을 한 번씩만 순회하여 시..

문제 www.acmicpc.net/problem/3665 3665번: 최종 순위 올해 ACM-ICPC 대전 인터넷 예선에는 총 n개의 팀이 참가했다. 팀은 1번부터 n번까지 번호가 매겨져 있다. 놀랍게도 올해 참가하는 팀은 작년에 참가했던 팀과 동일하다. 올해는 인터넷 예선 본부에 www.acmicpc.net 풀이 solved.ac 난이도: Gold 1 [백준] 알고스팟어(2848)과 비슷한 위상 정렬 문제였다. 처음에는 저번 대회의 순위를 저장하여 등수가 바뀐 쌍에서 저번 대회에 더 순위가 높았던 팀이 이번에는 더 낮은 팀으로 바뀌게 설정하였다.(간선을 이번 대회에서 높은 팀 -> 낮은 팀으로) 이렇게 바뀐 쌍에서만 방향 그래프의 연결을 진행하였더니 아래와 같은 결과가 나왔다. 예제의 입력 저번 대회 ..

문제 https://www.acmicpc.net/problem/2637 2637번: 장난감조립 첫째 줄에는 자연수 N(3 ≤ N ≤ 100)이 주어지는데, 1부터 N-1까지는 기본 부품이나 중간 부품의 번호를 나타내고, N은 완제품의 번호를 나타낸다. 그리고 그 다음 줄에는 자연수 M(3 ≤ M ≤ 100)이 주 www.acmicpc.net 풀이 solved.ac 난이도: Gold 2 위상 정렬(Topological sort)로 해결할 수 있는 문제이다. 다른 위상정렬 문제들과는 조금 다르게 모든 케이스가 DAG가 만족하게 주어지기 때문에 부품수를 계산하는데 집중하면 된다. 이번 문제를 해결하기 위해 큐를 이용한 위상 정렬을 구현하였다. 큐를 이용한 위상 정렬에서는 노드로의 진입 차수(indegree)를..

문제 www.acmicpc.net/problem/2848 2848번: 알고스팟어 첫째 줄에 알고스팟어의 알파벳 순서를 출력한다. 만약, 올바른 순서가 없다면 "!"를, 가능한 순서가 한 개 이상이라면 "?"를 출력한다. www.acmicpc.net 풀이 solved.ac 난이도: Platium 5 알고스팟의 고대어 사전(DICTIONARY) 문제와 같은 문제인 듯했지만 가능한 순서가 한 개 이상인지 판별해야 하는 문제였다. 위의 고대어 문제와 같이 DFS 위상 정렬로 해결하려다 계속 틀려서 큐를 이용한 위상 정렬로 해결하였다. 큐를 이용하는 위상 정렬 구현에 대해서는 HeeJeong Kwon님의 게시글을 참고하자. [알고리즘] 위상 정렬(Topological Sort)이란 - HeeJeong Kwon 큐..

문제 https://www.acmicpc.net/problem/9466 9466번: 텀 프로젝트 이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을 www.acmicpc.net 풀이 solved.ac 난이도: Gold 4 조금 특이한 DFS문제였다. 해당 문제에서 팀이 결성되기 위해서는 서로 선택한 학생들끼리의 사이클이 만들어져야 한다. 이 사이클은 자기 자신을 선택하는 것도 인정한다. 예를 들어 아래와 같은 입력에서 선택 관계를 그려보자. 학생 번호: 1, 2, 3, 4, 5 선택 번호 3, 4, 4, 5, 3 이때 사이클을 구성하는 것은 3->4->5(->3)이다. ..

문제 https://www.acmicpc.net/problem/13306 13306번: 트리 표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 트리의 정점의 개수와 질의의 개수를 나타내는 두 정수 N과 Q (1 ≤ N, Q ≤ 200,000)가 주어진다. 다음 N-1개의 줄의 i번째 줄에는 정점 i+1의 부 www.acmicpc.net 풀이 solved.ac 난이도: Platium 5 해당 문제에서 오프라인 알고리즘으로 해결해도 된다는 것을 알아차리는 게 중요했다. 온라인 알고리즘은 대부분의 문제들에서 원하는 출력 방식으로, 입력으로 답을 할 쿼리(질의)가 주어지면 바로 다음 줄에 답을 출력해주어야 한다. 온라인 알고리즘에서는 모든 입력 데이터를 가지지 않은 상태에서의 실시간 입출력이 중요하다. 오프..

문제 www.acmicpc.net/problem/17619 17619번: 개구리 점프 첫 번째 줄에 통나무 개수 N과 질문의 개수 Q가 주어진다. 다음 N개의 줄에 각 통나무에 x1, x2, y의 세 정수 좌표가 주어진다. 주어진 통나무는 두 점 (x1, y)와 (x2, y)를 잇는 형태이다. (x1 < x2) 모든 www.acmicpc.net 풀이 solved.ac 난이도: Gold 3 정렬과 분리 집합(Disjoint set)으로 해결하는 문제이다. 이번 문제의 분리 집합의 구현에 사용하는 Union-Find(유니온-파인드) 자료구조에 대해서는 아래 게시글에 정리해두었다. 유니온-파인드(Union-Find), 분리 집합 이번 문제에서는 점프로 이동 가능한 통나무들을 한 집합으로 묶어 서로 이동 가능한..

문제 https://www.acmicpc.net/problem/4195 4195번: 친구 네트워크 첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스의 첫째 줄에는 친구 관계의 수 F가 주어지며, 이 값은 100,000을 넘지 않는다. 다음 F개의 줄에는 친구 관계가 생긴 순서대로 주어진 www.acmicpc.net 풀이 solved.ac 난이도: Gold 2 Union-Find(유니온 파인드)에 map자료구조를 적용하면 간단히 해결할 수 있는 분리 집합(DisJoint Set) 문제였다. 분리 집합을 구현하는 데 사용하는 기본적인 Union-Find(유니온 파인드) 자료구조에 대해서는 아래의 게시글을 참고하자. 유니온-파인드(Union-Find), 분리 집합 이번 문제에서는 노드의 번호가 아..

문제 https://www.acmicpc.net/problem/2934 2934번: LRH 식물 상근이는 유전자 조작을 통해 줄기 두 개로 이루어진 식물을 만들었다. 이 식물은 줄기의 x좌표 L, R과 높이 H로 나타낼 수 있다. 아래 그림은 L=2, R=5, H=4인 식물이다. 상근이는 매일 매일 화단에 www.acmicpc.net 풀이 solved.ac 난이도: Platium 4 느리게 갱신되는 세그먼트 트리로 풀 수 있는 문제이지만 원소를 다르게 표현하는 펜윅 트리로도 해결할 수 있다. 문제에서 식물의 높이는 항상 이전의 식물들보다 크다. 따라서 이전의 식물들의 구평 선분과 현재 식물의 수직 선분과의 교차점이 꽃이 피는 개수이다. 수평 선분을 구간이라고 생각해보자. 트리에서 해당 구간의 값들을 모두..

문제 https://www.acmicpc.net/problem/1395 1395번: 스위치 첫 줄에는 스위치의 개수 N(2 ≤ N ≤ 100,000)과 처리할 일의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 M개의 줄에 대해 각 줄에 처리할 일에 대한 정보가 담겨진 세 개의 정수 O, Si, Ti가 입력된다. O www.acmicpc.net 풀이 solved.ac 난이도: Platium 3 세그먼트 트리에서 특정 구간의 값들이 자주 변경되어야 할 때 사용되는 Segment Tree Lazy Propagation(느리게 갱신되는 세그먼트 트리) 문제이다. Segment Tree Lazy Propagation에 대해서는 깔끔히 설명해주신 백준님의 게시글을 보고 오자. 세그먼트 트리 나중에 업데..