선택한 원소의 인접한 원소는 선택할 수 없을 때 원소 합을 최대로 선택하는 방법

7265번: Herbamedžiai (acmicpc.net)  배열에서 i번째 원소를 선택하면 i-1번째, i+1번째 원소는 선택할 수 없을때, 선택할 수 있는 원소의 최대 합을 구한다면 n이 최대 10만이라 O(N)에는 해결해줘야한다 $O(N^{2})$ 아니면 못할것 같지만 놀랍게도 O(N)에 되더라고 DP[i] = i번째 원소까지 봤을때 선택한 원소들의 최대합 만약 i번째 원소를 선택하지 않는다면? dp[i] = dp[i-1]로 그대로 가져오면 된다 만약 i번째 원소를 선택한다면? i-1번째 원소는 선택할 수 없으므로, dp[i-2]에다가 i번째 원소 선택 A[i]를 더해주면 된다 dp[i] = dp[i-2] + A[i] 여기서 둘 중 더 큰 값을 고르면 된다 dp[i] = max(dp[i-1], d..

• format_list_bulleted 다이나믹 프로그래밍
• · 2024. 8. 10.
• textsms

2^30으로 나눈 나머지로 2^5으로 나눈 나머지를 구할 수 있을까

8672번: Drabina (acmicpc.net) 사다리의 맨 끝단 s까지 올라가는데 한걸음 혹은 두걸음씩 올라갈 수 있다 이 때 끝까지 올라가는 방법의 수를 $2^{p}$로 나눈 나머지를 구해야한다. 이것만 보면 매우 쉬운 문제다 dp[i] = i번째까지 올라가는 방법의 수하면 가능한 경우는 한걸음 혹은 두걸음이므로... dp[i] += dp[i-1]dp[i] += dp[i-2] 인 전형적인 문제 dp = [0]*(s+1)dp[0] = 1mod = 2**pfor i in range(1,s+1): for j in range(1,3): if i >= j: dp[i] += (dp[i-j]) dp[i] %= mod  문제는 최대 ..

• format_list_bulleted 정수론
• · 2024. 8. 10.
• textsms

홀수 길이의 연속 부분 배열의 합 중 가장 큰 값을 구하는 방법

19355번: A Really Odd Sequence (acmicpc.net) 주어진 배열에서 길이가 홀수인 연속 부분 배열의 원소 합 중 가장 큰 값을 구하는 문제 https://deepdata.tistory.com/390 다이나믹 프로그래밍 - Kadane algorithm1. 문제 https://www.acmicpc.net/problem/1912 1912번: 연속합첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거deepdata.tistory.com 카데인 알고리즘의 연장선상이긴 한데 문제는 홀수 길이여야한다는 것... 카데인 알고리즘은 배열의 길이를 모른다.. 길이 정보를 담자니...

• format_list_bulleted 다이나믹 프로그래밍
• · 2024. 8. 5.
• textsms

사각형과 원이 겹치는 영역의 좌표의 개수는 O(N)에 구할 수 있을까

21676번: Газон (acmicpc.net) 왼쪽 아래 (x1,y1), 오른쪽 위 (x2,y2)로 주어지는 사각형과 중심 (x3,y3), 반지름 r로 주어지는 원이 서로 겹치는 영역의 정수 점 (x,y)의 개수를 구하는 문제 정말 단순하게 생각하면 사각형 안의 모든 정수 점 (x,y)에 대하여 원의 방정식 내부 (x-x3)**2 + (y-y3)**2  def check(x,y): v = (x-x3)**2 + (y-y3)**2 if v   하지만 x1,x2,y1,y2,x3,y3의 범위가 -10만~10만이라 $O(N^{2})$은 시간초과가 날수밖에 없다 하지만... 이것말고 방법이 있나? x를 정했으면 그거에 대해 y는 모든 범위를 돌아봐야할텐데..? 방법은 원의 방정식은 (x-x3)..

• format_list_bulleted 기하학
• · 2024. 8. 1.
• textsms

안정 결혼 문제(stable matching, stable marriage, gale shapley algorithm)

1. 어떻게 남녀를 맺어줘야 행복하게 살수 있을까? 결혼중매업자인 대혁에게는 200명의 고객이 있다. 100명은 남자, 100명은 여자이다. 여자 고객은 각자 남자 고객 100명을 대상으로 선호도에 따라 순위를 매겨 대혁에게 제출한다. 각자 명단의 맨 위에는 완벽한 이상형이 있고, 아래로 갈수록 호감도가 떨어져 맨 아래에는 최악의 기피남이 있다. 남자 고객 100명도 마찬가지로 여자 고객 100명을 대상으로 순위를 매겨 제출한다 대혁은 이 선호도 조사 결과를 바탕으로 남녀 고객을 맺어줘야한다. 어떻게 맺어줘야 이들이 결혼에 골인하고 가정을 이루고 오래오래 행복하게 살 수 있을까? 당연한 말이지만, 일부는 자신의 제1지망과 맺어지지 못한다.  같은 남자를 여러 여자가 제1지망으로 찍었다면 누군가는 고배를 ..

• format_list_bulleted 고급 알고리즘
• · 2024. 7. 31.
• textsms

원 안에 원을 가득 채우는 문제?(circle packing in a circle)

20744번: Cucumber Conundrum (acmicpc.net) 반지름이 s인 원 모양의 샌드위치가 있고 반지름이 r인 원 모양의 피클이 n개 있는데  이 피클을 샌드위치 위에 최대한 많이 높고 싶다 이 때 샌드위치 면적의 최대 z%까지만 놓을 수 있고 두 피클이 서로 겹치지 않아야한다 최대 몇개의 피클을 놓을 수 있는가? 샌드위치의 면적이 $\pi * s^{2}$이고 이것의 최대 z%가 피클 x개의 넓이 $\pi * r^{2} * x$이므로  $$\pi * s^{2} * \frac{z}{100} >= \pi * r^{2} *x$$  식을 정리하면 $x  사실 이것만 만족하면 되는줄 알았는데... 아니더라고 https://en.wikipedia.org/wiki/Circle_packing_in_a_..

• format_list_bulleted 기하학
• · 2024. 7. 27.
• textsms