[LG 유레카]
트리
- 배열을 이용한 이진 트리의 표현
- 노드 번호의 성질
- 노드 번호가 i인 노드의 부모 노드 번호? ➡ i/2
- 노드 번호가 i인 노드의 왼쪽 자식 노드 번호? ➡ 2 * i
- 노드 번호가 idls 노드의 오른쪽 자식 노드 번호? ➡ 2 * i + 1
- 레벨 n의 노드 번호 시작 번호는? 2n
너비 우선 탐색
루트 노드의 자식 노드들을 먼저 모두 차례로 방문한 후에, 방문했던 자식 노드들을 기준으로 하여 다시 해당노드의 자식 노드들을 차례로 방문하는 방식
인접하 노드들에 대해 탐색을 한 후, 차례로 다시 너비우선탐색을 진핸해야 하므로, 선입선출 형태의 자료구조인 큐를 활용함
깊이 우선 탐색
루트 노드에서 출발하여 한 방으로 갈 수 있는 경로가 있는 곳까지 깊이 탐색해 가다가 더 이상 갈곳이 없게 되면, 가장 마지막에 만났던 갈림길 가선이 있는 노드로 되돌강와서 다른 방향의 노드로 탐색을 계속 반복하여 결국 모든 노드를 방문하는 순회방법
탐욕 알고리즘
-
최적해를 구하는 데 사용되는 근시안적인 방법
-
최적화 문제란 가능한 해들 중에서 가장 좋은(최대 또는 최소)해를 찾는 문제이다.
-
일반적으로, 머리 속에 떠오르는 생각을 검증 없이 바로 구현하면 Greedy 접근이 된다.
-
여러 갱우 중 하나를 선택 할 때마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식으로 진행하여 최종적인 해답에 도달한다.
-
각 선택 시점에서 이루어지는 결정은 지역적으로는 최적이지만, 그 선택들을 계속 수집하여 최종적인 해답을 만들었다고 하여, 그것이 최적이라는 보장은 없다.
-
일단, 한번 선택된 것은 번복❌
이런 특성 때문에 대부분의 탐욕 알고리즘드은 단순하며, 또한 제한적인 문제들에 적용된다.
탐욕 대표 알고리즘
-
탐욕적 선택 속성greedy choice property
-
탐욕적 선택은 최적해로 갈수 있음을 보여라.
➡즉, 탐욕적 선택은 항상 안전하다.
-
-
최적 부분 구조optimal substructure property
-
최적화 문제를 정형화하라
➡하나의 선택을 하면 풀어야 할 하나의 하위 문제가 남는다.
-
-
원문제의 최적해 = 탐욕적 선택 + 하위 문제의 최적해 임을 증명
-
대표적인 탐욕 기법의 알고리즘
알고리즘 | 목적 | 설명 | 유형 |
---|---|---|---|
Prim | |||
댓글남기기