[강의] 11월 27일 수업정리

다른 방식으로 이진 검색 알고리즘, 힙 구조에 대한 간단한 내용에 대한 수업을 들었다.

 

1. 이진 검색 

1.1 배열 초기화에 대한 오해 

배열의 초기화와 관련하여 오해하는 부분이 존재한다.

특히, 배열의 인덱스를 -1로 초기화하는 경우가 이에 해당이 되는데. 요세는 배열의 0번지를 의도적으로 비워두고 "값 없음" 으로 있고 없고를 판단하는 방식으로 사용한다.

하지만 -1로 초기화를 하는 경우 조건이 존재하는데 일반 int형이 아닌 unsigned int형을 사용해야한다. 이것이 핵심이다.

 

1.2 low, high를 이용하여 이진 검색 

#include <iostream>

int main()
{
	int arData[40]{};

	for (int i = 0; i < 40; i++)
	{
		arData[i] = i * 2;
	}

	int nData{};
	scanf_s("%d", &nData);

	int* pData = arData;
	int nLow = 0;
	int nHigh = 39;
	int nMiddle{}; 
	bool nFind{};

	while (nHigh >= nLow && !nFind)
	{
		nMiddle = (nLow + nHigh) / 2;
		if (pData[nMiddle] < nData)
			nLow = nMiddle + 1;
		else if (pData[nMiddle] > nData)
			nHigh = nMiddle - 1;
		else
			nFind = true;
	}

	if (nFind)
		printf("nIndex : %d\n", nMiddle);
	else
		printf("실패\n");
}

 

1.3 함수화

#include <iostream>

bool binaySearch(int *pData, int nLow, int nHigh, int nData, int &nIndex);

int main()
{
	int arData[40]{};

	for (int i = 0; i < 40; i++)
	{
		arData[i] = i * 2;
	}

	int nData{};
	int nResult{};
	scanf_s("%d", &nData);


	if (binaySearch(arData, 0, 39, nData, nResult))
		printf("nIndex : %d\n", nResult);
	else
		printf("실패\n");
}

bool binaySearch(int* pData, int nLow, int nHigh, int nData, int& nIndex)
{
	int nMiddle{};
	bool nFind{};

	while (nHigh >= nLow && !nFind)
	{
		nMiddle = (nLow + nHigh) / 2;
		if (pData[nMiddle] < nData)
			nLow = nMiddle + 1;
		else if (pData[nMiddle] > nData)
			nHigh = nMiddle - 1;
		else
			nFind = true;
	}

	nIndex = nMiddle;
	return nFind;
}

 

1.4 재귀 함수

#include <iostream>

bool binaySearch(int* pData, int nLow, int nHigh, int nData, int& nIndex);

int main()
{
	int arData[40]{};

	for (int i = 0; i < 40; i++)
	{
		arData[i] = i * 2;
	}

	int nData{};
	int nResult{};
	scanf_s("%d", &nData);


	if (binaySearch(arData, 0, 39, nData, nResult))
		printf("nIndex : %d\n", nResult);
	else
		printf("실패\n");
}

bool binaySearch(int* pData, int nLow, int nHigh, int nData, int& nIndex)
{

	if (nHigh < nLow)
		return false;

	int nMiddle = (nLow + nHigh) / 2;

	if (pData[nMiddle] < nData)
		return binaySearch(pData, nMiddle + 1, nHigh, nData, nIndex);
	else if (pData[nMiddle] > nData)
		return binaySearch(pData, nLow, nMiddle - 1, nData, nIndex);

	nIndex = nMiddle;
	return true;
}

 

2. HEAP 구조

HEAP구조는 데이터에서 최댓값과 최솟값을 빠르게 찾기 위해 고안된 완전 이진 트리이며 시간 복잡도가 O(log n)인 자료구조이다.

이는 특정 변종 ArrayList와 유사하며, 이전 데이터에 특정 조작이 이루어질 수 있다.

HEAP구조는 일반적으로 배열의 0번지를 사용하지 않는다. 이를 통해 "있다 / 없다"를 판단하거나, 계산을 간소화하기 위한 목적으로 1번 인덱스 부터 데이터를 저장한다.

 

힙에서 노드 간 관계는 다음과 같은 규칙이 존재한다.

• 왼쪽 자식 노드: n * 2
• 오른쪽 자식 노드: n * 2 + 1
• 부모 노드: n / 2 (n은 현재 노드의 인덱스이며, 정수 나눗셈 기준)