글 읽기 - 이런 자료구조를 뭐라고 부르나요?

yukariko 9년 전 0

https://www.acmicpc.net/problem/3653

주로 이런 문제를 해결할 때 제가 주로 사용하는 방법인데

1~n 범위의 배열을 m단위로 분해해서 합이나 순서를 유추하는 자료구조입니다.

예를들면

a[] = { 1 , 2 , 3 , 4 , 5, 6, 7, 8, 9 }

위와 같은 배열에서 (편의를 위해 1~9지만 규칙성은 없다고 가정)

a배열의 2번부터 5번 인덱스 사이의 합을 구하는 문제라고 하면

원래는 2~5까지 순차적으로 구하면 되지만, 범위가 크고 구간합을 구해야하는 케이스가 많으면 시간초과가 뜰겁니다.

그래서 저는 위 배열을 3개씩 끊어서 다음과 같은 배열을 만들었습니다.

b[] = { 6(1+2+3), 15(4+5+6), 24(7+8+9) }

이제 3번부터 6번사이의 구간합은 a[2] + b[1] = 18이 됩니다.

시간 복잡도는 원래 O(n) 을 n = a * b 라고 가정하면 O(ab) -> O(a+b)가 되겠군요..

저는 이러한 자료구조를 pack 이라고 불렀고, 이렇게 해결한 문제가 지금까지 6개정도 되는데, 실제로는 어떤 이름인지가 궁금합니다.

amugeona 9년 전 1

글쎄요... 저는 그냥 그룹화라고 부릅니다.

yukariko 9년 전 1

그룹화..

적절한 이름이네요

왜 그룹이란 단어를 생각하지 못했지..

pichulia 9년 전 3

다양한 이름이 있지만... 저같은 경우는 "인덱스 트리" 라고 부릅니다.

저렇게 pack으로 묶은 애를, 묶인 애들의 "부모" 라고 생각하면 트리구조가 만들어지니까요..

혹은 "팬윅 트리" 나 "버켓 머시기" 같은것도 있는데...자세한건 기억이 안나네요 ㅠㅠㅠ

yukariko 9년 전 1

아.. 그래서 그런지 이러한 문제가 풀리는 상황은 항상 인덱스 트리로 해결이 가능하더라구요

결국은 같은 의미였군요

amugeona 9년 전 1

@yukariko 모든 그룹화 문제가 인덱스트리로 해결되는 것은 아닙니다. 아닌 문제들도 많습니다...

zzapCoder 9년 전 1

sqrt decomposition 인가요?

RiKang 9년 전 3

저런 식으로 해결하는 걸 bucket method ( 버킷 방식? ) 이라고 하고 이럴땐 보통 n개 원소들을 sqrt(n) 마다 묶어서 하는데 이건 sqrt decomposition ( 평방 분할이었나? ) 이라고 해서 쿼리당 sqrt(n)의 시간복잡도가 나오는데 구간트리로 불가능한 경우에 쓰이거나 그냥 구간트리보다 솔루션이 쉬워서 쓰거나 그렇죠

RiKang 9년 전 1

http://www.acmicpc.net/problem/8462

요런거 2차원 평방 분할로 해결가능한데 인덱스 트리로는 힘들더라구요 ( 전 포기하고 sqrt decomposition으로... )

yukariko 9년 전 0

다들 감사합니다. 많이 배워가네요 ㅎㅎ

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

이런 자료구조를 뭐라고 부르나요?

yukariko 9년 전 0

amugeona 9년 전 1

yukariko 9년 전 1

pichulia 9년 전 3

yukariko 9년 전 1

amugeona 9년 전 1

zzapCoder 9년 전 1

RiKang 9년 전 3

RiKang 9년 전 1

yukariko 9년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말