메타 스터디 그룹

[자료구조 목차]

1. Tree 개요

 가. Tree 정의

 - 노드(Node)들이 나무 가지처럼 연결된 비선형 계층적 자료 구조

 - 아래 그림 같이 나무를 거꾸로 뒤집어 놓은 모양과 유사함

 나. Tree 특징

  - 그래프의 한 종류이며, '최소 연결 트리' 불림

  - 계층적 모델이고, DAG(Directed Acyclic Graphs, 방향성이 있는 비순환 그래프)의 한 종류

  - 노드가 N개인 트리는 항상 N-1 개의 간선(Edge)를 가짐

  - 루트에서 어떤 노드로 가는 경로는 유일함

  - 1개의 Root Node만 존재하며, 모든 자식 Node는 1개의 부모 노드만 가짐

2. Tree 구성도 및 구성요소

 가. Tree 구성도

 나.Tree 구성 요소 설명

3. Tree 순회 방식

[자료구조 목차]

이진트리 (Binary Tree)

1. 탐색작업의 효율화를 위한 자료구조, 이진트리 개념

• 각 노드가 2개 이하의 자식노드를 가지는 트리형 자료구조로 탐색 작업을 효율적으로 하기 위한 자료구조
• 노드의 차수(degree)가 2 이하로 구성된 트리
• 왼쪽 자식 노드는 부모보다 작고, 오른쪽 자식 노드는 부모보다 큰 트리구조 형태
• (연산유형) 탐색, 삽입, 삭제

2. 이진트리의 순회방식 및 유형

1) 이진트리 순회방식

• 전위 순회 : 루트노드를 먼저 탐색하고, 자식노드를 탐색하는 방식
• 중위 순회 : 왼쪽 자식 노드를 탐색하고, 루트노드를 탐색하고,오른쪽 자식 노드를 탐색하는 방식
• 후위 순회 : 왼쪽 자식 노드를 탐색하고, 오른쪽 자식 노드를 탐색하고, 루트 노드를 탐색하는 방식

순회 방식	그림	설명
전위 순회		- 루트노드를 먼저 탐색하고, 자식노드를 탐색하는 방식
중위 순회		- 왼쪽 자식 노드를 탐색하고, 루트노드를 탐색하고,오른쪽 자식 노드를 탐색하는 방식
후위 순회		- 왼쪽 자식 노드를 탐색하고, 오른쪽 자식 노드를 탐색하고, 루트 노드를 탐색하는 방식
레벨 순회		- 루트 노드를 먼저 탐색하고, 그 다음 레벨의 노드를 탐색하는 방식 - 큐를 선언하고 루트노드를 넣어준 다음, 큐에 넣어준 노드를 하나씩 탐색하면서 자식 노드를 큐에 넣고 큐가 비어있을 때까지 반복

2) 이진트리 유형

유형	개념도	설명
포화 이진		leaf 노드들이 모두 같은 높이에 존재 총 노드 개수 : 2^k - 1 (k ≥ 1)
완전 이진		leaf 노드들이 트리의 왼쪽부터 차곡차곡 채워진 형태 총 노드 개수 : 2^(k-1) ~ 2^k -1
경사 이진		한쪽 방향으로 노드들이 채워진 형태

• 깊이가 k인 이진트리의 최대 노드의 수 : 2^k - 1
• 이진 트리의 레벨 i에서 최대 노드의 수 : 2^(i - 1)
• n0 = n2 + 1 (n0 : 이진 트리의 터미널 노드, n2 : 차수가 2인 노드 수)

[자료구조 목차]

1. 우선순위 큐를 위한 Heap

1) 정의 

- 여러 개의 노드들 가운데서 최대값이나 최소값을 빠른 시간내에 찾아내도록 만들어진 완전 이진 트리 자료 구조

** 이진트리,  우선순위 큐

2) 특징

- 힙 순서 속성 만족, 대부분 이진 힙, O(log n)

2. Heap 의 종류 및 연산

1) Max Heap과 Min Heap

구분	Max Heap	Min Heap
개념도
개념	부모노드의 키 값이 자식노드의 키 값보다 크거나 같은 완전 이진 트리	부모노드의 키 값이 자식노드의 키 값보다 작거나 같은 완전 이진 트리
힙 순서 속성	key(부모노드) ≥ key(자식노드)	key(부모노드) ≤ key(자식노드)

2) Heap의 연산

구분	설명
삽입 연산	1. 최고 깊이, 최우측에 새 노드 추가 2. 삽입 노드와 부모노드 비교 3. 삽입노드보다 부모노드가 작으면 연산 종료, 크면 위치 교환 4. 2번 단계 다시 진행
삭제 연산	1. 최고 깊이, 최우측에 있던 노드를 루트노드로 이동(힙속성 파괴) 2. 옮겨온 노드와 양쪽 자식 비교, 작은쪽 자식과 위치 교환 3. 옮겨온 노드가 더 이상 자식이 없거나 양쪽 자식보다 작은 값인 경우 연산 종료, 아닌 경우 2번 진행

[자료구조 목차]

I.  재귀알고리즘의 개요

가.  재귀알고리즘의 정의

-   수학적 귀납법을 역순으로 이용하여 자신의 함수를 반복적으로 호출하는 알고리즘

수행 과정 중 스스로 호출하는 함수

재귀의 설명 그대로 함수에서 자기 자신을 다시 호출해 작업을 수행하는 방식이다.

그렇기에 특정 분기까지 자기 자신을 계속해서 호출하는데, 주로 반복문을 구현할 때 사용한다.

우리가 흔히 알고 있는 반복문은 for, while 등이 있는데, 이러한 반복문으로 구현가능한 로직은 모두 재귀함수로도 가능하고 그 반대 역시 가능하다.

II. 종료조건

가 종료조건 필요성

종료조건이 없으면 무한 루프 및 Stack Overflow 발생

나. 종료조건

호출이 일어날때마다 재귀 케이스에서 인자 값이 감소

최종적으로 if 문의 조건을 만족시켜 기본 케이스 실행 후 종료

if(함수 호출 멈출 조건) : #기본 케이스

    마지막으로 실행할 명령

else: #재귀 케이스

    재귀함수 호출

III.  재귀알고리즘의 작성절차 및 효율성

가. 재귀알고리즘의 작성절차

나. 재귀 알고리즘의 효율성

-   공간적 비효율(저장공간)

-   시간적 비효율(저장, 복원에 걸리는 시간)

-   가능하다면 반복문으로 대치하는 것이 유리

[자료구조 목차]

개념

• 선택 시 마다 그 순간 최적의 해를 선택하여 최종적인 해를 도출하는 알고리즘
• 최적해를 구하는 목적으로 사용하는 근시안적인 알고리즘 기법

도출 해의 최적에 대한 보장은 불가

그리디 알고리즘의 특징

그리디 알고리즘 수행절차

그리디 알고리즘 적용조건

• 탐욕적 선택 속성(Greedy Choice Property) : 앞의 선택이 이후의 선택에 영향을 주지 않음.
• 최적 부분 구조(Optimal Substructure) : 문제에 대한 최종 해결 방법은 부분 문제에 대한 최적해로 구성.
• 이러한 조건이 성립하지 않는 경우에는 탐욕 알고리즘은 최적해를 구하지 못함 
  -> 이러한 경우에도 탐욕 알고리즘은 근사 알고리즘으로 사용이 가능, 계산 속도 빨라 실용적 사용 가능.
• Matroid 구조에서는 탐욕 알고리즘은 언제나 최적해 구할 수 있음
  * Matroid : 일차독립의 성질을 공리화하여 얻은 조합론적 구조
   매트로이드 - 위키백과, 우리 모두의 백과사전 (wikipedia.org)