8주차 개념 강의 중 질문입니다.

강사님 안녕하세요,

8주차 개념강의 중 질문입니다.

강의 노트 웹페이지에 2번째 그림에서,
"2~8 까지의 최소인덱스 3번째 4번째 6번째 인덱스만 비교해서 최소 인덱스를 반환" 이라는 말이 잘 이해가 안되어서요.

그림상 파란 화살표 표시한 것이 3,4,6 인덱스를 의미 하는 것인지 그리고, 3,4,6째 인덱스를 비교한다는 것이 왜 필요한 것인지 궁금합니다.

제가 이해한 것은 2~8 까지의 최소 인덱스는 Level 1 에 저장된 Index 3 만 확인하여 Index 3 에 위치한 "1" 이 최소값인 것으로 이해를 했거든요.
강의 노트 웹페이지에서 5번째 그림에서,
파랑 노드를 만들면 된다고 갑자기 설명을 하시는데, (강의 3:03 구간)
그림상 주황색 노드(3,4,10,11)의 의미, 파랑색 노드(1,2,3,4)의 의미에 대한 안내도 없고...
그림에 표시된 화살표도 어떤 연산이 수행되었고, 화살표로 연결된 두 노드의 관계에 대한 설명도 없어 이해가 되지 않습니다.
관련 내용 상세 설명 좀 다시 부탁드리겠습니다.

안녕하세요 Kyoung님 ㅎㅎ

음.. 제가 설명이 좀 부족했던 것 같네요.. ㅠ

좀 더 설명을 드리자면요 다음과 같습니다. :)

그림상 파란 화살표 표시한 것이 3,4,6 인덱스를 의미 하는 것인지 그리고, 3,4,6째 인덱스를 비교한다는 것이 왜 필요한 것인지 궁금합니다.

>> A의 요소 2, 4, ... , 8까지의 요소중 최소값을 구해야 합니다.

여기서 0 ~ 6까지의 요소를 다 탐색하는 것이 아니라 펜윅트리를 만들게 되면

min[0, 3] = 3

min[4, 5] = 4

min[6] = 6

부분의 최솟값만 보면 된다는 의미입니다.

파랑 노드를 만들면 된다고 갑자기 설명을 하시는데, (강의 3:03 구간)
그림상 주황색 노드(3,4,10,11)의 의미, 파랑색 노드(1,2,3,4)의 의미에 대한 안내도 없고

>> 주황색노드는 그냥 하나의 배열입니다. 3, 4, 10, 11이라는 배열입니다.

파란색노드는 해당 펜윅트리의 노드를 만든다는 의미입니다.

앞의 그림 처럼 3의 요소가 1, 2, 4 노드에 반영되는 것을 볼 수 있습니다.

4라는 요소는 2, 4에 반영되고 있는 것을 볼 수 있습니다.

펜윅트리의 코드를 보시면 다음과 같습니다.

void update(vector<long long> &tree, int i, long long diff) {
    while (i < tree.size()) {
        tree[i] += diff;
        i += (i & -i);
    }
}

앞의 코드에서 만약 요소 3 즉, 1번째요소(펜윅트리를 만들 때는 0번째가 아니라 1번째요소 부터 만들어서 진행합니다.)

를 기반으로 펜윅트리를 만든다면 다음과 같은 과정을 거쳐서 트리가 만들어집니다.

tree[1] += 3

i += 1

tree[2] += 3

i += 2

tree[4] += 3

i += 4

종료.

즉, 이런식으로 1, 2, 4라는 인덱스를 가진 tree의 노드에 해당 값이 반영되는 것을 의미합니다.

또 질문 있으시면 언제든지 질문 부탁드립니다.

좋은 수강평과 별점 5점은 제가 큰 힘이 됩니다. :)

감사합니다.

강사 큰돌 올림.

인프런 커뮤니티 질문&답변