728x90 C++18 [C++][백준] 10090 Counting Inversions 이번 문제는 병합정렬(Merge sort)를 이용해서 해결하는 문제입니다. 문제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 10 inversions in total. They are the following pairs: 4.. 2024. 7. 10. [C++][백준] 2512 예산 이번 문제는 이분 탐색을 활용하는 문제이다.문제국가의 역할 중 하나는 여러 지방의 예산요청을 심사하여 국가의 예산을 분배하는 것이다. 국가예산의 총액은 미리 정해져 있어서 모든 예산요청을 배정해 주기는 어려울 수도 있다. 그래서 정해진 총액 이하에서 가능한 한 최대의 총 예산을 다음과 같은 방법으로 배정한다.1. 모든 요청이 배정될 수 있는 경우에는 요청한 금액을 그대로 배정한다.2. 모든 요청이 배정될 수 없는 경우에는 특정한 정수 상한액을 계산하여 그 이상인 예산요청에는 모두 상한액을 배정한다. 상한액 이하의 예산요청에 대해서는 요청한 금액을 그대로 배정한다. 예를 들어, 전체 국가예산이 485이고 4개 지방의 예산요청이 각각 120, 110, 140, 150이라고 하자. 이 경우, 상한액을 127로.. 2024. 7. 7. [C++][백준] 11819 The Shortest does not Mean the Simplest 1629번 곱셈 문제와 동일하지만 수 범위가 더 큰 문제이다.문제자연수 A를 B번 곱한 수를 알고 싶다. 단 구하려는 수가 매우 커질 수 있으므로 이를 C로 나눈 나머지를 구하는 프로그램을 작성하시오. 입력첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다. 출력첫째 줄에 A를 B번 곱한 수를 C로 나눈 나머지를 출력한다. 자세한 설명은 여기 있으니 관심있다면 한번 보도록 하자.https://cromcode.tistory.com/15 코드를 살펴보자#includeusing namespace std;using ull = unsigned long long;__int128_t ipow(ull a, ull b, ull c){ .. 2024. 7. 4. [C++][백준] 1629 곱셈 이번 문제는 빠른 거듭제곱을 활용하면 쉽고 빠르게 풀 수 있다.빠른 거듭제곱이 뭘까?어떤 숫자 x를 n번 거듭제곱 한다고 하면 x를 n번 곱하는 것이 일반적인 계산법이다. 예를들어 2의 31제곱을 구해야 한다고 하자. 그렇다면 계산 과정은 아래와 같을 것이다.2x2x2x2x2x2x2x2x2x2x....x2x2x2x2x2x2x2x2x2x2x2x2x2x2(31번 곱했다고 치자.) 이 방법의 경우는 시간복잡도가 O(n)이다. 만약 n이 아주 큰 수라면 계산하는 시간이 오래 걸리게 될 것이다. 더 빨리 구하는 방법은 무엇일까? 생각을 약간 틀어서 지수인 31을 이진수로 생각해보자. 31 => 11111(2)이다. 211111(2)을 계산한다고 생각하면24 x 23 x 22 x 21 x 20 만 계산하면 된다. .. 2024. 7. 3. [C++][백준] 17466 N! mod P(1) 이번 문제는 간단한 팩토리얼 문제이다.문제양의 정수 N과, N보다 큰 소수 P가 주어질 때, N!을 P로 나눈 나머지를 구하여라. 입력첫째 줄에 N과 P가 공백으로 구분되어 주어진다. 출력N!을 P로 나눈 나머지를 구하여라. 제한1 ≤ N P는 소수 코드를 살펴보자#includeusing namespace std;int main(){ long long n,p,r=1; cin >> n >> p; while(n) { if (n == 0) break; r = r*n%p; n--; } cout 사실 N과 P의 범위가 108이하이기 때문에 int범위로 선언해도 되지만 최종 값을 저장할 r의 값은 오버플로우가 날 경우가 생길 .. 2024. 7. 3. [C++][백준] 4307 개미 이번 문제는 간단한 구현 문제이다.문제는 어려워 보이지만 약간 생각을 다르게 한다면 쉬운 문제가 된다.문제개미 여러 마리가 길이가 lcm인 막대 위에 있다. 각 개미의 이동 속도는 모두 일정하며, 1cm/s이다. 개미가 막대의 마지막까지 걸어간다면, 개미는 그 즉시 떨어지게 된다. 또, 두 개미가 만나게 된다면, 방향을 반대로 바꾸어 걸어가게 된다.가장 처음에 막대 상에서 개미의 위치를 알고 있다. 하지만, 개미가 어느 방향으로 움직이는 지는 알 수가 없다. 이때, 모든 개미가 땅으로 떨어질 때까지 가능한 시간 중 가장 빠른 시간과 느린 시간을 구하는 프로그램을 작성하시오. 입력첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스의 첫째 줄에는 막대의 길이와 개미의 수 n이 주어진다. 다음 n개.. 2024. 7. 1. 이전 1 2 3 다음 728x90 반응형
