[묘공단]파이썬 스터디 5주차

---

이 글은 골든래빗 코딩 테스트 합격자 되기 파이썬 편의 9장 써머리입니다.

• 트리

데이터를 탐색하기에 유용한 구조로 계층 구조를 표현하는 용도로 사용.

- 인공지능

- 자동 완성 기능

- 데이터베이스

 

• 구성요소

- 노드 

루트 노드 : 가장 위에 있는 노드

리프 노드 : 자식이 없는 노드

부모 노드 : 상대적으로 위에 있는 노드

자식 노드 : 아리에 있는 노드

- 에지(간선)

노드와 노드사이를 이어주는 선

차수(degree) : 아래로 향하는 간선의 개수

 

• 표현방법

- 배열로 구현

장점 : 구현 난이도가 쉬워 구현 시간이 단축된다.

단점 : 메모리 공간 낭비.

- 포인터로 구현

장점 : 메모리 공간을 낭비하지 않음.

단점 : 구현 난이도 어려움.

 

• 이진트리 순회

현재 노드를 부모 노드로 생각했을 때,

- 전위 순회 : 부모 노드 -> 왼쪽 자식 노드 -> 오른쪽 자식 노드

- 중위 순회 : 왼쪽 자식 노드 -> 부모 노드 -> 오른쪽 자식 노드

- 후위 순회 : 왼쪽 자식 노드 -> 오른쪽 자식 노드 -> 부모 노드

 

• 이진트리 구축

데이터 크기를 따져 크기가 작으면 왼쪽 자식 위치에, 크거나 같으면 오른쪽 자식 위치에 배치.

 

- 배열 탐색 vs 이진 탐색 트리 

이진 탐색 트리가 데이터 크기에 따라 하위 데이터 중 한 방향을 검색 대상에서 제외하므로, 이진 탐색 트리가 훨씬 빠름.

 

- 시간 복잡도

균형 유지 가정했을 때, O(logN).

균형 유지가 안되었을 때, O(N). 배열과 비슷

** 균형 이진 탐색 트리 : 시간 복잡도 O(logN)

이진 트리의 탐색 연산 횟수가 트리의 높이에 비례 하고 트리의 높이는 logN

1. 양과 늑대 ★

sheep = 0
wolf = 1

#트리 생성
def solution(info, edges):
    tree = {}

    for edge in edges:
        parent, child = edge

        if parent not in tree:
            tree[parent] = []

        if child not in tree:
            tree[child] = []

        tree[parent].append(child)
        tree[child].append(parent)  # 양방향 연결, 부모자식 왔다갔다 가능

    answer = travel(tree, info, 0, set())

    return answer

def travel(tree, info, visit, visited):
    global sheep, wolf # 전역 변수로 양과 늑대 표시, 누적 후 최종 반환

    visited.add(visit) # 현재 노드를 방문했음을 표시

    if info[visit] == 0:  # 양이면
        sheep += 1
    else:
        wolf += 1

    if wolf >= sheep: #늑대가 많으면 0
        return 0

    max_sheep = sheep

    for new_visit in tree[visit]: # 현재 노드의 자식들에 대해
        if new_visit not in visited: #방문 안한 노드면
            local_sheep = travel(tree, info, new_visit, visited)  # 재귀적으로 양을 모음
            max_sheep = max(max_sheep, local_sheep)

    return max_sheep