힙 자료구조 힙 자료구조는 원소 값들 중에서 최대값과 최소값을 구하는데 효율적인 자료 구조를 의미합니다. 트리의 개념을 공부하고 싶으면 http://lktprogrammer.tistory.com/67 여기를 참조해주세요. 힙은 완전 이진 트리의 형태를 가지면서 동시에 다음과 같은 힙 성질을 만족해야 합니다. ● 부모노드가 자식노드보다 큰 경우 - 최대 힙 ● 부모노드가 자식노드보다 작은 경우 - 최소 힙 ▶ 이번 게시글에서는 최대 힙을 기준으로 설명 하겠습니다. 왼쪽 최대 힙을 보면 모두 부모 노드의 값이 자식 노드 값보다 큰 형태를 이루고 있습니다. 부모 노드 50의 경우 자식 노드 25와 40보다 크며, 부모 노드 25는 자식 노드 12와 14보다 큰 형태를 이루고 있습니다. 즉, 힙의 이러한 성질 ..

트리 (Tree) 계층적인 구조를 표현하기 위한 자료구조로 여러 노드가 한 노드를 가리킬 수 없는 구조를 의미합니다. 일반적으로 조직도, 디렉토리 구조등을 생각하면 됩니다. 스택이나 큐와 같은 선형구조가 아닌 뒤집어놓은 나무 모양 같은 계층구조를 가지며, 탐색이나 계층적 구조를 가져야 하는 데이터를 다루는데 많이 사용됩니다. 트리의 특징 ▶ 트리는 노드(A,B,C,D,E,F)와 노드들 사이를 이어주는 링크로 이루어져 있습니다. 트리의 노드가 n개라면 링크의 개수는 n-1개가 됩니다. 최상위 노드 A를 루트 노트라고 부르며 B,C를 가지노드라 하며 D,E,F와 같이 자식을 가지지 않는 최하위 노드들을 리프노드라고 부릅니다. ▶ 트리는 기본적으로 부모-자식 관계를 가집니다. A노드 입장에서는 B,C의 자식 ..

원형큐 (Circular Queue) 원형 큐는 선형 큐의 문제점을 보완하기 위한 자료구조입니다. 앞선 포스팅에서 선형큐의 문제점은 rear이 가르키는 포인터가 배열의 마지막 인덱스를 가르키고 있을 때 앞쪽에서 Dequeue로 발생한 배열의 빈 공간을 활용 할 수가 없었습니다. 원형큐에서는 포인터 증가 방식이 (rear+1)%arraysize 형식으로 변환하기 때문에 배열의 첫 인덱스부터 다시 데이터의 삽입이 가능해집니다. ■ Enqueue rear의 포인터를 1증가 시키고 그 위치에 데이터 삽입이 이루어집니다. 만약 rear+1이 배열의 끝이고 포화상태가 아니라면 배열의 첫 번째 인덱스에 데이터를 삽입합니다. → 배열의 포화상태 여부를 판단하기 위하여 배열의 1칸은 비워둡니다. (rear+1)%arra..

선형 큐 (Linear Queue) 큐는 가장 먼저 들어온 데이터가 가장 먼저 내보내지는 (FIFO : First In First Out) 구조를 가집니다. 선형 큐는 데이터를 집어넣는 Enqueue 기능과 데이터를 내보내는 Dequeue 기능을 제공합니다. ■Enqueue 기능 Enqueue는 큐 자료구조에 데이터를 집어 넣는 기능을 수행합니다. 영화 매표소에 사람들이 줄을 선다고 생각해봅니다. 이때 매표소 가장 앞사람을 가르키는 것을 front라 하고 마지막에 서있는 사람을 가르키는 것을 rear이라고 부릅니다. 1번이 Enqueue 되어진 상태입니다. 첫 번째로 줄을 선 사람이므로 front와 rear이 둘다 1번을 가르키고 있습니다. 다음으로 2번이 Enqueue 기능을 수행 한 상태입니다. Fr..

스택 (Stack) 스택(Stack)은 한 쪽 끝에서만 자료를 넣거나 뺄 수 있는 선형 구조(LIFO- Last In First Out)으로 되어있습니다. 자료를 넣는 것을 PUSH라고 하고 넣어둔 자료를 꺼내는 것을 POP이라고 합니다. ■ 스택 입/출력 방식 실제로 스택이 어떤 식으로 자료가 입/출력 되는지 살펴 보겠습니다. 상자안에 책을 쌓는다고 생각을 하면 됩니다. 즉 가장 먼저 넣은 책은 가장 나중에 꺼낼 수 있으며, 가장 최근에 넣은 책을 가장 먼저 뺄수 있습니다. 가장 먼저 5를 PUSH 합니다. 스택 자료 구조에 가장 아래에 위치하게 됩니다. 차례대로 PUSH 4, PUSH 3을 한 결과입니다. POP 2회를 실시하게 되면 출력 결과는 3,4가 됩니다. 즉 3은 가장 나중에 입력 되었지만 ..