4장. 자료구조의 끝판왕

실습_4. 자료구조의 끝판왕

프로그램의 핵심 : 되풀이

• 비슷한 일을 여러번 되풀이해서 풀어내기

def doDomething(nums):
  sum = 0
  for num in nums:
    sum = sum + num
  return sum

재귀

• 스스로를 호출하는 방식의 반복법
• 어떤 주어진 일(Tsak)이 같은 과정을 필요로 하지만 더 범위가 작은 일(Sub Task)들로 나눠질 수 있다면, 재귀를 적용할 수 있다.
• 언젠가는 끝이 나야하므로 식의 종료 조건이 필요
  • Base 조건(ex. f(0) = 1, f(1) = 2)

팩토리얼 계산

factorial(n) = n! = n*n-1*n-2*...*1
factorial(n-1) = n-1! = n-1*n-2*n-3*...*1

이 경우

factorial(n) = n * factorial(n-1)

• 즉, factorial 구현 안에서 factorial 사용 가능 = 재귀

동적 프로그래밍

• Dynamic Programming

• 재귀 + 정보 저장(메모이제이션)

• 한 부분 문제를 한번 계산했다면 다시 계산할 필요가 없도록

  • 저장 값을 다른 자료 구조에 저장

트리

• 나무 형태의 자료구조

부모와 자식

• 부모노드 -> 자식노드 방향으로 연결이 존재

루트와 리프

• 루트(root): 부모가 없는 노드
• 리프(leaf): 자식이 없는 노드

트리의 깊이

• 루트에서 리프까지의 경로의 길이, Depth

트리의 특성

• 루트는 하나
• 방향성 존재
• 순환 구조가 없음

이진 트리

• 모든 노드가 최대 2개의 자식 노드를 가지는 트리
• 완전 이진 트리(Complete Binary Tree)
  • 마지막 레벨을 제외하고 모든노드가 채워져있다
  • 마지막 레벨 노드가 왼쪽부터 채워져 있다
• 포화 이진 트리(Full Binary Tree)
  • 마지막 례벨을 제외하고 모든 노드에 2개의 자식이 있다

이진 탐색 트리

• Binary Search Tree
• 모든 부모 노드의 값이 왼쪽 자식 트리에 있는 값보다는 크고 오른쪽 자식 트리에 있는 값보다는 작은 형태의 트리

트리의 핵심: 탐색

• 루트 노드가 주어졌을 때 트리를 구석구석 훑어가며 원하는 목적을 달성하는 것
• 반복 또는 재귀를 활용

너비 우선 탐색(BFS)

• Breadth First Search : 반복 기반의 탐색

def BFS(root):
  q = queue.Queue()
  q = put(root)
    while q.qsize() > 0:
      node = q.get()
      if node:
        //doSomething
      q.put(node.left)
      q.put(node.right)

깊이 우선 탐색(DFS)

• Depth First Search :재귀 기반의 탐색

def DFS(node):
  //doSomething
  if node == 리프노드:
    doSomething
    return
  DFS(node.left)
  DFS(node.right)