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]에 저장해놓고 ..
22846번: 인증된 쉬운 게임 (acmicpc.net) 모니터에 1이 쓰여있는데, 두 사람이 선공부터 번갈아가며 모니터에 쓰인 수의 약수를 더해간다. 이 때 제한 k를 초과한 사람이 패배하게 된다. k가 주어질때, 항상 완벽하게 플레이하는 두 사람중 누가 이길까 이런 게임 문제는 보통 1부터 최선의 전략으로 해보면 눈치로 풀면 풀리는 경우가 종종 있더라 실제로 해보면 k = 2,6의 경우에만 선공이 이길 수 있고 나머지는 후공이 반드시 이긴다 k = int(input())if k == 2 or k == 6: print('Kali')else: print('Ringo') 근데 언제까지 이렇게만 할 수는 없지 그리고 이렇게 찾기 힘든 문제도 있더라 개념을 확실히 알아야돼 1) 상..
1. 왜 문자열의 hashing이 필요한가? https://deepdata.tistory.com/960 문자열 해싱(hashing) 기본 개념 배우기String Hashing - Algorithms for Competitive Programming (cp-algorithms.com) String Hashing - Algorithms for Competitive Programming String Hashing Hashing algorithms are helpful in solving a lot of problems. We want to solve the problem of comparing stringdeepdata.tistory.com 두 문자열 S1, S2가 서로 같은지 다른지 비교하고 싶을 때가 있..
SW Expert Academy SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 나이트가 (i,j)에 있을때, (i+1,j+2), (i+2,j+1) 둘 중 하나로만 움직일 수 있다고 하자. x,y가 주어질 때, (0,0)에서 출발하여 (x,y)로 이동할 수 있는 경우의 수는? dp[y][x] += dp[y-1][x-2], dp[y][x] += dp[y-2][x-1]로 구할 수 있을 것 같은데 X,Y가 $10^{6}$까지라서 메모리도 안되고 $O(N^{2})$이라 시간복잡도도 안된다 나이트가 (i,j)에서 이동하는 방법이 (i+1,j+2), (i+2,j+1) 2가지만 있다는 것을 생각한다면... (0,0)에서 (..
이미 알고있는 것들인데 블로그에 정리가 안되어 있어서 1. n!을 소수 p로 나눈 나머지 소수 p에 대하여 $n! mod p$를 구하는 문제가 있다. 단 하나의 $n! mod p$를 구해야한다면... $n! = n*(n-1)*(n-2)*...*1$이므로, 1부터 n까지 $O(N)$에 다 곱한 다음, p로 나눈 나머지를 구하는 것이 간단하다. 하지만 n이 매우 크면서, 여러가지 n에 대한 $n! mod p$가 필요하다면 이야기가 달라진다. 여러가지 n에 대한 $n! mod p$가 필요하다면 가능한 모든 n에 대해 $n! mod p$를 구해놓고 O(1)로 접근하면 된다. 여기서 다이나믹 프로그래밍에 의해 이전에 구해놓은 값을 저장해둔다면, O(N)에 모든 n에 대해 $n! mod p$를 구할 수 있다. $n..
1. 문제 1311번: 할 일 정하기 1 (acmicpc.net) 1311번: 할 일 정하기 1 N명의 사람과 N개의 일이 있다. 각 사람은 일을 하나 담당해야 하고, 각 일을 담당하는 사람은 한 명 이어야 한다. 또한, 모든 사람은 모든 일을 할 능력이 있다. 사람은 1번부터 N번까지 번호가 매 www.acmicpc.net N명의 사람이 있고, N개의 일이 있는데 각각의 일은 하는데 비용이 든다. 각 사람 1명당 1개의 일만 가능하고 각 일은 1명만이 맡을 수 있다. 이럴 때 최소비용은 얼마인가? 2. 풀이 이런 형태의 문제는 N명의 사람이 1,2,3,4,..,N의 순열대로 배정을 해본후, 각각의 경우에 대해 비용을 전부 조사해서 최솟값을 찾는 방식을 배웠다. 3명이면 (1,2,3), (1,3,2), ..
딥러닝/머신러닝, 통계학, IT프로그래밍, 알고리즘을 좋아하는 사람 https://github.com/yundaehyuck
