Hello World!

힙과 우선순위 큐 1. 우선순위 큐 Priority Queue(우선순위 큐)는 우선순위를 가진 원소들을 저장하고 우선순위가 높을수록 먼저 출력하는 자료구조이다. 우선순위 큐의 ADT를 살펴봤을 때 핵심적인 기능으로는 '삽입, (우선순위 제일 높은 원소) 삭제, (우선순위 제일 높은 원소) 반환'이 있다. 우선순위 큐는 여러가지 방법으로 구현이 가능하다. 1) 비정렬 시퀀스를 이용한 구현 우선순위 큐를 비정렬 시퀀스를 이용해 구현하는 경우 삽입은 간단하다. 비정렬 시퀀스이므로 시퀀스의 마지막에 삽입하고자 하는 원소를 담은 노드를 매달아 주면 된다. O(1)의 시간이 걸릴 뿐이다. n개의 모든 원소 삽입에 대해 O(1)이 시간이 걸리므로 총 O(n)의 시간이 걸린다. 하지만 우선순위 제일 높은 원소를 찾아 ..

Tree 1. Tree traversal Tree traversal(트리 순회)는 트리 구조에서 각각의 노드를 정확히 한번만, 체계적인 방법으로 방문하는 과정을 말한다. 앞서 살펴보았던 연결 리스트와 1차원 배열과 같은 선형 자료구조와 달리 트리는 순회에 많은 방법이 존재한다. 노드를 방문하는 순서에 따라 크게 4가지로 분류하여 설명할 예정이다. 1) preorder traversal(전위 순회) 전위 순회의 경우 노드 -> 제일 왼쪽 서브 트리 전위 순회 -> ... -> 제일 오른쪽 서브 트리의 전위 순회 순서로 진행된다. 위의 트리에서 전위 순회를 할 경우 a -> c -> h -> r -> l -> d -> x 의 순서로 노드를 방문하게 된다. 전위 순회는 depth-first traversal(..

Tree 1. Tree의 정의 및 관련 용어 Tree(트리)는 root라고 불리는 지정된 노드가 있고, root를 제외한 모든 노드가 유일한 부모 노드를 가지는 그래프의 일종이다. 관련 용어 - node(노드): 트리의 구성 요소 - edge(간선): 노드와 노드를 연결하는 연결선 - root node: 트리 구조에서 최상위에 존재하는 노드 - internal node(내부 노드): 잎 노드가 아닌 모든 노드 - leaf node(잎 노드): 자식 노드가 없는 노드 - depth(깊이): 자신을 제외한 조상 노드의 개수 - node의 height(높이): (해당 node가 leaf node면 0) 해당 노드의 자식의 height 중 가장 높은 값 + 1 - Tree의 height(높이): 해당 트리의 루..

Array and Linked List 1. Array Array(배열)은 동일한 자료형의 원소들을 순서 있게 저장하는 자료구조이다. 순서 있다는 말이 배열 안의 원소들이 정렬되어야 한다는 의미가 아니다. 배열은 선형 자료구조로 값의 번호가 곧 배열의 시작점으로부터 값이 저장되어 있는 상대적인 위치가 된다. 이를 '순서 있다'라고 표현한 것이고, 각 원소들은 index를 통해 접근 가능하다. 이는 O(1), 즉 상수시간이 걸리므로 원소에 대한 접근이 빠르다는 점이 배열의 장점 중 하나이다. 배열은 일반적으로 정적 할당을 하게 되는데, 이 경우 처음 배열 선언시 지정한 크기만큼만 사용할 수 있다. 만약 지정한 크기보다 더 많은 원소들을 저장할 필요가 있으면, 크기가 더 큰 새로운 배열을 선언 후 기존의 원..

queue 1. queue queue(큐)는 출구와 입구가 양쪽에 각각 있는 선형 자료구조이다. 즉, front에 데이터를 삽입하면 rear에서 빠져나온다. 이는 큐의 FIFO(First In First Out) 성질을 보장해주는데 먼저 들어간 데이터가 먼저 나온다는 뜻이다. 큐의 구조는 아래 그림과 같다. 이제 그림을 통해 삽입 과정을 이해해보자. int형 데이터를 담는 큐에 5, 4, 2, 1을 순서대로 push해보자. 제일 먼저 들어간 5가 rear, 제일 마지막에 들어간 1이 front에 위치하고 있다. 그렇다면 처음 삭제 연산이 수행됐을 때 삭제되는 원소는 무엇일까? rear에 위치하는, 즉 가장 먼저 들어온 5이다. 만약 삭제 연산이 2번 연속 수행된다면 5와 4가 차례로 삭제되고, 큐는 아래..

stack 1. stack stack(스택)은 출입구가 하나로 통일된 선형 자료구조이다. 즉, 데이터의 삽입 및 삭제가 한 곳에서만 일어난다. 스택은 위의 그림처럼 한 쪽(우리는 이를 top이라 부른다)만 뚫려 있는 기다란 통과 같은 구조이다. 그림을 통해 삽입 과정을 이해해보자. int형 데이터를 담는 스택에 차례로 5, 4, 2, 1을 삽입해보자. 입구가 하나이므로 삽입하는 순서대로 그림처럼 스택에 쌓일 것이다. 제일 위에 있는 원소 1은 당연히 제일 마지막에 삽입한 원소이다. 이 원소의 위치를 스택의 top이라 부른다. 만약 다음과 같은 스택에서 2에 바로 접근할 수 있을까? 안된다. 2에 접근하기 위해서는 위에 쌓여있는 1을 빼내야만 한다. 1을 빼내고 나면 그다음 원소 2가 top에 위치한다. ..