1. 스케줄링 문제에 접근하는 이진 탐색 트리 소개
● 탐색 (Search)
가장 중요한 컴퓨터 응용의 하나
● 이진 탐색 트리 (BST, Binary Search Tree)
- 이진트리 기반의 효율적인 탐색 작업을 위한 자료구조
- key(왼쪽서브트리) <= key(루트노드) <= key(오른쪽서브트리)
- 이때 왼쪽과 오른쪽 서브트리도 모두 이진 탐색 트리임
- 이진탐색를 중위순회하면 오름차순으로 정렬된 값을 얻을 수 있음
● 이진 탐색 트리의 연산
- 탐색연산
→ search(key): 키 값이 key인 노드를 찾아 반환
1) 비교한 결과가 같으면 탐색이 성공적으로 끝남 - 루트부터 탐색해 나감
2) 키 값이 루트보다 작으면 왼쪽 자식을 기준으로 다시 탐색
3) 키 값이 루트보다 크면 오른쪽 자식을 기준으로 다시 탐색
→ 탐색연산의 구현
(순환적인 구현 / 반복적인 구현), (일반 함수 구현 / 트리의 멤버함수 구현 /
노드의 멤버함수 구현)
EX1) 순환적인 일반함수 구현
: 현재 비교하려는 트리의 노드와 구하려는 key값을 함수에 인자로 입력받음
만약 노드가 비었다면 NULL을 반환
노드 안의 데이터값과 key값이 같으면 그 값을 반환
노드 안의 데이터값보다 key값이 작으면 왼쪽 자식노드와 key값을 넣어 함수 재실행
노드 안의 데이터값보다 key값이 크면 오른쪽 자식노드와 key값을 넣어 함수 재실행
EX2) 반복적인 일반함수 구현
: 1번 방법과 유사하나 함수 안에 while 반복문을 추가해
노드가 NULL값이 나올 때까지 반복함
이 방식은 다시 함수를 실행하진 않음, 반복문을 통해 이 부분을 해결함
EX3) 노드의 멤버함수로 구현 (순환적)
: key값을 함수에 인자로 입력받음
현재 노드의 데이터와 key값이 같으면 이 노드의 데이터를 반환
노드의 데이터보다 key값이 작고 왼쪽자식노드가 비어있지 않다면
왼쪽자식노드의 탐색함수를 실행
노드의 데이터보다 key값이 크고 오른쪽자식노드가 비어있지 않다면
오른쪽자식노드의 탐색함수를 실행
찾는 데이터를 가진 노드가 없다면 NULL을 반환
...
- 삽입연산
→ insert(n): 이진 탐색 트리의 특성을 유지하면서 새로운 노드 n을 이진 탐색 트리에 삽입
1) 이진 탐색 트리에 원소를 삽입하기 위해서는 먼저 탐색을 수행 하는 것이 필요
(루트부터 NULL이 나올 때까지 아래로 탐색해 나감)
2) 탐색에 실패한 위치가 바로 새로운 노드를 삽입하는 위치임
→ 삽입연산의 구현
EX1) 순환적으로 구현한 삽입연산(일반함수 또는 트리의 멤버함수)
: 트리안의 노드 r과 새로 넣으려는 노드 n을 함수인자로 입력받음
만약 r과 n의 데이터 값이 같다면 함수를 종료
만약 r보다 n의 데이터 값이 작다면
왼쪽노드가 비었으면 n을 추가하고 노드가 있다면 그 노드와 n을 다시 함수에 입력
만약 r보다 n의 데이터 값이 크다면
오른쪽노드가 비었으면 n을 추가하고 노드가 있다면 그 노드와 n을 다시 함수에 입력
...
- 삭제연산
→ remove(n): 이진 탐색 트리의 특성을 유지하면서 노드 n을 트리에서 삭제
→ 노드 삭제의 3가지 경우
1) 삭제하려는 노드가 단말 노드일 경우
: 단말노드 삭제 - 단말노드의 부모노드를 찾아서 연결을 끊음
2) 삭제하려는 노드가 하나의 왼쪽이나 오른쪽 서브 트리중 하나만 가지고 있는 경우
: 자식이 하나인 노드 삭제 - 노드는 삭제하고 서브 트리는 부모 노드에 붙여줌
3) 삭제하려는 노드가 두개의 서브 트리 모두 가지고 있는 경우
: 두 개의 자식을 가진 노드 삭제
- 가장 비슷한 값을 가진 노드를 삭제 노드 위치로 가져옴
(후계노드를 선택)
→ 삭제연산의 구현
EX1) 트리의 멤버함수로 구현 (노드의 멤버함수로는 구현이 불가능, 함수 중복 사용)
: 가장 위의 부모노드와 삭제하려는 노드를 함수인자로 입력받음
if-else문을 이용해 노드를 삭제하려는 3가지 경우로 나눔
(3가지 경우로 나눠 노드를 삭제하고 자식노드와 부모노드를 연결하는 코드를 사용)
● 한 쪽으로만 길게 이어진 이진 트리는 이진 탐색 트리가 맞을까?
- Binary Search Tree 가 맞음,
하지만 그 상태로 두면 list(탐색연산 시 복잡도 O(n))와 다를 바가 없으므로
루트를 잘 설정해 트리의 높이를 가능한 줄여야 우리가 원하는 성능의 알고리즘이 나옴.
2. Big - O 소개
● Big - O 표기법
- 알고리즘 복잡도(Algorithm's usage)를 계산하기 위한 것
- 시간복잡도(Time Complexity) 식에서 가장 큰 차수만 적는 방법이 빅오 표기법
- 흐르는 시간과는 무관하며 오로지 input size |x|와 관련있음
- Boundary upper Bound(loose bound): 최악의 경우 이 정도까지 걸린다는 최악의 복잡도
- O(1): 제일 좋은 알고리즘을 나타내는 복잡도, 어떤 수를 넣어도 복잡도가 일정한 알고리즘임
- O(log(2)N): 매우 좋은 알고리즘
- O(N): 선형 모양
- O(1) < O(log(2)N) < O(N) < O(NlogN) < O(N**2) < O(2**N)
- 팩토리얼 함수
: if (n <= 0) return 1 , else return n * f(n-1)
else 가 여러번 반복되므로 알고리즘의 시간 복잡도를 빅오 표기법으로 표현하면 O(N)
- 피보나치 수열
: f (n) = f (n-2) + f (n-1)
층이 하나씩 쌓일 때마다 가지가 두개씩 늘어남
그래서 알고리즘의 시간 복잡도는 O(2**N)(-> 최악의 알고리즘)일 것 같지만
사실 이 정도까지는 아님
Dynamic Programming을 이용해 알고리즘 복잡도를 낮춰야 함
- 완전 이진 트리
: Insert => 최악의 경우 트리의 높이만큼 계산이 발생
최악이더라도 O(log2N)의 복잡도이므로 힙은 좋은 알고리즘
● 이진 탐색 트리의 성능
- 이진 탐색 트리에서의 탐색, 삽입, 삭제 연산의 시간복잡도는 트리의 높이를 h라고 했을 때
" h에 비례 "
→ 최선의 경우 → 최악의 경우
이진 트리가 균형적으로 생 성되어 있는 경우: h=log2n 경사이진트리: h=n
시간복잡도: O(logn) 시간복잡도: O(n)
3. 문제 풀이
3-1.
◎ LeetCode 98.
- 문제: 입력되는 이진트리가 이진탐색트리가 맞는지 아닌지를 출력하기
- 풀이:
< 순환적인 일반함수를 통해 트리 구현 >
루트노드보다 앞에 있는 노드들을 저장해 값들의 크기 비교에 기준이 되도록 하기 위한
'previous'라는 노드 변수를 선언한다.
왼쪽 자식노드부터 탐색하는 도중 루트노드보다 큰 값이 있으면 false 반환
왼쪽 자식노드가 모두 true라면 오른쪽 자식노드를 탐색하는 함수 실행
◎ LeetCode 99.
- 문제: 입력되는 이진 탐색 트리의 잘못된 부분을 고쳐 제대로 된 이진 탐색 트리 출력하기
- 풀이:
1) InorderTraversal 함수 구현 (탐색하는 코드)
중위 순회를 통해 노드의 값을 쭉 나열하는 코드
(이후 역전된 값들만 swap하도록 함)
2) 잘못된 노드가 있을 시 노드의 위치를 서로 바꿔주는 change 함수 구현
노드에 연결된 왼쪽 자식노드, 오른쪽 자식노드를 바꿈
3) 코드 실행 함수 구현
먼저 1)의 DFS 탐색 코드를 실행해 노드의 값을 벡터에 쭉 저장
이후 for반복문을 통해 벡터에서 값을 하나씩 꺼내어 역전된 부분이 있는지 확인
역전된 부분이 있다면 노드의 위치를 바꾸도록 2)의 changeValTree 함수를 실행
◎ LeetCode 700.
- 문제: 이진탐색트리에서 주어진 val 값을 루트노드로 하는 subtree 값들을 차례로 출력하기
- 풀이:
< 순환적인 일반함수를 통해 문제 해결 >
만약 루트노드가 비었다면, NULL을 반환
만약 val값이 루트노드와 같다면, root만을 반환(출력)
만약 val값이 루트노드보다 크다면,
루트노드의 오른쪽 자식노드와 val값을 다시 함수에 넣어 실행
만약 val값이 루트노드보다 작다면,
루트노드의 왼쪽 자식노드와 val값을 다시 함수에 넣어 실행
(만족하는 값을 찾을 때까지 크기에 따라 왼쪽 자식노드, 오른쪽 자식노드를
함수에 넣어 실행, 맞는 값이 있으면 출력하고 없다면
그 자식노드를 불러 실행하는 것을 반복함,
단말노드까지 가서 null값이 모두 나올 때까지 반복하여 실행하게 됨)
◎ LeetCode 701.
- 문제: 주어진 이진탐색트리에 주어진 val 값을 맞게 삽입해 전체 이진탐색트리 값을 출력하기
- 풀이:
< 재귀호출을 통해 문제 해결 >
이진트리의 루트노드 값과 val값을 비교한다.
만약 root가 비었다면 새로운 (이진탐색트리)노드를 만들어 val값을 넣고 반환
만약 root값이 val 값보다 크다면
root의 왼쪽 자식노드와 val을 함수인자로 넣고 다시 함수 실행
만약 root값이 val 값보다 작다면
root의 오른쪽 자식노드와 val을 함수인자로 넣고 다시 함수 실행
(계속 아래로 아래로 내려가며 최적의 자리를 찾아나감,
빈 자리를 찾으면 거기에 노드생성해 삽입됨)
return root; 를 통해 새로 만들어진 이진탐색트리의 값들을 하나씩 출력
3-2.
◎ 백준 5639
- 문제: 이진탐색트리의 전위 순회한 결과가 주어지면 후위 순회한 결과를 출력하기
- 풀이:
< 재귀호출을 통해 문제 해결 >
~ postOrder 함수:
전위 순회는 (루트, 왼, 오) 순서이고 후위 순회는 (왼, 오, 루트) 순서.
재귀함수를 통해 후위 연산을 해 결과값을 출력
~ main 함수:
트리의 노드개수를 입력받고, 그 개수만큼 숫자를 입력받아 vector에 저장
postOrder()함수를 실행해 후위 순회한 결과를 출력하도록 함
◎ 백준 1539
- 문제: 주어진 배열의 값들로 이진탐색트리를 만들었을 때 모든 노드의 높이 합을 출력하기
- 풀이:
(map을 사용했음)
for문을 통해 값을 하나씩 입력받을 때마다 해당 value의 노드 높이를 구해 합계에 더함
lower_bound를 이용해 노드의 높이를 계산
총 계산한 합계를 출력
(+ 이미지 출처: DATA STRUCTURES USING C++_PPT_Chapter 9_이진 탐색 트리)
'자료구조실습 수업' 카테고리의 다른 글
| [9주차 과제] (0) | 2022.11.06 |
|---|---|
| [MID] 중간 프로젝트 (0) | 2022.10.16 |
| [4주차 과제] (0) | 2022.10.02 |
| [2주차 과제] (0) | 2022.09.18 |
| [1주차 과제] 리포트 요약 과제 (0) | 2022.09.12 |