inflearn logo
강의

강의

N
챌린지

챌린지

멘토링

멘토링

N
클립

클립

로드맵

로드맵

지식공유

[C#과 유니티로 만드는 MMORPG 게임 개발 시리즈] Part2: 자료구조와 알고리즘

우선순위 큐

이 부분이 이해가 잘 안갑니다

해결된 질문

274

Hyobin Kim

작성한 질문수 81

0

        public int Pop()
        {
            // Create a variable storing the return value
            int ret = _heap[0];

            // Rearrange the Heap since the root node is removed
            // move the very last data into the root node
            int lastIndex = _heap.Count - 1;
            _heap[0] = _heap[lastIndex];
            _heap.RemoveAt(lastIndex);
            lastIndex--;

            // Value comparision downwards begins
            // the index of the current node
            int now = 0;
            while(true)
            {
                // the indices of the child nodes
                int left = 2 * now + 1;
                int right = 2 * now + 2;

                int next = now;

                // move to the left if the left value is bigger
                if (left < lastIndex && _heap[next] < _heap[left])
                    next = left;
                // move to the right if the right value is bigger, which contains the previous case as well (that's why it's not else if)
                if (right < lastIndex && _heap[next] < _heap[right])
                    next = right;
                // Exit the loop if the left/right values are smaller than the current value
                if (next == now)
                    break;

                // Exchange the values
                int temp = _heap[now];
                _heap[now] = _heap[next];
                _heap[next] = temp;

                // Move to the next index
                now = next;
            }

            return ret;
        }

우선순위큐의 Pop 함수에서, 

저기 if 구문 3개가 나오는 부분에서 어째서 else if를 쓰지 않는 것인지 이해가 쉽사리 되지가 않습니다

C#

답변 7

1

Rookiss

왼쪽/오른쪽 두 값 모두 현재값보다 크면,
무조건 왼쪽으로 가는게 아니라
왼쪽/오른쪽 중에서 더 큰쪽으로 이동해야 하기 때문입니다.

첫 if는 왼쪽과 비교해서 더 크면 왼쪽으로 이동하는 구문인데,
끝판왕이 오른쪽인 상황이 있다면 왼쪽 이동을 취소하고
오른쪽으로 다시 마음을 다잡기 위해 한 번 더 비교를 해주고 있습니다.

0

Hyobin Kim

정말 그렇네요

뭐랄까 이전에도 이와 비슷한 경우가 있었던거 같은데

이 처럼 코드에서 보여지는 거 외에 뭔가 더 생각해봐야 될 게 있는 경우는 시간이 걸리네요 이해하기 까지

그래도 감사합니다!

0

Rookiss

만약에 now 값보다 left값, right값 둘다 크다면,
무조건 오른쪽으로 진행하도록 짜여진거라고 보면 되는군요?

-> 그렇지 않습니다.
코드를 유심히 보면 둘 다 now보다 클 경우
left, right 중에 더 큰 쪽으로 이동하게 되어 있습니다.

next = left로 먼저 왼쪽으로 이동하게 설정한 다음,
다음 if에서 _heap[next]와 _heap[right]을 비교하니
만약 여기서 left다 더 크면 끝나고
아니면 next = right을 하게 됩니다.

0

Hyobin Kim

만약에 now 값보다 left값, right값 둘다 크다면,

무조건 오른쪽으로 진행하도록 짜여진거라고 보면 되는군요?

이래도  되는 이유는 이진트리와는 다르게 왼쪽 오른쪽 상관없이 차일드 노드의 값이 더 작기만 하면 되고, 항상 왼쪽부터 채워진다는 특성들 때문인가요?

0

Rookiss

어느쪽이 더 큰지는 굳이 기억할 필요 없습니다!
어차피 now에 둘 중 큰 값이 들어가 있을테니,
나머지 로직은 동일하게 실행될겁니다.

0

Hyobin Kim

덮어쓰기 인거네요

그런데 저렇게 되면 왼쪽/오른쪽 중 어디가 더 큰건지는 모르게 되는거 아닌가요?

0

Rookiss

물론 if가 연속해서 나오는게 싫다면,
먼저 왼쪽/오른쪽 중 더 큰 값이 어느쪽인지를 구한 다음
그 부분과 now를 비교해서 한 번에 처리하는 것도 괜찮습니다.

게임개발에서 주로 어느부분에 알고리즘들이 쓰이는지 궁금합니다

0

170

2

글꼴 바꿔도 자간이 좁아 찌그러져보이시는 분들

0

86

1

NullReferenceException 예외) 같은 실수하시는분 계실까봐 남겨요

0

66

1

parent를 Pos타입으로 만든 이유

0

74

1

콘솔창에 격자가 안나옴 미로 생성 X

0

133

1

격자 생성 안됨 무한루프

0

113

1

BFS 질문

0

143

2

격자 무한 출력

0

166

2

A* 의 PriorityQueue 관련 질문입니다

0

155

2

vscode에서 원그리기

0

179

1

환결설정 강의 원 그리기

0

122

1

15-17분

0

86

1

3:16초에 근데 이렇게 해가지고 부분에 "{}"를 만들어서 자식 node들을 생성하던데 왜 중괄호로 감싸게 만드는 건가요?

0

141

2

동적 배열 관련 질문입니다!

0

209

1

Big-o 표기법에서 시간 복잡도

0

167

1

7:40에서 언급하신 색상이 날아가는 문제 이해를 못하겠습니다

0

151

1

트리구현연습 강의 질문있어요

0

142

1

창은 뜨는데 맵이 나타나지 않아요.

0

174

1

Ctrl F5 하면 나오는 창은 어디서 설정할까요??

0

271

1

void CalcPathFromParent(Pos[,] parent)에 대해서

0

202

2

NullReferenceException예외가 발생했을때 어떻게 해야하나요?

0

228

1

[해결] 환경설정 강의에서 원이 이상하게 그려지는 문제

3

308

2

오른손 법칙에서 플레이어 점이 안 움직입니다

0

243

2

맵 만들기 오류

0

178

1