레야몬

1. 문제 한 양방향 그래프에서 어떤 예술가 한 쌍이 s지점에서 출발해서 g와 h 교차로 사이 도로를 지나 최단경로로 이동해 어떤 목적지로 도달한다고 할 때 어디로 가고 있을까? .- 1 - 테스트 케이스의 개수 \(T(1 \leq T \leq 100)\) - 1 - \(n, m, t(2 \leq n \leq 2,000, 1 \leq m \leq 50,000, 1\ \leq t \leq 100)\) 교차로, 도로 목적지 후보의 개수 - 2 - \(s, g, h(1 \leq s, g, h \leq n)\) s: 예술가의 출발지 \((g \neq h)\) - m개의 줄 - \(b, d(1 \leq a < b \leq n, 1 \leq d \leq 1,000)\) a와 b사이에 길이 d의 양방향 도로가 존재 ..

1. 문제 두 사람 A, B가 서로 볼 수 있으려면, 두 사람 사이에 A 또는 B보다 키가 큰 사람이 없어야 한다. 줄에 서 있는 사람의 키가 주어질 때, 서로 볼 수 있는 쌍의 수를 구하는 프로그램을 작성하시오 - 1 - 기다리는 사람의 수 \(N(1 \leq N \leq 500,000)\) - N개의 줄 - 키 \(height(1 \leq height \leq 2^{31})\) 서로 볼 수 있는 사람의 수 2. 재정의 수열이 주어질 때 두 수 사이에 있는 값이 더 작거나 같은 두 수의 순서쌍의 개수를 구하라 3. 해결 방법 순차적으로 같거나 내려갈 경우 스택에 추가 올라갈 경우 스택에 있는 키를 꺼내는데 같은 키의 개수를 구하자 같은 키의 개수를 더하고 스택에 더 있으면 한 번 더 더하자. 같은 키C..

1. 문제 백준이가 동생에게 숫자를 불러줄 때, 그때까지 불러준 수들 중 중간값을 동생이 말해야 한다. - 1 - 백준이가 외치는 정수의 개수 \(N(1 \leq N \leq 100,000)\) - N줄 - 정수 \(num(-10,000 \leq num \leq 10,000)\) 중간값 2. 재정의 수열들의 중간값 출력 3. 해결 방법 오름차순, 내림차순 우선순위 큐를 각각 하나씩 만든다. 오름차순 우선순위 큐의 top이 내림차순 우선순위 큐의 top보다 항상 작게 만들고 오름차순, 내림차순의 원소 수를 같게 한다면 항상 오름차순 우선순위 큐의 top이 중간값이다. 4. 실수한 점, 개선할 점 거의 다 생각했는데 끝을 생각해내지 못한 게 너무 아쉽다. 조금 체계적으로 사고하는 연습을 해야 할 필요가 있을..

1. 문제 N * N 크기의 배열 A[i][j] = i * j이다. 이를 배열 B에 넣으면 크기는 N * N이 된다. B를 오름차순 정렬했을 때 B[k]를 구해보자. A, B의 인덱스는 1부터 시작 - 1 - 배열의 크기 \(N(1 \leq N \leq 10^{5}\) - 2 - \(k(1 \leq k \leq min(10^{9}, N^{2})\) B[k] 2. 재정의 A[i][j] = i *j일때 이들의 오름차순 순서를 구하시오. 3. 해결 방법 이 프로그램의 목표는 k번째 숫자인 mid를 찾는 것이다. cnt(mid)를 통해 mid 아래에 몇 개의 숫자가 있는지 확인하며 cnt(mid) = k이면 hi = mi..

1. 문제 크기가 N*N인 행렬 A가 주어질 때 A의 B제곱을 구하는 프로그램을 작성하시오. 각 원소를 1,000으로 나눈 나머지를 출력한다. - 1 - \(N, B(2 \leq N \leq 5, 1 \leq B \leq 100,000,000,000)\) - N개의 줄 - 행렬의 각 원소가 주어진다. 행렬의 각 원소는 1,000보다 작거나 같은 자연수, 또는 0이다. 행렬 A를 B 제곱한 결과를 출력한다. 2. 재정의 X 3. 해결 방법 X 4. 실수한 점, 개선할 점 문제 조건, 특히 숫자 범위를 확인하고 long long 범위를 넘어갈 수 있는지 재차 확인하기! #include #define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);..

1. 문제 M개의 자연수 N과 정수 K가 주어졌을 때 이항 계수 \(_{n}C_{k}\)를 \(1,000,000,007\)로 나눈 나머지를 구하는 프로그램을 작성하시오 - 1 - \(M(1 \leq M \leq 100,000)\) - M개의 줄 - \(N, K(1 \leq N \leq 4,000,000, 0 \leq K \leq N)\) M개의 줄에 \(_{n}C_{k}\)를 \(1,000,000,007\)로 나눈 나머지를 출력한다. 2. 재정의 X 3. 해결 방법 factorial값을 모두 저정한 다음 페르마의 소정리를 이용해 간단하게 풀면 된다. 4. 실수한 점, 개선할 점 항상 나오지만 자료형 범위 조심하자 분할 정복 사용할 때 재귀 함수를 사용하지 않고 반복문을 이용해하는 방법도 있었다. 이렇게 ..

1. 문제 자연수 N과 정수 K가 주어졌을 때 이항 계수 nCk를 M으로 나눈 나머지를 구하는 프로그램을 작성하시오. - 1 - \(N, K, M(1 \leq N \leq 10^{18}, 0 \leq K \leq N, 2 \leq M \leq 2,000, M is prime)\) \(_{n}C_{k}\)를 \(M\)으로 나눈 나머지를 출력한다. 2. 재정의 X 3. 해결 방법 뤼카의 정리를 이용하면 간단하게 풀 수 있다. 4. 실수한 점, 개선할 점 binomial을 사용할 때 dp를 사용하지 않고 Euler's little theorem을 사용하면 0ms로 풀 수 있다. #include #include using namespace std; typedef long long ll; const int MAX..

1. 문제 \(_{n}C_{k} \% 1,000,000,007\)을 구하시오 - 1 - \(N, K(1 \leq N \leq 4,000,000, 0 \leq k \leq N)\) \(_{n}C_{k} \% 1,000,000,007\) 2. 재정의 X 3. 해결 방법 \(P = N! \% M\)을 구하기 \(S = (N-K)! \times k! \% M\) 구하기 \(S^{1,000,000,005} \% M\) 구하기 \(P \times S \% M\) 구하기 4. 실수한 점, 개선할 점 nCr을 팩토리얼로 계산할 때 반복문 하나로 줄일 수 있다. #include using namespace std; typedef long long ll; // 소수 const int mod = 1000000007; // ..