공부중

우선순위 큐에 적당한 것은 힙으로 결정이 되었다. 힙은 '트리 구조'이다. 트리를 구현하는 방법에는 배열과 연결 리스트 둘 중 하나를 선택 해야 하는데.. 앞에서 트리를 구성했을 때 연결 리스트로 구현을 하였으니 여기서도 똑같이 구현 하면 되겠지만 이와 같은 단점이 있다. "연결 리스트를 기반으로 힙을 구현시 새로운 노드를 힙의 마지막 위치에 추가하는 것이 쉽지 않다." 해결은 가능하고 사소하지만 간단한 문제가 아니다.. 배열 기반의 힙의 경우 이런 문제는 매우 간단하게 처리 된다. 그래서 '힙'같이 새로운 노드를 추가한 이후에도 완전 이진 트리를 유지해야 하는 경우 연결리스트가 아닌 배열을 기반으로 트리를 구현해야 한다. 배열을 기반으로 힙을 구현할 때 필요한 것은 다음과 같을 것이다. 왼쪽과 오른쪽 ..

큐는 연산의 결과로 먼저 들어간 데이터가 먼저 나오나 우선순위 큐는 다르다. 들어간 순서에 상관없이 우선순위가 높은 데이터가 먼저 나온다. 일상 예제로 병원의 응급실을 예로 들어보면 물론 모든 환자분들이 빠른 치료를 받고 완치가 되면 좋겟지만 제일 응급한 환자부터 치료를 하게 된다. 즉 우선순위가 높은 환자가 먼저 치료를 받는 것이다. 이렇게 우선순위 큐에서 중요한 것은 우선순위 이다. 데이터를 근거로 우선순위를 판단해야 되고 목적에 맞게 우선순위를 프로그래머가 판단해서 결정해야 되는 일이다. 우선순위가 다른 데이터 뿐만 아니라 같은 데이터가 존재할 수도 있다. 우선순위 큐를 구현하는 방법은 세 가지로 나뉘어진다. 배열을 기반으로 구현하는 방법 연결리스트를 기반으로 구현 하는 방법 힙(Heap)을 이용하..

힙(Heap)은 무엇인가를 차곡차곡 쌓아 올린 더미라는 뜻을 가지고 있다. 그런 뜻을 가진 힙(Heap)이.. 이 자료구조에서의 힙(Heap)은.. 간단히 정의를 내리자면 힙은 완전 이진 트리이다. 그리고 모든 노드에 저장된 값은 자식 노드에 저장된 값보다 크거나 같아야 한다. 루트노드에 저장된 값이 가장 커야 한다. 위 문장에서 말하는 형태의 이진트리는.. 다음 그림들과 같다. 위와 같이 루트 노드로 올라갈수록 값이 커지는 완전 이진 트리를 '최대 힙(Max Heap)' 이라 한다. 이번에는 루트 노드로 올라갈수록 저장된 값이 작아지는 완전 이진 트리를 '최소 힙(Min Heap)'이라 한다.

이진 트리의 경우도 배열과 리스트 2가지 방법으로 구현이 가능하다. 트리가 완성된 이후에는 매우 자주 탐색이 이루어 진다. 그래서 배열로 구성 해볼 만 하다. 배열을 기반으로 이진 트리를 구현하려면 노드에 고유의 노드 번호를 부여해야 한다. 이 번호들은 데이터가 저장되어야 할 배열의 인덱스 값이다. 인덱스가 0인 배열의 요소를 사용하지 않는 이유는 개인 차가 있겠지만 구현의 편의와 실수를 줄이기 위해서 일반적으로 사용하지 않는다. 다음은 연결리스트 기반의 구현방법이다. 그림만 봐도 단번에 이해가 될 만큼 쉽게 표현 가능하다. 그림에 나온대로 구성하면 되므로 별 다른 설명은 필요 하지 않을 것 같다.. 만약에.. 연결리스트로 이진 트리를 구현 했다고 했을시. "삭제는 어떻게 하겠는가?" 둘 이상의 노드로 ..

이번에는 이진 트리를 구현 해보기 전에.. 이진 트리는 뭔가용?? 매우 간단 하게 설명하면 위 그림처럼 자식 노드가 2개씩 달린 트리이다. 이진 트리는 다음 두 조건을 만족 해야 한다. 루트 노드를 중심으로 두 개의 서브 트리로 나뉘어진다.나뉘어진 두 서브 트리도 모두 이진 트리어야 한다. 그러면 다음 구조는 이진 트리가 맞을까?? 이것을 보고 이진 트리가 아닌거 같지만 이것도 이진 트리가 맞다 왜냐하면 이진 트리 관련해서 다음의 내용이 추가로 정의 되어있다. 노드가 위치할 수 있는 곳에 노드가 존재하지 않는다면 공집합(empty set)노드가 존재하는 것으로 간주 공집합 노드도 이진 트리의 판단에 있어서 노드로 인정! 그러므로 공집합까지 보이면 다음 그림과 같이 된다. 이러한 공집합 노드 때문에 서브 ..

이번에는 트리 자료 구조이다. 트리(Tree)는 말그대로 … 나무이다. 트리구조는 나무를 보고 나뭇가지가 쭉쭉 뻗어있는 모습이 연상되서 이름이 그렇게 지어진 것 같다. 이렇게 나뭇가지처럼 뻗은 모습이 연상 된다. 트리는 계층적 관계(Hierarchical Relationship)를 표현 한 자료 구조이다. 단순히 무엇인가 저장하고 꺼내는 것이 전부가 아닌 무엇인가 표현하는 것이다 단지 표현을 위해서 저장과 삭제라는 기능이 제공되어 있을 뿐 이다. 트리가 아래로 뻗으나 옆으로 뻗으나 중요치는 않다. 중요한 것은 가지가지를 늘려가며 뻗어간다는 사실이다. 이러한 구조도 트리 구조이다. 방향만 다르고 가지가 뻗어가는 모습은 같지 않은가? 일단 트리에 관해서 용어를 설명하자면 … 노드 node트리의 구성요소에 해..

이전 글에 이어서 원형 큐를 구현 해보겠습니다. Candy.h#pragma once enum eCandy { eRed = 1, eGreen, eBlack, }; class Candy { public: Candy(); virtual ~Candy(); virtual void SeeCandy() = 0; private: }; class CRedCandy : public Candy { public: CRedCandy(); virtual ~CRedCandy(); void SeeCandy(); private: }; class CGreenCandy : public Candy { public: CGreenCandy(); virtual ~CGreenCandy(); void SeeCandy(); private: }; cl..

이번에 보일 자료는 큐(Queue)이다. 큐는 바로 먼저 들어간 것이 먼저 나오는 선입선출(先入先出), FIFO(First-In, First-Out) 구조의 자료구조 이다. 큐도 스택과 같이 우리 주변에서 많이 살펴볼 수 있다. 예를 들자면.. 이런 주사기가 있겠고. 이렇게 줄서기 등등 스택과 같이 큐도 그렇게 어렵지 않은 개념의 자료구조 이다. 간단하게 생각하기에는 "뭐 스택에서 조금만 바꿔주면 큐가 되겟네?" 라고 생각할 수 있다. 그럼 일단 큐의 배열 구현 모델을 살펴보자 큐에 데이터를 삽입할 때를 표현해본 것이다 여기서 F는 Front의 약자이고 R은 Rear의 약자로 F는 큐의 맨 앞 머리, R은 큐의 맨 뒤 꼬리를 가리키는 것이다. 그리고 삭제할 때를 살펴보자 이 그림에서 보이는 방식은 F가 ..