Krafton_jungle 5기 31 ~ 32일차 TIL - RB-Tree, 알고리즘

RB-Tree

RB-Tree란?	자가 균형 이진 탐색 트리의 일종으로, 이진탐색 트리를 가지고 있고, 노드의 삽입과 삭제를 할 때 전체 트리의 높이를 균형있게 제한하는 이진 탐색 트리이다.
RB-Tree의 특징	RB-Tree의 가장 큰 특징은 각각의 노드가 색깔에 관한 정보를 갖는다는 점과, 규칙을 만족하지 않으면 케이스 별로 노드를 회전시키며 균형을 맞춘다는 점이다. (노드를 승격시키는 B트리와의 차별점)
NIL 노드	NIL 노드란, 실제 데이터를 갖는 트리가 아닌, 리프노드 끝에 NULL 대신 NIL 노드를 선언해 해당 트리의 끝을 알린다. (NIL 노드를 사용하면 트리의 끝을 NULL 포인터로 처리하는 대신 트리의 모든 노드를 동일한 방식으로 처리할 수 있다. 이로 인해 코드의 일관성과 가독성이 향상)
레드블랙 트리 규칙	1. 각 노드는 red or black이다 2. 루트노드는 black이다 3. NIL 노드는 black이다. 4. 모든 red 노드는 연속될 수 없다. 5. 한 노드로부터 자기 자신의 모든 자손 NIL 노드까지 black 노드의 수는 같다. 이렇게 글로만 써놓으니 잘 와닿지 않을 수 있는데 각 규칙에 위배됐을때 트리의 균형을 맞추는 과정은 https://youtu.be/2MdsebfJOyM?si=a8JEWBatdW_yo4P1 해당 유튜브 채널에 아주 상세하게 잘 설명되어 있다.

 

 

알고리즘

 

그동안 많은 문제를 풀었지만 인상깊었던 문제를 하나만 서술하겠다.

 

1074(Z)

 

처음 문제에 접근한 방법은 다음과 같았다.

# 실패코드!
import sys
input = sys.stdin.readline


def recursive(start_y, start_x, length):

    global cur

    if length <= 1:
        cur += 1
        if start_y == c and start_x == r:
            print(cur - 1)
            sys.exit(0)
        return

    mid = length // 2

    recursive(start_y, start_x, mid)
    recursive(start_y, start_x+mid, mid)
    recursive(start_y+mid, start_x, mid)
    recursive(start_y+mid, start_x+mid, mid)


n, c, r = map(int,input().split())

cur = 0

recursive(0,0,2**n)

주어진 조건에 상관없이 모든 경우의 수를 따져보는 무식한 방법으로 접근했다.

테스트 케이스는 모두 통과했지만 결과는 메모리 부족으로 실패!

그래서 다른 방법을 생각해내다가 내린 결론이 총 4개의 사분면으로 영역을 나눈 뒤, 조건에 부합하는 경우의 수를 모두 따져보는 방법이였다.

그렇게 해서 나온 답이 아래의 코드와 같다.

import sys
sys.setrecursionlimit(10**3)
input = sys.stdin.readline


def recursive(row, col, length, value):

    length = length // 2

    if row < length and col < length:
        if length == 1:
            print(value)
            sys.exit(0)
        recursive(row, col, length, value)
    elif row >= length and col < length:
        if length == 1:
            print(value + 1)
            sys.exit(0)
        recursive(row - length, col, length, value + length ** 2)
    elif row < length and col >= length:
        if length == 1:
            print(value + 2)
            sys.exit(0)
        recursive(row, col - length, length, value + length ** 2 * 2)
    elif row >= length and col >= length:
        if length == 1:
            print(value + 3)
            sys.exit(0)
        recursive(row - length, col-length, length, value + length ** 2 * 3)


n, c, r = map(int,input().split())

recursive(r,c,2**n, 0)

 

 

솔직히 요즘 C언어로 빠르게 자료구조를 구현해버리고, 살짝 느슨해진 감이 없진 않은것같다.

하지만 이번 보이저 X의 채용 설명회를 듣고, 개발자로써 커리어를 시작하려는 나에겐 다신 찾아오지 않을 기회가 아닐까 하는 생각에 정신이 번쩍 들었던 것 같다.

그리고 또 하나, 기록하는데 너무 집중하지 말고 그 경험을 온전히 담을 수 있게 핵심만 골라서 정리해야 겠다.

다시한번 초심을 되찾고 열심히 달려보자!