C언어/알고리즘 (17) 썸네일형 리스트형 [알고리즘] ch 5. 탐색(2) - 이진 탐색 트리 5.4 이진 탐색 트리 이진 탐색 트리 (Binary Serach Tree) - '이진 탐색'을 위한 '이진 트리' - 이진 탐색은 배열에만 사용 가능한 알고리즘 -> 이진 탐색을 사용하려면 데이터의 처음과 끝을 알아야 하고 데이터의 중앙 요소를 계산할 수 있어야 하며 계산된 중앙 요소에 즉시 접근할 수 있어야 함 -> 링크드 리스트는 상기된 작업 불가 - 이진 탐색 트리는 동적으로 노드를 추가하거나 제거할 수 있으면서 이진 탐색 알고리즘도 사용할 수 있게 함 5.4.1 이진 탐색 트리 표현 - 이진 탐색 트리 노드의 조건 -> 이진 탐색 트리의 각 노드는 왼쪽 자식 노드보다 크고 오른쪽 자식 노드보다 작다 5.4.2 이진 탐색 트리의 기본 연산 - 이진 탐색 트리는 이진 탐색이 가능한 상태로 정렬되어 .. [알고리즘] ch 5. 탐색 (1)- 순차 탐색, 이진 탐색 5.1 탐색 알고리즘의 개요 - 탐색이란 '데이터를 찾는것' - 자료구조 형태에 따라 사용할 수 있는 여러 가지 탐색 알고리즘 - 순차 탐색, 이진 탐색, 이진 탐색 트리, 레드 블랙 트리 5.2 순차 탐색 순차 탐색 (Sequential Search) - 처음부터 끝까지 차례대로 모든 요소를 비교하여 원하는 데이터를 찾는 탐색 알고리즘 - 어느 한쪽 방향으로만 탐색할 수 있는 알고리즘이므로 선형 탐색(Linear Search)라고 부름 - 성능이 좋지 않지만, 정렬되지 않은 데이터에서 원하는 항목을 찾을 수 있는 유일한 방법이며 구현이 간단 - 극적으로 놓은 성능이 필요하지 않거나 데이터의 크기가 작은 상황에서 유용하게 활용 - 배열이나 링크드 리스트에 쉽게 적용할 수 있는 알고리즘 ex) 링크드 리스.. [자료구조] ch 4. 트리 (2) - 수식 트리, 분리 집합 4.3 수식 트리 수식 이진 트리(Expression Binary Tree) - 수식을 표현하는 이진 트리 - 피연산자는 잎 노드이다. - 연산자는 뿌리 노드 또는 가지 노드이다. ex) 1*2+(7-8) - 뿌리 노드를 연산자로, 왼쪽 하위 수식 트리의 결괏값과 오른쪽 하위 수식 트리의 결괏값을 피연산자로 하여 계산을 수행하면 전체 수식의 계산 결과를 얻을 수 있음 -가장 아래에 있는 하위 수식 트리(잎 노드)로부터 수 또는 계산 결괏값을 병합해 올라가는 과정을 반복하며 계산을 수행 - 후위 순회는 왼쪽 하위 트리 - 오른쪽 하위 트리 - 뿌리 노드 순으로 순회하기 때문에 양쪽 하위 트리에서부터 결괏값을 병합해 올라와야 하는 수식 트리를 계산할 때 안성맞춤 4.3.1 수식 트리 구축 방법 수식 트리 구.. [자료구조] ch 4 트리 (1) - 이진 트리 4.1 트리 ADT 4.1.1 트리의 개념 - 트리는 나무를 닮은 자료구조 - 운영체제 파일 시스템, DOM, 검색 엔진, 데이터베이스 4.1.2 트리의 구성 요소 뿌리(root) - 트리 자료구조의 가장 위에 있는 노드 가지(Branch) - 뿌리와 잎 사이에 있는 모든 노드 잎(Leaf) - 가지의 끝에 매달린 노드 - 단말 노드 (Terminal node) - B는 C와 D의 부모 (Parent) - C와 D는 B의 자식(Children) - C와 D는 형제 (Sibling) 경로(Path) - 한 노드에서 다른 한 노드까지 이르는 길 사이에 있는 노드들의 순서 ex) B 노드에서 F 노드를 찾아가려면 B 노드에서 출발하여 D 노드를 방문하고 D에서 출발하여 F에 도착 'B->D->F' 길이 (Le.. [자료구조] ch 3. 큐 3.1 큐 ADT 3.1.1 큐의 개념 - 먼저 들어간 데이터가 먼저 나오는 (FIFO First In First Out , 선입선출) 자료구조 - 입력과 출력 창구가 따로 존재하고, 제일 먼저 들어간 데이터가 제일 먼저 나옴\ 3.1.2 큐의 핵심 기능 : 삽입과 제거 연산 - 전단(Front) : 큐의 가장 앞 요소 - 후단(Rear) : 큐의 가장 마지막 요소 - 삽입 연산 : 후단에 노드를 덧붙여서 새로운 후단을 만드는 연산 - 제거 연산 : 전단의 노드를 없애서 전단 뒤에 있는 노드를 새로운 전단으로 만드는 연산 3.2 순환큐 순환 큐 (Circular Queue) - 시작과 끝을 연결해서 효율적인 삽입/삭제 연산이 가능하도록 고안된 큐 - 배열의 시작과 끝을 연결 - 전단을 가리키는 변수를 도.. [자료구조] ch 2. 스택(2) - 사칙 연산 계산기 2.4 스택의 응용 : 사칙 연산 계산기 - 수식 분석기 기반의 사칙 연산 계산기 - 원본 수식을 컴퓨터가 풀기 쉬운 형식으로 변환 후 , 이렇게 변환된 수식을 계산 2.4.1 수식의 중위 표기법과 후위 표기법 후위 표기법(Postfic Notation) - 연산자가 피연산자 뒤에 위치 - 1 2 33 /+9 13 * - 전위 표기법(Infix Notation) - 연산자가 피연산자 가운데에 위치 - 1+2/33-9*13 2.4.2 후위 표기식을 계산하는 알고리즘 1) 식의 왼쪽부터 요소를 읽어내면서 그 요소가 피연산자라면 스택에 삽입 2) 연산자가 나타나면 스택에서 피연산자 2개를 꺼내 연산을 실행하고 그 연산 결과를 다시 스택에 삽입 - 곱셈을 수행하는 *이므로 스택에서 두 번의 제거 연산을 수행하여.. [자료구조] ch 2. 스택 (1) 2.1 스택 ADT 2.1.1 스택의 개념 - 스택에서 데이터 입/출력은 오로지 스택의 꼭대기에서만 이루어짐 - 가장 마지막에 들어간 데이터가 제일 먼저 나오고(LIFO Last-In-First Out) 가장 먼저 들어간 데이터는 가장 나중에 나옴(FILO First In Last out) 2.1.2 스택의 핵심 기능 : 삽입과 제거 연산 삽입 연산 - 스택 위에 새로운 노드(요소)를 "쌓는" 일 제거 연산 - 스택에서 최상위 노드를 "걷어"냄 2.2 배열로 구현하는 스택 - 배열 기반의 스택은 각 노드를 동적으로 생성하고 제거하는 대신, 스택 생성 초기에 사용자가 부여한 용량만큼의 노드를 한꺼번에 생성 - 최상위 노드의 위치를 나타내는 변수를 두고 삽입과 제거 연산 수행 2.2.1 배열 기반 스택과 스.. [자료구조] ch1 리스트 (2) 1.3 더블 링크드 리스트 더블 링크드 리스트 (Doubly Linked List) - 링크드 리스트의 탐색 기능을 개선한 자료구조 - 더블 링크드 리스트에서는 양방향으로 탐색 가능 - 더블 링크드 리스트의 노드는 자신 앞에 있는 노드를 가리키는 포인터도 갖고 있음 - 더블 링크드 리스트의 노드 Typedef int ElementType; typedef struct tagNode { ElementType Data; struct tagNode* PrevNode; //이전 노드를 가리키는 포인터 struct tagNode* NextNode; //다음 노드를 가리키는 포인터 }Node; 1.3.1 더블 링크드 리스트의 주요 연산 1) 노드 생성/소멸 연산 노드 생성 함수 DLL_CreateNode() Node.. 이전 1 2 3 다음
