[Do it_java]
2. 배열·리스트와 구간 합
혜리노베이션
2023. 5. 23. 22:21
p. 33~55 (2일차)
강의: 배열과 리스트, 구간 합
1. 배열과 리스트
✔ 배열
- 연속 공간에 값이 채워져 있는 형태의 자료구조
- 인덱스를 통해 참조할 수 있다.
- 새로운 값을 삽입하거나 특정 인덱스에 있는 값을 삭제하기 어렵다. * 삽입 또는 삭제 시 주변 값을 이동하는 과정이 필요함
- 배열의 크기는 선연할 때 지정할 수 있으며, 한 번 선언하면 크기를 늘리거나 줄일 수 없다
* A[10] 으로 선언하면 10칸의 배열이 생긴 것 -> 이후에 크기 변경 불가
✔ 리스트
- 값과 포인터를 묶은 노드라는 것을 포인터로 연결한 자료구조
- 인데스가 없으므로 head 포인터부터 순서대로 접근해야 한다. *속도가 느리다
- 포인터로 연결되어 있어 데이터 삽입 및 삭제 연산 속도가 빠르다 *포인터를 이동
- 리스트의 크기는 정해져 있지 않으므로 크기가 변하기 쉬운 데이터를 다룰 때 적절하다.
2. 구간 합 *코테 핵심개념
- 합 배열을 이용하여 시간 복잡도를 줄이기 위해 사용하는 특수한 목적의 알고리즘
✔ 구간 합의 핵심이론
1) 합 배열 S 정의: S[ i ] = A[0] + A[1] + A[2] + ... + A[i] * 0~i 까지의 합
2) 합 배열 S를 만드는 공식: S[i] = S[i-1] + A[i]
3) 구간 합을 구하는 공식: S[ j ] - S[ i - 1 ] * i에서 j까지 구간 합
