[n522] Data Structure (2)

트리 (Tree)

• Node: 트리에서 데이터를 저장하는 기본 요소.
• Root Node: 트리 맨 위에 있는 노드 이다.
• Level: 최상위 노드를 Level 0이며, 하위 Branch로 연결된 노드의 깊이를 나타낸다.
• Parent Node: 어떤 노드의 다음 레벨에 연결된 노드
• Child Node: 어떤 노드의 자식 노드
• Leaf Node (Terminal Node): Child Node가 하나도 없는 노드 (가장 맨 끝의 노드)
• Sibling (Brother Node): 동일한 Parent Node를 가진 노드
• Depth: 트리에서 Node가 가질 수 있는 최대 Level

[자료구조] 트리

 

Binary Tree - 이진 트리

• 노드에 child가 최대 2개인 트리
• 왜 사용할까? 검색에 용이하므로. (사실, 이진 검색 트리를 위해 배우는 중)

 

Binary Search Tree (BST) - 이진 검색 트리

• Binary tree 성질 + 왼쪽 노드가 현재 노드보다 작아야 하고, 오른쪽 노드는 커야한다. 
• 왼쪽 서브노드의 값(left child) < 루트(부모)노드의 값(root node) <  오른쪽 서브노드의 값(right child) 
• BST는 노드 값에 따라 정렬되어 있으므로 빠른 탐색에 용이하다. 
• 검색이 일반 이진트리보다 빠르기 때문에 노드를 삽입하기 쉽다.

 

 

Complete Binary Tree

• leaf node들이 왼쪽부터 채워진 경우이다. 노드가 위에서 아래로 채워져있다.

 

 

검색과 재귀 (Search and Recursion)

# 입력된 리스트에서 요소들의 합을 큰 순서대로 구해보자(조건 : 모든 요소들의 합이 아니다.)
# 리스트의 메소드와 반복문을 활용해야 한다.

def remain_sum(numbers):
  result = []
  init_value = 0

  # 왼쪽인덱스부터 합을 구한다.
  # 반복문 : 0부터 4까지 result 리스트에 값을 append 한다.(반복인덱스 : 0,1,2,3)
  for i in range(0, len(numbers)):
    result.append(init_value)
    print("left sum - result[",i,"]:",result[i])
    init_value = init_value + numbers[i]    # append되는 index와 value를 구분해야 된다.

  init_value = 0   # 값 초기화(왼쪽에 대한 합을 구했으니, 이제 오른쪽인덱스부터 합구하기)

  # 구해진 값을 활용하여 오른쪽인덱스부터 더하면서 최종 리스트값을 구한다.
  # 반복문 : 3부터 -1까지 -1줄어들면서 result 리스트에 값을 더한다.(반복인덱스 : 3,2,1,0)
  for i in range(len(numbers)-1, 0-1, -1):
    result[i] = result[i] + init_value
    print("final sum - result[",i,"]:",result[i])
    init_value = init_value + numbers[i]

  return result

numbers = [int(numbers) for numbers in input("리스트값을 입력하세요 : ").split(',')]
print("결과:",remain_sum(numbers))

 

검색(Searching)

• 노드를 추가 또는 삭제를 하기 위해서는 검색을 먼저 해야한다.

# 선형 검색 알고리즘
# 하나의 반복문과 리스트의 인덱스, 조건문을 활용하여 특정값을 검색할 때까지 반복한다.

def linear_search(arr, target):

    # 입력 배열의 각 항목을 반복
    for idx in range(len(arr)):
        # 현재 인덱스의 항목이 비교 대상과 같은지 확인
        if arr[idx] == target:
            # 현재 인덱스를 일치 항목으로 반환
            return idx
            
    # 전체 배열을 반복할 수 있다면, 비교 대상은 존재하지 않는다.(의미없는 -1 값 반환)
    return -1

print(linear_search([0,1,2], 2)) # case 1 - true
print(linear_search([0,1,2], 3)) # case 2 - false

 

재귀(Recursion)

• 큰 문제를 최소한의 작은 단위로 나눠서, 스스로 함수를 다시 호출 하는 것을 뜻한다. 
• 재귀를 사용하면 메모리를 많이 사용하므로 주의해야 한다. 
• Divide and conquer (분할 정복법)이 대표적인 재귀를 이용한 문제해결 알고리즘이다. 
• 다음 예시를 참고하면 색종이 수를 구하기 위해 재귀를 사용하는 것을 배울 수 있다.

GitHub - DAWUNHAN/algorithms-and-dataStructure: Algorithms and DataStructure with Python