sec 61) 트리(Tree) (A)
* 트리
- 트리는 정점(Node, 노드)과 선분(Branch, 가지)을 이용하여 사이클을 이루지 않도록 구성한 그래프(Graph)의 특수한 형태
- 트리는 하나의 기억 공간을 노드(Node)라고 하며, 노드와 노드를 연결하는 선을 링크(Link)라고 함.
필기 20.8, 20.6
* 트리 관련용어
p250 참고
- 노드(Node): 트리의 기본 요소로서 자료 항목과 다른 항목에 대한 가지(Branch)를 합친 것
- 근 노드(Root Node): 트리의 맨 위에 있는 노드
- 디그리(Degree, 차수): 각 노드에서 뻗어나온 가지의 수
- 단말 노드(Terminal Node) = 잎 노드(Leaf Node): 자식이 하나도 없는 노드, 즉 Degree가 0인 노드
- 비단말 노드(Non-Terminal Node): 자식이 하나라도 있는 노드, 즉 Degree가 0이 아닌 노드
- 조상 노드(Ancestors Node): 임의의 노드에서 근 노드에 이르는 경로상에 있는 노드들
- 자식 노드(Son Node): 어떤 노드에 연결된 다음 레벨의 노드들
- 부모 노드(Parent Node): 어떤 노드에 연결된 이전 레벨의 노드들
- 형제 노드(Brother Node, Sibling): 동일한 부모를 갖는 노드들
- Level: 근 노드의 Level을 1로 가정한 후 어떤 Level이 L이면 자식 노드는 L+1
- 깊이(Depth, Height): Tree에서 노드가 가질 수 있는 최대의 레벨
- 숲(Forest): 여러개의 트리가 모여 있는 것
- 트리의 디그리: 노드들의 디그리 중에서 가장 많은 수
sec 62) 이진 트리(Tree) (A)
* 이진 트리
- 이진트리는 차수(Degree)가 2이하인 노드들로 구성된 트리, 즉 자식이 둘이하인 노트들로만 구성된 트리를 말함.
- 이진 트리의 레벨 i에서 최대 노드의 수는
- 이진 트리에서 Terminal Node수가 n0, 차수가 2인 노드 n2라 할 때 n0=n2+1
*트리의 운행법
- 트리를 구성하는 각 노드들을 찾아가는 방법을 운행법(Traversal)이라 한다.
- 이진 트리를 운행하는 방법은 산술식의 표기법과 연관성을 갖는다.
>> 이진 트리의 운행법( p253-p256 추가 참고)
- Preorder 운행 - Root -> Left -> Right
- Inorder 운행 - Left -> Root -> Right
- Postorder 운행 - Left -> Right -> Root
sec 63) 정렬(Sort) (A)
필기 20.9
* 삽입 정렬(Insertion Sort)
- 삽입 정렬은 가장 간단한 정렬 방식으로, 이미 순서화된 파일에 새로운 하나의 레코드를 순서에 맞게 삽입시켜 정렬하는 방식
- 평균과 최악 모두 수행 시간 복잡도는 O(
)
필기 20.8
* 선택정렬(Selection Sort)
- 선택 정렬은 n개의 레코드 중에서 최솟값을 찾아 첫 번째 레코드 위치에 놓고, 나머지 (n-1)개 중에서 다시 최솟값을 찾아 두 번째 레코드 위치에 놓는 방식을 반복하여 정렬하는 방식
- 평균과 최악 모두 수행 시간 복잡도는 O(
)
* 버블 정렬(Bubble Sort)
- 버블 정렬은 주어진 파일에서 인접한 두 개의 레코드 키 값을 비교하여 그 크기에 따라 레코드 위치를 서로 교환하는 정렬 방식
- 평균과 최악 모두 수행 시간 복잡도는 O(
)
* 쉘 정렬(Shell Sort)
- 쉘 정렬은 입력파일을 어떤 매개변수의 값으로 서브파일을 구성하고, 각 서브파일을 Insertion 정렬방식으로 순서 배열하는 과정을 반복하는 정렬 방식
- 삽입 정렬(Insertion Sort)을 확장한 개념
- 평균 수행 시간 복잡도는 O(
)이고, 최악의 수행시간 복잡도는 O(
)
* 퀵 정렬(Quick Sort)
- 퀵 정렬은 키를 기준으로 작은 값은 왼쪽, 큰 값은 오른쪽 서브 파일에 분해시키는 과정을 반복하는 정렬방식
- 레코드의 많은 자료 이동을 없애고 하나의 파일을 부분적으로 나누어 가면서 정렬
- 평균 수행시간 복잡도는 O(
)최악의 수행 시간 복잡도는 O(
)
* 힙 정렬(Heap Sort)
- 힙 정렬은 전이진 트리를 이용한 정렬 방식
- 구성된 전이진 트리(Complete Binary Tree)를 Heap Tree로 변환하여 정렬
- 평균과 최악 모두 시간 복잡도O(
)
* 2-Way 합병 정렬(Merge Sort)
- 2-Way 합병 정렬은 이미 정렬되어 있는 두 개의 파일을 한 개의 파일로 합병하는 정렬 방식
- 평균과 최악 모두 시간 복잡도 O(
)
* 기수 정렬(Radix Sort) = Bucket Sort
- 기수 정렬은 Queue를 이용하여 자리수(Digit)별로 정렬하는 방식
- 레코드의 키 값을 분석해 같은 수 또는 같은 문자끼리 그 순서에 맞는 버킷에 분배하였다가 버킷의 순서대로 레코드를 꺼내어 정렬
- 평균과 최악 모두 시간 복잡도 O(dn)
* 트리
- 트리는 정점(Node, 노드)과 선분(Branch, 가지)을 이용하여 사이클을 이루지 않도록 구성한 그래프(Graph)의 특수한 형태
- 트리는 하나의 기억 공간을 노드(Node)라고 하며, 노드와 노드를 연결하는 선을 링크(Link)라고 함.
필기 20.8, 20.6
* 트리 관련용어
p250 참고
- 노드(Node): 트리의 기본 요소로서 자료 항목과 다른 항목에 대한 가지(Branch)를 합친 것
- 근 노드(Root Node): 트리의 맨 위에 있는 노드
- 디그리(Degree, 차수): 각 노드에서 뻗어나온 가지의 수
- 단말 노드(Terminal Node) = 잎 노드(Leaf Node): 자식이 하나도 없는 노드, 즉 Degree가 0인 노드
- 비단말 노드(Non-Terminal Node): 자식이 하나라도 있는 노드, 즉 Degree가 0이 아닌 노드
- 조상 노드(Ancestors Node): 임의의 노드에서 근 노드에 이르는 경로상에 있는 노드들
- 자식 노드(Son Node): 어떤 노드에 연결된 다음 레벨의 노드들
- 부모 노드(Parent Node): 어떤 노드에 연결된 이전 레벨의 노드들
- 형제 노드(Brother Node, Sibling): 동일한 부모를 갖는 노드들
- Level: 근 노드의 Level을 1로 가정한 후 어떤 Level이 L이면 자식 노드는 L+1
- 깊이(Depth, Height): Tree에서 노드가 가질 수 있는 최대의 레벨
- 숲(Forest): 여러개의 트리가 모여 있는 것
- 트리의 디그리: 노드들의 디그리 중에서 가장 많은 수
sec 62) 이진 트리(Tree) (A)
* 이진 트리
- 이진트리는 차수(Degree)가 2이하인 노드들로 구성된 트리, 즉 자식이 둘이하인 노트들로만 구성된 트리를 말함.
- 이진 트리의 레벨 i에서 최대 노드의 수는
- 이진 트리에서 Terminal Node수가
, 차수가 2인 노드 n가
라 할 때
=
+1
*트리의 운행법
- 트리를 구성하는 각 노드들을 찾아가는 방법을 운행법(Traversal)이라 한다.
- 이진 트리를 운행하는 방법은 산술식의 표기법과 연관성을 갖는다.
>> 이진 트리의 운행법( p253-p256 추가 참고)
- Preorder 운행 - Root -> Left -> Right
- Inorder 운행 - Left -> Root -> Right
- Postorder 운행 - Left -> Right -> Root
sec 63) 정렬(Sort) (A)
필기 20.9
* 삽입 정렬(Insertion Sort)
- 삽입 정렬은 가장 간단한 정렬 방식으로, 이미 순서화된 파일에 새로운 하나의 레코드를 순서에 맞게 삽입시켜 정렬하는 방식
- 평균과 최악 모두 수행 시간 복잡도는 O(
)
필기 20.8
* 선택정렬(Selection Sort)
- 선택 정렬은 n개의 레코드 중에서 최솟값을 찾아 첫 번째 레코드 위치에 놓고, 나머지 (n-1)개 중에서 다시 최솟값을 찾아 두 번째 레코드 위치에 놓는 방식을 반복하여 정렬하는 방식
- 평균과 최악 모두 수행 시간 복잡도는 O(
)
* 버블 정렬(Bubble Sort)
- 버블 정렬은 주어진 파일에서 인접한 두 개의 레코드 키 값을 비교하여 그 크기에 따라 레코드 위치를 서로 교환하는 정렬 방식
- 평균과 최악 모두 수행 시간 복잡도는 O(
)
* 쉘 정렬(Shell Sort)
- 쉘 정렬은 입력파일을 어떤 매개변수의 값으로 서브파일을 구성하고, 각 서브파일을 Insertion 정렬방식으로 순서 배열하는 과정을 반복하는 정렬 방식
- 삽입 정렬(Insertion Sort)을 확장한 개념
- 평균 수행 시간 복잡도는 O(
)이고, 최악의 수행시간 복잡도는 O(
)
* 퀵 정렬(Quick Sort)
- 퀵 정렬은 키를 기준으로 작은 값은 왼쪽, 큰 값은 오른쪽 서브 파일에 분해시키는 과정을 반복하는 정렬방식
- 레코드의 많은 자료 이동을 없애고 하나의 파일을 부분적으로 나누어 가면서 정렬
- 평균 수행시간 복잡도는 O(
)최악의 수행 시간 복잡도는 O(
)
* 힙 정렬(Heap Sort)
- 힙 정렬은 전이진 트리를 이용한 정렬 방식
- 구성된 전이진 트리(Complete Binary Tree)를 Heap Tree로 변환하여 정렬
- 평균과 최악 모두 시간 복잡도O(
)
* 2-Way 합병 정렬(Merge Sort)
- 2-Way 합병 정렬은 이미 정렬되어 있는 두 개의 파일을 한 개의 파일로 합병하는 정렬 방식
- 평균과 최악 모두 시간 복잡도 O(
)
* 기수 정렬(Radix Sort) = Bucket Sort
- 기수 정렬은 Queue를 이용하여 자리수(Digit)별로 정렬하는 방식
- 레코드의 키 값을 분석해 같은 수 또는 같은 문자끼리 그 순서에 맞는 버킷에 분배하였다가 버킷의 순서대로 레코드를 꺼내어 정렬
- 평균과 최악 모두 시간 복잡도 O(dn)
- 트리는 정점(Node, 노드)과 선분(Branch, 가지)을 이용하여 사이클을 이루지 않도록 구성한 그래프(Graph)의 특수한 형태
- 트리는 하나의 기억 공간을 노드(Node)라고 하며, 노드와 노드를 연결하는 선을 링크(Link)라고 함.
필기 20.8, 20.6
* 트리 관련용어
p250 참고
- 노드(Node): 트리의 기본 요소로서 자료 항목과 다른 항목에 대한 가지(Branch)를 합친 것
- 근 노드(Root Node): 트리의 맨 위에 있는 노드
- 디그리(Degree, 차수): 각 노드에서 뻗어나온 가지의 수
- 단말 노드(Terminal Node) = 잎 노드(Leaf Node): 자식이 하나도 없는 노드, 즉 Degree가 0인 노드
- 비단말 노드(Non-Terminal Node): 자식이 하나라도 있는 노드, 즉 Degree가 0이 아닌 노드
- 조상 노드(Ancestors Node): 임의의 노드에서 근 노드에 이르는 경로상에 있는 노드들
- 자식 노드(Son Node): 어떤 노드에 연결된 다음 레벨의 노드들
- 부모 노드(Parent Node): 어떤 노드에 연결된 이전 레벨의 노드들
- 형제 노드(Brother Node, Sibling): 동일한 부모를 갖는 노드들
- Level: 근 노드의 Level을 1로 가정한 후 어떤 Level이 L이면 자식 노드는 L+1
- 깊이(Depth, Height): Tree에서 노드가 가질 수 있는 최대의 레벨
- 숲(Forest): 여러개의 트리가 모여 있는 것
- 트리의 디그리: 노드들의 디그리 중에서 가장 많은 수
sec 62) 이진 트리(Tree) (A)
* 이진 트리
- 이진트리는 차수(Degree)가 2이하인 노드들로 구성된 트리, 즉 자식이 둘이하인 노트들로만 구성된 트리를 말함.
- 이진 트리의 레벨 i에서 최대 노드의 수는
- 이진 트리에서 Terminal Node수가
, 차수가 2인 노드 n가
라 할 때
=
+1
*트리의 운행법
- 트리를 구성하는 각 노드들을 찾아가는 방법을 운행법(Traversal)이라 한다.
- 이진 트리를 운행하는 방법은 산술식의 표기법과 연관성을 갖는다.
>> 이진 트리의 운행법( p253-p256 추가 참고)
- Preorder 운행 - Root -> Left -> Right
- Inorder 운행 - Left -> Root -> Right
- Postorder 운행 - Left -> Right -> Root
sec 63) 정렬(Sort) (A)
필기 20.9
* 삽입 정렬(Insertion Sort)
- 삽입 정렬은 가장 간단한 정렬 방식으로, 이미 순서화된 파일에 새로운 하나의 레코드를 순서에 맞게 삽입시켜 정렬하는 방식
- 평균과 최악 모두 수행 시간 복잡도는 O(
)
필기 20.8
* 선택정렬(Selection Sort)
- 선택 정렬은 n개의 레코드 중에서 최솟값을 찾아 첫 번째 레코드 위치에 놓고, 나머지 (n-1)개 중에서 다시 최솟값을 찾아 두 번째 레코드 위치에 놓는 방식을 반복하여 정렬하는 방식
- 평균과 최악 모두 수행 시간 복잡도는 O(
)
* 버블 정렬(Bubble Sort)
- 버블 정렬은 주어진 파일에서 인접한 두 개의 레코드 키 값을 비교하여 그 크기에 따라 레코드 위치를 서로 교환하는 정렬 방식
- 평균과 최악 모두 수행 시간 복잡도는 O(
)
* 쉘 정렬(Shell Sort)
- 쉘 정렬은 입력파일을 어떤 매개변수의 값으로 서브파일을 구성하고, 각 서브파일을 Insertion 정렬방식으로 순서 배열하는 과정을 반복하는 정렬 방식
- 삽입 정렬(Insertion Sort)을 확장한 개념
- 평균 수행 시간 복잡도는 O(
)이고, 최악의 수행시간 복잡도는 O(
)
* 퀵 정렬(Quick Sort)
- 퀵 정렬은 키를 기준으로 작은 값은 왼쪽, 큰 값은 오른쪽 서브 파일에 분해시키는 과정을 반복하는 정렬방식
- 레코드의 많은 자료 이동을 없애고 하나의 파일을 부분적으로 나누어 가면서 정렬
- 평균 수행시간 복잡도는 O(
)최악의 수행 시간 복잡도는 O(
)
* 힙 정렬(Heap Sort)
- 힙 정렬은 전이진 트리를 이용한 정렬 방식
- 구성된 전이진 트리(Complete Binary Tree)를 Heap Tree로 변환하여 정렬
- 평균과 최악 모두 시간 복잡도O(
)
* 2-Way 합병 정렬(Merge Sort)
- 2-Way 합병 정렬은 이미 정렬되어 있는 두 개의 파일을 한 개의 파일로 합병하는 정렬 방식
- 평균과 최악 모두 시간 복잡도 O(
)
* 기수 정렬(Radix Sort) = Bucket Sort
- 기수 정렬은 Queue를 이용하여 자리수(Digit)별로 정렬하는 방식
- 레코드의 키 값을 분석해 같은 수 또는 같은 문자끼리 그 순서에 맞는 버킷에 분배하였다가 버킷의 순서대로 레코드를 꺼내어 정렬
- 평균과 최악 모두 시간 복잡도 O(dn)
- 트리는 하나의 기억 공간을 노드(Node)라고 하며, 노드와 노드를 연결하는 선을 링크(Link)라고 함.
필기 20.8, 20.6
* 트리 관련용어
p250 참고
- 노드(Node): 트리의 기본 요소로서 자료 항목과 다른 항목에 대한 가지(Branch)를 합친 것
- 근 노드(Root Node): 트리의 맨 위에 있는 노드
- 디그리(Degree, 차수): 각 노드에서 뻗어나온 가지의 수
- 단말 노드(Terminal Node) = 잎 노드(Leaf Node): 자식이 하나도 없는 노드, 즉 Degree가 0인 노드
- 비단말 노드(Non-Terminal Node): 자식이 하나라도 있는 노드, 즉 Degree가 0이 아닌 노드
- 조상 노드(Ancestors Node): 임의의 노드에서 근 노드에 이르는 경로상에 있는 노드들
- 자식 노드(Son Node): 어떤 노드에 연결된 다음 레벨의 노드들
- 부모 노드(Parent Node): 어떤 노드에 연결된 이전 레벨의 노드들
- 형제 노드(Brother Node, Sibling): 동일한 부모를 갖는 노드들
- Level: 근 노드의 Level을 1로 가정한 후 어떤 Level이 L이면 자식 노드는 L+1
- 깊이(Depth, Height): Tree에서 노드가 가질 수 있는 최대의 레벨
- 숲(Forest): 여러개의 트리가 모여 있는 것
- 트리의 디그리: 노드들의 디그리 중에서 가장 많은 수
sec 62) 이진 트리(Tree) (A)
* 이진 트리
- 이진트리는 차수(Degree)가 2이하인 노드들로 구성된 트리, 즉 자식이 둘이하인 노트들로만 구성된 트리를 말함.
- 이진 트리의 레벨 i에서 최대 노드의 수는
- 이진 트리에서 Terminal Node수가
, 차수가 2인 노드 n가
라 할 때
=
+1
*트리의 운행법
- 트리를 구성하는 각 노드들을 찾아가는 방법을 운행법(Traversal)이라 한다.
- 이진 트리를 운행하는 방법은 산술식의 표기법과 연관성을 갖는다.
>> 이진 트리의 운행법( p253-p256 추가 참고)
- Preorder 운행 - Root -> Left -> Right
- Inorder 운행 - Left -> Root -> Right
- Postorder 운행 - Left -> Right -> Root
sec 63) 정렬(Sort) (A)
필기 20.9
* 삽입 정렬(Insertion Sort)
- 삽입 정렬은 가장 간단한 정렬 방식으로, 이미 순서화된 파일에 새로운 하나의 레코드를 순서에 맞게 삽입시켜 정렬하는 방식
- 평균과 최악 모두 수행 시간 복잡도는 O(
)
필기 20.8
* 선택정렬(Selection Sort)
- 선택 정렬은 n개의 레코드 중에서 최솟값을 찾아 첫 번째 레코드 위치에 놓고, 나머지 (n-1)개 중에서 다시 최솟값을 찾아 두 번째 레코드 위치에 놓는 방식을 반복하여 정렬하는 방식
- 평균과 최악 모두 수행 시간 복잡도는 O(
)
* 버블 정렬(Bubble Sort)
- 버블 정렬은 주어진 파일에서 인접한 두 개의 레코드 키 값을 비교하여 그 크기에 따라 레코드 위치를 서로 교환하는 정렬 방식
- 평균과 최악 모두 수행 시간 복잡도는 O(
)
* 쉘 정렬(Shell Sort)
- 쉘 정렬은 입력파일을 어떤 매개변수의 값으로 서브파일을 구성하고, 각 서브파일을 Insertion 정렬방식으로 순서 배열하는 과정을 반복하는 정렬 방식
- 삽입 정렬(Insertion Sort)을 확장한 개념
- 평균 수행 시간 복잡도는 O(
)이고, 최악의 수행시간 복잡도는 O(
)
* 퀵 정렬(Quick Sort)
- 퀵 정렬은 키를 기준으로 작은 값은 왼쪽, 큰 값은 오른쪽 서브 파일에 분해시키는 과정을 반복하는 정렬방식
- 레코드의 많은 자료 이동을 없애고 하나의 파일을 부분적으로 나누어 가면서 정렬
- 평균 수행시간 복잡도는 O(
)최악의 수행 시간 복잡도는 O(
)
* 힙 정렬(Heap Sort)
- 힙 정렬은 전이진 트리를 이용한 정렬 방식
- 구성된 전이진 트리(Complete Binary Tree)를 Heap Tree로 변환하여 정렬
- 평균과 최악 모두 시간 복잡도O(
)
* 2-Way 합병 정렬(Merge Sort)
- 2-Way 합병 정렬은 이미 정렬되어 있는 두 개의 파일을 한 개의 파일로 합병하는 정렬 방식
- 평균과 최악 모두 시간 복잡도 O(
)
* 기수 정렬(Radix Sort) = Bucket Sort
- 기수 정렬은 Queue를 이용하여 자리수(Digit)별로 정렬하는 방식
- 레코드의 키 값을 분석해 같은 수 또는 같은 문자끼리 그 순서에 맞는 버킷에 분배하였다가 버킷의 순서대로 레코드를 꺼내어 정렬
- 평균과 최악 모두 시간 복잡도 O(dn)
필기 20.8, 20.6
* 트리 관련용어
p250 참고
- 노드(Node): 트리의 기본 요소로서 자료 항목과 다른 항목에 대한 가지(Branch)를 합친 것
- 근 노드(Root Node): 트리의 맨 위에 있는 노드
- 디그리(Degree, 차수): 각 노드에서 뻗어나온 가지의 수
- 단말 노드(Terminal Node) = 잎 노드(Leaf Node): 자식이 하나도 없는 노드, 즉 Degree가 0인 노드
- 비단말 노드(Non-Terminal Node): 자식이 하나라도 있는 노드, 즉 Degree가 0이 아닌 노드
- 조상 노드(Ancestors Node): 임의의 노드에서 근 노드에 이르는 경로상에 있는 노드들
- 자식 노드(Son Node): 어떤 노드에 연결된 다음 레벨의 노드들
- 부모 노드(Parent Node): 어떤 노드에 연결된 이전 레벨의 노드들
- 형제 노드(Brother Node, Sibling): 동일한 부모를 갖는 노드들
- Level: 근 노드의 Level을 1로 가정한 후 어떤 Level이 L이면 자식 노드는 L+1
- 깊이(Depth, Height): Tree에서 노드가 가질 수 있는 최대의 레벨
- 숲(Forest): 여러개의 트리가 모여 있는 것
- 트리의 디그리: 노드들의 디그리 중에서 가장 많은 수
sec 62) 이진 트리(Tree) (A)
* 이진 트리
- 이진트리는 차수(Degree)가 2이하인 노드들로 구성된 트리, 즉 자식이 둘이하인 노트들로만 구성된 트리를 말함.
- 이진 트리의 레벨 i에서 최대 노드의 수는
- 이진 트리에서 Terminal Node수가
, 차수가 2인 노드 n가
라 할 때
=
+1
*트리의 운행법
- 트리를 구성하는 각 노드들을 찾아가는 방법을 운행법(Traversal)이라 한다.
- 이진 트리를 운행하는 방법은 산술식의 표기법과 연관성을 갖는다.
>> 이진 트리의 운행법( p253-p256 추가 참고)
- Preorder 운행 - Root -> Left -> Right
- Inorder 운행 - Left -> Root -> Right
- Postorder 운행 - Left -> Right -> Root
sec 63) 정렬(Sort) (A)
필기 20.9
* 삽입 정렬(Insertion Sort)
- 삽입 정렬은 가장 간단한 정렬 방식으로, 이미 순서화된 파일에 새로운 하나의 레코드를 순서에 맞게 삽입시켜 정렬하는 방식
- 평균과 최악 모두 수행 시간 복잡도는 O(
)
필기 20.8
* 선택정렬(Selection Sort)
- 선택 정렬은 n개의 레코드 중에서 최솟값을 찾아 첫 번째 레코드 위치에 놓고, 나머지 (n-1)개 중에서 다시 최솟값을 찾아 두 번째 레코드 위치에 놓는 방식을 반복하여 정렬하는 방식
- 평균과 최악 모두 수행 시간 복잡도는 O(
)
* 버블 정렬(Bubble Sort)
- 버블 정렬은 주어진 파일에서 인접한 두 개의 레코드 키 값을 비교하여 그 크기에 따라 레코드 위치를 서로 교환하는 정렬 방식
- 평균과 최악 모두 수행 시간 복잡도는 O(
)
* 쉘 정렬(Shell Sort)
- 쉘 정렬은 입력파일을 어떤 매개변수의 값으로 서브파일을 구성하고, 각 서브파일을 Insertion 정렬방식으로 순서 배열하는 과정을 반복하는 정렬 방식
- 삽입 정렬(Insertion Sort)을 확장한 개념
- 평균 수행 시간 복잡도는 O(
)이고, 최악의 수행시간 복잡도는 O(
)
* 퀵 정렬(Quick Sort)
- 퀵 정렬은 키를 기준으로 작은 값은 왼쪽, 큰 값은 오른쪽 서브 파일에 분해시키는 과정을 반복하는 정렬방식
- 레코드의 많은 자료 이동을 없애고 하나의 파일을 부분적으로 나누어 가면서 정렬
- 평균 수행시간 복잡도는 O(
)최악의 수행 시간 복잡도는 O(
)
* 힙 정렬(Heap Sort)
- 힙 정렬은 전이진 트리를 이용한 정렬 방식
- 구성된 전이진 트리(Complete Binary Tree)를 Heap Tree로 변환하여 정렬
- 평균과 최악 모두 시간 복잡도O(
)
* 2-Way 합병 정렬(Merge Sort)
- 2-Way 합병 정렬은 이미 정렬되어 있는 두 개의 파일을 한 개의 파일로 합병하는 정렬 방식
- 평균과 최악 모두 시간 복잡도 O(
)
* 기수 정렬(Radix Sort) = Bucket Sort
- 기수 정렬은 Queue를 이용하여 자리수(Digit)별로 정렬하는 방식
- 레코드의 키 값을 분석해 같은 수 또는 같은 문자끼리 그 순서에 맞는 버킷에 분배하였다가 버킷의 순서대로 레코드를 꺼내어 정렬
- 평균과 최악 모두 시간 복잡도 O(dn)
* 트리 관련용어
p250 참고
- 노드(Node): 트리의 기본 요소로서 자료 항목과 다른 항목에 대한 가지(Branch)를 합친 것
- 근 노드(Root Node): 트리의 맨 위에 있는 노드
- 디그리(Degree, 차수): 각 노드에서 뻗어나온 가지의 수
- 단말 노드(Terminal Node) = 잎 노드(Leaf Node): 자식이 하나도 없는 노드, 즉 Degree가 0인 노드
- 비단말 노드(Non-Terminal Node): 자식이 하나라도 있는 노드, 즉 Degree가 0이 아닌 노드
- 조상 노드(Ancestors Node): 임의의 노드에서 근 노드에 이르는 경로상에 있는 노드들
- 자식 노드(Son Node): 어떤 노드에 연결된 다음 레벨의 노드들
- 부모 노드(Parent Node): 어떤 노드에 연결된 이전 레벨의 노드들
- 형제 노드(Brother Node, Sibling): 동일한 부모를 갖는 노드들
- Level: 근 노드의 Level을 1로 가정한 후 어떤 Level이 L이면 자식 노드는 L+1
- 깊이(Depth, Height): Tree에서 노드가 가질 수 있는 최대의 레벨
- 숲(Forest): 여러개의 트리가 모여 있는 것
- 트리의 디그리: 노드들의 디그리 중에서 가장 많은 수
sec 62) 이진 트리(Tree) (A)
* 이진 트리
- 이진트리는 차수(Degree)가 2이하인 노드들로 구성된 트리, 즉 자식이 둘이하인 노트들로만 구성된 트리를 말함.
- 이진 트리의 레벨 i에서 최대 노드의 수는
- 이진 트리에서 Terminal Node수가
, 차수가 2인 노드 n가
라 할 때
=
+1
*트리의 운행법
- 트리를 구성하는 각 노드들을 찾아가는 방법을 운행법(Traversal)이라 한다.
- 이진 트리를 운행하는 방법은 산술식의 표기법과 연관성을 갖는다.
>> 이진 트리의 운행법( p253-p256 추가 참고)
- Preorder 운행 - Root -> Left -> Right
- Inorder 운행 - Left -> Root -> Right
- Postorder 운행 - Left -> Right -> Root
sec 63) 정렬(Sort) (A)
필기 20.9
* 삽입 정렬(Insertion Sort)
- 삽입 정렬은 가장 간단한 정렬 방식으로, 이미 순서화된 파일에 새로운 하나의 레코드를 순서에 맞게 삽입시켜 정렬하는 방식
- 평균과 최악 모두 수행 시간 복잡도는 O(
)
필기 20.8
* 선택정렬(Selection Sort)
- 선택 정렬은 n개의 레코드 중에서 최솟값을 찾아 첫 번째 레코드 위치에 놓고, 나머지 (n-1)개 중에서 다시 최솟값을 찾아 두 번째 레코드 위치에 놓는 방식을 반복하여 정렬하는 방식
- 평균과 최악 모두 수행 시간 복잡도는 O(
)
* 버블 정렬(Bubble Sort)
- 버블 정렬은 주어진 파일에서 인접한 두 개의 레코드 키 값을 비교하여 그 크기에 따라 레코드 위치를 서로 교환하는 정렬 방식
- 평균과 최악 모두 수행 시간 복잡도는 O(
)
* 쉘 정렬(Shell Sort)
- 쉘 정렬은 입력파일을 어떤 매개변수의 값으로 서브파일을 구성하고, 각 서브파일을 Insertion 정렬방식으로 순서 배열하는 과정을 반복하는 정렬 방식
- 삽입 정렬(Insertion Sort)을 확장한 개념
- 평균 수행 시간 복잡도는 O(
)이고, 최악의 수행시간 복잡도는 O(
)
* 퀵 정렬(Quick Sort)
- 퀵 정렬은 키를 기준으로 작은 값은 왼쪽, 큰 값은 오른쪽 서브 파일에 분해시키는 과정을 반복하는 정렬방식
- 레코드의 많은 자료 이동을 없애고 하나의 파일을 부분적으로 나누어 가면서 정렬
- 평균 수행시간 복잡도는 O(
)최악의 수행 시간 복잡도는 O(
)
* 힙 정렬(Heap Sort)
- 힙 정렬은 전이진 트리를 이용한 정렬 방식
- 구성된 전이진 트리(Complete Binary Tree)를 Heap Tree로 변환하여 정렬
- 평균과 최악 모두 시간 복잡도O(
)
* 2-Way 합병 정렬(Merge Sort)
- 2-Way 합병 정렬은 이미 정렬되어 있는 두 개의 파일을 한 개의 파일로 합병하는 정렬 방식
- 평균과 최악 모두 시간 복잡도 O(
)
* 기수 정렬(Radix Sort) = Bucket Sort
- 기수 정렬은 Queue를 이용하여 자리수(Digit)별로 정렬하는 방식
- 레코드의 키 값을 분석해 같은 수 또는 같은 문자끼리 그 순서에 맞는 버킷에 분배하였다가 버킷의 순서대로 레코드를 꺼내어 정렬
- 평균과 최악 모두 시간 복잡도 O(dn)
p250 참고
- 노드(Node): 트리의 기본 요소로서 자료 항목과 다른 항목에 대한 가지(Branch)를 합친 것
- 근 노드(Root Node): 트리의 맨 위에 있는 노드
- 디그리(Degree, 차수): 각 노드에서 뻗어나온 가지의 수
- 단말 노드(Terminal Node) = 잎 노드(Leaf Node): 자식이 하나도 없는 노드, 즉 Degree가 0인 노드
- 비단말 노드(Non-Terminal Node): 자식이 하나라도 있는 노드, 즉 Degree가 0이 아닌 노드
- 조상 노드(Ancestors Node): 임의의 노드에서 근 노드에 이르는 경로상에 있는 노드들
- 자식 노드(Son Node): 어떤 노드에 연결된 다음 레벨의 노드들
- 부모 노드(Parent Node): 어떤 노드에 연결된 이전 레벨의 노드들
- 형제 노드(Brother Node, Sibling): 동일한 부모를 갖는 노드들
- Level: 근 노드의 Level을 1로 가정한 후 어떤 Level이 L이면 자식 노드는 L+1
- 깊이(Depth, Height): Tree에서 노드가 가질 수 있는 최대의 레벨
- 숲(Forest): 여러개의 트리가 모여 있는 것
- 트리의 디그리: 노드들의 디그리 중에서 가장 많은 수
sec 62) 이진 트리(Tree) (A)
* 이진 트리
- 이진트리는 차수(Degree)가 2이하인 노드들로 구성된 트리, 즉 자식이 둘이하인 노트들로만 구성된 트리를 말함.
- 이진 트리의 레벨 i에서 최대 노드의 수는
- 이진 트리에서 Terminal Node수가
, 차수가 2인 노드 n가
라 할 때
=
+1
*트리의 운행법
- 트리를 구성하는 각 노드들을 찾아가는 방법을 운행법(Traversal)이라 한다.
- 이진 트리를 운행하는 방법은 산술식의 표기법과 연관성을 갖는다.
>> 이진 트리의 운행법( p253-p256 추가 참고)
- Preorder 운행 - Root -> Left -> Right
- Inorder 운행 - Left -> Root -> Right
- Postorder 운행 - Left -> Right -> Root
sec 63) 정렬(Sort) (A)
필기 20.9
* 삽입 정렬(Insertion Sort)
- 삽입 정렬은 가장 간단한 정렬 방식으로, 이미 순서화된 파일에 새로운 하나의 레코드를 순서에 맞게 삽입시켜 정렬하는 방식
- 평균과 최악 모두 수행 시간 복잡도는 O(
)
필기 20.8
* 선택정렬(Selection Sort)
- 선택 정렬은 n개의 레코드 중에서 최솟값을 찾아 첫 번째 레코드 위치에 놓고, 나머지 (n-1)개 중에서 다시 최솟값을 찾아 두 번째 레코드 위치에 놓는 방식을 반복하여 정렬하는 방식
- 평균과 최악 모두 수행 시간 복잡도는 O(
)
* 버블 정렬(Bubble Sort)
- 버블 정렬은 주어진 파일에서 인접한 두 개의 레코드 키 값을 비교하여 그 크기에 따라 레코드 위치를 서로 교환하는 정렬 방식
- 평균과 최악 모두 수행 시간 복잡도는 O(
)
* 쉘 정렬(Shell Sort)
- 쉘 정렬은 입력파일을 어떤 매개변수의 값으로 서브파일을 구성하고, 각 서브파일을 Insertion 정렬방식으로 순서 배열하는 과정을 반복하는 정렬 방식
- 삽입 정렬(Insertion Sort)을 확장한 개념
- 평균 수행 시간 복잡도는 O(
)이고, 최악의 수행시간 복잡도는 O(
)
* 퀵 정렬(Quick Sort)
- 퀵 정렬은 키를 기준으로 작은 값은 왼쪽, 큰 값은 오른쪽 서브 파일에 분해시키는 과정을 반복하는 정렬방식
- 레코드의 많은 자료 이동을 없애고 하나의 파일을 부분적으로 나누어 가면서 정렬
- 평균 수행시간 복잡도는 O(
)최악의 수행 시간 복잡도는 O(
)
* 힙 정렬(Heap Sort)
- 힙 정렬은 전이진 트리를 이용한 정렬 방식
- 구성된 전이진 트리(Complete Binary Tree)를 Heap Tree로 변환하여 정렬
- 평균과 최악 모두 시간 복잡도O(
)
* 2-Way 합병 정렬(Merge Sort)
- 2-Way 합병 정렬은 이미 정렬되어 있는 두 개의 파일을 한 개의 파일로 합병하는 정렬 방식
- 평균과 최악 모두 시간 복잡도 O(
)
* 기수 정렬(Radix Sort) = Bucket Sort
- 기수 정렬은 Queue를 이용하여 자리수(Digit)별로 정렬하는 방식
- 레코드의 키 값을 분석해 같은 수 또는 같은 문자끼리 그 순서에 맞는 버킷에 분배하였다가 버킷의 순서대로 레코드를 꺼내어 정렬
- 평균과 최악 모두 시간 복잡도 O(dn)
- 노드(Node): 트리의 기본 요소로서 자료 항목과 다른 항목에 대한 가지(Branch)를 합친 것
- 근 노드(Root Node): 트리의 맨 위에 있는 노드
- 디그리(Degree, 차수): 각 노드에서 뻗어나온 가지의 수
- 단말 노드(Terminal Node) = 잎 노드(Leaf Node): 자식이 하나도 없는 노드, 즉 Degree가 0인 노드
- 비단말 노드(Non-Terminal Node): 자식이 하나라도 있는 노드, 즉 Degree가 0이 아닌 노드
- 조상 노드(Ancestors Node): 임의의 노드에서 근 노드에 이르는 경로상에 있는 노드들
- 자식 노드(Son Node): 어떤 노드에 연결된 다음 레벨의 노드들
- 부모 노드(Parent Node): 어떤 노드에 연결된 이전 레벨의 노드들
- 형제 노드(Brother Node, Sibling): 동일한 부모를 갖는 노드들
- Level: 근 노드의 Level을 1로 가정한 후 어떤 Level이 L이면 자식 노드는 L+1
- 깊이(Depth, Height): Tree에서 노드가 가질 수 있는 최대의 레벨
- 숲(Forest): 여러개의 트리가 모여 있는 것
- 트리의 디그리: 노드들의 디그리 중에서 가장 많은 수
sec 62) 이진 트리(Tree) (A)
* 이진 트리
- 이진트리는 차수(Degree)가 2이하인 노드들로 구성된 트리, 즉 자식이 둘이하인 노트들로만 구성된 트리를 말함.
- 이진 트리의 레벨 i에서 최대 노드의 수는
- 이진 트리에서 Terminal Node수가
, 차수가 2인 노드 n가
라 할 때
=
+1
*트리의 운행법
- 트리를 구성하는 각 노드들을 찾아가는 방법을 운행법(Traversal)이라 한다.
- 이진 트리를 운행하는 방법은 산술식의 표기법과 연관성을 갖는다.
>> 이진 트리의 운행법( p253-p256 추가 참고)
- Preorder 운행 - Root -> Left -> Right
- Inorder 운행 - Left -> Root -> Right
- Postorder 운행 - Left -> Right -> Root
sec 63) 정렬(Sort) (A)
필기 20.9
* 삽입 정렬(Insertion Sort)
- 삽입 정렬은 가장 간단한 정렬 방식으로, 이미 순서화된 파일에 새로운 하나의 레코드를 순서에 맞게 삽입시켜 정렬하는 방식
- 평균과 최악 모두 수행 시간 복잡도는 O(
)
필기 20.8
* 선택정렬(Selection Sort)
- 선택 정렬은 n개의 레코드 중에서 최솟값을 찾아 첫 번째 레코드 위치에 놓고, 나머지 (n-1)개 중에서 다시 최솟값을 찾아 두 번째 레코드 위치에 놓는 방식을 반복하여 정렬하는 방식
- 평균과 최악 모두 수행 시간 복잡도는 O(
)
* 버블 정렬(Bubble Sort)
- 버블 정렬은 주어진 파일에서 인접한 두 개의 레코드 키 값을 비교하여 그 크기에 따라 레코드 위치를 서로 교환하는 정렬 방식
- 평균과 최악 모두 수행 시간 복잡도는 O(
)
* 쉘 정렬(Shell Sort)
- 쉘 정렬은 입력파일을 어떤 매개변수의 값으로 서브파일을 구성하고, 각 서브파일을 Insertion 정렬방식으로 순서 배열하는 과정을 반복하는 정렬 방식
- 삽입 정렬(Insertion Sort)을 확장한 개념
- 평균 수행 시간 복잡도는 O(
)이고, 최악의 수행시간 복잡도는 O(
)
* 퀵 정렬(Quick Sort)
- 퀵 정렬은 키를 기준으로 작은 값은 왼쪽, 큰 값은 오른쪽 서브 파일에 분해시키는 과정을 반복하는 정렬방식
- 레코드의 많은 자료 이동을 없애고 하나의 파일을 부분적으로 나누어 가면서 정렬
- 평균 수행시간 복잡도는 O(
)최악의 수행 시간 복잡도는 O(
)
* 힙 정렬(Heap Sort)
- 힙 정렬은 전이진 트리를 이용한 정렬 방식
- 구성된 전이진 트리(Complete Binary Tree)를 Heap Tree로 변환하여 정렬
- 평균과 최악 모두 시간 복잡도O(
)
* 2-Way 합병 정렬(Merge Sort)
- 2-Way 합병 정렬은 이미 정렬되어 있는 두 개의 파일을 한 개의 파일로 합병하는 정렬 방식
- 평균과 최악 모두 시간 복잡도 O(
)
* 기수 정렬(Radix Sort) = Bucket Sort
- 기수 정렬은 Queue를 이용하여 자리수(Digit)별로 정렬하는 방식
- 레코드의 키 값을 분석해 같은 수 또는 같은 문자끼리 그 순서에 맞는 버킷에 분배하였다가 버킷의 순서대로 레코드를 꺼내어 정렬
- 평균과 최악 모두 시간 복잡도 O(dn)
- 근 노드(Root Node): 트리의 맨 위에 있는 노드
- 디그리(Degree, 차수): 각 노드에서 뻗어나온 가지의 수
- 단말 노드(Terminal Node) = 잎 노드(Leaf Node): 자식이 하나도 없는 노드, 즉 Degree가 0인 노드
- 비단말 노드(Non-Terminal Node): 자식이 하나라도 있는 노드, 즉 Degree가 0이 아닌 노드
- 조상 노드(Ancestors Node): 임의의 노드에서 근 노드에 이르는 경로상에 있는 노드들
- 자식 노드(Son Node): 어떤 노드에 연결된 다음 레벨의 노드들
- 부모 노드(Parent Node): 어떤 노드에 연결된 이전 레벨의 노드들
- 형제 노드(Brother Node, Sibling): 동일한 부모를 갖는 노드들
- Level: 근 노드의 Level을 1로 가정한 후 어떤 Level이 L이면 자식 노드는 L+1
- 깊이(Depth, Height): Tree에서 노드가 가질 수 있는 최대의 레벨
- 숲(Forest): 여러개의 트리가 모여 있는 것
- 트리의 디그리: 노드들의 디그리 중에서 가장 많은 수
sec 62) 이진 트리(Tree) (A)
* 이진 트리
- 이진트리는 차수(Degree)가 2이하인 노드들로 구성된 트리, 즉 자식이 둘이하인 노트들로만 구성된 트리를 말함.
- 이진 트리의 레벨 i에서 최대 노드의 수는
- 이진 트리에서 Terminal Node수가
, 차수가 2인 노드 n가
라 할 때
=
+1
*트리의 운행법
- 트리를 구성하는 각 노드들을 찾아가는 방법을 운행법(Traversal)이라 한다.
- 이진 트리를 운행하는 방법은 산술식의 표기법과 연관성을 갖는다.
>> 이진 트리의 운행법( p253-p256 추가 참고)
- Preorder 운행 - Root -> Left -> Right
- Inorder 운행 - Left -> Root -> Right
- Postorder 운행 - Left -> Right -> Root
sec 63) 정렬(Sort) (A)
필기 20.9
* 삽입 정렬(Insertion Sort)
- 삽입 정렬은 가장 간단한 정렬 방식으로, 이미 순서화된 파일에 새로운 하나의 레코드를 순서에 맞게 삽입시켜 정렬하는 방식
- 평균과 최악 모두 수행 시간 복잡도는 O(
)
필기 20.8
* 선택정렬(Selection Sort)
- 선택 정렬은 n개의 레코드 중에서 최솟값을 찾아 첫 번째 레코드 위치에 놓고, 나머지 (n-1)개 중에서 다시 최솟값을 찾아 두 번째 레코드 위치에 놓는 방식을 반복하여 정렬하는 방식
- 평균과 최악 모두 수행 시간 복잡도는 O(
)
* 버블 정렬(Bubble Sort)
- 버블 정렬은 주어진 파일에서 인접한 두 개의 레코드 키 값을 비교하여 그 크기에 따라 레코드 위치를 서로 교환하는 정렬 방식
- 평균과 최악 모두 수행 시간 복잡도는 O(
)
* 쉘 정렬(Shell Sort)
- 쉘 정렬은 입력파일을 어떤 매개변수의 값으로 서브파일을 구성하고, 각 서브파일을 Insertion 정렬방식으로 순서 배열하는 과정을 반복하는 정렬 방식
- 삽입 정렬(Insertion Sort)을 확장한 개념
- 평균 수행 시간 복잡도는 O(
)이고, 최악의 수행시간 복잡도는 O(
)
* 퀵 정렬(Quick Sort)
- 퀵 정렬은 키를 기준으로 작은 값은 왼쪽, 큰 값은 오른쪽 서브 파일에 분해시키는 과정을 반복하는 정렬방식
- 레코드의 많은 자료 이동을 없애고 하나의 파일을 부분적으로 나누어 가면서 정렬
- 평균 수행시간 복잡도는 O(
)최악의 수행 시간 복잡도는 O(
)
* 힙 정렬(Heap Sort)
- 힙 정렬은 전이진 트리를 이용한 정렬 방식
- 구성된 전이진 트리(Complete Binary Tree)를 Heap Tree로 변환하여 정렬
- 평균과 최악 모두 시간 복잡도O(
)
* 2-Way 합병 정렬(Merge Sort)
- 2-Way 합병 정렬은 이미 정렬되어 있는 두 개의 파일을 한 개의 파일로 합병하는 정렬 방식
- 평균과 최악 모두 시간 복잡도 O(
)
* 기수 정렬(Radix Sort) = Bucket Sort
- 기수 정렬은 Queue를 이용하여 자리수(Digit)별로 정렬하는 방식
- 레코드의 키 값을 분석해 같은 수 또는 같은 문자끼리 그 순서에 맞는 버킷에 분배하였다가 버킷의 순서대로 레코드를 꺼내어 정렬
- 평균과 최악 모두 시간 복잡도 O(dn)
- 디그리(Degree, 차수): 각 노드에서 뻗어나온 가지의 수
- 단말 노드(Terminal Node) = 잎 노드(Leaf Node): 자식이 하나도 없는 노드, 즉 Degree가 0인 노드
- 비단말 노드(Non-Terminal Node): 자식이 하나라도 있는 노드, 즉 Degree가 0이 아닌 노드
- 조상 노드(Ancestors Node): 임의의 노드에서 근 노드에 이르는 경로상에 있는 노드들
- 자식 노드(Son Node): 어떤 노드에 연결된 다음 레벨의 노드들
- 부모 노드(Parent Node): 어떤 노드에 연결된 이전 레벨의 노드들
- 형제 노드(Brother Node, Sibling): 동일한 부모를 갖는 노드들
- Level: 근 노드의 Level을 1로 가정한 후 어떤 Level이 L이면 자식 노드는 L+1
- 깊이(Depth, Height): Tree에서 노드가 가질 수 있는 최대의 레벨
- 숲(Forest): 여러개의 트리가 모여 있는 것
- 트리의 디그리: 노드들의 디그리 중에서 가장 많은 수
sec 62) 이진 트리(Tree) (A)
* 이진 트리
- 이진트리는 차수(Degree)가 2이하인 노드들로 구성된 트리, 즉 자식이 둘이하인 노트들로만 구성된 트리를 말함.
- 이진 트리의 레벨 i에서 최대 노드의 수는
- 이진 트리에서 Terminal Node수가
, 차수가 2인 노드 n가
라 할 때
=
+1
*트리의 운행법
- 트리를 구성하는 각 노드들을 찾아가는 방법을 운행법(Traversal)이라 한다.
- 이진 트리를 운행하는 방법은 산술식의 표기법과 연관성을 갖는다.
>> 이진 트리의 운행법( p253-p256 추가 참고)
- Preorder 운행 - Root -> Left -> Right
- Inorder 운행 - Left -> Root -> Right
- Postorder 운행 - Left -> Right -> Root
sec 63) 정렬(Sort) (A)
필기 20.9
* 삽입 정렬(Insertion Sort)
- 삽입 정렬은 가장 간단한 정렬 방식으로, 이미 순서화된 파일에 새로운 하나의 레코드를 순서에 맞게 삽입시켜 정렬하는 방식
- 평균과 최악 모두 수행 시간 복잡도는 O(
)
필기 20.8
* 선택정렬(Selection Sort)
- 선택 정렬은 n개의 레코드 중에서 최솟값을 찾아 첫 번째 레코드 위치에 놓고, 나머지 (n-1)개 중에서 다시 최솟값을 찾아 두 번째 레코드 위치에 놓는 방식을 반복하여 정렬하는 방식
- 평균과 최악 모두 수행 시간 복잡도는 O(
)
* 버블 정렬(Bubble Sort)
- 버블 정렬은 주어진 파일에서 인접한 두 개의 레코드 키 값을 비교하여 그 크기에 따라 레코드 위치를 서로 교환하는 정렬 방식
- 평균과 최악 모두 수행 시간 복잡도는 O(
)
* 쉘 정렬(Shell Sort)
- 쉘 정렬은 입력파일을 어떤 매개변수의 값으로 서브파일을 구성하고, 각 서브파일을 Insertion 정렬방식으로 순서 배열하는 과정을 반복하는 정렬 방식
- 삽입 정렬(Insertion Sort)을 확장한 개념
- 평균 수행 시간 복잡도는 O(
)이고, 최악의 수행시간 복잡도는 O(
)
* 퀵 정렬(Quick Sort)
- 퀵 정렬은 키를 기준으로 작은 값은 왼쪽, 큰 값은 오른쪽 서브 파일에 분해시키는 과정을 반복하는 정렬방식
- 레코드의 많은 자료 이동을 없애고 하나의 파일을 부분적으로 나누어 가면서 정렬
- 평균 수행시간 복잡도는 O(
)최악의 수행 시간 복잡도는 O(
)
* 힙 정렬(Heap Sort)
- 힙 정렬은 전이진 트리를 이용한 정렬 방식
- 구성된 전이진 트리(Complete Binary Tree)를 Heap Tree로 변환하여 정렬
- 평균과 최악 모두 시간 복잡도O(
)
* 2-Way 합병 정렬(Merge Sort)
- 2-Way 합병 정렬은 이미 정렬되어 있는 두 개의 파일을 한 개의 파일로 합병하는 정렬 방식
- 평균과 최악 모두 시간 복잡도 O(
)
* 기수 정렬(Radix Sort) = Bucket Sort
- 기수 정렬은 Queue를 이용하여 자리수(Digit)별로 정렬하는 방식
- 레코드의 키 값을 분석해 같은 수 또는 같은 문자끼리 그 순서에 맞는 버킷에 분배하였다가 버킷의 순서대로 레코드를 꺼내어 정렬
- 평균과 최악 모두 시간 복잡도 O(dn)
- 단말 노드(Terminal Node) = 잎 노드(Leaf Node): 자식이 하나도 없는 노드, 즉 Degree가 0인 노드
- 비단말 노드(Non-Terminal Node): 자식이 하나라도 있는 노드, 즉 Degree가 0이 아닌 노드
- 조상 노드(Ancestors Node): 임의의 노드에서 근 노드에 이르는 경로상에 있는 노드들
- 자식 노드(Son Node): 어떤 노드에 연결된 다음 레벨의 노드들
- 부모 노드(Parent Node): 어떤 노드에 연결된 이전 레벨의 노드들
- 형제 노드(Brother Node, Sibling): 동일한 부모를 갖는 노드들
- Level: 근 노드의 Level을 1로 가정한 후 어떤 Level이 L이면 자식 노드는 L+1
- 깊이(Depth, Height): Tree에서 노드가 가질 수 있는 최대의 레벨
- 숲(Forest): 여러개의 트리가 모여 있는 것
- 트리의 디그리: 노드들의 디그리 중에서 가장 많은 수
sec 62) 이진 트리(Tree) (A)
* 이진 트리
- 이진트리는 차수(Degree)가 2이하인 노드들로 구성된 트리, 즉 자식이 둘이하인 노트들로만 구성된 트리를 말함.
- 이진 트리의 레벨 i에서 최대 노드의 수는
- 이진 트리에서 Terminal Node수가
, 차수가 2인 노드 n가
라 할 때
=
+1
*트리의 운행법
- 트리를 구성하는 각 노드들을 찾아가는 방법을 운행법(Traversal)이라 한다.
- 이진 트리를 운행하는 방법은 산술식의 표기법과 연관성을 갖는다.
>> 이진 트리의 운행법( p253-p256 추가 참고)
- Preorder 운행 - Root -> Left -> Right
- Inorder 운행 - Left -> Root -> Right
- Postorder 운행 - Left -> Right -> Root
sec 63) 정렬(Sort) (A)
필기 20.9
* 삽입 정렬(Insertion Sort)
- 삽입 정렬은 가장 간단한 정렬 방식으로, 이미 순서화된 파일에 새로운 하나의 레코드를 순서에 맞게 삽입시켜 정렬하는 방식
- 평균과 최악 모두 수행 시간 복잡도는 O(
)
필기 20.8
* 선택정렬(Selection Sort)
- 선택 정렬은 n개의 레코드 중에서 최솟값을 찾아 첫 번째 레코드 위치에 놓고, 나머지 (n-1)개 중에서 다시 최솟값을 찾아 두 번째 레코드 위치에 놓는 방식을 반복하여 정렬하는 방식
- 평균과 최악 모두 수행 시간 복잡도는 O(
)
* 버블 정렬(Bubble Sort)
- 버블 정렬은 주어진 파일에서 인접한 두 개의 레코드 키 값을 비교하여 그 크기에 따라 레코드 위치를 서로 교환하는 정렬 방식
- 평균과 최악 모두 수행 시간 복잡도는 O(
)
* 쉘 정렬(Shell Sort)
- 쉘 정렬은 입력파일을 어떤 매개변수의 값으로 서브파일을 구성하고, 각 서브파일을 Insertion 정렬방식으로 순서 배열하는 과정을 반복하는 정렬 방식
- 삽입 정렬(Insertion Sort)을 확장한 개념
- 평균 수행 시간 복잡도는 O(
)이고, 최악의 수행시간 복잡도는 O(
)
* 퀵 정렬(Quick Sort)
- 퀵 정렬은 키를 기준으로 작은 값은 왼쪽, 큰 값은 오른쪽 서브 파일에 분해시키는 과정을 반복하는 정렬방식
- 레코드의 많은 자료 이동을 없애고 하나의 파일을 부분적으로 나누어 가면서 정렬
- 평균 수행시간 복잡도는 O(
)최악의 수행 시간 복잡도는 O(
)
* 힙 정렬(Heap Sort)
- 힙 정렬은 전이진 트리를 이용한 정렬 방식
- 구성된 전이진 트리(Complete Binary Tree)를 Heap Tree로 변환하여 정렬
- 평균과 최악 모두 시간 복잡도O(
)
* 2-Way 합병 정렬(Merge Sort)
- 2-Way 합병 정렬은 이미 정렬되어 있는 두 개의 파일을 한 개의 파일로 합병하는 정렬 방식
- 평균과 최악 모두 시간 복잡도 O(
)
* 기수 정렬(Radix Sort) = Bucket Sort
- 기수 정렬은 Queue를 이용하여 자리수(Digit)별로 정렬하는 방식
- 레코드의 키 값을 분석해 같은 수 또는 같은 문자끼리 그 순서에 맞는 버킷에 분배하였다가 버킷의 순서대로 레코드를 꺼내어 정렬
- 평균과 최악 모두 시간 복잡도 O(dn)
- 비단말 노드(Non-Terminal Node): 자식이 하나라도 있는 노드, 즉 Degree가 0이 아닌 노드
- 조상 노드(Ancestors Node): 임의의 노드에서 근 노드에 이르는 경로상에 있는 노드들
- 자식 노드(Son Node): 어떤 노드에 연결된 다음 레벨의 노드들
- 부모 노드(Parent Node): 어떤 노드에 연결된 이전 레벨의 노드들
- 형제 노드(Brother Node, Sibling): 동일한 부모를 갖는 노드들
- Level: 근 노드의 Level을 1로 가정한 후 어떤 Level이 L이면 자식 노드는 L+1
- 깊이(Depth, Height): Tree에서 노드가 가질 수 있는 최대의 레벨
- 숲(Forest): 여러개의 트리가 모여 있는 것
- 트리의 디그리: 노드들의 디그리 중에서 가장 많은 수
sec 62) 이진 트리(Tree) (A)
* 이진 트리
- 이진트리는 차수(Degree)가 2이하인 노드들로 구성된 트리, 즉 자식이 둘이하인 노트들로만 구성된 트리를 말함.
- 이진 트리의 레벨 i에서 최대 노드의 수는
- 이진 트리에서 Terminal Node수가
, 차수가 2인 노드 n가
라 할 때
=
+1
*트리의 운행법
- 트리를 구성하는 각 노드들을 찾아가는 방법을 운행법(Traversal)이라 한다.
- 이진 트리를 운행하는 방법은 산술식의 표기법과 연관성을 갖는다.
>> 이진 트리의 운행법( p253-p256 추가 참고)
- Preorder 운행 - Root -> Left -> Right
- Inorder 운행 - Left -> Root -> Right
- Postorder 운행 - Left -> Right -> Root
sec 63) 정렬(Sort) (A)
필기 20.9
* 삽입 정렬(Insertion Sort)
- 삽입 정렬은 가장 간단한 정렬 방식으로, 이미 순서화된 파일에 새로운 하나의 레코드를 순서에 맞게 삽입시켜 정렬하는 방식
- 평균과 최악 모두 수행 시간 복잡도는 O(
)
필기 20.8
* 선택정렬(Selection Sort)
- 선택 정렬은 n개의 레코드 중에서 최솟값을 찾아 첫 번째 레코드 위치에 놓고, 나머지 (n-1)개 중에서 다시 최솟값을 찾아 두 번째 레코드 위치에 놓는 방식을 반복하여 정렬하는 방식
- 평균과 최악 모두 수행 시간 복잡도는 O(
)
* 버블 정렬(Bubble Sort)
- 버블 정렬은 주어진 파일에서 인접한 두 개의 레코드 키 값을 비교하여 그 크기에 따라 레코드 위치를 서로 교환하는 정렬 방식
- 평균과 최악 모두 수행 시간 복잡도는 O(
)
* 쉘 정렬(Shell Sort)
- 쉘 정렬은 입력파일을 어떤 매개변수의 값으로 서브파일을 구성하고, 각 서브파일을 Insertion 정렬방식으로 순서 배열하는 과정을 반복하는 정렬 방식
- 삽입 정렬(Insertion Sort)을 확장한 개념
- 평균 수행 시간 복잡도는 O(
)이고, 최악의 수행시간 복잡도는 O(
)
* 퀵 정렬(Quick Sort)
- 퀵 정렬은 키를 기준으로 작은 값은 왼쪽, 큰 값은 오른쪽 서브 파일에 분해시키는 과정을 반복하는 정렬방식
- 레코드의 많은 자료 이동을 없애고 하나의 파일을 부분적으로 나누어 가면서 정렬
- 평균 수행시간 복잡도는 O(
)최악의 수행 시간 복잡도는 O(
)
* 힙 정렬(Heap Sort)
- 힙 정렬은 전이진 트리를 이용한 정렬 방식
- 구성된 전이진 트리(Complete Binary Tree)를 Heap Tree로 변환하여 정렬
- 평균과 최악 모두 시간 복잡도O(
)
* 2-Way 합병 정렬(Merge Sort)
- 2-Way 합병 정렬은 이미 정렬되어 있는 두 개의 파일을 한 개의 파일로 합병하는 정렬 방식
- 평균과 최악 모두 시간 복잡도 O(
)
* 기수 정렬(Radix Sort) = Bucket Sort
- 기수 정렬은 Queue를 이용하여 자리수(Digit)별로 정렬하는 방식
- 레코드의 키 값을 분석해 같은 수 또는 같은 문자끼리 그 순서에 맞는 버킷에 분배하였다가 버킷의 순서대로 레코드를 꺼내어 정렬
- 평균과 최악 모두 시간 복잡도 O(dn)
- 조상 노드(Ancestors Node): 임의의 노드에서 근 노드에 이르는 경로상에 있는 노드들
- 자식 노드(Son Node): 어떤 노드에 연결된 다음 레벨의 노드들
- 부모 노드(Parent Node): 어떤 노드에 연결된 이전 레벨의 노드들
- 형제 노드(Brother Node, Sibling): 동일한 부모를 갖는 노드들
- Level: 근 노드의 Level을 1로 가정한 후 어떤 Level이 L이면 자식 노드는 L+1
- 깊이(Depth, Height): Tree에서 노드가 가질 수 있는 최대의 레벨
- 숲(Forest): 여러개의 트리가 모여 있는 것
- 트리의 디그리: 노드들의 디그리 중에서 가장 많은 수
sec 62) 이진 트리(Tree) (A)
* 이진 트리
- 이진트리는 차수(Degree)가 2이하인 노드들로 구성된 트리, 즉 자식이 둘이하인 노트들로만 구성된 트리를 말함.
- 이진 트리의 레벨 i에서 최대 노드의 수는
- 이진 트리에서 Terminal Node수가
, 차수가 2인 노드 n가
라 할 때
=
+1
*트리의 운행법
- 트리를 구성하는 각 노드들을 찾아가는 방법을 운행법(Traversal)이라 한다.
- 이진 트리를 운행하는 방법은 산술식의 표기법과 연관성을 갖는다.
>> 이진 트리의 운행법( p253-p256 추가 참고)
- Preorder 운행 - Root -> Left -> Right
- Inorder 운행 - Left -> Root -> Right
- Postorder 운행 - Left -> Right -> Root
sec 63) 정렬(Sort) (A)
필기 20.9
* 삽입 정렬(Insertion Sort)
- 삽입 정렬은 가장 간단한 정렬 방식으로, 이미 순서화된 파일에 새로운 하나의 레코드를 순서에 맞게 삽입시켜 정렬하는 방식
- 평균과 최악 모두 수행 시간 복잡도는 O(
)
필기 20.8
* 선택정렬(Selection Sort)
- 선택 정렬은 n개의 레코드 중에서 최솟값을 찾아 첫 번째 레코드 위치에 놓고, 나머지 (n-1)개 중에서 다시 최솟값을 찾아 두 번째 레코드 위치에 놓는 방식을 반복하여 정렬하는 방식
- 평균과 최악 모두 수행 시간 복잡도는 O(
)
* 버블 정렬(Bubble Sort)
- 버블 정렬은 주어진 파일에서 인접한 두 개의 레코드 키 값을 비교하여 그 크기에 따라 레코드 위치를 서로 교환하는 정렬 방식
- 평균과 최악 모두 수행 시간 복잡도는 O(
)
* 쉘 정렬(Shell Sort)
- 쉘 정렬은 입력파일을 어떤 매개변수의 값으로 서브파일을 구성하고, 각 서브파일을 Insertion 정렬방식으로 순서 배열하는 과정을 반복하는 정렬 방식
- 삽입 정렬(Insertion Sort)을 확장한 개념
- 평균 수행 시간 복잡도는 O(
)이고, 최악의 수행시간 복잡도는 O(
)
* 퀵 정렬(Quick Sort)
- 퀵 정렬은 키를 기준으로 작은 값은 왼쪽, 큰 값은 오른쪽 서브 파일에 분해시키는 과정을 반복하는 정렬방식
- 레코드의 많은 자료 이동을 없애고 하나의 파일을 부분적으로 나누어 가면서 정렬
- 평균 수행시간 복잡도는 O(
)최악의 수행 시간 복잡도는 O(
)
* 힙 정렬(Heap Sort)
- 힙 정렬은 전이진 트리를 이용한 정렬 방식
- 구성된 전이진 트리(Complete Binary Tree)를 Heap Tree로 변환하여 정렬
- 평균과 최악 모두 시간 복잡도O(
)
* 2-Way 합병 정렬(Merge Sort)
- 2-Way 합병 정렬은 이미 정렬되어 있는 두 개의 파일을 한 개의 파일로 합병하는 정렬 방식
- 평균과 최악 모두 시간 복잡도 O(
)
* 기수 정렬(Radix Sort) = Bucket Sort
- 기수 정렬은 Queue를 이용하여 자리수(Digit)별로 정렬하는 방식
- 레코드의 키 값을 분석해 같은 수 또는 같은 문자끼리 그 순서에 맞는 버킷에 분배하였다가 버킷의 순서대로 레코드를 꺼내어 정렬
- 평균과 최악 모두 시간 복잡도 O(dn)
- 자식 노드(Son Node): 어떤 노드에 연결된 다음 레벨의 노드들
- 부모 노드(Parent Node): 어떤 노드에 연결된 이전 레벨의 노드들
- 형제 노드(Brother Node, Sibling): 동일한 부모를 갖는 노드들
- Level: 근 노드의 Level을 1로 가정한 후 어떤 Level이 L이면 자식 노드는 L+1
- 깊이(Depth, Height): Tree에서 노드가 가질 수 있는 최대의 레벨
- 숲(Forest): 여러개의 트리가 모여 있는 것
- 트리의 디그리: 노드들의 디그리 중에서 가장 많은 수
sec 62) 이진 트리(Tree) (A)
* 이진 트리
- 이진트리는 차수(Degree)가 2이하인 노드들로 구성된 트리, 즉 자식이 둘이하인 노트들로만 구성된 트리를 말함.
- 이진 트리의 레벨 i에서 최대 노드의 수는
- 이진 트리에서 Terminal Node수가
, 차수가 2인 노드 n가
라 할 때
=
+1
*트리의 운행법
- 트리를 구성하는 각 노드들을 찾아가는 방법을 운행법(Traversal)이라 한다.
- 이진 트리를 운행하는 방법은 산술식의 표기법과 연관성을 갖는다.
>> 이진 트리의 운행법( p253-p256 추가 참고)
- Preorder 운행 - Root -> Left -> Right
- Inorder 운행 - Left -> Root -> Right
- Postorder 운행 - Left -> Right -> Root
sec 63) 정렬(Sort) (A)
필기 20.9
* 삽입 정렬(Insertion Sort)
- 삽입 정렬은 가장 간단한 정렬 방식으로, 이미 순서화된 파일에 새로운 하나의 레코드를 순서에 맞게 삽입시켜 정렬하는 방식
- 평균과 최악 모두 수행 시간 복잡도는 O(
)
필기 20.8
* 선택정렬(Selection Sort)
- 선택 정렬은 n개의 레코드 중에서 최솟값을 찾아 첫 번째 레코드 위치에 놓고, 나머지 (n-1)개 중에서 다시 최솟값을 찾아 두 번째 레코드 위치에 놓는 방식을 반복하여 정렬하는 방식
- 평균과 최악 모두 수행 시간 복잡도는 O(
)
* 버블 정렬(Bubble Sort)
- 버블 정렬은 주어진 파일에서 인접한 두 개의 레코드 키 값을 비교하여 그 크기에 따라 레코드 위치를 서로 교환하는 정렬 방식
- 평균과 최악 모두 수행 시간 복잡도는 O(
)
* 쉘 정렬(Shell Sort)
- 쉘 정렬은 입력파일을 어떤 매개변수의 값으로 서브파일을 구성하고, 각 서브파일을 Insertion 정렬방식으로 순서 배열하는 과정을 반복하는 정렬 방식
- 삽입 정렬(Insertion Sort)을 확장한 개념
- 평균 수행 시간 복잡도는 O(
)이고, 최악의 수행시간 복잡도는 O(
)
* 퀵 정렬(Quick Sort)
- 퀵 정렬은 키를 기준으로 작은 값은 왼쪽, 큰 값은 오른쪽 서브 파일에 분해시키는 과정을 반복하는 정렬방식
- 레코드의 많은 자료 이동을 없애고 하나의 파일을 부분적으로 나누어 가면서 정렬
- 평균 수행시간 복잡도는 O(
)최악의 수행 시간 복잡도는 O(
)
* 힙 정렬(Heap Sort)
- 힙 정렬은 전이진 트리를 이용한 정렬 방식
- 구성된 전이진 트리(Complete Binary Tree)를 Heap Tree로 변환하여 정렬
- 평균과 최악 모두 시간 복잡도O(
)
* 2-Way 합병 정렬(Merge Sort)
- 2-Way 합병 정렬은 이미 정렬되어 있는 두 개의 파일을 한 개의 파일로 합병하는 정렬 방식
- 평균과 최악 모두 시간 복잡도 O(
)
* 기수 정렬(Radix Sort) = Bucket Sort
- 기수 정렬은 Queue를 이용하여 자리수(Digit)별로 정렬하는 방식
- 레코드의 키 값을 분석해 같은 수 또는 같은 문자끼리 그 순서에 맞는 버킷에 분배하였다가 버킷의 순서대로 레코드를 꺼내어 정렬
- 평균과 최악 모두 시간 복잡도 O(dn)