선형 검색 알고리즘과 이진 검색 알고리즘

참 쉽죠....?

 

 

소프트웨어의 알고리즘을 설명할 때 음식의 레시피에 자주 비유하곤 한다

 

초콜릿 케이크 레시피	***프로그램
재료: ~	연산에 필요한 데이터
< 만드는 법 > 오븐에서 30분, 또는 반죽이 자리 잡을 때까지 구우세요. 표면 위에 손바닥을 살짝 올려서 확인하세요.	수행할 작업
완성	결과

 

하지만 실제 프로그램의 알고리즘은 레시피와 같이 모호하지 않다.

 

'반죽이 자리 잡을 때'

'손바닥을 살짝 올려서 확인'

 

솔직히 사람인 내가 들어도 모호한 표현이다.

 

 

 

▼ 알고리즘

• 어떤 문제를 풀기 위한 절차나 방법
• 어떤 문제가 있을 때 주어진 '입력' 정보를 원하는 '출력(답)' 정보로 만드는 일련의 과정을 구체적이고 명료하게 적은 것.
• '세심, 정확, 명료'가 중요한 키워드.

 

[ 알고리즘 유의사항 ]

• 데이터가 어떤 유형이어야 하는지도 제공해야하며, 모든 가능한 상황을 다루어야 한다.
• 연산의 의미와 수행 방법에 의심의 여지가 없을 정도로 상세하고 정확하게 완전히 명시해야 한다.
• 다음에 무엇을 해야 할지 알려주어야 하고, 결국 멈춰야 한다.

→ 즉, 컴퓨터는 바보이므로 하나부터 열까지 실행 단계를 명확하고 상세하게 알려줘야 한다.

 

 

 

 

 

우선 가장 기본적인 알고리즘인 선형 알고리즘을 알아보자.

 

▼ 선형 알고리즘 - 반에서 가장 키 큰 사람 찾기

선형 검색

 

대략적인 순서를 나타내면 아래와 같다

1. 한 명 한 명 차례로 키가 몇인지 묻는다.
2. 지금까지 확인한 사람 중에 가장 키 큰 사람이 누군지 계속 체크한다.

 

하나하나 뜯어서 생각해보자.

1. a의 키를 묻는다.
2. 만약 a에게 처음으로 키를 물어본 것이라면 현재 a가 가장 키 큰 사람이다.
3. b의 키를 묻는다.
4. b의 키가 a보다 더 크다면 이제 b가 가장 키 큰 사람이고, 그렇지 않으면 a가 순위를 유지한다.
5. 세 번째 사람에게도 이어서 질문하고, 일련의 과정을 반복하며 끝까지 도달한다.
6. 모든 학생에게 다 물어 봤다면 가장 키 큰 사람과 그의 키를 알 수 있다.

 

 

만약 다른 조건이 추가된다면?

중복값

위와 같이 두 명 이상의 학생이 키가 값은 상황이 발생하면 어떻게 해야할까

 

먼저 물어본 사람을 기록? 나중에 물어본 사람을 기록? 아니면 모두 기록? 아니면 랜덤?

 

이런 문제를 해결하려면 자료구조(data structure)가 필요하다.

계산 과정에서 필요한 정보를 표현하는 방법으로, 효율적인 알고리즘을 사용할 수 있게 해준다

잘 고른 자료구조 하나 열 부럽지 않다(?)

 

[참고] 자료구조에 대해 간단히 알고 싶다면? 노마드코더 - 개발자라면 무조건 알아야하는 자료구조! 5분컷.

 

 

 

▶ 그렇다면 학생들의 전체 키의 평균을 계산하고 싶다면?

 

1. sum을 0으로 설정한다

2. 각 학생들의 키 값을 sum에 더한다

3. 합계를 학생 수로 나눈다

 

 

이때 학생 수는 어떻게 알 수 있을까

과연 바보 컴퓨터가 알 수 있을까?

→ 합계를 계산하면서 사람 수(항목)의 개수도 세어줘야한다.

 

1. sum을 0으로 설정한다
2. N을 0으로 설정한다
3. 각 키 값마다 아래의 두 단계를 반복한다.
   • sum에 다음 학생의 키 값을 더한다
   • N에 1을 더한다
4. N이 0보다 크면 평균을 'sum / N'으로 설정한다.
5. 그렇지 않으면 주어진 키 값이 없다고 알린다. (아니면 0으로 나눠버리는 사태가 발생할 수 있음)

 

 

위 예제의 경우, 컴퓨터가 작업을 수행하는 데 걸리는 시간(단계의 수)은 데이터의 양에 정비례한다.

 

 

 

→ 일반적으로 선형 알고리즘은 동일한 기본 형태를 갖는다

1. 초기화가 필요하다
2. 각 항목을 차례로 검사하고, 항목에 대해 간단한 계산을 수행한다.
3. 작업을 끝내기 위한 단계가 필요하다 (위 예시의 경우 평균을 계산하는 일)

그러므로 각 항목에 대한 연산 시간이 비슷하다면, 전체 소요 시간은 항목의 수(데이터의 수)에 비례한다.

 

 

 

▼ 알고리즘의 효율성

'알고리즘이 빠른가, 느린가?'

'주어진 양의 데이터를 처리하는 데 시간이 얼마나 걸릴 것으로 예상되는가?'

 

효율적인 알고리즘의 설계, 분석, 구현이 컴퓨터과학에서도 핵심적인 부분이다.

 

 

그렇다면 알고리즘의 효율성을 위해  선형 검색의 시간을 단축할 수 없을까?

 

 

▼ 이진 검색(binary search) 알고리즘

(참고로 이진 검색 알고리즘은 전제 조건이 필요하다. 정렬된 배열이어야 한다.)

 

이진 검색이란 마치 술자리에서 소주 뚜껑에 적힌 생산라인 넘버로 하던 업&다운 게임과 유사하다

성인이라면 알 거라 믿는다.

 

배열의 길이가 작다면 이진 검색 알고리점의 이점이 크지 않지만, 만약 100개의 값을 갖는 배열이라면?

 

예) 1~100 중 77을 찾아라!

• 선형 검색에 필요한 최대 단계 수 : 100단계
• 이진 검색에 필요한 최대 단계 수 : 7단계

· 선형 검색의 경우 1부터 차례대로 찾기 시작할 경우 총 77번의 단계를 수행해야한다.

만약 100번을 찾는 거였다면 무려 100단계까지 걸린다.

 

· 이진 검색의 경우 추측 할 때마다 검색해야 할 셀 중 절반을 제거할 수 있다.

위와 같은 과정으로 아무리 많아도 7단계 내에서 끝난다.

 

 

※ 여기서 배열의 데이터를 두 배로 늘린다면?

 

· 선형 검색은 데이터 수만큼 단계가 필요하므로 배열의 데이터가 두 배로 늘어나면 검색에 필요한 단계 수도 두 배로 늘어난다.

 

· 이진 검색의 경우 100개 → 200개가 되더라도, 첫 단계에서 반으로 줄여버린다. 그러므로 총 데이터가 두 배로 늘어나도 총 단계수는 최대 한 단계만 더 추가된다.

선형 검색과 이진 검색

원소 수(데이터 수)가 늘어날수록 소요되는 단계 수를 그래프로 나타내면 위와 같다.

 

 

→ 데이터를 삽입할 때 순서대로 정렬하여 정렬된 배열을 만들어 놓으면 검색에서 이점을 얻을 수 있다.

물론 정렬된 배열을 사용하면 삽입은 다소 느릴 수 있고, 어떤 구조가 더 좋다고 할 순 없다.

 

이는 무엇을 개발하느냐에 따라 달라진다.

 

소프트웨어에서 삽입이 자주 일어나는가? 아니면 검색이 개발 중인 앱의 중대한 기능인가?

→ 항상 개발을 할 때 어떤 구조가 더 좋은지 분석하고 생각해보자.

 

 

 

 

 

 

 

[참고] 1일 1로그 100일 완성 IT지식

1일 1로그 100일 완성 IT 지식

[참고] 누구나 자료 구조와 알고리즘

누구나 자료 구조와 알고리즘

[참고] 이진 탐색

[참고] 파인만 아저씨에 대한 재미난 루머(?)