2025 정보처리기사 필기 도전기 20 - 트리
트리의 개요
정점(노드)과 선분(가지)을 이용하여 사이클을 이루지 않도록 구성한 그래프의 특수한 형태임
1. 트리는 하나의 기억 공간을 노드라고 하며, 노드와노드를 연결하는 선을 링크라고 함.ㅁ
2. 트리는 가족의 계보(족보),조직도 등을 표현하기에 적합함.
트리의 운행법
트리를 구성하는 각 노드들을 찾아가는 방법을 운행법이라 함.
1. 이진 트리를 운행하는 방법은 산술식의 표기법과 연관성을 갖는다.
2. 이진 트리의 운행법은 다음 세가지가 있음
수식의 표기법
산술식을 계산하기 위해 기억공간에 기억하는 방법으로 이진트를 많이 사용함
이진 트리로 만들어진 수식을 인오더, 프리오더, 포스트오더로 운행하면 각각 중위,전위,후위 표기법이 된다.
삽입 정렬
삽입 정렬은 가장 간단한 정렬 방식으로 이미 순서화된 파일에 새로운 하나의 레코드를 순서에 맞게 삽입시켜 정렬함.
1. 두번째 키와 첫번째 키를 비교해 순서대로 나열(1회전)하고, 이어서 세번째 키를 첫 번째, 두번째 키와 비교해 순서대로 나열(2회전)하고, 계속해서 n번째 키를 앞의 n-1의 키와 비교하여 알맞은 순서에 삽입하여 정렬하는 방식
2. 평균과 최악 모두 수행 시간 복잡도는 O(n제곱)이다.
쉘정렬
쉘 정렬은 삽입정렬을 확장한 개념
1. 입력 파일을 어떤 매개변수의 값으로 서브파일을 구성하고, 각 서비파일을 Insertion 정렬방식으로 순서 배열하는 과정을 반복하는 정렬 방식, 즉 임의의 레크드 키와 h만큼 떨어진 곳의 레코드 키를 비교하여 순서화되어 있지 않으면 서로 교환하는 것을 반복하는 정렬 방식
2. 입력파일이 부분적으로 정렬되어 있는 경우에 유리한 방식
3. 평균 수행시간 복잡도는 O(n으 1.5제곱)이고, 최악의 수행 시간 복잡도는 O(n의 제곱)이다.
선택정렬
선택정렬은 n개의 레코드 중에서 최소값을 찾아 첫번째 레코드 위치에 놓고,나머지(n-1)개 중에서 다시 최소값을 찾아 두번째 레코드 위치에 놓는 방식을 반복하여 정렬
평균과 최악 모두 수행시간 복잡도는 0(n의 제곱)이다.
버블 정렬
버블정렬은 주어진 파일에서 인접한 두개의 레코드 키값을 비교하여 그 크기에 따라 레코드의 위치를 서로 교환하는 정렬 방식
계속 정렬 여부를 플래그 비트(f)로 결정함
평균과 최악 모두 수행 시간 복잡도는 O(n의 제곱)이다.
퀵정렬
퀵 정렬은 레코드의 많은 자료 이동으 없애고 하나의 파일을 부분적으로 나누어 가면서 정렬하는 방법으로 키를 기준으로 작은 값은 왼쪽에, 큰값은 오른쪽에 서브파일로 분해시키는 방식으로 정렬함ㅁㅁ.
1. 위치에 관계없이 임의의 키를 분할 원소로 사용할 수 있음
2. 정렬 방식 중에서 가장 빠른 방식
3. 프로그램에서 되부름을 이용하기 땜문에 스택이 필요함.
4. 분할과 정복을 통해 자료를 정렬함.
분할 : 기준값인 피봇을 중심으로 정렬할 자료들을 2개의 부분집합으로 나눈다.
정복 : 부분집합의 원소들 중 피봇보다 작은 원소들은 왼쪽, ㅍ피봇보다 큰 원소들은 오른쪽 부분집합으로 정렬한다.
부분집합의 크기가 더 이상 나누어 질 수 없을때까지 분할과 정복을 반복수행한다.
5. 평균 수행시간 복잡도는 O(nlog2n)이고, 최악의 수행시간 복잡도는 O(n의 제곱)이다.
힙 정렬
전이진 트리를 이용한 정렬 방식
1. 구성된 전이진 트리를 Heap Tree로 변환하여 정렬함.
2. 평균과 최악 모두 시간 복잡도는 O(nlog2n)이다.
값을 비교할 때 최하위 > 상위 / 오른쪽 > 왼쪽
2-Way 합병 정렬
2 Way Merge Sort는 이미 정렬되어 있는 두 개의 파일을 한 개의 파일로 합병하는 정렬 방식
그 방법은 다음과 같다.
1. 두 개의 키들을 한 쌍으로 하여 각 쌍에 대하여 순서를 정함.
2. 순서대로 정렬된 각 쌍의 키들을 합병하여 하나의 정렬된 서브리스트로 만든다.
3. 위 과정에서 정렬된 서브리스트들을 하나의 정렬된 파일이 될 때까지 반복함.
4. 평균과 최악 모두 시간 복잡도는 O(nlog2n)이다.
정렬
기수 정렬(Radix Sort) = Bucket Sort
1. 기수 정렬은 Queue를 이용하여 자릿수별로 정렬하는 방식
2. 레코드의 키 값을 분석하여 같은 수 또는 같은 문자끼리 그 순서에 맞는 버킷에 분배하였다가 버킷의 순서대로 레크드를 꺼내어 정렬함
3. 평균과 최악 모두 시간 복잡도는 O(dn)이다.