Algorithms/PS (29) 썸네일형 리스트형 [PS] 백준 #19535. ㄷㄷㄷㅈ 문제 정보 난이도: 골드 III 문제 주소: https://www.acmicpc.net/problem/19535 이 문제를 푼 이유: 알고리즘 스터디 - 트리, dp 문제 어느 날, 트리를 물끄러미 보고 있던 동현이는 엄청난 사실을 하나 발견했다. 바로 정점이 네 개인 트리는 ‘ㄷ’과 ‘ㅈ’의 두 종류밖에 없다는 사실이다! 정점이 네 개 이상 있는 임의의 트리에 대해, 그 트리에서 정점 네 개로 이루어진 집합을 고르자. 전체 트리의 간선들 중 집합에 속한 두 정점을 잇는 간선만을 남겼을 때, 네 개의 정점이 하나의 트리 형태로 이어지게 된다면 ‘ㄷ’ 모양이거나 ‘ㅈ’ 모양일 것이다. 트리에서 ‘ㄷ’의 개수와 ‘ㅈ’의 개수를 각각 트리에서 ‘ㄷ’ 모양, ‘ㅈ’ 모양을 이루는 정점 네 개짜리 집합의 개수라고.. [PS] 백준 #3977. 축구 전술 문제 정보 난이도: 플래티넘 IV 문제 주소: https://www.acmicpc.net/problem/3977 이 문제를 푼 이유: 알고리즘 스터디 - SCC 문제 World Soccer Championship이 다가오고 있다! 천재적인 전술을 창조하는 플랜 아티스트 감독 도현이는 자신의 팀이 승리하도록 만반의 준비를 가하고 있다. 도현이의 전략은 경기장을 여러 개의 구역으로 나누고, 어떤 선수가 A구역에서 B구역으로 이동하게 하는 움직임을 (A, B)로 표현한다. 모든 도현이의 팀 선수들이 이 움직임만을 따라서 이동한다면 승리하리라고 도현이는 확신한다. 도현이는 선수들에게 자신의 전술을 말해주며, 다른 모든 구역에 도달할 수 있는 시작 구역을 찾은 뒤 지시한 움직임만을 따라가라고 했다. 그러나 도현이.. [PS] 백준 #11661. 해의 개수 문제 정보 난이도: 플래티넘 I 문제 주소: https://www.acmicpc.net/problem/11661 이 문제를 푼 이유: 알고리즘 스터디 - 유클리드 호제법 문제 방정식 Ax + By + C = 0의 해의 개수를 구하는 프로그램을 작성하시오. A, B, C, x, y는 모두 정수이고, x1 ≤ x ≤ x2, y1 ≤ y ≤ y2인 해의 개수를 구해야 한다. 나의 풀이 자세한 개념은 https://pongkijoa.tistory.com/91 이 글에 작성해두었다. $d = gcd(a,b)$라 하자. 먼저 유클리드 호제법을 이용하여 a와 b의 최대공약수 d를 구한다. 유클리드 호제법을 역산하여 d를 a와 b의 일차결합 형태로 나타낸다. 이 때의 특수해를 $x_1, y_1$ 이라 하자. $ax +.. [PS] 백준 #24520. Meet In The Middle 문제 정보 난이도: 플래티넘 IV 문제 주소: https://www.acmicpc.net/problem/24520 이 문제를 푼 이유: 알고리즘 스터디 - LCA 문제 신촌 왕국에는 $1$번부터 $N$번까지 $N$개의 마을이 있고 $N-1$개의 도로가 서로 다른 두 마을을 연결하고 있다. 모든 마을은 도로를 통해 다른 마을로 갈 수 있고, 이때 마을 내에서의 이동 거리는 무시할 수 있다. 현재 신촌 왕국은 "대칭병"의 대유행으로 혼란을 겪고 있다. 대칭병은 어떤 것이든 대칭을 이루지 않으면 심신이 불편해져 일상생활을 할 수 없게 만드는 병이다. 대칭병의 여파는 엄청났는데 심지어 사람과 사람 간의 만남조차 어렵게 됐다. 신촌 왕국의 두 사람이 만나는 상황을 생각해보자. 약속 장소가 둘 중 한 사람의 마을에.. [PS] 백준 #1761. 정점들의 거리 문제 정보 난이도: 플래티넘 V 문제 주소: https://www.acmicpc.net/problem/1761 이 문제를 푼 이유: 알고리즘 스터디 - LCA 문제 N(2 ≤ N ≤ 40,000)개의 정점으로 이루어진 트리가 주어지고 M(1 ≤ M ≤ 10,000)개의 두 노드 쌍을 입력받을 때 두 노드 사이의 거리를 출력하라. 나의 풀이 두 노드 사이의 거리는 두 노드를 잇는 최단경로의 거리로 정의되는데, 이 최단경로에는 항상 LCA가 포함된다. 따라서 이 문제는 두 노드의 LCA를 찾아서 최단 경로의 거리를 구하는 문제이다. (LCA에 관한 내용은 https://pongkijoa.tistory.com/78?category=543159 에 자세히 서술해두었다.) 이 문제의 핵심은 DFS를 돌 때 각 정.. [PS] 백준 #2517. 달리기 문제 정보 난이도: 플래티넘 IV 문제 주소: https://www.acmicpc.net/problem/2517 이 문제를 푼 이유: 알고리즘 스터디 - 세그먼트 트리 문제 KOI 장거리 달리기 대회가 진행되어 모든 선수가 반환점을 넘었다. 각 선수의 입장에서 자기보다 앞에 달리고 있는 선수들 중 평소 실력이 자기보다 좋은 선수를 남은 거리 동안 앞지르는 것은 불가능하다. 반대로, 평소 실력이 자기보다 좋지 않은 선수가 앞에 달리고 있으면 남은 거리 동안 앞지르는 것이 가능하다. 이러한 가정 하에서 각 선수는 자신이 앞으로 얻을 수 있는 최선의 등수를 알 수 있다. 각 선수의 평소 실력은 정수로 주어지는데 더 큰 값이 더 좋은 실력을 의미한다. 현재 달리고 있는 선수를 앞에서 부터 표시했을 때 평소 실력.. [PS] 백준 #10090. Counting Inversions 문제 정보 난이도: 플래티넘 V 문제 주소: https://www.acmicpc.net/problem/10090 이 문제를 푼 이유: 알고리즘 스터디 - 세그먼트 트리 문제 A permutation of integers from 1 to n is a sequence a1, a2, ..., an, such that each integer from 1 to n is appeared in the sequence exactly once. Two integers in а permutation form an inversion, when the bigger one is before the smaller one. As an example, in the permutation 4 2 7 1 5 6 3, there are .. [PS] 백준 #11509. 풍선 맞추기 문제 정보 난이도: 골드 V 문제 주소: https://www.acmicpc.net/problem/11509 이 문제를 푼 이유: 알고리즘 스터디 - 브루트포스와 그리디 문제 큰 방에 N개의 풍선이 떠있다. 풍선들은 왼쪽부터 오른쪽까지 일렬로 있다. 진솔이는 화살 가지고 노는 것과 사냥 연습하는 것을 좋아한다. 진솔이는 화살을 왼쪽에서 오른쪽으로 쏜다. 높이는 임의로 선택한다. 화살은 선택된 높이 H에서 풍선을 마주칠 때까지 왼쪽에서 오른쪽으로 이동한다. 화살이 풍선을 마주치는 순간, 풍선은 터지고 사라진다. 화살은 계속해서 가던길을 가는데 높이는 1 줄어든다. 그러므로 만약 화살이 높이 H에서 이동 중이었다면 풍선을 터트린 후에는 높이가 H-1이 된다. 우리의 목표는 모든 풍선을 터트리되 가능한한 적은.. 이전 1 2 3 4 다음
