2021.07.18
알고리즘
알고리즘의 정의 : " 문제를 해결하기 위한 절차 "
알고리즘 != 프로그래밍
알고리즘을 설명할 때는 코드를 그대로 설명하는게 ❌
핵심 아이디어를 중심으로 어느 정도까지 세부적으로 설명하는 것
프로그래밍은 알고리즘을 이용해 코드를 짜는 것! 어떻게 구현하는지 생각하는 것
좋은 알고리즘이란?
- 이해할 수 있어야 하며, 간결한 것
- 재이용하기 쉽고, 유지보수가 쉬운 것
- 하드웨어(메모리)등 주어진 자원을 고려하는 알고리즘
- 수행시간이 빠른 알고리즘
시간복잡도
시간복잡도를 계산할때, 상수와 계수를 빼고 최고차항만 고려해도 똑같다.
위 식은 n^2 vs n 으로 볼수있음 -> Big-O 표기법
0.1n^2 + 3n + 7 = O(n^2) 이니까 적당한 큰수에 대해서
-> 0.1n^2 + 3n + 7은 n^2보다는 항상 작다는 것.
-> 0.1n^2 + 3n + 7의 대략적인 상한을 알 수 있다는 것!
정렬
버블 정렬
버블~버블~💦
앞에서부터 인접한 2개를 비교하면서 올바른 순서가 되도록 한다.
한바퀴를 다 돌면 다시 반복한다.
i번째 반복을 수행하는 경우, 끝에서 i번째 원소를 제외하고 비교해도 된다. (맨 마지막엔 제일 큰수가 와있을 것이니까!)
삽입 정렬
i번째 수를 앞으로 비교하면서 보내며 올바른 자리에 위치시킨다.
정렬을 할수록 앞에 정렬된 배열이 생긴다.
병합 정렬
Hongik CE