글 읽기 - 조건문에서 +1 의 차이 질문입니다.

his130 6년 전 1

최대힙 구하는 문제를 아래와 같이 pop , push 함수로 나눠서 나타냈습니다.

그런데 다름이 아니라

pop 함수의 for 문에서 i의 조건문을

i*2+1 <= last;

하니 틀렸습니다가 나왔습니다.

그리고 i*2<=last 로 하니 맞았습니다가 나왔습니다.

for문 안에서 가장 최대값까지 설정해줬는데 왜 두개가 다른지 잘 모르겠습니다...ㅠㅠ

#include<iostream>

using namespace std;

int N;
int last = 0;
int heap[100001];

void push(int n)
{
	heap[++last] = n;

	for (int i = last; i > 1; i /= 2)
	{
		if (heap[i] > heap[i / 2])
		{
			swap(heap[i], heap[i / 2]);
		}
		else
		{
			break;
		}
	}
}
void pop()
{
	printf("%d\n", heap[1]);

	if (last == 0)
	{
		return;
	}

	swap(heap[1], heap[last]);
	heap[last--] = 0;

	for (int i = 1; i*2+1 <= last;)
	{
		if (heap[i] > heap[i * 2] && heap[i] > heap[i * 2 + 1])
		{
			break;
		}
		else
		{
			if (heap[i * 2] > heap[i * 2 + 1])
			{
				swap(heap[i], heap[i * 2]);
				i = i * 2;
			}
			else
			{
				swap(heap[i], heap[i * 2+1]);
				i = i * 2 + 1;
			}
		}
	}


}

int main()
{
	cin >> N;
	for (int i = 0; i < N; i++)
	{
		int tmp;
		cin >> tmp;

		if (tmp == 0)
		{
			pop();
		}
		else if (tmp > 0)
		{
			push(tmp);
		}
	}

	return 0;
}

RiKang 6년 전 1

i의 자식이 1개일 때가 다릅니다.

i의 자식 노드중에서 i*2 는 존재하고, i*2+1 는 존재하지 않는 경우입니다.

그런 경우에도 heap[i*2] > heap[i] 라면 둘을 스왑해야 합니다.

위의 소스에서 i=1 , last = 2 인 경우를 생각해보면 heap[1] 과 heap[2] 를 비교해봐야 하는데, 그 전에 i*2+1<=last 에 걸려서 반복문이 그대로 끝나버립니다.

his130 6년 전 0

아하 그렇군요..

i*2 노드는 존재하지 않고 i*2+1 노드는 존재하는 경우는 없기 때문인거죠?

RiKang 6년 전 1

네, 힙의 구현 특성상 i*2+1 노드가 존재하면 i*2 노드도 존재하기 때문에

for 안에 들어가야할 ( 자식 노드가 존재하는가? ) 이런 조건이

자식 노드가 존재하는가?

-> 왼쪽 노드가 존재하는가? || 오른쪽 노드가 존재하는가?

-> i*2 노드가 존재하는가? || i*2+1 노드가 존재하는가?

-> i*2 <= last || i*2+1 <= last

-> i*2 <= last

이런식으로 단순화 되는 것 같습니다.

his130 6년 전 0

친절한 설명 정말 감사드립니다! 복받으세요

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

문제

문제

출처

ICPC

조건문에서 +1 의 차이 질문입니다.

his130 6년 전 1

RiKang 6년 전 1

his130 6년 전 0

RiKang 6년 전 1

his130 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말