CS/알고리즘
-
크기가 큰 배열에서의 탐색 & 캐시 히트CS/알고리즘 2023. 1. 12. 20:44
https://www.acmicpc.net/problem/7453 7453번: 합이 0인 네 정수 첫째 줄에 배열의 크기 n (1 ≤ n ≤ 4000)이 주어진다. 다음 n개 줄에는 A, B, C, D에 포함되는 정수가 공백으로 구분되어져서 주어진다. 배열에 들어있는 정수의 절댓값은 최대 228이다. www.acmicpc.net 위 문제를 풀 때 큰 배열에서 탐색을 하는 과정에서 특이한 현상을 겪어 쓰는 글. 위 문제는 크기가 4000인 배열 A, B, C, D의 원소의 합이 0인 경우의 수를 구하는 문제이다. 이를 단순하게 접근하면 모든 배열에서 한 개의 원소를 뽑는 경우이므로, 4000 ^ 4 = 256조. 시간복잡도를 줄이기 위해서, A와 B의 합을 AB, C와 D의 합을 CD로 놓으면, 경우의 수..