Algorithms (42) 썸네일형 리스트형 [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를 돌 때 각 정.. [알고개념] 4. 트리 1. 트리의 기초 용어 Internal node: nodes with at least one child External node (Leaf): nodes without children Ancestor of a node: parent, grandparent, grand grandparent, and so on (including itself) Descendant of a node: child, grandchild, grand grandchild, and so on (including itself) Sibling : nodes that have the same parent Subtree : a tree that consists of a node of the original tree as the root an.. [알고개념] 3. 유클리드 호제법 1. 유클리드 호제법 두 수 m, n의 최대공약수 GCD(m, n) 를 구할 때 사용하는 알고리즘으로, 실제 계산기에도 이 알고리즘을 이용하여 구현되어 있다고 한다. 유클리드 호제법은 다음과 같이 작성할 수 있다. a를 b로 나눈 몫과 나머지를 각각 매개변수로 갖는 GCD 함수를 다시 호출한다. a를 b로 나눈 나머지가 0이면 b를 답으로 리턴한다. int GCD(a, b) { if (a % b == 0) return b; return GCD(b, a % b); } 이 때 a와 b의 대소관계는 따질 필요가 없다. a가 b보다 항상 커야 할 것 같지만 b가 a보다 클 경우 자동으로 GCD(a, b)를 호출하기 때문이다. 2. 유클리드 호제법의 역산 두 수 x, y에 대하여 GCD(x, y)를 구하는 유클리.. [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 5 6 다음
