패스트캠퍼스 챌린지 12일차

---

Part 2. 알고리즘 이론

 

Ch 16. 정렬 알고리즘 몸풀기

 

01. 순차 탐색

 

02. 이진 탐색

---

 오늘은 정렬 알고리즘 몸풀기로 순차 탐색과 이진 탐색에 대해 배웠다. 강사님께서는 알고리즘을 공부했던 자기 경험을 바탕으로 강의 계획도 완급 조절하셨다. 병합 정렬과 퀵 정렬을 배우며 머리가 아플 수강생을 위해 쉬어가는 겸 다음 단계로 넘어가게 위한 준비로 순차 탐색과 이진 탐색을 가르쳐주신 것이다. 덕분에 나의 뇌도 쉬어갈 수 있었다. 아마 오늘도 병합 정렬이나 퀵 정렬처럼 어려운 걸 배웠다면 아마 과부하가 발생했을지도 모른다.

 순차 탐색이란 말 그대로 순서대로 탐색하는 것을 말한다. 쉽게 생각하면 우리가 for문을 이용할 때를 생각하면 된다. 열 개의 정수를 담을 수 있는 배열에 1부터 10까지 입력해뒀을 때, 어떤 값을 찾기 위해 for문을 이용해 배열의 인덱스를 순서대로 탐색해 원하는 값을 찾는 것이다. 하나씩 확인하기 때문에 시간 복잡도는 O(n)이다. 이진 탐색은 pivot이라는 기준점 대신 가운데 인덱스를 사용한다는 점에서 퀵 정렬과 비슷하다. 가운데 인덱스를 기준으로 찾고자 하는 값이 크다면 오른쪽으로, 작다면 왼쪽으로 간다. 그다음 원하는 값을 찾을 때까지 반으로 나눠 크기를 비교하는 것을 반복한다. 이진 탐색은 순차 탐색처럼 하나하나 훑는 것이 아니라 크기를 비교하며 탐색하기 때문에 시간 복잡도 O(log n)으로 빠르다는 장점이 있으나 이진 탐색을 사용하기 위해서는 배열이 정렬되어있어야 한다는 단점이 있다.

오늘은 말로 설명하는 것도 어렵지 않은 쉬운 개념을 배웠다. 여기서부터 퀵과 병합으로 거슬러 올라가며 복습을 다시 해야겠다.

 

 

---

 

https://bit.ly/3FVdhDa

수강료 100% 환급 챌린지 | 패스트캠퍼스

- 본 포스팅은 패스트캠퍼스 환급 챌린지 참여를 위해 작성되었습니다.-