알고리즘
컴퓨터 알고리즘이란 어떤 문제를 해결하기 위해서 컴퓨터가 이해할 수 있는 방식으로 정리되어 있는 해결 방법을 말한다.
좋은 알고리즘을 사용해야 하는 이유는 내 취향에 맞게 영상을 추천해주는 서비스처럼(EX 영화 어플이나 유튜브 동영상 같은) 알고리즘이 얼마나 좋은지에 따라 서비스의 성패가 갈리는 경우가 많기 때문이다.
탐색이란 원하는 정보들 중에서 원하는 값을 찾는 것이다.
-
선형 탐색 알고리즘 (처음부터 끝까지 순서대로 탐색하기)
-
이진 탐색 알고리즘 (반씩 제외시키면서 탐색하기)
-
가장 오래 걸리는 경우(최악의 경우) 비교
| 리스트 길이 | 선형탐색 | 이진탐색 |
|---|---|---|
| 16 | 16개 | 4개 |
| 32 | 32개 | 5개 |
| 64 | 64개 | 6개 |
| 128 | 128개 | 7개 |
이진 탐색이 가능하기 위해서는 정렬이 이미되어있어야한다.
정렬이란 리스트의 원소들을 특정 순서로 정리하는 것이다.
- 선택 정렬 (위치에 어떤 값이 들어갈지 찾는다)
- 삽입 정렬 (값이 어떤 위치에 들어갈지 찾는다)
다양한 정렬 알고리즘
정렬은 상황에 따라 각 알고리즘의 장단점을 파악해서 사용해야 한다.
이유는 정렬 문제에 있어 절대적인 좋은 답은 없기 때문이다.
상황에 따라 각 알고리즘의 장단점을 파악하기 위해서는 알고리즘을 평가하는 능력을 길러야 한다.
알고리즘의 평가에는 시간 복잡도와 공간 복잡도가 있다.
시간 복잡도란, 데이터가 많아질수록 걸리는 시간이 얼마나 급격히 증가하는가를 의미한다.
점근 표기법이란, n이 엄청나게 크다는 가정을 두고 시간 복잡도를 나타내는 용도로 사용된다.
점근 표기법 Big-O
-점근 표기법에서의 n은 가장 흔히 사용되는 문자이고 그래프나 트리같은
특수한 자료 구조가 인풋으로 들어올 때에는 n이 아닌 다른 문자를 쓰기도 한다.
-인풋 크기와 상관없이 실행되는 코드는 시간복잡도가 O(1)로 계산되어 제외된다.
