2021년 8월 3일 - Binary & Linear

● 본 공부와 기록은 유튜버 '노마드 코더 Nomad Coders' 님의 "검색 알고리즘? 기초개념 잡아드림. 10분 순삭."을 기본으로 하였다.

→ https://www.youtube.com/watch?v=WjIlVlmmNqs&list=PL7jH19IHhOLMdHvl3KBfFI70r9P0lkJwL&index=3

 

 

☆ 훌륭한 알고리즘

 

→ 이번에는 왜 알고리즘이 중요한지 배우기 위해 같은 작업을 수행하는 2개의 알고리즘을 비교해볼 것이다.

→ 배열 안에 있는 숫자를 어떻게 찾을 수 있는지(Searching)가 오늘의 주제이다.

→ 자료 구조처럼 어떤 알고리즘을 선택하느냐에 따라 해당 작업을 수행하는 스피드가 굉장히 차이난다. 

→ 완벽한 자료구조, 알고리즘 조합을 찾아내면 코드의 속도 자체가 달라진다.

→ 알고리즘은 단지 어떠한 작업을 수행할 때, 우리가 따라야하는 절차/스텝들이다.

→ 알고리즘에도 시간 복잡도Time Complexity가 존재한다. 

→ 적은 절차로 같은 작업을 수행하는 알고리즘이 더 훌륭한 알고리즘이다.

 

---

 

☆ Search Algorithm Family

• 이진검색 알고리즘 Binary Search Algorithm
• 선형검색 알고리즘 Linear Search Algorithm

→ 이진검색과 선형검색 알고리즘은 둘 다 Search Algorithm Family에 속한다.

→ 검색 관련 작업을 수행하는 가족군으로, 최대한 빠르게 검색 작업을 수행하는 것이다.

→ 다른 Algorithm Family로는 정렬 알고리즘 Sorting Algorithm이 존재하고, 자료를 정렬한다.

ex) A ~ Z, 작은 수 ~ 큰 수

 

---

 

☆ 선형검색 알고리즘 Linear Search Algorithm

 

→ 검색을 하기 위한 가장 자연스러운 방법이다.

ex) 10개 숫자의 배열이 존재하고, 그 배열에서 '7'을 찾는다면 0번 아이템부터 차례대로 7이 맞는지 확인해야 한다.

 

 

→ 이렇게 순서대로 처음부터 끝까지 차근차근 목표값을 찾는 것을 의미한다.

→ 선형검색의 최악의 경우엔 우리가 찾는 아이템이 맨 마지막에 있거나, 없는 경우이다.

→ 이를 선형 시간복잡도 Linear Time Complexity O(n)라고 한다.

→ 배열이 커지면 커질수록 선형검색을 하는 시간 또한 길어지게 된다.

 

 

→ 인풋이 많으면 많을수록, 수행하는 시간 역시 선형으로 증가한다는 뜻이다.

 

---

 

☆ 이진검색 알고리즘 Binary Search Algorithm (1)

 

→ 선형 시간복잡도 해결을 위한 더 나은 방법이다.

→ 그러나 이진검색 알고리즘을 모든 배열에 사용할 수는 없다.

→ 어떤 알고리즘은 특정 자료구조에서만 사용이 가능하다.

→ 선형검색은 어느 배열에서나 사용이 가능하지만, 이진검색 알고리즘은 아니다.

→ 이진검색 알고리즘은 오로지 정렬된 배열 Sorted Array에서만 사용이 가능하다. 

 

 

★ 정렬된 배열 Sorted Array란?

 

 

 

→ 배열들이 순서대로 정렬된 경우를 의미한다.

→ 이렇게 정렬된 배열에 아이템을 추가하는 것은, 정렬이 안된 경우보다 시간이 더 걸린다.

 

 

→ 정렬이 안된 배열에 단순히 아이템을 추가하는 건 매우빠르다.

→ 공간이 있기만 하면, 그냥 맨 끝에 아이템을 추가하면 끝나는 것이다.

→ 반대로 정렬된 배열에서 아이템을 추가하는 것은 시간이 걸린다.

 

 

ex) 만약 위의 배열에서 '8'을 추가한다고 가정하자.

① 먼저 해당 배열에서 8보다 큰 아이템을 먼저 찾아야 한다.

② 해당 아이템을 찾은 후, 8을 해당 아이템의 왼쪽에 추가해야 한다.

③ 이 작업을 위해, 인덱스 0부터 해당 숫자가 추가하고 싶은 숫자보다 큰지, 작은지 각각 비교하는 작업을 반복한다.

④ 추가하려는 숫자보다 큰 값을 발견하면, 추가하고 싶은 위치의 오른쪽에 있는 아이템(10)을 움직여 더한다.

 

→ 따라서 정렬이 안된 배열에 값을 추가하는 것보다, 정렬된 배열에 추가하는 것이 시간이 더 오래 걸린다.

→ 아이템들을 하나씩 비교하고, 이를 통해 포지션을 찾고 나면, 해당 아이템 오른쪽에 있는 모든 걸 옮겨야 한다.

→ 하지만, 배열에 추가하고 정렬하는데 시간을 투자하면, 검색에 굉장히 보람을 느낄 수 있다.

 

→ 정렬된 배열에서 검색 Searching을 하는 것은, 정렬이 안된 경우보다 매우 빠르다.

 

---

 

☆ 이진검색 알고리즘 Binary Search Algorithm (2)

 

→ 이진검색 Binary Search에서 이진Binary는 말 그대로 '0'과 '1'을 의미하지 않는다. 

→ 여기서 Binary란, '반으로 쪼개는 것'을 의미한다.

 

 

ex) 1~10까지 정렬된 배열이 있고, 여기서 '9'를 찾아야Searching하는 상황이다.

→ 선형검색과 달리, 이진검색에서는 인덱스 0부터 즉, 처음부터 검색하지 않는다.

→ 이진검색에서는 정렬의 정중앙에서부터 시작한다.

→ 정 가운데에 있는 숫자가 우리 목표보다 큰지 작은지를 본다.

 

 

→ 만약 목표보다 크다면, 그 경우 아이템의 왼쪽으로 이동한다.

 

 

→ 만약 목표보다 숫자가 작다면, 아이템의 오른쪽으로 이동한다.

 

 

① 1에서 10까지 정렬된 상황에서 중간은 '5'이고, 찾으려는 목표는 '9'이다.

② 5는 9보다 작으므로, 왼쪽은 전부 무시하고 오른쪽으로 이동한다. (첫번째 프로세스)

③ 그리고 해당 프로세스를 반복하는데, 해당 배열의 중간의 중간으로 이동한다.

 

 

④ 이 경우, 숫자는 '8'이 된다.

⑤ '8'은 '9'보다 작으므로, 마찬가지로 해당 아이템의 왼쪽을 전부 무시한다. (두번째 프로세스)

 

 

⑥ 그 다음 프로세스에서 남은 아이템이 2개뿐이기에, 드디어 목표값을 찾을 수 있다. (세번째 프로세스)

⑦ '9'의 값을 선택하게 된다.

 

 

→ 이진검색에서는 3번의 과정Step만에 우리가 원하는 값을 찾는데 성공했다.

→ 선형검색이었다면, 무려 9번의 시도가 필요했을 것이다.

 

---

 

Q.

20개의 목록이 있는 배열에서 타겟 '13'을 찾는데 드는 과정Step이 수를 구하시오.

 

 

① Step Num 1

 

 

② Step Num 2

 

 

③ Step Num 3

 

 

④ Step Num 4

 

 

→ 따라서 '4단계Steps'가 소요된다.

→ 배열의 목록이 2배가 되었음에도, 스텝이 딱 1단계 증가할 뿐이다.

 

 

→ 여기서 보다시피 인풋은 2배가 되었지만, 필요한 스텝은 2배가 되지 않았다.

→ 이진검색은 매 스탭마다 절반의 아이템을 없애기 때문이다.

→ 즉, 우리의 자료가 2배가 되어도 작업을 수행하는데 필요한 스텝은 +1 될 뿐이라는 뜻이다.

→ 이는 특히 큰 사이즈의 데이터를 처리할 때, 엄청나게 효율적인 방법이다.

 

---

 

☆ 이진검색 & 선형검색 비교

 

→ 1만개의 아이템이 있는 상황이라면, 선형검색은 최악의 경우 1만 개의 스텝을 요구한다.

→ 반대로 이진검색은 최악의 경우에도 14 스텝만을 요구한다.

 

 

→ 이것이 알고리즘이 중요한 이유이다.

→ 14개의 스텝과 1만 개의 스텝 차이는 어마어마하다.

→ 이는 곧바로 속도로 실감할 수 있다.

 

 

★ 정리

 

→ 이진검색은 거대한 배열을 다룰때 효율적이다.

→ 그러나 이진검색을 하고 싶다면 먼저 배열을 정렬해야한다.

→ 이는 시간이 소요되는 일이다.

→ 여기서 트레이드 오프Trade Off가 발생한다.

→ 검색을 많이하는 상황이라면, 일단 정렬을 해야한다.

→ 하지만, 배열을 정렬하려면 아이템 추가시 시간이 소요된다는 것이다. 

→ 이러한 상충관계는 명확히 인지해야 한다.