devmoon

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자리의 수 역시 매우 큰 수 이므..