[자료구조] 트리

트리의 개념 트리(tree)는 계층적인 자료를 표현하는데 적합한 자료구조이다. 트리의 구성 요소에 해당하는 A, B, C, D, E, F, G, H, I, J를 노드(Node)라 한다. 트리는 한 개이상의 노드로 이루어진 유한 집합이다. 이들 중 하나의 노드는 루트(root) 노드라 불리고 나머지 노드들은 서브 트리(subtree)라고 불린다. 계층적인 구조에서 가장 높은 곳에 있는 노드인 A가 루트가 된다. 위 노드에서 루트 노드는 A이고, 나머지 노드들은 {B, E, F}, {C, G}, {D, H, I}로 3개의 집합으로 나누어지는데 이들을 A의 서브트리라고 한다. 다시 서브 트리인 {B, E, F}의 루트는 B가 되고 나머지 노드들은 다시 2개의 서브 트리, 즉 {E}, {F}로 나누어진다. 트리..

[자료구조] 덱

덱(deque)은 double-ended queue의 줄임말로서 큐의 전단(front)과 후단(rear)에서 모두 삽입과 삭제가 가능한 큐를 의미한다. 그렇지만 여전히 중간에 삽입하거나 삭제하는 것은 허용하지 않는다. 덱의 추상자료형 객체 : n개의 element형의 요소들의 순서 있는 모임 연산 : create() ::= 덱을 생성한다. init(dq) ::= 덱을 초기화한다. is_empty(dq) ::= 덱이 공백 상태인지를 검사한다. is_full(dq) ::= 덱이 포화 상태인지를 검사한다. add_front(dq, e) ::= 덱의 앞에 요소를 추가한다. add_rear(dq, e) ::= 덱의 뒤에 요소를 추가한다. delete_front(dq) ::= 덱의 앞에 있는 요소를 반환한 다음 삭..

[자료구조] 큐

스택의경우, 나중에 들어온 데이터가 먼저 나가는 구조인데 반하여 큐(queue)는 먼저 들어온 데이터가 먼저 나가는 구조로 이러한 특성을 선입선출(FIFO: First-In First-Out)이라고 한다. 큐의 예로는 매표소에서 표를 사기 위해 늘어선 줄을 들 수 있겠다. 줄에 있는 사람들 중 가장 앞에 있는 사람(즉 가장 먼저 온 사람)이 가장 먼저 표를 사게 될 것이다. 나중에 온 사람들은 줄의 맨 뒤에 서야 할 것이다. 큐는 뒤에서 새로운 데이터가 추가되고 앞에서 데이터가 하나씩 삭제되는 구조를 가지고 있다. 구조상으로 큐가 스택과 다른 점은 스택의 경우, 삽입과 삭제가 같은 쪽에서 일어나지만 큐에서는 삽입과 삭제가 다른 쪽에서 일어난다는 것이다. 위의 그림과 같이, 큐에서 삽입이 일어나는 곳을 후..

[자료구조] 스택을 이용해 미로 탐색하기

위와 같은 6x6의 미로가 있을 때 도착 지점(4,5)까지 미로를 탐색하는 알고리즘은 다음과 같습니다. 현재 위치에서 이동이 가능한 칸들의 위치를 위, 아래, 왼쪽, 오른쪽의 순서로 스택에 저장합니다. 스택의 top 위치로 이동합니다. 위 과정을 반복합니다. 이동 가능한 위치를 모두 검사했거나, 현재의 위치가 도착 지점의 위치와 같다면 중단합니다. // 멤버 변수들 POINT m_MyPos;// 현재 내 위치 std::stack m_MovableStack;// 이동가능한 곳의 스택 bool m_IsEnd;// 도착 지점인지 enum class eMapAttr { S,// 시작 지점 O,// 이동 가능 X,// 이동 불가능 (벽) E,// 도착 지점 } // 스택에 원소가 있다면 (이동가능한 곳이 있다면)..

[자료구조] 스택

1. 스택이란? 책상에 쌓여있는 책, 창고에 쌓여있는 상자등이 스택의 전형적인 예이다. 새로운 상자를 쌓을 때는 상자더미의 맨 윗부분에 놓을 것이고, 상자가 필요하면 상자더미의 맨 위에 있는 상자를 꺼낼 것이다. 만약 중간에서 상자를 꺼내면 전체 상자 더미가 붕괴될 것이다. 따라서 가장 최근에 들어온 상자가 가장 위에 있게 되고, 또 먼저 나가게 된다. 이런 입출력 형태를 후입선출(LIFO : Last-In First-Out)이라고 한다. 스택에서의 입출력은 맨 위에서만 일어나고 스택의 중간에서는 데이터를 삭제할 수 없다. 위 그림처럼 스택에서 입출력이 이루어지는 부분을 스택 상단(stack top)이라 하고 반대쪽인 바닥부분을 스택 하단(stack bottom)이라고 한다. 스택에 저장되는 것을 요소(..

[자료구조] 배열

배열 배열의 개념 배열은 동일한 타입의 데이터를 한 번에 여러 개 만들 때 사용된다. 예를 들어서 6개의 정수를 저장할 공간이 필요한 경우, 배열이 없다면 다음과 같이 6개의 정수형의 변수를 선언하여야 할 것이다. int list1, list2, list3, list4, list5, list6 그러나 배열이 지원된다면 아주 간단하게 다음과 같이 선언하면 된다. int list[6] 배열을 사용하면 "연속적인 메모리 공간"이 할당되고 인덱스(index) 번호를 사용하여 쉽게 접근이 가능하기 때문에 반복 루프를 이용하여 여러가지 작업을 손쉽게 할 수 있다. 배열 ADT(추상 자료형) 배열을 추상 자료형으로 정의하여 보자. 즉 배열을 단순히 "연속적인 메모리 공간"으로만 보지 말고 배열의 핵심적인 내용을 추상..

[자료구조 알고리즘] 순환(재귀)

순환(재귀) 순환이란? 순환이란 어떤 알고리즘이나 함수가 자기 자신을 호출하여 문제를 해결하는 프로그래밍 기법이다. 예) 팩토리얼 int factorial(int n) { if( n 순환 호출을 하는 부분 } 순환 반복 프로그래밍 언어에서 되풀이하는 방법에는 반복(iteration)과 순환(recursion)의 2가지가 있다. 반복이란 for나 while등의 반복구조로 되풀이 하는 방법이다. 때로는 반복을 사용하게 되면 지나치게 복잡해지는 문제들도 존재한다. 이런 경우에는 순환이 좋은 해결책이 될 수 있다. 순환은 본질적으로 순환적(recursive)인 문제나 그러한 자료구조를 다루는 프로그램에 적합하다. 기본적으로 반복과 순환은 문제 해결 능력이 같으며 많은 경우에 순환 알고리즘을 반복 버전으로, 반복..

자료구조와 알고리즘 (2)

알고리즘의 성능 분석 - 수행시간 측정방법 가장 단순하지만 가장 확실한 방법은 알고리즘을 프로그래밍 언어로 작성하여 실제 컴퓨터상에서 실행시킨 다음, 그 수행시간을 측정하는 것이다. C언어에서 수행시간을 측정하는 방법에는 다음과 같이 2가지의 방법이 있다. [방법 1] #include start = clock(); ... stop = clock(); double duration = (double)(stop - start) / CLOCKS_PER_SEC; clock() 함수는 호출 프로세스에 의하여 사용된 CPU 시간을 계산한다. clock() 함수는 호출되었을 때의 시스템 시각을 CLOCKS_PER_SEC 단위로 반환한다. 따라서 초단위의 시간을 측정하기 위하여 (stop - start)값을 CLOCKS..