시간복잡도와 공간복잡도
Big-O
니보다 연산이 적다!
Big-Omega
니보다 연산이 크다!
Big-Theta
위 두 개의 사이. 샌드위치
Brute-Force
다 해보는 거 노가다!!!
정렬과 탐색을 위한 효과적인 방법
순차 탐색과 이진 탐색
순차 탐색
이름 그대로다. 첫번째부터 순차적으로 점검해나가는 것
이진 탐색
정렬이 되어 있다는 전제!!!!!
이진 탐색의 이름따라 반으로 가른다!
반에 나오는 수가 찾고자 하는 수보다 작으면 왼쪽 버려!! 크면 오른쪽 버려!!!
이 과정을 반복한다.
정렬을 위한 기본 알고리즘
Bubble Sort
이웃끼리 비교한다. 두 개씩 비교하는데 이 모양이 버블 모양 같이 생겼나보다.
Insertion Sort
말 그대로 삽입하는 것이다. 얘는 왼쪽만 본다. 그리고 본인의 자리를 찾으면 쏙!! 들어간다.
Selection Sort
선택을 한다! 뭐를?? 가장 최소의 원소를!!
그리고 맨 앞으로 보낸다.
Heap Sort
Heap 성질을 유지하면서 정렬을 계속하는 것이다.
Radix Sort
이것은 앞에 나온 것과는 다르게 비교하는 것이 아니라 점검하는 것이다.
각 자리 수를 점검하여 정렬을 진행한다.
휴리스틱과 욕심쟁이 알고리즘
링크텍스트
지금 상황에서 최고!!의 선택을 하는 것
분할정복의 뜻과 문제 해결에의 적용
분할정복
분할정복은 쪼개고 다시 합치는 것이다
Merge Sort
수열을 절반으로 쪼개고 다시 합치는 과정에서 정렬을 해나가는 것이다.
쪼갠 두 팀을 비교하면서 정렬한다.
Quick Sort
피봇을 정한다. 그리고 양쪽에서 ><으로 출발해 pivot보다 큰지, 작은지 점검한다. 만약 왼쪽에 있는데 피봇보다 크다, 혹은 오른쪽에 있는데 피봇보다 작은면 원소의 자리를 바꾼다. ><이 <> 모양이 될 때까지 진행한다.
동적계획을 이용한 문제 해결 성능 제고
점화식을 세운다는 것을 기억할 것!
memoization
top-down
이전 값을 기록하여 쓸데없는 반복을 피한다.
Tabulation
down-up
빈 표에 값을 채워가는 방식이다.
