https://atcoder.jp/contests/abc363/tasks/abc363_d D - Palindromic NumberAtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.atcoder.jp n이 최대 10^18까지라서 보통의 방법으로는 찾을 수 없다는 것이 느껴진다 그래서 일단 가능한 팰린드롬 수를 차례대로 나열해본다 0,1,2,3,4,5,6,7,8,9 >>> 10개 11,22,33,44,55,66,77,88,99 >>> 9개 101, 111, 121, 131, 141, ... ,191202,212,222,232,..., 292303..
25427번: DKSH를 찾아라 (acmicpc.net) 문자열 S가 주어질때, 인덱스 a N이 10만이라 4중 for문으로 찾으면 당연히 시간초과 문자열이 'DDDDKKK'로 이루어질때, 만들 수 있는 'DK'의 개수는? 인덱스를 기준으로 세볼 때 (0,4), (0,5), (0,6) (1,4), (1,5), (1,6) (2,4), (2,5), (2,6) (3,4), (3,5), (3,6) K를 기준으로 본다면, (0,4), (1,4), (2,4), (3,4) (0,5), (1,5), (2,5), (3,5) (0,6), (1,6), (2,6), (3,6) 처음에 D의 개수를 하나씩 세다가, K를 만나면 그 동안 만난 D의 개수를 누적해서 더해주면 된다 어떤 문자열이 주어지면, D의 위치 인덱스를 (..
1. 문제 배열 A가 주어질때, A를 2개의 부분집합으로 분할하고자 하는데, 각 부분집합의 원소의 합이 X,Y이면 abs(X-Y)가 최소가 되도록 분할하고자 한다 이때, 그 최솟값을 구하거나 X,Y를 구하는 문제 A의 원소의 합이 total = sum(A)라면, 두 부분집합의 원소 합의 차이가 최소가 되는 것은 정확히 절반이 되는 경우이다. 그러니까 최대 target = total//2에 도달하는게 가장 좋다. 1) dp[i] = A의 원소를 일부 골라서 합했을때, i가 될 수 있는가? 만약 i-w를 만들 수 있다면, w를 더하면 i가 될 수 있으므로 dp[i-w] = 1이면 dp[i] = 1이 된다. #dp[i] = 배열 v의 원소를 일부 골라 합해서 i를 만들 수 있는가?target = total//..
1. 다중 배낭 문제(multiple 0-1 knapsack) https://atcoder.jp/contests/past202206-open/tasks/past202206_h H - Two KnapsacksAtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.atcoder.jp 각각 무게 제한이 A,B인 2개의 가방이 있다고 하자. 이 2개의 가방에 무게가 W, 가치가 V인 물건을 담고자 한다. 2개의 가방에 담긴 물건 가치 합이 최대가 되도록 하는 방법은? 처음에는... 단순히 무게 제한이 A인 가방에 물건을 담고, 담은 물건은 제외한 다음 무..
12865번: 평범한 배낭 (acmicpc.net) 최대 한도 무게가 K로 정해진 가방 1개에 무게가 W이고 가치가 V인 N개의 물건을 담고자 할때, 가치가 최대가 되도록 담고자 한다. 당연히 하나의 물건은 가방에 한번만 담을 수 있다 1. 1차원 배열 DP[i] = 가방에 담긴 물건들의 무게 합이 i일때, 가치의 최댓값 DP[i] = max(DP[i], DP[i-w] + v) dp = [0]*(K+1)for w,v in bag: for i in range(K,-1,-1): if i-w >= 0: dp[i] = max(dp[i], dp[i-w] + v)print(dp[K]) 주목할 부분은 무게 i = 0,1,2,3,..,K가 아..
15487번: A[j]-A[i]+A[l]-A[k] (acmicpc.net) 크기 N인 주어진 배열 A에서 i N은 최대 1000000이라 4중 for문으로 찾는건 당연히 불가능하다 A[j] - A[i]의 최댓값과 A[l] - A[k]의 최댓값을 나눠서 구하면 좋을 것 같다 근데 i 어떻게 구할 수 있을까? 현재 0 ~ j 구간을 보고 있을때 A[j] - A[i]의 최댓값은, A[j] - (A[0] ~ A[j-1]중 최솟값) dp[j] = i j = 0, 1, 2, 3, ... 가면서 A[j]의 최솟값을 min_value로 항상 갱신해놓는다면, 현재 j에 대해 0~j-1까지 최솟값은 min_value이고 그러므로 A[j] - min_value로 최댓값을 구할 수 있다. 이를 dp[j]에 저장해놓고 ..
딥러닝/머신러닝, 통계학, IT프로그래밍, 알고리즘을 좋아하는 사람 https://github.com/yundaehyuck
