NAN-NOO

https://www.acmicpc.net/problem/11660 11660번: 구간 합 구하기 5 첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 www.acmicpc.net [코딩 테스트/개념] - 구간 합 # 1

https://www.acmicpc.net/problem/11659 11659번: 구간 합 구하기 4 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j www.acmicpc.net [코딩 테스트/개념] - 구간 합 # 1

합 배열을 이용하여 시간 복잡도를 더 줄이기 위해 사용하는 알고리즘 배열의 데이터 변경이 적을 때 활용 -> 많을 땐? index tree 구간 합 알고리즘을 활용하려면 먼저 합 배열을 구해야 함 합 배열 S S[i] = A[0] + A[1] + ... + A[i - 1] + A[i] S[i] = S[i - 1] + A[i] 합 배열을 구해 놓으면 기존 배열의 일정 구간 합을 구하는 시간 복잡도가 O(N)에서 O(1)로 감 구간 합 공식(인덱스 i에서 j까지 합) S[j] - S[i - 1]

🔰자료구조 배열 연속된 메모리 공간에 데이터를 저장하고 있는 자료구조다. 인덱스로 값에 바로 접근할 수 있다(O(1)). 첫번째 값의 메모리 주소를 기준으로 메모리 주소를 계산한다. 새로운 값 삽입, 또는 기존값 삭제가 어렵다. 기존 배열에 있는 값들을 이동시켜야 한다. 배열의 크기는 선언할 때 지정하고, 선언 후에 크기를 변경할 수 없다. 리스트(linked list) 데이터를 저장하고 있는 각 노드가 포인터로 연결되어 있는 자료구조다. 인덱스가 없으므로 값에 접근하려면 O(n)의 시간복잡도를 가진다. 새로운 값 삽입, 또는 기존값 삭제가 빠르다(O(1)). 포인터로 노드를 연결하면 된다. dynamic list라고도 불리며, 선언 후에도 크기를 변경할 수 있다. 🍎 파이썬에서는 배열과 리스트를 구분하..

🔰기본 개념 n: input size c_op: execution time for basic operation C(n): number of times basic operation is executed T(n): running time ≒ c_op * C(n) O(g(n)): worst(upper bound). The set of all functions with a lower or same order of growth as g(n) T(n) ≤ c_op * g(n) n^3 ∉ O(n^2) Ω(g(n)): best(lower bound). The set of all functions with a higher or same order of growth as g(n) T(n) ≥ c_op * g(n) n^3 ..