RAM = CPU(메모리에 있는 데이터를 읽고 쓰고 변형한다.) + MEMORY(프로그램이 다루는 데이터가 다 여기에 올라가고) + 기본연산(단위시간에 수행되는 연산들의 모음)
기본연산이란? (1단위시간내에 수행된다.)
- 배정, 대입, 복사연산 (EX. A=B 메모리에 접근해서 B를 읽어 A에 쓴다)
- 산술연산
- 비교연산
- 논리연산 : AND, OR, NOT
- 비트연산
점화식 : 수열의 일반항 사이의 관계식
2항 점화식 : 일반항이 두개로 구성된 점화식
수열의 귀납적 정의 - 어떤 수열인지를 나중에 알려주는것
단서가 되는 식을 점화식이라고 한다. 점점 되어가는 식
이웃한 3항이 있을때에는 최소 2개의 항을 알아야 점화식으로의 역할을 할 수 있다?
정렬알고리즘
-성질1. stable VS unstable
같은 숫자가 입력됐을때 입력한 순서가 유지되는가?
유지된다면 stable
일반적으로 stable한 알고리즘이 더 낫대
-성질2 in-place VS not in-place
메모리를 상수정도만 사용하는것
추가 사용 메모리 : O(1) VS O(n)
기본알고리즘 : selection bubble, insertion
간단하지만 느린 알고리즘
공통점 : (n-1)번의 rooud로 매 라운드마다 값 하나의 순서를 확정한다.
in-place이다.
selection
최댓값을 찾아서 맨 뒤로
T(n) = T(n-1)+cn
= O(n^2)
T(n) = 2T(n/2) + cn
= O(nlogn)
MergeSortion
MoM이 뭐야??
반을 강제로 나눠 sort하고 merge하기
merge하는 방법은 정렬된 그룹A와 그룹B 를 비교해 더 작은것 뽑아와 그룹 C에 넣는다. 그리고 남아있는것은 그냥 넣는다.
MoM(Median of Medians)
완전 이진 트리
자식의 개수가 무조건 2개인것
힙
루트가 가장 큰(혹은 작은) 값이어야 한다.
힙에서 부모와 자식 관계는 일정하지만 형제 사이의 대소 관계는 일정하지 않다.
힙은 형제의 대소 관꼐가 정해져 있지 않은 특성이 있기 때문에 부분순서트리라고도 한다.
힙 정렬
힙 정렬은 선택 정렬을 응용한 알고리즘이며 힙에서 가장 큰 값인 루트를 꺼내고 남은 요소에서 다시 가장 큰 값을 구해야 한다.
