📕 자료구조와 알고리즘(심화)

✅ Red-Black 트리

• AVL 트리는 균형을 엄격히 지키기 때문에 삽입, 제거는 느리지만 검색이 빠름

• Red-Black 트리는 균형에 대해 관대하여 삽입, 제거는 빠르지만 검색이 느림

삽입 규칙

1. 모든 노드는 빨간색이나 검은색 두 가지 색 중 하나이다

2. 루트 노드는 항상 검은색이다

3. 모든 터미널 노드(NIL)는 검정색이다

4. 연속해서 빨간색 노드가 올 수 없다.

1. 현재 노드가 빨간색이라면 부모, 자식은 빨간색일 수 없음

5. 검은색은 연속으로 올 수 있다

6. 루트 노드에서 터미널 노드인 NIL노드까지 모든 경로에는 같은 수의 검은색 노드가 있어야 한다.

높이

1. 트리의 높이

2. Black Height: 루트부터 NIL 노드까지 Black 노드의 수

삽입을 할 때 회전도 하지만 노드의 색도 다시 칠해준다. (recoloring)

새로운 노드를 삷입할 때 무조건 빨간 색 노드를 칠한다.

이 후 균형을 잡아주는 함수를 호출(rebalanceAfterInsertion 함수)

1. 새로운 노드가 루트노드인 경우

1. 검정색으로 변경

2. 부모노드와 삼촌노드가 빨간색인 경우

1. 삼촌노드: 부모의 형제 노드

2. 할아버지를 빨간색으로, 부모/삼촌 노드를 검정색으로 변경

3. 규칙을 위반하지 않을 때까지 재귀적으로 상위로 올라감

3. 부모는 빨간색, 삼촌은 검정색, 새로운 노드는 안쪽 손자인 경우

1. 안쪽 손자: 할아버지, 부모, 자신이 삼각형을 이루는 노드 (RL)

2. 부모 노드를 회전, 할아버지 노드는 반대 회전

3. 새로 삽입된 노드는 검은색, 할아버지 노드는 빨간색으로 변경

4. 부모 빨간색, 삼촌 검정색, 새로운 노드가 바깥쪽 손자인 경우

1. 바깥쪽 손자: 할아버지, 부모, 자신이 일자를 이루는 노드(LL)

2. 할아버지노드는 삽입 방향 반대로 회전

3. 부모 노드는 검정, 할아버지 노드는 빨강으로 변경

제거 규칙

1. 터미널 노드를 제거

1. 제거할 노드의 두 자식 노드가 모두 NIL인 경우

1. 해당 노드 제거 후 부모 노드를 NIL에 연결

2. 제거할 노드의 자식 노드 중 하나가 NIL

1. 해당 노드 제거 후 부모 노드에 나머지 노드 연결

3. 제거할 노드의 자식노드에 NIL이 없음

1. 왼쪽 자식 노드의 큰 값 혹은 오른쪽 자식 노드의 작은 값으로 대체

2. 대체한 후 나머지 자식노드를 대체 노드의 자식으로 연결

3. 제거한 노드가 빨간색인 경우에는 색 규칙이 올바름

4. 검은색이라면 균형을 잡아야 함

균형을 잡는 방법

1. 형제 노드가 빨간색인 경우

1. 형제 노드의 색을 검정, 부모노드를 빨간색으로 변경

2. 부모노드 왼쪽 회전, 부모노드를 검정색으로, 형제 노드를 빨간색으로 변경

2. 형제노드와 형제노드의 자식노드들이 검은색이고 부모노드는 빨간색

1. 형제 노드 빨간색, 부모 노드 검은색

3. 형제노드와 형제노드의 자식노드, 부모 노드 모두 검정색

1. 형제노드의 색을 빨간색으로 변경

2. 부모노드에 대해 2번 규칙 적용

4. 형제노드가 검은색, 형제 두 자식 노드 중 하나라도 빨간색 노드가 있고 바깥쪽 조카 노드가 검은 색인 경우

1. 안쪽 조카는 검정, 형제 노드는 빨간색

2. 형제 노드를 제거한 노드의 반대방향으로 회전

3. 조카노드와 부모, 형제 노드 색 변경

4. 부모 노드 제거 노드 반대방향으로 회전

5. 형제 노드가 검은색이고 형제의 두 자식노드 중 하나라도 빨간색 노드가 있고 바깥쪽 조카가 빨간색인 경우

1. 형제 노드를 부모 노드 색으로 변경

2. 부모노드와 바깥쪽 조카 노드 색 변경

3. 부모 노드를 제거된 노드의 방향으로 변경

✅ 우선순위 큐와 힙

개념

• 큐: FIFO > 먼저 들어간 데이터가 먼저 나온다.

• 우선순위 큐: 먼저 들어간 순서와 상관없이 우선순위에 따라 나온다.

  • Enqueue: 삽입

  • Dequeue: 삭제

• 힙(heap): 완전 이진트리 - 최소 힙: 루트 노드가 가장 작은 값을 가지는 완전 이진 트리 - 최대 힙: 루트 노드가 가장 큰 값을 가지는 완전 이진 트리

힙

1. 삽입

1. 마지막 노드로부터 부모 노드와 비교해가며 적절한 위치에 삽입

2. 처음 삽입할 위치를 찾는 것은 어렵기 때문에 미리 마지막 삽입 노드 위치를 저장해둠

2. 제거

1. 마지막 삽입 노드를 루트 노드를 가져온 후, 자식 노드와 비교하면서 위치를 바꿈

2. 마지막 삽입 노드의 위치를 마지막 이전에 삽입된 노드로 변경

3. 성능: 삽입, 제거: O(log n)

• 새로 삽입될 위치 (`getInsertingParent`)

1. 루트 노드인 경우

1. 루트 노드의 왼쪽 자식으로 삽입

2. 부모노드의 왼쪽 자식인 경우

1. 오른쪽 형제, 부모 노드 오른쪽 자식으로 삽입

3. 부모노드의 오른쪽 자식인 경우

1. 부모노드의 오른쪽 형제 노드가 자식 노드를 가지는 경우

1. 해당 형제 노드의 왼쪽 자식 노드로 내려감

2. 오른쪽 형제 노드가 없는 경우

1. 루트 노드부터 가장 왼쪽 노드로 내려감

힙 정렬

• 최소 힙에서 dequeue를 하면 오름 차순 정렬

• 최대 힙에서 dequeue를 하면 내림 차순 정렬

• 성능: O(nlogn)

📕 컴퓨터 구조

✅ 하드웨어 만들기

멀티플렉서: 여러 입력 중 하나를 선택하여 출력으로 내보내는 장치

디멀티 플렉서: 하나의 입력을 여러 출력 중 하나로 내보내는 장치

• selection을 통해 선택

• 입력 수에 따라 비트 수가 달라짐

• Selection이 가리키는 수에 따라서만 출력이 변경됨

  • 0 -> 0번

  • 1 -> 1번

  • 10 -> 2번

• 선이 많이지기 때문에 터널을 통해 연결할 수 있다.

디코더: n 비트의 입력을 2^n개의 출력 중 하나만 활성화하는 장치

컨트롤 버퍼: 출력을 제어하는 장치 - 선을 끊어주는 역할을 한다.

전압은 물리적으로 방해를 받을 수도 있기 때문에 출력을 제어할 수 있게 된다.

✅ CPU 만들기

반가산기

1비트 두 개를 더할 때는 올림을 표현하는 carry와 합을 의미하는 sum 이 필요

• carry: AND 게이트

• sum: XOR

> 1비트의 두 값만 더할 수 있기 때문에, 다비트 연산에서는 LSB 자리에만 쓰고, 나머지 자리에서는 전가산기를 써야 한다

📌 전가산기

전압은 물리적으로 방해를 받을 수도 있기 때문에 출력을 제어할 수 있게 된다.

✅ 메모리

조합 논리회로: 입력에 대해서만 출력하기 때문에 상태를 기억할 수 없음

• 기본 게이트, 멀티플렉서, 디코더, 반가산기, 전가산기, ALU,,

• 순차 논리회로(메모리 역할)

  • 출력을 다시 조합 논리회로의 입력으로 들어가야지 현재 상태를 만들어서 다음 상태를 결정시킬 수 있음

1. SR Latch

2. D latch

3. JK latch

클럭과 플리플롭

여러 회로의 딜레이 차이로 인해 순차적으로 결과값이 출력되고 있다. -> 원하지 않는 출력을 받게된다.

• 레지스터: 1비트 메모리 Latch를 연결해 여러 비트를 저장할 수 있는 메모리

레지스터의 enable을 0으로 바꿔서 값이 다 처리될 때까지 기다렸다가 끝나면 enable을 1로 바꿔준다.

클럭이 정해진 주기에 따라 enable을 직접 변경시켜준다.

클럭이 1인 상태에서 출력 값이 계속 바뀔 수 있다는 문제가 있다.

-> 트리거: 래치의 출력을 활성화하는 조건

1. 레벨 트리거

1. High Level: 입력이 1인 동안에만 반영

2. Low Level: 입력이 0인 동안에만 반영

2. 엣지 트리거

1. Rising Edge: 0에서 1이 되었을 때 반영

2. Falling Edge: 1에서 0이 되었을 때 반영

-> 플리플롭: 래치 트리거를 엣지 트리거로 변경하는 것

레지스터

데이터를 출력하고 LOAD를 통해 레지스터에 저장해두었다가 Enable을 통해 출력을 통제한다.

8비트 레지스터 = 0~255까지 데이터 저장 가능

CPU내부에 있어서 적은 메모리만 저장

RAM

1비트 저장 - 래치 || 플립플롭

8비트 저장 - 레지스터

• MSB를 포함한 4비트 = 명령어

• LSB를 포함한 4비트 = 메모리 주소

• 메모리 주소는 0 ~ 15번까지 사용 가능

RAM은 16개의 메모리 주소를 갖으며 하나의 메모리 주소는 8비트(1바이트)의 레지스터로 구성 => 16바이트 메모리

-> 현대 컴퓨터는 최소 4GB의 램이다.

address에서 주소를 받아서 디코더를 통해 출력된 값을 해당 메모리 주소에 연결해주면 각각의 레지스터에 값을 저장해둘 수 있다.

레지스터의 출력을 멀티플레서에 연결하고 Enable을 통해 제어하면 값을 출력할 수 있다.

후기

Red-Black Tree나 우선순위 큐와 같은 이론이 한번에 이해가 되지 않았고 구현하는 과정이 익숙하지 않아서 이론과 함께 반복적으로 확인해보면서 구현을 거쳤던 것 같다. 반복적으로 개념을 익혀나가면서 구현하다보니 점점 어느정도 감이 잡히는 것 같다는 느낌이 들었고 미션을 통해 직접 과제를 구현하다보면 더 자료구조에 대해 가까워질 수 있을 것 같다.

컴퓨터 구조를 만들어볼 수 있는 logisim 프로그램이 맥북에서는 설치가 안되거나 파일을 바로 열 수가 없어서 애 좀 먹었던 것 같다. 단축키를 몰라서 하나씩 조합을 하다보니 시간이 좀 걸렸지만 점점 강의를 따라하면서 이 또한 손에 점점 익어갔다.

CPU에 들어가있는 레지스터라는 존재에 대해서만 알고 있었지만 레지스터가 어떻게 동작하는 지, 내부 회로가 어떤 식으로 연결되어있는 지 직접 구현해보면서 확인해보니 흥미로웠었고 RAM 또한 레지스터와 어떤 관계를 갖고 있는지 알 수 있어서 좋았던 것 같다.