목록알고리즘/개념 (1)
시작하는 중
구간합
만약 1~n까지, 3~m까지, z~x까지 모두 1씩 더해야한다고 하자. 모든 변수는 1부터 시작하고 최대 1000까지이다. 이때 가장 큰 값은? 그렇다면 코드로는 info_list = [[1, n], [3, m], [x, y]] number_list = list(0 for i in range(1001) for info in info_list: s, e = info for index in range(s, e): number_list[index] += 1 print(max(number_list)) 이렇게 이중 반복문을 돌아야한다. 때문에 시간복잡도는 O(N^2)가 된다. 하지만 이런 구간의 합에 대한 것을 구간에 대한 순회와 숫자열에 대한 순회, 총 두번만 순회하면 되는 방법이 있다. 바로 구간합! info..
알고리즘/개념
2023. 2. 5. 15:35