[LG 유레카]

트리

• 배열을 이용한 이진 트리의 표현
• 노드 번호의 성질
  • 노드 번호가 i인 노드의 부모 노드 번호? ➡ i/2
  • 노드 번호가 i인 노드의 왼쪽 자식 노드 번호? ➡ 2 * i
  • 노드 번호가 idls 노드의 오른쪽 자식 노드 번호? ➡ 2 * i + 1
  • 레벨 n의 노드 번호 시작 번호는? 2ⁿ

너비 우선 탐색

루트 노드의 자식 노드들을 먼저 모두 차례로 방문한 후에, 방문했던 자식 노드들을 기준으로 하여 다시 해당노드의 자식 노드들을 차례로 방문하는 방식

인접하 노드들에 대해 탐색을 한 후, 차례로 다시 너비우선탐색을 진핸해야 하므로, 선입선출 형태의 자료구조인 큐를 활용함

깊이 우선 탐색

루트 노드에서 출발하여 한 방으로 갈 수 있는 경로가 있는 곳까지 깊이 탐색해 가다가 더 이상 갈곳이 없게 되면, 가장 마지막에 만났던 갈림길 가선이 있는 노드로 되돌강와서 다른 방향의 노드로 탐색을 계속 반복하여 결국 모든 노드를 방문하는 순회방법

탐욕 알고리즘

• 최적해를 구하는 데 사용되는 근시안적인 방법

• 최적화 문제란 가능한 해들 중에서 가장 좋은(최대 또는 최소)해를 찾는 문제이다.

• 일반적으로, 머리 속에 떠오르는 생각을 검증 없이 바로 구현하면 Greedy 접근이 된다.

• 여러 갱우 중 하나를 선택 할 때마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식으로 진행하여 최종적인 해답에 도달한다.

• 각 선택 시점에서 이루어지는 결정은 지역적으로는 최적이지만, 그 선택들을 계속 수집하여 최종적인 해답을 만들었다고 하여, 그것이 최적이라는 보장은 없다.

• 일단, 한번 선택된 것은 번복❌

  이런 특성 때문에 대부분의 탐욕 알고리즘드은 단순하며, 또한 제한적인 문제들에 적용된다.

탐욕 대표 알고리즘

• 탐욕적 선택 속성greedy choice property

  • 탐욕적 선택은 최적해로 갈수 있음을 보여라.

    ➡즉, 탐욕적 선택은 항상 안전하다.

• 최적 부분 구조optimal substructure property

  • 최적화 문제를 정형화하라

    ➡하나의 선택을 하면 풀어야 할 하나의 하위 문제가 남는다.

• 원문제의 최적해 = 탐욕적 선택 + 하위 문제의 최적해 임을 증명

• 대표적인 탐욕 기법의 알고리즘

알고리즘	목적	설명	유형
Prim