[Algorithm] 배열과 리스트, 구간 합 알고리즘

2026.02.22 - [Java] - [Java] 컬렉션 프레임워크 - List(ArrayList, LinkedList)의 이해

[Java] 컬렉션 프레임워크 - List(ArrayList, LinkedList)의 이해

 

배열과 리스트

자료구조에서 데이터를 저장하는 방식에는 여러 가지가 있습니다.

그 중에서도 가장 기본적인 구조가 배열(Array)과 리스트(List) 입니다.

 

두 자료 구조는 데이터를 저장한다는 공통점이 있지만, 데이터를 저장하고 접근하는 방식에서 큰 차이가 있습니다.

---

배열(Array)

배열은 메모리의 연속된 공간에 데이터를 저장하는 자료 구조 입니다.

배열의 각 데이터는 인덱스(index)를 통해 접근할 수 있으며, 하나의 배열에는 같은 자료형의 데이터만 저장할 수 있습니다.

배열의 특징

특징	시간 복잡도	설명
인덱스를 이용한 빠른 접근	O(1)	arr[i] 등을 이용하여 바로 값 접근 가능
삽입/삭제의 어려움	O(n)	값의 삽입 삭제에는 뒤에 있는 데이터를 이동 과정이 필요해서 느림
크기 고정		한 번 선언된 배열의 크기는 변경 불가

✔ 즉, 배열은 인덱스를 통한 빠른 접근이 가능하지만 삽입 및 삭제는 느린 자료 구조

배열의 삽입 및 삭제 과정

---

리스트(List)

리스트는 노드(Node)라는 단위로 데이터를 저장하는 자료 구조 입니다.

각 노드는 다음 두 가지 정보를 가지고 있습니다.

✔ 노드(Node) : 본인의 데이터 + 다음 노드를 가리키는 포인터
✔ 포인터 :  어떤 데이터를 직접 저장하는 것이 아닌, 그 데이터가 저장된 위치를 기억하는 값
   *마지막 노드는 더 이상 연결된 노드가 없기에 null값

리스트의 특징

특징	시간 복잡도	설명
순차 접근 구조	O(n)	인덱스가 없기에, 데이터에 접근하려면 Head(첫 번째 노드)부터 순차적으로 탐색
빠른 삽입/삭제	O(1)	노드 간의 연결만 변경하면 되므로 삽입과 삭제가 매우 빠름
동적 크기		배열과 달리 크기를 미리 정할 필요 없음.
추가 메모리 사용		각 노드는 포인터를 함께 저장해야 하므로, 배열보다 더 많은 메모리 사용 *상대적으로 더 복잡한 구조

✔ 즉, 리스트는 연결 구조를 통해 삽입/삭제는 빠르지만, 조회는 느린 자료 구조

리스트와 배열의 차이

✔ 배열 : 데이터를 연속된 메모리 공간에 저장
    ↳ 중간에 값을 추가하거나 삭제할 경우 기존 데이터를 이동해야 하는 비용 발생

✔ 리스트 : 데이터를 노드로 나누고 연결
    ↳ 노드 간의 연결(포인터)만 변경하면 되기에 데이터 이동 없이 빠른 삽입/삭제 가능

---

구간 합(Prefix Sum)

구간 합은 배열에서 특정 구간의 합을 빠르게 구하기 위해 사용하는 알고리즘입니다.

일반적으로 배열의 합을 구할 때는 반복문을 사용하여 구하는데, 이 경우 시간 복잡도는 O(n)이고 이 연산을 여러번 수행하면 비효율적입니다.

 

이 문제를 해결하기 위한 것이 바로 구간 합 알고리즘입니다.

이를 활용하기 위해서는 먼저 합 배열을 이용해야 합니다.

✔️ 핵심 :  미리 누적된 합(합 배열)을 만들어 두고, 필요할 때 빠르게 계산한다.

이를 구간 합 알고리즘이라고 하는데, 이를 활용하기 위해서는 먼저 합 배열을 이용해야 합니다.

합 배열(Prefix Sum Array)

배열 A가 있을때는 합 배열 S는 다음과 같이 정의 합니다.

✔️합 배열 S : A[0] ~ A[i] 까지의 합
S[i] = A[0] + A[1] + A[2] + ... + A[i - 1] + A[i]  

✔️합 배열 S를 만드는 공식
S[i] = S[i - 1] + A[i]

 

구간 합 공식

✔️구간 합 공식
S[j] - S[i - 1]

✔️ 합 배열 S는 0번부터 해당 인덱스까지의 누적 합을 의미합니다.
ex) S[5] =  A[0] + A[1] + A[2] + A[3] + A[4] + A[5]

---

예시 문제 풀이

예시 문제를 통해 과정을 살펴보겠습니다.

❓ A 배열의 1 ~ 3 구간의 합 구하기
A = [3, 6, 7, 10, 14]

1. S 배열 생성

✔️ S 배열 생성(위 합배열 공식 이용)
S = [3, 9, 16, 26, 40]

 

2. 구간 합 확인

✔️ 구간 합 확인
A[1] + A[2] + A[3] 
= 6 + 7 + 10 
= 23

✔️ 구간 합 공식 사용
S[j] - S[i - 1]
= 26 - 3
= 23

공식을 사용해도 값이 동일한 것을 확인할 수 있습니다.

 

3. 과정 설명

✔️ 합배열 S는 0번부터 지정 인덱스까지의 누적 합

S[4] = A[0] + A[1] + A[2] + A[3] + A[4]
S[1] = A[0] + A[1]

✔️ 우리가 구하고 싶은 값은 1 ~ 3의 구간으로 S배열에는 필요 없는 값(S[0])이 포함되어 있음.
✔️ 합배열 공식 : S[j] - S[i - 1]

S[j] = A[0] ~ A[j]
S[i - 1] = A[0] ~ A[i - 1] 
 
A = [3, 6, 7, 10, 14]
S = [3, 9, 16, 26, 40]

💡 정리
전체 합 : (0 ~ j)
앞 부분 : 앞 부분(0 ~ i - 1)
원하는 구간 : (i ~ j)

✔ 즉, 앞에서부터 누적된 합에서필요없는 앞부분만 뺴면 원하는 구간 합이 나옴