Persistence

풀이 def accumulator(index, target_DNA, DNA_mapper): for DNA in DNA_mapper: if target_DNA == DNA: DNA_mapper[target_DNA][index + 1] = DNA_mapper[target_DNA][index] + 1 else: DNA_mapper[DNA][index + 1] = DNA_mapper[DNA][index] def get_minumum_impact_factor(start_index, end_index, DNA_mapper): for DNA in DNA_mapper: if DNA_mapper[DNA][end_index + 1] - DNA_mapper[DNA][start_index] > 0: return DNA els..

Prefix Sums array의 어떠한 slice라도 sum을 빠르게 계산할 수 있도록 해주는 방법이다. 예를 들어 어떤 배열의 인덱스 i부터 j까지의 합을 구하려고 할 때 for문을 써서 일일이 접근해서 더하면 O(N)이지만, 이 방법을 사용하면 O(1)이다. def prefix_sums(A): n = len(A) P = [0] * (n + 1) for i in range(1, n + 1): P[i] = P[i - 1] + A[i - 1] return P 점화식: P[i] = P[i - 1] + A[i - 1] A라는 배열이 있을 때, A 배열의 sum의 누적값을 계산해서 P에 넣는 것이다. P[i] = P[i - 1] + A[i - 1]으로 계산되고, P[i]는 A 배열의 i번째 원소(인덱스로는 i..