Min'sLog

● 이진 탐색 트리란?   이진트리를 기반으로 탐색을 용이하게 하기 위해 규칙을 추가한 트리이다.해당 규칙은 다음과 같다.  1.  이진탐색트리의 각 노드에 저장된 Key 값은 유일하다.  2.  루트노드의 키보다 작은 값은 왼쪽 서브트리에 저장 / 루트노드 보다 큰 키값은 오른쪽 서브트리에 저장한다.   3.  왼쪽 / 오른쪽 서브트리 역시 이진 탐색 트리이다.   이진 탐색 트리의 탐색은 탐색을 할때 마다, 탐색할 대상 데이터가 절반 길이씩 줄기 때문에,   균형잡힌 이진 탐색트리라 가정한다면 수행속도는 O(log2n) 이 된다. ● 이진 탐색 트리를 구성하는 노드 구조체    이진 탐색 트리를 구성하는 노드의 구조체는 이진트리의 구조체와 동일하며, 다음과 같다.   구조체 자신을 참조를 하는 포인터..

● 퀵 정렬(quick sort) 이란‘  찰스 앤터니 리처드 호어(Charles Antony Richard Hoare)’가 개발한 정렬 알고리즘   퀵 정렬은 불안정 정렬 에 속하며, 다른 원소와의 비교만으로 정렬을 수행하는 비교 정렬 에 속한다.   분할 정복 알고리즘(Divide and Conquer)의 하나로, 평균적으로 매우 빠른 수행 속도를 자랑하는 정렬 방법● 퀵정렬 : 정렬 방법 정리  분할 정복(Divide Conquer)을 활용한 순환호출로 구현한다. ○  퀵정렬 과정    1. 리스트 안에 있는 한 요소를 선택한다. 이렇게 고른 원소를 피벗(pivot) 이라고 한다.    2. 피벗을 기준으로 피벗보다 작은 요소들은 모두 피벗의 왼쪽으로 옮겨지고      피벗보다 큰 요소들은 모두 피..

● 병합 정렬: Divide and Conquer (DAC)  - '존 폰 노이만(John von Neumann)’이 제안한 정렬 방법. - 일반적인 방법으로 구현했을 때 이 정렬은 안정 정렬 에 속하며, 분할 정복(DAC) 알고리즘의 하나이다.※ 분할정복 (Divide And Conquer) 란?   - 1단계 분할(Divide) : 해결이 용이한 단계까지 문제를 분할해 나간다.   - 2단계 정복(Conquer) : 해결이 용이한 수준까지 분할된 문제를 해결한다.   - 3단계 결합(Combine) : 분할해서 해결한 결과를 결합하여 마무리한다. 병합정렬은 아래와 같이 구현한다.  ○ Divide    별도의 정렬을 진행하지 않아도 될 수준까지 분할을 진행한다.   1/2 씩 분할하며,  분할은 가장..

● 정렬(sort) => 탐색(search)을 용이하기 위해 사용 한다.    = 어떠한 기준을 가지고 정렬된 대상을 효율적으로 탐색할 것인가   - 단순한 정렬 알고리즘 : 구현이 용이한 반면 성능이 만족스럽지 않다.   - 복잡한 정렬 알고리즘  : 구현이 복잡하지만 성능이 만족스럽다.  복잡한 정렬 알고리즘은 성능이 중요할때, 공통적으로 사용하기위해 라이브러리화 하여 사용하는 케이스가 많고,간단한 정렬 알고리즘은 구현이 간단한 만큼, 정렬대상(데이터)이 많지 않을 경우 간편히 구현해서 사용할 수 있는 장점이 있다.1. 버블 정렬 (Bubble Sort)     이전 포스팅중 버블 정렬에 대한 설명 및 구현이 있었기 때문에  간략히만 설명하면     수열중 양옆의 수를 계속 비교하여 우선순위별로 비교..

● 힙(heap)이란?    힙은 완전 이진 트리이다.    모든 노드에 저장된 값은 자식 노드에 저장된 값보다 크거나 같아야 한다.(혹은 작거나 같아야 한다.)   즉, 루트 노드에 저장된 값이 가장 큰 경우 -> 최대 힙 : max heap        루트 노드에 저장된  값이 가장 작은 경우 -> 최소 힙 : min heap※ 자료구조에서의 Heap 과 Heap 메모리는 관련이 없다!● 힙의 데이터 저장 과정(규칙 오름차순 정렬 기준 )    완전 이진 트리 이면서 자식노드 데이터의 우선순위    1. 우선은 리프노드에 데이터를 저장.    2. 부모노드와의 우선순위를 비교한 후 자리 바꿈(swap)         (...반복...)   3. 자리를 찾으면 해당 노드에 데이터를 저장한다.● 힙에서..

● 수식트리란? 이진트리의 일종으로 피연산자와 연산자를 하나의 트리로 구성하는것이다.중위 표기법은 인간이 인식하기 좋지만, 컴퓨터는 연산자의 우선순위를 고려해야 하기 때문에, C언어의 컴파일러는 중위 표기법의 수식을 수식트리의 형태로 치환한다.  중위 표기법의 수식을 수식 트리로 변환하는 프로그램의 작성이 목적이다. 예시) ※ 수식트리 -> 수식을 표현하는 하나의 표현 방법 ●  수식 트리를 만드는 구성중위 표기법의 수식을 바로 수식 트리로 표현하기 쉽지 않으므로, 이전 챕터(스택의 활용편)에서 계산기 프로그램을 위해 만들어둔 함수 ConvToRPNExp 함수 (Infix -> PostFix) 를 통해 PostFix로 변환해준다. 변환한 수식을 이진트리와 스택을 활용하여, 수식트리로 변환한다. ● 수식트..

● 구현 개념이진트리의 순회는 재귀적(Recursive)으로 구현이 가능하다. ○ 순회의 세가지 방법 기준은 루트 노드를 언제 방문하느냐에 있다. - 전위 순회 (O L RN) : 첫번째에 루트노드 접근  - 중위 순회 (L O RN) : 중간에 루트노드 접근  - 후위 순회 (L RN O) : 마지막에 루트노드 접근높이가 2 이상인 트리의 순회도 이와 다르지 않다. 재귀적인 형태로 순회의 과정을 구성하면 높이에 상관없이 순회가 가능하다!  ● 예시중위(Inorder Traverse) 순회의 과정은 아래와 같다1단계. 왼쪽 서브트리의 순회 2단계. 루트 노드의 방문 3단계. 오른쪽 서브트리의 순회  Left -> RN -> Right위 텍스트를 그대로 재귀 코드 구현하면 아래와 같다. void Inord..

● 이진트리의 이해트리의 한 종류로, 루트를 기점으로 두개의 자식 노드를 갖는 트리이다. - 이진 트리의 조건 (Condition)   1. 루트 노드를 중심으로 두 개의 서브 트리로 나뉘어 진다.   2. 나뉘어진 두 서브 트리도 모두 이진 트리이어야 한다. 이진 트리가 되려면, 루트 노드를 중심으로 둘로 나뉘는 두개의 서브 트리도 이진트리이어야 하고, 그 서브 트리의 모든 서브 트리도 이진 트리이어야 한다. (재귀적인 성향을 담아내지 못한 완전하지 않은 표현) ※ 트리의 구조는 재귀적이다.    따라서 트리와 관련된 연산은 재귀적으로 사고하고 재귀적으로 구현할 필요가 있다. ● 이진 트리와 공집합 노드 공집합(empty set) 도 이진 트리에서는 노드로 간주한다. -> 즉 한개의 자식만 생성되었을 ..