배열과 리스트

배열

메모리의 연속된 공간에 값이 채워져 있는 형태의 자료구조.

인덱스를 통하여 참조할 수 있다.

새로운 값을 삽입하거나 특정 인덱스에 있는 값을 삭제하기 어렵다.

값을 삽입하거나 삭제하려면 해당 인덱스 주변에 있는 값을 이동시키는 과정이 필요하기 때문.

(배열은 연속되어야 하기 때문!)

배열의 크기는 선언할 때 지정할 수 있으며, 한 번 선언하면 크기를 늘리거나 줄일 수 없다.

리스트

인덱스가 없다.

값에 접근하려면 Head 부터 순서대로 접근해야 한다.

따라서, 값에 접근하는 속도가 느리다.

데이터를 삽입하거나 삭제하는 연산 속도가 빠르다.

리스트의 크기는 정해져 있지 않으며, 크기가 변하기 쉬운 데이터를 다룰 때 적절하다.

포인터를 저장할 공간이 필요하므로 배열보다 구조가 복잡하다.

---

• String
  • toCharArray
  • arr[i] - '0'; // 요소를 정수형으로 변환

---

구간 합

구간 합 알고리즘을 활용하려면 먼저 합 배열을 구해야 한다.

합 배열은 기존의 배열을 전처리한 배열이라 생각하면 된다.

합 배열을 미리 구해 놓으면 기존 배열의 일정 범위의 합을 구하는 시간 복잡도가 O(N)에서O(1)로 감소한다.

// 합 배열 공식
// 합 배열 S, 기존 배열 A
S[i] = S[i-1] + A[i]

// 구간 합을 구하는 공식
S[j] - S[i-1]

*2차원 배열이라면 2차월 배열의 구간 합을 구해서 문제를 풀어야 한다.