devmoon

1. 문제 출처 https://www.acmicpc.net/problem/13309 13309번: 트리 표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 트리의 정점의 개수와 질의의 개수를 나타내는 두 정수 N과 Q (1 ≤ N, Q ≤ 200,000)가 주어진다. 다음 N-1개의 줄의 i번째 줄에는 정점 i+1의 부 www.acmicpc.net 2. 문제 접근 특정 구간내에 그래프가 연결되어 있는지의 정보를 O(log N)의 시간만에 알아내기 위해 세그먼트 트리 자료구조를 사용해야 했다. 하지만, 트리 구조이기 때문에 트리구조를 체인으로 분할 하는 heavy-light-decomposition 을 적용하여 문제를 해결해야 한다. 먼저 트리의 루트는 항상 1이라고 고정된 상태이기 때문에, 1을 루트로..

https://www.acmicpc.net/problem/16566 16566번: 카드 게임 첫째 줄에 세 개의 자연수 N, M, K가 주어진다. (1 ≤ M ≤ N ≤ 4,000,000, 1 ≤ K ≤ min(M, 10,000)) 다음 줄에 카드의 번호를 나타내는 M개의 자연수가 주어진다. 각각의 수들은 1 이상이고 N 이하이며 서로 www.acmicpc.net 1이상 4,000,000 이하의 수 $N$ 개를 입력받고 $K$개의 임의의 수 $k$를 입력 받았을 때, $N$ 개의 수에서 $k$ 보다 큰 수들 중 가장 작은 수를 출력하면 되는 문제이다. 따라서 입력받는 대로 모든 수를 정렬하고, upper_bound 로 만족하는 결과를 얻을 수 있는 set 의 자료 구조의 사용을 바로 떠올렸다. set s..

1. 문제 출처 https://www.acmicpc.net/problem/2517 2517번: 달리기 첫째 줄에는 선수의 수를 의미하는 정수 N이 주어진다. N은 3 이상 500,000 이하이다. 이후 N개의 줄에는 정수가 한 줄에 하나씩 주어진다. 이 값들은 각 선수들의 평소 실력을 앞에서 달리고 있는 www.acmicpc.net 2. 문제 접근 https://www.acmicpc.net/problem/10090 10090번: Counting Inversions 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 exac..

1. 문제 출처 https://www.acmicpc.net/problem/10999 10999번: 구간 합 구하기 2 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 합을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄 www.acmicpc.net 2. 문제 접근 기존에 알고 있었던 세그먼트 트리이지만, 업데이트해야 하는 것이 하나의 값이 아니라 구간에 대해서 업데이트를 진행해야 했다. 해당 구간에 대해서 일일이 업데이를 진행하는 것보다 lazy propataion방법을 사용하면 더 효율적으로 풀이가 가능했다. lazy propagation에 대한 정보가 없었..

1. 문제 출처 https://www.acmicpc.net/problem/8111 8111번: 0과 1 각각의 테스트 케이스마다 N의 배수이면서, 구사과가 좋아하는 수를 아무거나 출력한다. 만약, 그러한 수가 없다면 BRAK을 출력한다. www.acmicpc.net 2. 문제 접근 $N$이 주어졌을 때, 100 자릿수 이하인 $N$의 배수를 구하는 데에는 시간도 매우 많이 걸리고, 해당 수를 담을 자료형도 long long으로 부족하기 때문에 string연산으로 해결을 해줘야 한다. 따라서 반대로, 1과 0으로 이루어진 수들을 작은 자리 수부터 생성을 하고, 그 수가 $N$의 배수인지 ($N$)으로 나눈 나머지가 0인지) 확인만 해주면 되었다. 1과 0으로 이루어진 100자리의 수 역시 매우 큰 수 이므..

1. 문제 출처 https://www.acmicpc.net/problem/11402 11402번: 이항 계수 4 첫째 줄에 \(N\), \(K\)와 \(M\)이 주어진다. (1 ≤ \(N\) ≤ 1018, 0 ≤ \(K\) ≤ \(N\), 2 ≤ \(M\) ≤ 2,000, M은 소수) www.acmicpc.net 2. 문제 접근 $10^{18}$ 이하의 자연수 $n$과 $n$ 이하의 음이 아닌 정수 $k$가 주어졌을 때, $_nC_k$의 값을 구하는 문제이다. $_nC_k$ 의 값이 매우 커질 수 있으므로, 2000 이하의 임의의 소수 $m$이 주어지고 $_nC_k$의 값을 $m$으로 나눈 나머지를 출력하면 된다. 이 문제를 해결하기 위해서는 뤼카의 정리에 대해서 알아야 한다. 뤼카의 정리는 $_nC_k..

1. 문제 출처 https://www.acmicpc.net/problem/17071 17071번: 숨바꼭질 5 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 500,000)에 있고, 동생은 점 K(0 ≤ K ≤ 500,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 www.acmicpc.net 2. 문제 접근 도착점이 고정되어 있는 일반적인 BFS문제와는 달리, 도착점도 동시에 이동하는 BFS문제 수빈이가 이동할 수 있는 경우는 다음 3가지밖에 없다. 현재 위치 x에서 1칸 좌측(x - 1)으로 이동 현재 위치 x에서 1칸 우측(x + 1)으로 이동 현재 위치 x에서 순간이동하여 2배 떨어진 위치(x * 2)로 이동 특정 위치 x에 ..