희소 배열(Sparse Table)

희소 배열

배열 원소의 개수가 배열 length보다 작은 배열

 

배열 원소의 위치가 연속적이지 않음.

메모리의 낭비가 심함.

희소 배열의 특징을 이용하여 그래프의 cycle을 탐색해나갈 수 있음

 

 

희소 행렬과 유사.

(희소 행렬 :  행렬의 값 대부분이 0인 경우.)

 

 

 

EX))

위와 같이 사이클이 있는 그래프가 존재하며,

이 그래프의 정점(V)에서 시작하여 n번씩 이동한 후의 정점을 구해야 한다고 생각해 보자.

 

일반적인 방법으로는 n번씩의 "이동"을 통해 도착 정점을 구할 수 있다.

하지만 이 방식은 n의 값이 커질수록 큰 비용이 필요하며,

위의 그래프에서는 사이클이 존재하므로, 생략 없이 n번 모두를 이동하는 것은 비효율적이라고 생각할 수 있다.

 

이를 희소 배열을 적용하여 생각해 보았을 때,

간선의 이동 횟수를 1번, 2번, 3번,, 과 같이 연속적인 횟수로 생각하지 않고 

1번, 2번, 4번, 8번,, 의 횟수로 생각하여, 이에 대한 표를 작성해 본다면 다음과 같다.

 

이동횟수/시작V	1	2	3	4	5
1	3	3	5	4	3
2	5	5	3	4	5
4	5	5	3	4	5
8	5	5	3	4	5
16	5	5	3	4	5

 

그리고 위의 희소 배열을 이용하여, 3번 정점에서 출발하여 11번 이동하는 경우를 생각해 보면 다음과 같이 3번만의 탐색을 통하여 결과값을 구할 수 있다.

 

 

11 = 8 + 2 + 1

 

이와 같이 3번으로 탐색 횟수를 줄여 이동 결과를 빠르게 구할 수 있다.

 

 

---

🧩 [Algorithm] 희소 배열(Sparse Table) 알고리즘 | hello-capo!

🧩 [Algorithm] 희소 배열(Sparse Table) 알고리즘 | hello-capo!