Assignment 1 - Compute tree height / Extending stack interface

Assignment 1 - Compute tree height / Extending stack interface

과제 중 1번을 해결하고 다음 문제를 보니 당황스럽게도 이미 솔루션인 상태였다. 그래서 2번, 4번 문제의 의미만 파악하고 넘어가고자 한다.

먼저 2번 문제 : Compute tree height

강의 내용 중 tree의 height에 대한 정의와 계산하는 방법에 대해 배웠던 시간이 있었다. 이를 코드로 구현하는 것이며 2분 탐색 트리(BST : Binary Search Trees) 모델에 대해 height을 계산해야 한다.

예시를 보면서 이해하는 것이 빠르므로 첫번째 샘플을 보면

5
4 -1 4 1 1

와 같이 표기가 되어있다. 이는 노드는 총 5개이며 각 노드별로 누구의 child인지 기록한 것이다. -1은 root, 이외의 정수값은 그대로 특정 노드의 child가 되는 것이다.

0번째 노드는 4번 노드의 child, 1번째 노드는 root, 2번째 노드는 4번 노드의 child, 3번째 노드는 1번 노드의 child, 마지막 4번 노드는 1번 노드의 child가 되어 위의 트리구조를 가지게 된다.

바로 코드로 넘어가면,

# python3
import sys
import threading


def compute_height(n, parents):
    # Replace this code with a faster implementation    max_height = 0    for vertex in range(n):
        height = 0        current = vertex
        while current != -1:
            height += 1            current = parents[current]
        max_height = max(max_height, height)
    return max_height


def main():
    n = int(input())
    parents = list(map(int, input().split()))
    print(compute_height(n, parents))


# In Python, the default limit on recursion depth is rather low,# so raise it here for this problem. Note that to take advantage# of bigger stack, we have to launch the computation in a new thread.sys.setrecursionlimit(10**7)  # max depth of recursionthreading.stack_size(2**27)   # new thread will get stack of such sizethreading.Thread(target=main).start()

compute_height 함수는 몇개의 노드(n)인지 누가 부모(parents)인지를 인자로 받고 max_height을 0으로 초기화 한다. for문을 통해 vertex 변수를 n-1번째까지 증가시키며 다시 height과 current 변수를 생성한다.

while문 내에서 현재 노드가 루트가 아니라면 height은 1만큼 증가하며 현재 노드의 부모가 current에 저장된다. 그렇게 루트가 나타날때까지 height을 증가시키면서 반복하며 루트를 찾게되면 while문을 종료한다. 이후 max_height과 height을 비교하여 더 큰 값을 max_height에 다시금 넣어준다. 이를 반복하게 되면 max_height을 구해 반환이 가능하다.


다음은 4번 문제 : Extending stack interface

강의 내용처럼 stack에 대한 기능을 구현하는 일이다. push, pop, max를 통해 값을 추가, 삭제 및 최대값 반환을 하며 샘플 1을 보게 되면

5
push 2
push 1
max
pop
max

와 같이 입력이 되어 있다. 초기에 명령 5개가 들어갈 것임을 알려주고 이후 push 2로 스택에는 [2]가 저장, push 1로 [2 1]이 저장, max로 2를 반환, pop으로 1 제거, max로 2반환하여 출력으로는

2
2

와 같이 나타난다.

다른 샘플을 보아도 같은 알고리즘으로 동작하는 것을 알 수 있다.

바로 코드로 넘어가면

#python3import sys

class StackWithMax():
    def __init__(self):
        self.__stack = []

    def Push(self, a):
        self.__stack.append(a)

    def Pop(self):
        assert(len(self.__stack))
        self.__stack.pop()

    def Max(self):
        assert(len(self.__stack))
        return max(self.__stack)


if __name__ == '__main__':
    stack = StackWithMax()

    num_queries = int(sys.stdin.readline())
    for _ in range(num_queries):
        query = sys.stdin.readline().split()

        if query[0] == "push":
            stack.Push(int(query[1]))
        elif query[0] == "pop":
            stack.Pop()
        elif query[0] == "max":
            print(stack.Max())
        else:
            assert(0)

StackWithMax 클래스를 정의하는데 안에는 stack 내용, push, pop, max함수들로 구성이 되어 있다. 바로 실행 내용으로 넘어가면 stack에 StackWithMax클래스를 인스턴스로 받고 이후 num_queries에 인풋값들을 한줄씩 받아온다.

for문으로 넘어가 query에 입력내용들을 분해해 각 내용이 아래 push, pop, max 중 해당사항이 있다면 각 stack 인스턴스의 함수로 역할을 수행한다.