Notice
Recent Posts
Recent Comments
Link
목록2023/06/09 (1)
HJW's IT Blog
Algorithm: 문제풀이 3
# 부분배열의 합 # 배열 A 가 주어졌을 때, 이 배열의 부분배열 A[i:j]의 최대값을 구하시오 > Brute force : O(n^3) > 만약 A[i] + ... + A[j] 까지의 합을 구했다면, (A[i] + ... + A[j]) + A[j+1] 은 O(1) 에 구할 수 있다 >> 총 O(n^2) > 방법 3: 모든 구간은 어디선가 끝나야 하므로 각 위치마다 여기서 끝나는 값의 최대 값을 저장 >> 전체의 최대는 이 중 최대값 >> S[i] : i 위치에서 끝나는 합의 최대값 - ex) S[1] = max (0, A[1]), S[i] = max(0, S[i-1] + a[i]) # 부분배열의 합 변형 # 위와 동일하지만 자연수 k 가 주어지는데, 이때 j >= i + k 이다. # 즉 최소 k개..
알고리즘
2023. 6. 9. 13:06