과제

아래 내용을 포함하는 포트폴리오를 작성하고, 웹페이지 주소를 제출합니다.
1. 스케줄링 문제에 접근하는 이진 탐색 트리 소개(필수) (-> 응답시간 대기시간 등등 말하는 것 같음. "좋은 스케줄링은 프로세서의 효율성을 높이고, 프로세스의 응답시간을 최소화하여 시스템의 작업 처리 능력을 향상시킨다.")
2. Big-O 소개(선택)
3. 문제 풀이
3.1. LeetCode 98, 99, 700, 701(필수)
3.2. 백준 5639, 1539(선택)

LeetCode (ex. https://leetcode.com/problems/validate-binary-search-tree/) 문제는 기본적인 BST 구성으로 천천히 코드를 만들어 보세요.
접속해 보면 BST 구성을 위한 간단한 안내도 함께 있으니, 참조 코드들을 활용하지 않고 수강생 본인이 직접 알고리즘을 만들어 보면 많은 도움이 됩니다.
(선택) 항목인 3.2. 문제는 원하는 학생만 풀어서 작성하면 됩니다.
여러 페이지로 나누어 작성할 시, 다른 접속자들(친구들)이 보기 편하게 다른 페이지를 링크 시켜서 작성하세요.

차례

Big-O와 여러 가지 예시
이진 탐색 트리(BST), BST의 효율적인 탐색 방법
문제 풀기 → 준비 중

Big-O

알고리즘의 성능 분석

알고리즘의 성능 분석 방법에는 두 가지가 있다. 알고리즘의 실행 시간을 계산하는 시간 복잡도와 알고리즘이 사용하는 메모리를 분석하는 공간 복잡도이다. Big-O는 둘 중 시간 복잡도를 계산하며, 입력의 크기에 따라 알고리즘이 수행되는 최악의 경우를 상정한다.
이때 최악의 경우를 상정한다고 해도 식은 가능한 타이트하게 잡는다. 예를 들자면 “어디 살아요?”라는 질문에 “지구에 살아요.”라고 대답하면 그것은 너무 광범위한 대답이지만 “ㅁㅁ시에 살아요.”라고 대답하는 것이 적절한 것처럼 시간 복잡도도 너무 넉넉하게 계산하지 않는다.

Big-O의 종류

전제 : 입력의 크기는 n이고, 시간 복잡도에서 사용되는 log의 밑은 2이다.

O(1)

어떤 입력이 들어와도 무조건 같은 횟수의 연산을 한다. 수행 시간 면에서만 본다면 최상의 알고리즘.

O(logn)

입력의 크기 n이 작을 때는 수행 시간의 상승폭이 크지만, n이 커질수록 수행 시간의 상승폭은 줄어든다. 컴퓨터 사이언스에서 log는 기본적으로 밑을 2로 갖는다고 한다(출처 : 교수님 설명).

O(n)

선형 증가. 입력의 모든 요소를 한번씩 확인해야 하는 경우가 이에 해당한다. 예를 들면 정렬되지 않은 배열에서 최댓값 찾기, 배열의 모든 요소의 합 구하기 등이 있다.
시간 복잡도가 이정도만 나와도 준수한 알고리즘이다(출처 : 교수님 설명, 이하 ‘교수님’으로 표기).

O(nlogn)

n ⅹ logn이다. 여기까지도 괜찮은 알고리즘이다(교수님).

O(n²)

갈수록 상승폭이 커지기 때문에 안 좋은 알고리즘(교수님).

O(2ⁿ)

처음부터 발산하기 때문에 쓰면 안 된다(교수님).

시간 복잡도 연산

O() 안에 쓰인 식의 계수와 상수항은 전혀 의미가 없고, 무조건 최고차항의 비교만 의미있다. 무한대로 늘어나는 입력에 따른 시간 복잡도 계산 결과에서 가장 큰 영향을 미치는 것은 최고차항이기 때문.

예제

O(1) + O(1) == O(1) ⇒ 참
O(3n²) == O(1/2n²) ⇒ 참

여러 가지 예시

힙 삽입 연산의 Big-O

레벨(h) 3, 노드(n) 6개 있는 힙에 새 요소 추가하기
최선의 경우 : 어떠한 교환 연산도 일어나지 않음 → O(1)
최악의 경우 : 새 노드가 루트까지 교환됨 → O(h)
노드의 개수 n은 (2^h - 1)로 나타낼 수 있다. 고로 O(logn)이다. 자세한 이항 과정은 생략한다. 이 정도는 할 수 있잖아요.

피보나치 수열의 big-o

재귀로 구현한다면 O(2ⁿ)이지만 이건 loose bound이고, 잘만 하면 이것보다는 낫다는 것을 증명한 사람이 있다. 그건 알아서 찾아보라. (교수님)

예제 - 오븐

오븐 1개 예약받기
예약 → 오븐에 넣는 시간 t 결정
k 시간 예약 없으면 t ∊ R
다 구우면 Extraction

계산의 편의를 위해 k = 2라고 가정하자. 현재 예약된 시간은 2, 6, 8, 12, 17, 19, 23
현재 예약된 시간의 집합은 R, Big-O는 O(logn)으로 하고 싶다. 어떻게 할 수 있을까?

방법
1. unsorted array : O(n)
2. sorted array : O(n)
  1. search : O(logn)
  2. compare : O(1)
  3. insert : 삽입하려면 전부 자리를 하나씩 움직여야 하므로 O(n) → 이게 문제
3. (linked) list
  1. search : O(n) → 삽입 연산은 간단하지만 이게 문제
4. heap
  힙은 weekly invariant하기 때문에 삽입해도 되는지 검증하려면 모든 노드를 방문해야 한다. 고로 O(n)
제안
정렬된 배열의 탐색과 비교 연산, 힙의 삽입 연산을 합치면 O(logn)이 될 수 있다. → 서브트리의 좌우 크기까지 정렬하는 이진 탐색 트리를 쓴다.
탐색의 방향이 정해져 있고(탐색 O(h) == O(logn)), 삽입도 간단하니 모든 과정을 합해 O(logn) 가능?
문제
이진 탐색 트리의 루트 노드는 어떻게 정하나? 잘못 정하면 리스트와 다를 게 없어진다. 높이를 최소화해야 한다.
해결
양쪽 서브트리의 높이 차이를 1 이하로 유지한다.
이진 탐색 트리의 문제
서치는 간단하다. 그런데 만약 특정 값보다 작거나 큰 값의 개수를 세고 싶다면?
이진 탐색 트리 문제 해결
각 노드에 자기 자신을 포함한 자손 노드의 개수를 같이 저장한다.
원하는 값을 찾을 때까지 내려가면서
(1) 자기 자신보다 작거나 같으면 or 크거나 같으면 +1,
(2) 해당 노드의 왼쪽 or 오른쪽 자손 노드의 개수도 더한다.
원하는 노드를 찾으면 해당 노드의 개수를 세고 끝낸다.

이진 탐색 트리

예습 구경하기 : [자료구조] 이진 탐색 트리

이진 탐색 트리의 기본

지난 글에서 힙에 대해 공부했다. 이진 탐색 트리는 힙과 달리 서브 트리의 좌우 정렬까지 고려하는 트리이다. 왼쪽의 값이 루트보다 크고, 오른쪽의 값이 루트보다 작다. 간단히 구글에 검색해봤는데, STL 라이브러리는 없고, 직접 구현해야 한다.

이진 탐색 트리 설계 및 구현

코드 출처 : 교수님
개인적 편집 있음

노드

필요한 데이터를 담을 수 있어야 하고, 자신의 왼쪽과 오른쪽 서브트리를 가리켜야 한다. 일단 데이터는 간단하게 int로 하자.
연산은 생성자, 데이터 설정, 좌우 서브트리 설정, 리프노드 여부 등.

트리

자료형은 노드가 다 알아서 한다. 트리 클래스는 루트 관리, 삽입, 삭제, 탐색 등을 한다.

전체 구현 코드 보기

* 웬만한 설명은 다 주석과 출력문에 있다. 코드를 읽기만 해서는 아무리 봐도 이해가 잘 안 돼서 출력문을 잔뜩 추가하고 트리 그림까지 그려봤다. 적어도 어떻게 일이 돌아가는지는 알게 되었다. 출력문 자세히 썼으니 궁금하면 복사해서 직접 디버깅해보자.

코드가 길어 링크로 첨부한다.
깃허브에서 보기
코드 실행 결과 보기

이진 탐색 트리의 효율적인 탐색

이진 탐색 트리는 그것이 필요한 상황이라는 전제 하에, 특정 값에 대한 연산에는 효율적이다. 하지만 특정 범위에 대한 연산은 어떨까? 예를 들어 위의 예제 코드로 만들어진 트리에서 10보다 큰 값을 개수를 세고 싶다면 어떻게 해야 할까? 교수님은 맛있는 휘낭시에를 걸고 이 문제를 퀴즈로 내셨지만 아무도 시간 내에 맞히지 못했다.
교수님이 직접 공개한 정답은 각 노드에 자기 자신을 포함한 자식 노드의 수를 따로 기록하는 것이었다. 교수님의 코드를 개조해서 직접 구현해보고자 했지만 삭제 연산을 제대로 구현하지 못해 실패했다. 우선은 예시 코드에 재귀로 사용된 각종 탐색 메소드부터 반복으로 바꾸고 나서 생각해봐야 할 것 같다. 미래의 제게 맡기겠습니다.

글을 순서대로 정독했다면 알겠지만 위에서도 잠깐 언급이 된 내용이었다. 다시 한 번 보자.

각 노드에 자기 자신을 포함한 자손 노드의 개수를 같이 저장한다.
원하는 값을 찾을 때까지 내려가면서
(1) 자기 자신보다 작거나 같으면 or 크거나 같으면 +1,
(2) 해당 노드의 왼쪽 or 오른쪽 자손 노드의 개수도 더한다.
원하는 노드를 찾으면 해당 노드의 개수를 세고 끝낸다.

해야 할 일은 다음과 같다

노드 클래스에 카운트 변수 추가하고, 적절한 메소드 구현하기(카운트 반환, 카운트 증감)
트리 클래스의 삽입, 삭제 연산에서 카운트도 같이 조작할 수 있도록 메소드 수정하기
특정 값보다 크거나 작은 요소의 개수 세는 메소드 구현하기 → 만드는 사람 마음이니까 ‘크거나 같은’, ‘작거나 같은’ 요소의 수를 세어도 된다. 나는 등호를 포함하지 않았다.

삽입 메소드 수정은 노드가 지나는 길 따라 카운트만 건드리고 가면 되니까 금방 했고 가장 어려웠던 건 삭제 메소드 수정이었다. 삭제해야 할 노드가 양쪽 서브트리를 모두 갖는 경우, 대신 삭제될 후계 노드를 선정해야 한다. 이 부분을 포함해 삭제 메소드 전체가 재귀로 구현되었고, 나는 이것을 반복 형태로 수정하지 못했다. 그렇기 때문에 삭제 메소드 내에서는 노드의 카운트를 올바르게 수정할 수가 없었다.
재귀로 구현된 삭제 메소드를 반복으로 바꾸겠다고 한참을 내 마음대로 움직여주지 않는 포인터와 기싸움을 하다가 이건 내 수준에는 이해할 수 없는 문제라고 생각해(구글에 뭐라고 검색해야 하는지도 모름) 방법을 바꿨다. private로 정의된 삭제 메소드는 그대로 두고, public로 정의된 삭제 메소드를 건드렸다. 약간의 과정이 중복하여 수행되는 점을 감수하고 private 삭제 메소드를 호출하기 전에 몇 가지 과정을 추가했다. 추가라고 말은 했지만, 순서를 바꾼 것이기도 하다. 자세한 것은 아래 코드로 확인하자.

코드가 너무 길어서 링크로 첨부한다.
깃허브에서 보기
코드 실행 결과 보기

문제 풀기

1. LeetCode 98, 99, 700, 701(필수)
2. 백준 5639, 1539(선택)

링크 준비중

참고 자료

『C++로 쉽게 풀어쓴 자료구조』, 천인국ㆍ최영규 지음, 생능 출판사
『코딩 테스트를 위한 자료 구조와 알고리즘 with C++』, 존 캐리ㆍ셰리안 도시ㆍ파야스 라잔 지음, 황선규 옮김, 길벗 출판사
[자료구조] 이진탐색트리 (Binary Search Tree)

[자료구조] Big-O와 이진 탐색 트리

과제

차례