다이나믹 프로그래밍 - Kadane algorithm

1. 문제 https://www.acmicpc.net/problem/1912 1912번: 연속합첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다.www.acmicpc.net 주어진 n개의 임의의 수열에서 1개 이상의 연속된 부분 수열을 선택할 때, 가장 큰 합을 출력  2. 나의 풀이 단순한 규칙, 점화식으로는 풀기 어렵다 메모리, 시간제한 문제로 $O(N^2)$으로도 통과하기 어렵다 처음에 i번째부터 j번째까지 수열의 합을 dp[i][j]에 저장해서 테이블을 완성하려고 했는데 n의 최대가 100000이라 10만*10만 만들자 마자 메모리 초과 from sys impor..

• format_list_bulleted 다이나믹 프로그래밍
• · 2022. 9. 4.
• textsms

다이나믹 프로그래밍 정복기 2 - 연습문제 1로 만들기 -

1. 문제 https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 1이상의 정수 x가 주어질때, 1) x가 3으로 나누어 떨어지면 3으로 나눈다 2) x가 2로 나누어 떨어지면 2로 나눈다 3) x에서 1을 뺀다 3가지 연산을 적절히 사용해서 1을 만들고 싶다 연산을 사용한 횟수의 최솟값을 출력한다면? 2. 나의 풀이 다이나믹 프로그래밍 연습문제니까 다이나믹 프로그래밍을 써야겠지 기본이 바텀업이고 반복문 구현이라고 배웠으니까 이에 따라보자 작은 문제부터 구해놓고, 이들을 이용해서 반복문을 구현한다면.. 1이상이니까 dp[0] = 0, 1은 연산을 안해도 1이니까 d..

• format_list_bulleted 다이나믹 프로그래밍
• · 2022. 9. 3.
• textsms

매우 큰 수를 나머지 연산으로 줄일 수 있는 마법(백준-개미)

1. 문제 https://www.acmicpc.net/problem/10158 10158번: 개미 가로 길이가 w이고 세로 길이가 h인 2차원 격자 공간이 있다. 이 격자는 아래 그림처럼 왼쪽 아래가 (0,0)이고 오른쪽 위가 (w,h)이다. 이 공간 안의 좌표 (p,q)에 개미 한 마리가 놓여있다. 개미는 오 www.acmicpc.net 좌표평면 안에서 개미가 대각선 방향으로 움직이는데, 벽면에 부딪힐 경우, 반사되어 움직인다. 일정한 속력으로 움직일 때, 평면의 크기, 처음 좌표가 주어지고 시간 t가 주어질때, t시간 후에 개미의 위치를 구해본다면..? 2. 풀이 시간 t의 범위가 2억이나 되니까, 일반적인 1칸씩 가는 반복연산으로는 도저히 0.15초만에는 불가능 그렇다고 벽면까지 한번에 가는 방법으..

• format_list_bulleted 애드 혹 알고리즘
• · 2022. 8. 30.
• textsms

분할정복을 이용한 거듭제곱 빠르게하기

1. 분할정복 문제를 더 이상 나눌 수 없을 때까지 더 작은 문제로 나누면서 이 작은 문제들을 각각 풀면서, 병합하여 전체 문제의 답을 구하는 알고리즘 divide - conquer - combine 방식으로 설계한다. 문제가 분할이 가능하면 2개 이상의 작은 문제로 나눈다(divide) 나누어진 문제가 분할이 가능하면, 또 다시 문제를 분할하고 그렇지 않으면 문제를 푼다(conquer) 푼 문제들을 통합하여 전체 문제의 답을 구한다(combine) 당연하지만 divide를 잘 하면 나누어진 문제를 푸는 것은 매우 쉬우므로 divide를 잘 하는 것이 중요하다 재귀알고리즘을 많이 사용하게 되는데, 이 때문에 오히려 효율적이지 못할 수 있다. 2. 응용 - 거듭제곱 n번의 거듭제곱은 자신을 n번 곱하므로 ..

• format_list_bulleted 분할 정복
• · 2022. 8. 15.
• textsms

약수를 빠르게 구하는 알고리즘

1. 설명 어떤 자연수 n에 대하여 n = a*b가 되는 두 자연수 a,b를 n의 약수라고 한다. 이러한 a,b는 반드시 존재한다. 최소 (1,n)이 존재한다는 것. n의 약수를 프로그래밍으로 어떻게 구할까? 가장 쉽게 생각하는 방법은 n을 1부터 n까지 각각 나눠보면서 나누어 떨어지는 수를 찾는 것이다. 그런데 n이 너무 크면, 10억만 되어도 너무 오래걸린다는게 문제 ----------------------------------------------------------------------------------------------------------------------- 그런데 n = a*b에서 a,b의 관계를 생각해보면 a > b, a < b, a = b 3가지 경우가 가능하다. 근데 사실 ..

• format_list_bulleted 알고리즘 일반
• · 2022. 8. 10.
• textsms