07 트리 Tree 출처 C언어로 쉽게 풀어쓴 자료구조(천인국, 공용해, 하상호 저) 목차 트리의 개념 1-1. 트리란 1-2. 트리의 표현방법 트리의 종류 2-1. 이진 트리 2-2. 이진 탐색 트리 트리의 순회 3-1. 전위순회 3-2. 중위순회 3-3. 후위순회 트리의 구현 4-1. 이진 트리 구현 4-2. 이진 탐색 트리 구현 1. 트리의 개념 1-1. 트리란? 트리는 리스트, 스택, 큐와 같은 선형 자료 구조가 아닌 계층적인 특징을 가지고 있는 비선형 자료 구조이다. 트리라고 부르는 이유는 나무를 엎어놓은 것과 같은 모양새를 하고 있어 그 이름이 붙게 되었다. 트리를 이해하기 위해 필요한 용어 노드(node): 트리의 구성요소 간선(edge): 노드를 연결하는 선 루트(root): 부모가 없는 ..
06 연결리스트2 Linked List 목차 연결리스트 응용 1-1. 다항식 계산 1-2. 연결리스트 스택 1-3. 연결리스트 큐 원형 연결리스트 2-1. 원형 연결리스트란? 2-2. 원형 연결리스트 구현 이중 연결리스트 3-1. 이중 연결리스트란? 3-2. 이중 연결리스트구현 1. 연결리스트 응용 1-1. 다항식 계산 2개의 다항식을 더하는 덧셈 연산을 구현한다. 헤더노드를 통해 head부분과 tail부분을 따로 관리해 다항식 연산을 좀 더 효율적으로 할 수 있다. 코드 링크: 다항식 계산 1-2. 연결리스트 스택 링크드리스트로 스택을 구현했다. top을 이용해 스택을 관리한다. heap영역이 허용하는한 스택노드를 계속해서 생성할 수 있고, 노드를 이용한다는 점만 빼면 행렬구조체를 이용한 스택과 거의 ..
05 연결리스트 Linked List 출처 C언어로 쉽게 풀어쓴 자료구조(천인국, 공용해, 하상호 저) 1. 연결리스트의 개념 1-1. 리스트란? 리스트는 자료를 정리하는 방법 중의 하나로, 할일 목록 등과 같은 것들을 관리할 때 쓰이는 자료구조이다. 리스트는 항목이 차례대로 저장되어 있으며, 각 항목들은 순서와 위치를 가지고 있다. 1-2. 연결리스트의 기능 리스트의 기능는 삽입, 삭제, 탐색 등의 연산을 수행할 수 있고, Node를 통해 연결된다. 리스트의 ADT는 아래와 같다. - 객체: n개의 element 형으로 구성된 순서가 있는 모임 - 연산 insert(list, pos, item) ::= pos 위치에 요소를 추가한다. insert_last(list, item) ::= 맨 끝에 요소를 추..
04 큐 Queue 1. 큐의 개념 1-1. 큐란 무엇일까? 큐는 스택과 반대의 자료구조이다. 먼저 온 데이터가 먼저 나가는 선입선출(FIFO: First-In First-Out)의 특성을 가지고 있다. 스택도 많이 사용하는 자료구조지만, 큐는 스택보다 많이 사용되는 자료구조로 그 쓰임새가 많다. 일상생활의 예로는 매표소, 톨게이트 등이 있다. 순서대로 줄을 서는 모양이다. 1-2. 큐의 기능 큐의 기능은 스택과 비슷하다. 데이터를 삽입하고 읽어오고 삭제한다. 다만, 큐는 [top만 가지고 있는 스택]과는 다르게 front와 rear를 가지고 있다. front는 데이터가 삭제되는 부분을 가리키고, rear는 제일 나중에 들어온 데이터를 가리킨다. 스택의 추상자료형은 아래와 같다. 객체: 0개 이상의 요소..
03 스택 Stack 1. 스택의 개념 1-1. 스택이란? 스택은 쌓아놓은 더미이다. 상자를 쌓는다고 하면 아래에서부터 차곡차곡 쌓아놓을 것이다. 중간에 있는 상자가 필요하면 맨위에서부터 상자를 하나씩 빼서 꺼낼 것이다. 이런 입출력 형태를 선입후출(FILO: First In Last Out) 또는 후입선출(LIFO: Last In First Out)이라고 한다. 함수를 호출할 때도 컴퓨터 시스템은 위와 같은 스택 구조를 사용한다. 시스템 스택에 함수를 차곡차곡 쌓아 위에서부터 차례대로 꺼내 수행한다. 1-2. 스택의 기능 가장 기본적인 스택은 6가지 기능을 가지고 있다. create(): 스택을 생성한다. is_full(s): 스택이 포화상태인지 검사한다. is_empty(s): 스택이 공백상태인지 검..
02 순환 Recursion 1. 순환의 개념 1-1. 순환이란? 순환이란 알고리즘이나 함수가 수행 도중에 자기 자신을 다시 호출하여 문제를 해결하는 기법이다. 정의 자체가 순환적으로 되어 있는 경우에 적합한 방법이다. 순환의 가장 간단한 예로는 팩토리얼있다. 아래는 c언어로 팩토리얼 구하는 함수를 만든 것이다. int factorial(int n){ if (n ... -> 21 -> 20) 즉, 호출을 할 때마다 문제의 크기가 2로 나눈 것만큼 줄어들기 때문에 시간복잡도가 O(log2 n)이다. 반면 반복문은 n만큼 반복 연산해야하기 때문에 시간복잡도가 O(n)이다. 물론 수학적인 방식을 이용했기때문에 당연히 순환적인 방식이 빠를 수밖에 없는 거 아닌가라고 생각할 수 있을 것이다. 그러나 반복문에서는 ..
