개요

이번에 한 알고리즘 풀이에 사용되어서 공부하게 됐다.

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

특징

힙은 이진트리의 종류중 하나이고 최대 힙, 최소 힙 으로 나누어져 있고

루트 노드가 언제나 그 트리의 최대값 혹은 최소값을 가진다는 특성이 있다.

이는 루트 노드 뿐만 아니라

루트노드가 최대값이라면 모든 노드가 자기 자식 노드보다 큰 값을 가지고 있고 = 최대 트리

루트노드가 최소값이라면 모든 노드가 자기 자식 노드보다 작은 값을 가지고 있다. = 최소 트리

또한 완전 이진 트리어야 한다. 중간에 빈 노드가 없다는게 중요!

그래서 완전 이진 트리이기 때문에 배열로 구현하는게 정말 효율적이다.

배열로 구현하는게 정말 효율적이다 :

● 자기의 Index로 자식의 Index를 알수있고 그 반대도 가능하다

● 또한 특정 레벨의 최대 노드 개수도 간단히 구할 수 있다.

●

배열의 단점인 중간에 값을 삽입하는 일이 없다.● 인덱스 순서대로 삽입하면 트리가 기울어질일이 없다.

주의 할 것은 이 힙은 최대, 최소에 중점을 두었기 때문에

그 나머지 노드에 대해서는 느슨한 정렬 상태를 유지한다. [이진 탐색 불가능]

최대 트리여도 하위 레벨 노드보다 작을수도, 최소 트리라면 하위 레벨 노드보다 클 수도 있다는 말이다.

암튼 정리하면

최대 힙 = 최대 트리 + 완전 이진 트리

최소 힙 = 최소 트리 + 완전 이진 트리

왜 사용하는가?

오직 어떤 최소값이나 최대값을 얻고 싶다면 리스트나 배열을 한번 정렬해서 앞에서 쭉 가져오면 된다.

하지만 어떤 데이터가 추가되어 다시 정렬 후 최대, 최소 값을 가져올때 이 힙이 굉장히 강력한데

힙을 이용한 priority_queue과 퀵정렬을 사용하여 실험해 보았다.

데이터를 계속 추가하면서 내림차순으로 정렬하여 최대값을 출력한다.

암튼 데이터의 추가,삭제가 빈번할 때 최대, 최소 값을 얻고자 할 때 사용해야겠다 !

구현

생성 & 소멸

Private 멤버

데이터 삽입

데이터 삭제

결론

사용처

언리얼에서 포스트 프로세스라는 기능이 있는데 여기서 우선 순위를 정하여 렌더링 순서를 정할 수 가 있다.

이때 힙을 이용하면 편리할거 같다.

나머지는 또 생각해봐야겠다.

추가

stl::prioirity_queue & stl::make_heap

더보기

stl에 저 두가지가 비슷하게 쓰이는데

N3337에서 priority_queue은 힙으로 구현되고 생성자로 make_heap이 사용 된다고 한다.

 

 코드 내 주석으로 보면 복사나 이동이 필요할때 make_heap이 사용된다.

 

가장 뚜렷한 차이는

make_heap같은 경우는 이미 있던 컨테이너를 힙구조로 만들기때문에

루트 노드 뿐만아니라 다른 노드에도 접근이 가능할수도 있다는 것과

 

priority_queue같은 경우는 어댑터 클래스로 public한 함수가 루트 노드에만 접근이 가능하다는 점이 있다.

어떻게 보면 힙의 캡슐화 같은 느낌이 더 강하게 든다.

 

https://stackoverflow.com/questions/11266360/when-should-i-use-make-heap-vs-priority-queue

 

When should I use make_heap vs. Priority Queue?

I have a vector that I want to use to create a heap. I'm not sure if I should use the C++ make_heap function or put my vector in a priority queue? Which is better in terms of performance? When shou...

stackoverflow.com

https://leeminju531.tistory.com/20?category=979284 

 

(C++ STL) priority_queue, make_heap 제대로 이해하기(1)

http://www.cplusplus.com/reference/algorithm/make_heap/ make_heap - C++ Reference custom (2)template void make_heap (RandomAccessIterator first, RandomAccessIterator last, Compare comp ); www.cplusp..

leeminju531.tistory.com

개요

스택 알고리즘 풀이 하는 김에 좀 더 공부해봤다.

개념

불연속적인 메모리로 Last in first out 을 가진다.

[Top of pointer을 가지고있음]

구현

array형식으로도 구현가능하고 linked list로도 구현 가능하여 각 장,단점을 생각해 보았다.

array로 구현시

● 추가 메모리가 요구 되지 않는다.

● 먼저 array의 강력한 장점인 인덱스로 값을 찾는것이 stack에서는 그렇게 필요하지 않다고 느꼈다

어차피 맨 위의 데이터만 사용하려고 하는 것이기 때문이다.

● 크기에 대한 번거로운 과정이 있을 것이다(새로 할당받고 복사하고 원 메모리 반환)

그에 딸려오는 단편화 문제

Linked list로 구현시

● 임의의 위치에 데이터를 추가,삭제 하는 기능이 없기 때문에 이러한 장점을 살릴 수 없다.

● 크기에 제약이 없다!

● 옆의 노드의 주소를 저장 할 공간이 추가 요구 됨

● 맨 위의 데이터만을 참고 한다는 스택의 특징이 랜덤 액세스가 불가능한 연결리스트의 단점을 커버 해줌

나는 무난한 배열로 구현을 해보겠다.

생성 & 소멸 & 멤버 변수

#include <iostream>
using namespace std;
#define INIT_STACK_SIZE 10

template<typename T>
class Stack
{
public:

	Stack()
	{
		data = new T[INIT_STACK_SIZE];
		capacity = INIT_STACK_SIZE;
		topIndex = -1;
	}
	~Stack()
	{
		delete[] data;
		data = nullptr;
	}
    
    
/************생략************/
                                        

private:
	//스택에 넣을 데이터를 담을 포인터 형
	T * data;
	//맨 위의 인덱스
	int topIndex;
	//스택의 총 메모리 양
	int capacity;
};

데이터 삽입 (Push)

	void Push(T input)
	{
		++topIndex;
		if (capacity <= topIndex)
		{
			T * temp = new T[capacity * 2];
			memcpy(temp, data, sizeof(int) * capacity);
			delete[] data;
			data = temp;
			capacity *= 2;
		}
		data[topIndex] = input;
	}

배열이기 때문에 크기에 대한 처리를 따로 해주었다.

데이터 삭제 (Pop)

	void Pop()
	{
		if (IsEmpty() == true) return;
		--topIndex;
	}

맨 위의 데이터 꺼내기 (Top)

	T Top()
	{
		if (IsEmpty() == true) return -1;
		return data[topIndex];
	}

여기서 예외설정을 안해서 알고리즘에서 틀렸었다 😂

사용처

맨 위의 데이터를 다룬다는 것에 대하여 게임의 네비게이션에서 사용 할 수 있을거 같다.

이는 여태 시도하는 경로를 스택에 쌓아둠과 동시에 틀릴 경우 맨위부터 다시 돌아가 다른 경로를 탐색함에 있어서

LIFO인 스택과 같아 잘 맞는다.

[나중에 깊이 우선 탐색이라는 알고리즘이 이와 같다고한다?]

또한 상점에서 거래를 이전으로 돌리는 기능을 구현 할 수 있을 것 같다.(ctrl + z 처럼)

롤에서 상점에서 구매했던 것이나 팔았던 행위를 되돌릴 수 있는 것처럼!

또 다른 이용은 아직 데이터를 뒤집을때 편할듯 하다.

스택 프레임이란 개념도 있는데

함수가 호출될 때, 그 함수만의 스택 영역을 구분하기 위하여 생성되는 공간이라 한다.

그렇기에 함수 호출시에 생성되고 함수가 종료되면서 소멸한다.

이 공간에는 함수와 관계되는 지역 변수가 저장된다고 한다.

암튼 그렇다 ㅋㅋ

특징

노드 컨테이너로 이루어져 있다

탐색의 경우 처음부터 끝까지 하나씩 탐색해야하기 때문에 O(n)

=>인덱스를 지원하기 하지 않기 때문에 랜덤한 접근이 불가능하다

데이터의 어느곳이든지 삽입 삭제가 빠르다 O(1)

=>순서 변경도 마찬가지

컨테이너의 크기가 고정이 아닌 동적으로 이루어진다

근데 이 또한 vector처럼 동적할당으로 이루어지는데

자주 크기가 조정 될 시에 메모리단편화라는 단점이 거론되지 않는가 궁금했다.

추측인데 vector는 데이터가 메모리에 연속적으로 있어야 하지만

List는 각 데이터 하나 하나가 꼭 붙어 있지 않아도 되기에 미리 나누어져있는 메모리를 할당받을 확률이 높다고 생각한다.

※캐시라인이라는 개념으로 vector와 비교되는데 나중에 다시 찾아보기

결론

연결 리스트도 vector와 마찬가지로 가변성이 가장 큰 특징이라 생각이 들어

vector와 차이를 많이 못느꼈었는데

어느곳에서나 데이터의 삽입 삭제에 빠르며 메모리의 크기 조정 또한 빠르다

"변화에 강함" 이게 핵심인거 같다.

사용처

[작성중]

그 아이템 뺑뺑이 돌아가는거

특징

연속된 컨테이너를 가지고있다( = 메모리상 연속적으로 저장이 됨 )

탐색의 경우 처음부터 끝까지 하나씩 탐색해야하기 때문에 O(n)

인덱스를 지원하기때문에 랜덤한 접근은 빠르다(조회) O(1)

데이터의 끝부분에 삽입, 삭제는 빠르다. amortized O(1)

[ 삽입시 메모리를 다시 동적할당 받아올 경우 n개만큼 복사가 이루어지기때문에 이 상황에는 O(n) ]

하지만 중간에 삽입, 삭제시에는 그 뒤에 있는 모든 데이터를(n) 한칸씩 앞이나 뒤로 복사가 이루어져 느리다. O(n)

컨테이너의 크기가 고정이 아닌 동적으로 이루어진다

하지만 크기가 자주 변경된다면 불리한 자료구조이다.

=> 잦은 동적할당과 해제 => 메모리 단편화가 발생 할 소지가 많다.

결론

크기가 변할 가능성이 있으나 자주는 아닌 경우,

인덱스를 이용한 접근을 사용하는 경우,

처음부터 쭉 순회를 해야할 경우,

중간 삽입,삭제가 적을 경우

vector를 사용할것이다.

사용처

만약 내 게임에서 사용 한다면

게임 내의 모든 아이템 데이터를 담는 자료구조로 vector를 사용할거 같다.

아이템은 거의 꾸준히 업데이트 되기 때문에 가변적 특성을 띄고

꼭 순차하여 아이템 정보를 가져오는게 아닌

인덱스를 통해 원하는 아이템정보를 가져올 수 있기 때문이다.

플레이어의 분신같은 스킬을 사용할때

각 분신을 vector에 넣을거 같다.

이 스킬에 분신의 개수가 변경될 가능성이 있다고 생각하기 때문에 가변적 특성을 띄고

분신이 나타나고 사라지기 전까지 분신이 추가되는 중간 삽입,삭제가 없어 잘 맞는다고 생각했다.

한 맵에서 출현하는 몬스터들의 데이터를 저장할거 같다.

출현하는 몬스터의 수는 거의 고정적이지만 이벤트성이나 다른 몬스터의 추가로 수정 될 수 있다고 생각하였고

중간에 삽입 삭제할 경우가 없다고 생각이 들어 vector가 적당하다 생각했다.

추가

vector의 순회 속도

더보기

 

https://m.blog.naver.com/PostView.naver?isHttpsRedirect=true&blogId=4roring&logNo=221337048963

이 글과 비슷하게 나도 데이터를 순회 하는데 있어서 밑의 5가지 방법을 테스트 해봤다

1. 함수 at 사용

2. operator [ ] 사용

3. 주소를 직접받아 연산해 순회

4. iterator 사용

5. 범위기반 for문 사용

 

20,000,000개의 데이터를 순회하면서 int형 변수 result에 계속 더하여 테스트했다.

느낀 점

 

1.

이번에 찾아보면서 at과 [ ]를 비교하는 글이 많았었다.

at은 out of range 검사를 해주지만

[ ]은 검사를 하지 않기때문에 at보다 빠르다고 많이들 적혀있었는데

평균적으로 debug모드에서는 정말 차이가 없고 release모드에서만 차이가 확실히 났다.

 

2.

iterator를 사용한 경우 debug모드에서는 굉장히 느렸지만 release모드에서는 굉장히빠른 모습을 보였다

반전매력 ㄷㄷ

 

3.

다른 결과값이 나오기 전까지 vector를 순회할때는 range based for문을 사용해야겠다

 

4.

그래도 이 테스트는 절대적인 성능이 아니라 대략적으로 파악하기 위한거니

상황이 달라지면 결과도 바뀔수있기에 일반화하지 말자

 

코드 부분

왜 Index로 인한 조회는 O(1)?