실수 구간에서 이분 탐색 방법 제대로 배우기

1. 문제 21627번: Ice Cream (acmicpc.net) 21627번: Ice Cream The first line contains three integers $n$, $v$, $u$ --- the number of ice cream cones, the melting rate and the rate of eating ice cream ($1\le n\le 3\cdot10^5$, $1\le v,u \le 10^9$). The second lines contains $n$ integers $a_i$ ($1\le a_i \le 10^9$) --- www.acmicpc.net 2. 풀이 n개의 아이스크림이 초당 v만큼 동시에 녹으며, 나는 초당 u만큼 아이스크림을 1개씩 먹을 수 있다. 모든 아이스크..

• format_list_bulleted 이분 탐색
• · 2024. 4. 7.
• textsms

컴퓨터가 실수를 연분수 표현(continued fraction)으로 나타내는 방법

1. 유리수의 continued fraction continued fraction은 실수를 수렴하는 유리수의 수열로 표현하는 것이다. 이는 problem solving에서 유용할 수 있는데, 쉽게 계산될 수 있으며, 실수의 최적 유리수 근사를 찾는데 효과적으로 사용될 수 있어서 그렇다. 게다가 정수론에서 유용하게 사용되는 유클리드 알고리즘과 연관되어있다. 어떤 정수 $a_{0}, a_{1}, ..., a_{k}$에 대하여, $a_{1}, a_{2}, ... , a_{k}$가 1이상의 자연수일때, $$r = a_{0} + \frac{1}{a_{1} + \frac{1}{... + \frac{1}{a_{k}}}}$$ 를 유리수 r의 연분수 표현(continued fraction)이라고 부른다. 이를 r을 간단하..

• format_list_bulleted 대수학
• · 2023. 9. 20.
• textsms