[2024 동계 모각코] 4주차 계획
4주차 계획
개요
4주차(1. 22~ 1. 28)의 계획입니다.
- 13장 수치 해석
- 문제: ROOTS
- 문제: LOAN
- 문제: RATIO
- 문제: FOSSIL
- 14장 정수론
- 문제: PASS486
- 문제: POTION
13장 수치 해석
문제: ROOTS
$polynomial$과 이 $polynomial$의 해들이 범위 $[-20, 20]$내에 실수로 존재할 때, 해를 찾으시오.
도함수를 이용해 극점을 찾고, 극점 사이에 있는 근을 이분법으로 탐색하는 재귀적 수치해석 방법을 이용하는 문제입니다.
문제: LOAN
$x_n = x_{n-1} \cdot \left( 1 + \frac{p}{1200} \right) - C$ 이런 점화식의 답 C를 이진탐색으로 구하는 문제입니다.
문제: RATIO
승률 1%를 늘리기 위해 이겨야하는 게임 수(연승)를 구하는 문제입니다.
구현은 엄청 쉬웠으나, 게임 수가 int 범위를 넘는 숫자가 될 수도 있어서 long long을 사용해야 했고, 이진 탐색에서 문제가 발생해서(lo = 1이 아니라 lo = 0) 애먹었던 문제입니다.
이진 탐색 시 범위를 답 범위보다 조금 크게 잡아야 되는 것을 알았습니다.
문제: FOSSIL
계산 기하학 문제에서 볼록 다각형의 교집합의 y좌표 폭의 최댓값을 구하는 문제입니다.
14장 정수론
문제: PASS486
$[lo, hi]$까지의 범위에 속하는 약수의 개수가 $n$개인 정수의 개수를 구하는 문제입니다.
정수가 주어지면, 약수의 개수를 파악하는 알고리즘은 $O(\sqrt{n})$으로 쉽게 만들 수 있습니다만..
문제는 [lo, hi]의 범위에 대해 수행하여야 하고, 간격은 최대 백만 정수이기 때문에 다른 알고리즘을 선택해야했던 문제였습니다.
문제: POTION
재료 $n$개가 주어지면, 물약 한 병을 만들기 위해 필요한 재료의 양(단위: 숟가락)과 이미 넣은 재료의 양이 주어집니다. 배율을 맞추기 위한 넣어야 할 최소한의 재료의 양을 각각 구하시오, 단, 최소한 물약 한 병 이상을 만들 수 있어야 합니다.
최대공약수를 이용하여 푸는 문제로, 최대공약수를 쉽게 구할 수 있는 유클리드 알고리즘을 이용해 푸는 문제입니다.
수론적 배열 스케일링 문제(Number Theory + Scailing with Ratios)입니다.
추가적인 내용
정수론에 관한 문제는 더 없지만, 이론적으로 알고 있으면 좋을 만한 내용들이 있습니다.
모듈라 연산시 $(a+b) \bmod M = ((a\bmod M) + (b \bmod M)) \bmod M$처럼 유용하게 사용 가능합니다. 덧셈 이외에도 뺄셈, 곱셈에 관하여 성립하나, 나눗셈에 관하여는 성립하지 않습니다.
나눗셈에 관해서는 나중에 필요하면 공부할 예정입니다.
추가로, 모듈라 연산을 통해 이항 계수를 빠르게 계산할 수 있는데, 루카스의 정리라는 것으로 이것도 나중에 공부할 예정입니다.
중국인 나머지 정리, 확장 유클리드 알고리즘 등도 책에 나오는 내용이지만 스킵하도록 하겠습니다.