[방송통신대학교]알고리즘_동영상강의,기출_핵심요약노트

목차

1강. 알고리즘 학습에 앞서서
2강. 알고리즘의 기초
3강. 분할정복 알고리즘 (1)
4강. 분할정복 알고리즘 (2)
5강. 동적 프로그래밍 알고리즘 (1)
6강. 동적 프로그래밍 알고리즘 (2)
7강. 욕심쟁이 알고리즘 (1)
8강. 욕심쟁이 알고리즘 (2)
9강. 학습 PLUS+
10강. 정렬 알고리즘 (1)
11강. 정렬 알고리즘 (2)
12강. 탐색 알고리즘 (1)
13강. 탐색 알고리즘 (2)
14강. 근사 알고리즘
15강. 학습 PLUS+
16. 출석수업 정리

본문내용

1강. 알고리즘 학습에 앞서서
* 배열
배열은 같은 자료형을 갖는 여러 데이터를 하나의 변수명으로 모아놓은 데이터의 집합체로서, 논리적 순서와 저장된 물리적인 순서가 동일하기 때문에 삽입과 삭제가 발생할 때 순서 유지를 위해 부가적인 자료의 이동이 필요하며, 인덱스를 통한 빠른 임의 접근이 가능한 자료구조
데이터의 논리적 순서와 물리적 순서가 동일
원칙적으로 각 데이터에 대한 접근 시간은 동일
데이터의 삽입과 삭제 시 추가적인 자료의 이동이 발생

* 스택에서 push 하기 전에 top을 하나 올려준 뒤 값을 하나 넣는 식으로 하고, pop 할 때는 값을 하나 뺀 뒤 top을 하나 내려줌

* 큐에서 삽입되는 부분이 Rear / Tail이고 삭제되는 부분이 Front / Head
큐에서 맨 처음에 삽입되는 입구에 front, rear가 같이 위치해 있고, 삽입 시 rear를 하나 앞으로 보낸 뒤 값을 넣고, 삭제 시에는 front를 앞으로 하나 보낸 뒤 그 값을 뺌

* 트리
노드의 차수(degree) : 자신의 서브트리(가지) 개수
트리의 차수 : 트리에 있는 노드의 차수 중에서 가장 큰 값
리프(leaf) 노드 = 단말(terminal) 노드 : 노드의 차수가 0인 것들
비단말(nonterminal) 노드 : 리프 노드가 아닌 것들
레벨 : 루트 노드로부터의 거리(루트 노드의 레벨 : 0)
트리의 높이(깊이) : 가장 큰 레벨 + 1
숲 : 루트 노드를 잘랐을 때 밑에 생기는 서브트리들

* 이진 트리 : 각 노드의 차수가 2 이하인 순서 트리(아무 것도 없는 공백도 이진 트리로 취급)
레벨 i에서 최대 노드의 개수(i >= 0 ) : 2의 i승
높이 h인 이진 트리의 최대 노드의 개수(h >= 1) : 2의 h승 - 1
n0 = n2 + 1 (n0 : 단말 노드의 수, n2 : 차수가 2인 노드의 수)

* 포화(perfect) 이진 트리 : 꽉 찬 이진 트리
높이가 h인 포화 이진 트리의 노드 개수는 2의h승 - 1

참고자료

· 없음