기록(記錄)

본문 바로가기

알고리즘

백준 문제 풀이 [C++] 4442번 빌보의 생일 https://www.acmicpc.net/problem/4442 26/02/22 인버전 카운팅을 하는 문제다. 문제 접근 방식: 첫번째로 주어진 사람들의 목록에 번호를 매기자.문제에서 주어진 예시라면, Frodo에 $1$번, Sam에 $2$번, Bilbo에 $3$번을 매기는 것이다.두번째로 주어진 사람들의 목록을 매긴 번호로 치환한다. 문제의 예시라면 Sam Frodo Bilbo순으로 주어져있으므로, $2\ 1\ 3$으로 바뀐다.이후 바뀐 순열에 대해 인버전 카운팅 문제를 해결해주면 된다.아래는 내가 위의 접근 방식과 같이 작성한 C++ 코드이다. 더보기를 누르면 확인할 수 있다.더보기// 4442번 빌보의 생일// 자료 구조, 세그먼트 트리, 집합과 맵/*접근 방법:인버전 카운팅을 하는 문제다.첫..
백준 문제 풀이 [C++] 9463번 순열 그래프 https://www.acmicpc.net/problem/9463 26/02/21 인버전 카운팅을 하는 문제다. 문제 접근 방식: 첫번째로 주어진 순열이 $1\ 2\ 3\ \dots N$에 매핑된다고 간주하자.즉, 예제 입력 1의 첫번째 테스트 케이스를 예시로 들자면 $2\ 5\ 4\ 1\ 3$을 $1\ 2\ 3\ 4\ 5$로 간주하자는 뜻이다.즉, $2$를 $1$로, $5$를 $2$로, ... 그렇게 모든 수를 각각의 수로 간주하자.이후 두번째로 주어진 순열을 매핑된 수로 바꾸면, 주어진 순열에 대한 인버전 카운팅을 세는 문제로 바꿀 수 있다.아래는 내가 위의 접근 방식과 같이 작성한 C++ 코드이다. 더보기를 누르면 확인할 수 있다.더보기// 9463번 순열 그래프// 자료 구조, 세그먼트 트리 ..
백준 문제 풀이 [C++] 28866번 Морти покупает продукты https://www.acmicpc.net/problem/28866 26/02/18 자주 나왔던 단골 유형의 FFT문제이다. 문제 접근 방식: $N$개의 수들 중 중복을 포함하여 $K$개를 선택했을 때의 가능한 경우의 수를 세는 문제라고 요약할 수 있다.이전에 너무 많이 했던 FFT문제 유형이다. 특히, 보석 가게 문제와 거의 유사하다고 볼 수 있다.실제로 필요한 다항식의 차수는 $50\ 000$까지 밖에 안되므로, 거듭제곱을 하며 중간 중간 크기를 resize해줘도 상관 없다.또한, 여기서 $786\ 433$이라는 특이한 수가 쓰이는데, 이 수는 $3\times 2^{18}+1$로 NTT-friendly한 소수이다. 원시근은 $10$을 사용하면 된다.이 점만 유의하여 구현하고, 나온 결과를 누적합을..

수학

회고록

감상록

티스토리툴바