트리

트리 분야: 인공지능, 데이터베이스, 자동 완성 시스템 등 다양한 분야에서 사용

트리는 에지로 연결된 노드로 구성된 계층 구조

• 노드: 각 노드에는 데이터가 들어 있다.
• 루트: 최상위 노드로, 부모가 없는 노드
• 자식/부모: 계층적 방식으로 연결된 노드
• Leaf: 자식이 없는 노드.
• 에지: 부모 노드와 자식 노드 사이의 연결 고리

 

• 코테에서는 이진 트리만 알면 된다.
• 이진트리란 모든 노드의 최대 차수가 2를 넘지  않는 트리
• 이진 트리는 배열이나 포인터로 구현한다.

 

이진 트리 

 

배열로 표현

• 루트 노드가 인덱스 1에 있을 경우
• 왼쪽 자식 = 부모인덱스 * 2
• 오른쪽 자식 = 부모인덱스 * 2 + 1
• 루트 노드가 인덱스 0에 있을 경우
• 왼쪽 자식 = 부모인덱스 * 2 + 1
• 오른쪽 자식 = 부모인덱스 * 2 + 2

단점: 이 표현은 배열에 빈 공간을 확보해야 하므로 노드가 희박한 경우 공간을 낭비할 수 있다.

시간 복잡도: 이진 트리 노드가 N개 일때, 배열로 이진 트리 생성하면 O(N)이 걸린다.

 

이진 트리 순회

• 전위 순회: 현재 노드를 부모 노드로 생각했을 때 부모 노드 -> 왼쪽 자식 노드 -> 오른쪽 자식 노드 순서로 방문
• 중위 순회: 현재 노드를 부모 노드로 생각했을 때 왼쪽 자식 노드 -> 부모 노드 -> 오른쪽 자식 노드 순서로 방문
• 후위 순회: 현재 노드를 부모 노드로 생각했을 때 왼쪽 자식 노드 -> 오른쪽 자식 노드 -> 부모 노드 순서로 방문

가장 중요한건 현재 노드를 부모 노드로 생각하는 것

 

포인터로 표현

• 포인터를 사용한 트리 구조는 배열로 구현한 것보다 메모리 사용량이 적다. 배열은 트리의 모든 자리를 미리 차지하게 되지만, 포인터를 사용하면 필요한 노드만 메모리에 할당되기 때문
• 포인터를 사용하여 부모와 자식 노드를 연결하고, 데이터를 삽입하고 탐색할 때마다 해당 노드의 자식을 따라가는 방식으로 접근

 

이진 탐색 트리 구축 방법

• 이진 탐색 트리는 각 노드가 왼쪽 자식은 부모보다 작은 값을 가지고, 오른쪽 자식은 부모보다 크거나 같은 값을 가지는 구조
• 데이터가 삽입되면서 동시에 정렬이 이루어진다.

 

이진 탐색 트리 탐색 방법

1. 현재 노드의 값이 찾는 값과 같으면 탐색 종료: 그 값을 찾은 것이므로 해당 노드에서 탐색을 끝낸다.
2. 현재 노드의 값이 찾는 값보다 작다면: 오른쪽 자식 노드를 탐색
3. 현재 노드의 값이 찾는 값보다 크다면: 왼쪽 자식 노드를 탐색
4. 노드가 없을 때까지 탐색을 계속하다가 값이 없으면: 트리에 그 값이 존재하지 않는다는 것을 의미한다.

 

이진 탐색 트리의 시간 복잡도

• 균형이 맞는 경우: 트리의 깊이가 로그 형태로 감소하므로 O(log N)의 시간 복잡도
  • 트리가 균형 잡혀 있다는 것은 좌우의 자식 노드가 비슷한 수의 하위 노드를 가지고 있다는 것
• 균형이 맞지 않는 경우: 트리의 한쪽으로만 데이터가 계속 쌓이는 경우에는, 최악의 경우 트리는 하나의 선형 구조처럼 변할 수 있다.
  • 이때는 탐색의 시간 복잡도가 O(N) -> 배열 탐색과 비슷한 성능

 

균형 맞추기

• 이진 탐색 트리의 장점은 값이 계속 정렬된 상태로 유지되기 때문에 빠르게 값을 찾을 수 있다는 점
• 균형 이진탐색 트리 구현은 난이도가 높아서 코딩테스트에는 잘 나오지 않는다
• ex)AVL 트리, 레드-블랙 트리 같은 자료구조

 

문제

https://github.com/dremdeveloper/codingtest_python/blob/main/solution/26.py

 

예상 대진표

https://school.programmers.co.kr/learn/courses/30/lessons/12985

'''
n명의 사람이 경쟁해서, a와 b가 언제 맞붙는지
a,b는 항상 이기고
a,b가 짝수면 a는 a-1과 붙고, b는 b-1과 붙고 a,b= a//2
a,b가 홀수면 a는 a+1과 붙고, b는 b+1과 붙고 a,b= a//2+1
a,b가 1,2가 될때까지 반복하고 그 반복한 횟수를 return하면 됨
a -> 4 -> 2 ->1 
b -> 7 -> 4 -> 2
'''
def odd_even(n):
    if n%2==0:
        return n//2
    else:
        return (n//2)+1


def solution(n,a,b):
    cnt = 1
    while not(b==a+1 and a%2==1):
        a = odd_even(a)
        b = odd_even(b)
        cnt+=1
    return cnt

print(solution(8,4,7))
print(solution(1048576,12345,12346))
#결과 3

시간초과가 난다 -> a,b의 대소비교에 시간을 쓰기 때문

def odd_even(n):
    if n%2==0:
        return n//2
    else:
        return (n//2)+1


def solution(n,a,b):
    cnt = 1
    while not(b==a+1 and a%2==1):
        if a > b:
            a, b = b, a
        a = odd_even(a)
        b = odd_even(b)
        cnt+=1
    return cnt

이런 경우는 처음이다. 테스트 케이스 34개중 한개에서 시간초과가 난다...

def odd_even(n):
    if n%2==0:
        return n//2
    else:
        return (n//2)+1


def solution(n,a,b):
    cnt = 0
    while a != b:
        if a > b:
            a, b = b, a
        a = odd_even(a)
        b = odd_even(b)
        cnt+=1
    return cnt

while문 조건을 바꿨다.

간단하게 생각하면 아래처럼 하면 된다. a,b 값이 1~8일때 손으로 써가면서 비교해보면 쉽게 이해할 수 있다.

def solution(n,a,b):
    cnt=0
    while a != b:
        a = (a+1)//2
        b = (b+1)//2
        cnt+=1

    return cnt

 

다단계 칫솔 판매

https://school.programmers.co.kr/learn/courses/30/lessons/77486

def solution(enroll, referral, seller, amount):
  # dic = {}
  # for i in range(len(enroll)):
  #     dic[enroll[i]] = referral[i]
  dic = dict(zip(enroll, referral))

  total = {}
  for i in range(len(enroll)):
      total[enroll[i]] = 0
  for i in range(len(amount)):
    cur = seller[i]
    money = amount[i] *100
    while money>0 and cur != '-':
      total[cur] += money - money//10
      money = money//10
      cur = dic[cur]
  arr=[]
  for k,v in total.items():
    arr.append(v)
  return arr
print(solution(["john", "mary", "edward", "sam", "emily", "jaimie", "tod", "young"],
               ["-", "-", "mary", "edward", "mary", "mary", "jaimie", "edward"],
               ["young", "john", "tod", "emily", "mary"], [12, 4, 2, 5, 10]))

 

• 최소 시간, 최소 경로 -> 너비우선탐색, 다익스트라
• 이때, 가중치가 없다면 -> 너비우선탐색