무게가 실수 float인 배낭 문제에 필요한 테크닉

4781번: 사탕 가게  가지고 있는 돈이 있고 사탕의 가격과 칼로리가 주어질때, 주어진 돈으로 얻을 수 있는 최대 칼로리를 구하는 문제 각 사탕은 중복해서 구매할 수 있다 무한 배낭 문제인데 특이한 점은 무게가 소수점 둘째자리까지 주어진다는 점 배낭 문제로 해결하고 싶어도 배열의 크기는 실수로 만들수 없다 그러면 어떻게 해야할까? 소수점 둘째자리까지 주어지기 때문에, 실수인 가격을 모두 100을 곱해서 정수로 만들면 모두 동등하게 100을 곱했기 때문에 아무 문제가 없다 그리고 무한 배낭 문제이기 때문에 무게를 순회할때는 정방향으로 순회하도록 for i in range(p,m+1): 이렇게 from sys import stdinwhile 1: n,m = stdin.readline().rstrip(..

• format_list_bulleted 다이나믹 프로그래밍
• · 2025. 1. 4.
• textsms

floating point와 fixed point 간단하게

1. floating point와 fixed point의 차이 fixed point는 부호(+ , - )와 정수부와 소수부로 나누어서 실수를 저장하는 것 만약 32bit인 경우 예를 들면 정수는 8비트 소수부는 23비트만 저장하겠다고 고정을 하고 실수를 저장함 정수를 표현하고자하는 비트 수를 늘린다면 더 큰 숫자를 표현할 수 있지만  그만큼 소수부 비트가 줄어들어서 정밀한 숫자를 표현하기 어렵다 반면 소수부 비트를 늘린다면 정밀한 숫자를 표현할 수는 있어도 큰 숫자를 표현하기는 어렵다  이런 문제를 해결하기 위해 floating point 방식이 등장했다 모든 실수를 부호(+,-)와 가수부와 지수부로 나누어 저장함   소수점을 옮긴다는 생각은 의미가 없는게  floating point는 12345를 $1..

• format_list_bulleted 컴퓨터과학(CS)
• · 2024. 5. 22.
• textsms

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

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

C++ 알고리즘 기초6 -실수 입력받기, 공백을 사이에 두고, 여러 줄 걸쳐서 입력받기 -

1. 실수 입력받기 cin 함수를 이용해서 입력받을 수 있으며, 변수 선언에 double로 선언한 변수에 저장하면 된다 다음은 실수 n을 입력받아 소수점 셋째자리에서 반올림하여 소수점 둘째자리까지 출력하는 코드 cout > n; cout a >> b; cout > a >> b; cout > b; cout

• format_list_bulleted C++ 기초
• · 2023. 5. 12.
• textsms

되도록이면 실수로 알고리즘을 풀지 말아야하는 이유1

1. 문제 27496번: 발머의 피크 이론 (acmicpc.net) 27496번: 발머의 피크 이론 각 시간에 따른 혈중 알코올 농도는 {0.045, 0.089, 0.133, 0.131, 0.127}이다. 따라서 지금으로부터 2시간 후와 3시간 후, 총 두 시간 동안 혈중 알코올 농도를 유지할 수 있다. www.acmicpc.net 2. 풀이 혈중 알코올 농도는 알코올 양 정수 * 0.001로 정의한다고 하니까, 정수 배열로 주어지는 배열을 왼쪽부터 순회하면서, 0.001을 곱한 다음 합해나가면서, 매 인덱스마다 0.129와 0.138사이에 몇번이나 있었는지 세면 될것 O(N)에 해결하기 위해 prefix sum을 사용한다. 그런데 시간 L 이후에는, L 전에 먹었던 알코올이 사라지므로... 최초로 술을..

• format_list_bulleted 정밀도
• · 2023. 4. 8.
• textsms

특별한 이분탐색 -실수 구간에서도 이분탐색이 가능할까-

1. 문제 14609번: 구분구적법 (Large) (acmicpc.net) 14609번: 구분구적법 (Large) 첫 번째 줄에는 다항함수의 차수를 나타내는 양의 정수 K(1 ≤ K ≤ 10) 가 주어진다. 두 번째 줄에는 최고차항부터 내림차순으로 각 항의 계수를 나타내는 정수 ci (0 ≤ ci ≤ 10, 1 ≤ c1 ≤ 10) 가 www.acmicpc.net 2. 풀이 실제 적분값과 근삿값이 일치하게 만드는 epslion을 찾는다 그러면 실제 적분값을 먼저 구해야겠지 최대 10차 다항함수까지로 제한되어있고 다항함수 적분 방법도 힌트로 나와있다 그러면 $c_{0}x^{k} + c_{1}x^{k-1} + ... + c_{k}$를 적분하면 된다 그러면 $$\frac{c_{0}x^{k+1}}{k+1} + \..

• format_list_bulleted 이분 탐색
• · 2023. 4. 2.
• textsms