1. Algorithm

- 알고리즘이 뭐야?

알고리즘은 우리가 따라야 하는 절차/스텝들이다. 우리는 평소에도 알고리즘을 사용해서 생활을 한다. 우리는 아침에 일어나 각자의 알고리즘(절차/Steps)에 맞춰서 생활을 한다. 누구는 밥을 먼저먹고 샤워를 하고 출근을 한다. 누구는 회사가 멀어서 밥을 출근하면서 해결한다. 어떤 상황에서 본인에게 맞는 생활패턴, 순서들을 통해서 출근이라는 문제를 해결한다. 항상 아침을 거르는 사람에게 아침을 먹고 시작하는 알고리즘을 적용한다면 힘든 하루를 보낼 것이다.

위의 예시를 대입해서 우리의 코드에 적용한다고 생각해보자. 상황에 맞는 자료구조와 알고리즘이 있다. 우리는 이 두 요소의 조합을 잘 맞춰서 사용해야 최고의 효율을 가져올 수 있다.

- 왜 필요한가?

서비스의 성능을 높이기 위해 상황에 맞춰 적절한 자료구조와 알고리즘을 선택해서 코딩을 해야한다. 완벽한 자료구조와 알고리즘의 조합이 가져오는 효과를 두 가지 알고리즘 비교와 함께 알아보려고한다.

2. Linear Search / 선형검색 알고리즘

- 선형? 선형이 무슨 뜻인가? 사전적 정의

선형성(線型性, linearity) 또는 선형(線型, linear, 라틴어: linearis)은 직선처럼 똑바른 도형, 또는 그와 비슷한 성질을 갖는 대상이라는 뜻으로, 이러한 성질을 갖고 있는 변환 등에 대하여 쓰는 용어이다. 함수의 경우, 어떠한 함수가 진행하는 모양이 '직선'이라는 의미로 사용. 이러한 개념은 수학, 물리학 등에서 많이 사용(use)된다. 다른 말로 1차(一次)라고도 한다. (단어 '1차' 자체는, '선형'을 의미하지 않는 경우도 많다.)

- 선형 검색 알고리즘

선형 검색 알고리즘은 그림과 같이 input값이 증가하면 그 만큼 시간(step)이 증가하는 알고리즘이다.

우리는 배열에서 숫자 2를 찾기위해 인덱스 0번부터 원하는 값을 찾을때까지 시간(step)을 증가시킨다.

최악의 경우는 원하는 값이 맨 끝에 있거나 아예 없을 경우이다. 이런 문제를 해결하기 위해 이진 검색 알고리즘이 있다.

3. Binary Search / 이진검색 알고리즘

- Binary?

![]() 하나를 두개로 쪼개는 것을 의미한다. 배열의 가운데에 있는 숫자가 우리가 원하는 숫자보다 큰지, 작은지를 판단하는 방식이다.

원하는 값보다 가운데 숫자가 크다면 focus가 왼쪽으로 이동한다.

다시 말하면 배열의 중간 값이 원하는 값보다 크다면 해당 값 이후에 있는 값들을 버린다는 뜻이다.

이 과정을 반복하면서 원하는 값을 찾는다.

- 모든 배열에 적용할 수 없다.

Binary Search 알고리즘은 Sorted Array(정렬된 배열)에서만 사용이 가능하다.

선형검색 알고리즘은 어느 배열에서도 사용이 가능하지만 이진검색 알고리즘을 포함한 몇몇 알고리즘은 제한된 상황에서 사용이 가능하다.

- Sorted Array?

정렬된 배열을 뜻한다. 예를들어 작은 수에서 큰 수로 정렬된 배열을 의미한다.

하지만 정렬된 배열에 아이템을 추가하는 것은 정렬이 안된 경우보다 시간이 더 소요된다.

컴퓨터는 정렬된 배열에 데이터를 추가하기 위해서는 배열에 어느 위치에 데이터를 추가해야 정렬된 배열이 유지되는지 연산해야한다.

이 과정에서 배열의 시작부터 원하는 위치가 나올때까지 추가할 데이터를 비교를 해야하 시간 복잡도가 올라간다.
배열의 시작부터 원하는 위치가 나올때까지 비교를 통해서 검색한다. 이 과정에서 당연하게

그리고 원하는 위치를 찾고 데이터를 추가하면 원래 위치에 있던 데이터들이 한 칸씩 밀린다.

이 과정에서 메모리는 많은 연산이 필요하고 이는 곧, 성능을 저하시킨다.

4. 아니 그럼 이진검색 알고리즘을 왜쓰나?

• 배열을 효율적으로 검색하기 위해서 선형검색 알고리즘이 아닌 이진검색 알고리즘을 사용해야한다.
• 이진검색 알고리즘을 쓰기 위해서는 정렬된 배열이 필수 조건이다.
• 정렬된 배열은 리소스 낭비를 불러올 수 있다.

여기서 우리는 알고리즘과 자료구조를 배우는 이유를 알 수 있다.

어떤 배열과 알고리즘을 선택하는 기준이 무엇이 있고 이를 비교해서 최고의 조합이 무엇인지?
어떤 조합에서 트레이드 오프가 발생하는지?

정렬된 배열의 단점과 이진검색의 장점이 선형검색의 단점을 비교하며 상황에 맞춘 알고리즘과 자료구조를 선택해야 한다.

이제 우리는 많은 데이터가 담긴 정렬된 배열에서 검색 기능을 자주 사용할 경우 우리는 이진검색 알고리즘을 고려할 수 있다.