공부 기록

카데인 알고리즘 (Kadane's Algorithm) ?배열 내의 연속된 부분 배열의 합 중에서 합이 최대인 부분 배열을 찾는 알고리즘이다.배열을 한 번 순회하면서 현재 위치에서 끝나는 가장 큰 부분 배열의 합을 계산하고 이를 통해 전체 배열에서의 최대 부분 배열 합을 구하는 방식이다. 이 알고리즘은 시간 복잡도가 O(n), 공간 복잡도가 O(1)로 매우 효율적이다. 또한 1차원 배열뿐만 아니라 2차원 배열에서도 적용할 수 있다. 2차원 배열에서 최대 합을 갖는 부분 행렬을 찾는 문제는 복잡하지만 알고리즘을 행별로 적용하여 문제를 1차원 문제로 축소함으로써 해결할 수 있다. 핵심 아이디어카데인 알고리즘은 다음과 같은 두 가지 값을 사용한다.현재까지의 최대 부분 배열 합 (current_max) : 특정 ..

✏️ 문제 문제 파악처음에 이중 반복문 써서 풀고 있다가.. 시간 초과나서 찾아보니 최대 부분합을 푸는 방법 중 카데인 알고리즘을 써야 풀리는 문제였다.간단하게 설명하자면 시작 원소를 기준으로 부분 배열을 구하는 게 아니라 끝 원소를 기준으로 모든 부분 배열을 구하는 알고리즘이다.   알고리즘다이나믹 프로그래밍   코드시간 초과 코드import sysinput = sys.stdin.readlinen = int(input())ary = list(map(int, input().split())) value = -1000for i in range(n): temp = ary[i] for j in range(i+1, n): value = max(value, temp) temp += ary[j]pri..

✏️ 문제 문제 파악입력으로 주는 배열을 기준으로 합을 담은 dp 배열의 값을 구하면 다음과 같이 나온다.중요한 것은 그림의 빨간 부분과 같이 중간에 겹치는 부분이 생기는데 이때문에 경우를 나눠서 구해야 한다.dp[n][0]dp[n][1] ~ dp[n][n-1] : 어짜피 최대값을 구하므로 max 값만 두면 된다.dp[n][n]  알고리즘다이나믹 프로그래밍   코드n = int(input())ary = [list(map(int, input().split())) for _ in range(n)] dp = [[0] * (n+1) for _ in range(n)]dp[0][0] = ary[0][0]for i in range(1, n): for j in range(i + 1): if j == 0: ..

✏️ 문제 문제 파악첨에 반복되는 게 있는 지 찾는데 안보였다..고민하다가 문제에서 P(1)부터 P(10)까지 주는 이유가 있을 것 같아서 찾아보니 다음과 같은 반복이 보였다!이를 토대로 점화식은 P(n) = P(n-1) + P(n-5) 이 나왔다.  알고리즘다이나믹 프로그래밍   코드for _ in range(int(input())): p = [0, 1, 1, 1, 2, 2, 3, 4, 5, 7, 9] n = int(input()) for i in range(len(p), n+1): p.append(p[i-1] + p[i-5]) print(p[n])