(자료구조 강의) Chapter 02 - 자료구조와 알고리즘의 이해

우리가 지난 강의에서 살펴본 탐색 알고리즘에는 여러 가지가 있습니다.

 

또한 사용하는 자료구조에 따라 알고리즘이 달라지기도 합니다.

 

배열도 자료구조 중 하나입니다. 우리는 배열이라는 자료구조를 사용해서 선형 탐색, 이진 탐색 알고리즘을 적용시킨 것이죠.

자료구조는 크게 선형 구조와 비선형 구조로 나눌 수 있습니다.

 

여기서 배열은 리스트에 들어간다고 보시면 됩니다.

리스트는 선형 리스트와 연결 리스트로 나눌 수 있는데 연결 리스트에 대해서는 다음에 자세히 알아보도록 할게요.

 

자료구조가 정확히 뭐지?

보통 첫 프로그래밍 언어로 C언어를 선택했다면 그 다음엔 자료구조를 공부하는 분이 많을 겁니다. 저도 그랬습니다.

 

지난 강의에서도 자료구조 공부의 중요성을 얘기하고 주변에서도 자료구조를 꼭 배워야 한다고 합니다.

 

그래서 그 '자료구조'라는 녀석은 대체 뭐길래 주변에서 다들 공부를 하라고 할까요?

일상에서 예시를 찾아보겠습니다.

우리가 방을 정리하려는데 왼쪽 처럼 물건들을 한 상자에 넣어버리면 어떤 물건이 들어 있는지도 모르고 찾기도 어려울 겁니다.

 

하지만 일정한 기준으로 분류해서 오른쪽과 같이 정리해서 담아놓으면 찾기 쉽습니다.

 

이런식으로 '데이터'를 어떠한 기준으로 어떻게 분류하는지에 대해 다루는 과목이 바로 자료구조입니다.

 

선형 탐색 알고리즘

위와 같은 10칸 짜리 배열에 숫자를 정리하지 않고 집어 넣었습니다.

 

여기서 30이라는 숫자를 찾으려면 어떤 방법이 있을까요?

 

처음부터 하나씩 비교해보면 됩니다. 여기서 쓰이는 알고리즘이 바로 선형 탐색 알고리즘입니다.

 

지난 강의에서는 성능 비교가 목적이었기 때문에 편의상 C++를 사용했지만 앞으로 자료구조와 알고리즘 구현은 C로 진행하겠습니다.

 

선형 탐색 알고리즘 코드

#include <stdio.h>

int linear_search(int arr[], int len, int target)
{
    for(int i = 0; i < len; i++)
    {
        if(arr[i] == target)
            return i;
    }

    return -1;
}

int main(void)
{
    int arr[10] = { 20, 40, 10, 50, 90, 60, 70, 80, 100, 30 };
    int idx;

    idx=linear_search(arr, 10, 30);

    if(idx == -1)
        printf("탐색 실패 \n");
    else
        printf("탐색 데이터 위치: %d \n", idx);

    return 0;
}

실행 결과

탐색 데이터 위치: 9

자료구조를 공부하고 있다면 기본적인 C언어 문법은 익힌 상태일테니 어려움 없이 해석 가능한 코드일 것입니다.

 

이진 탐색 알고리즘

이진 탐색 알고리즘은 배열의 데이터가 오름차순 혹은 내림차순으로 정렬되어 있어야 사용 가능한 알고리즘입니다.

 

오름차순은

1, 2, 3 과 같이 숫자가 증가하는 형태

 

내림차순은

3, 2, 1 과 같이 숫자가 감소하는 형태를 의미합니다.

 

 

아까 사용한 배열을 정렬해왔습니다. 정렬을 다루는 알고리즘도 여러 가지가 있지만 나중에 자세히 알아보겠습니다.

 

나름의 규칙이 생겼기 때문에 선형 탐색보다 더 효율적으로 찾을 수 있을 것 같습니다.

그 효율적인 방법으로 90이라는 숫자를 찾아보겠습니다.

 

이진 탐색 알고리즘은 다음과 같은 순서로 동작 합니다.

 

1. 탐색 범위의 (첫 번째 인덱스 + 마지막 인덱스) / 2 로 중앙값을 찾는다.
2. 찾고자 하는 데이터가 중앙값 보다 크다면 탐색 범위를 중앙값 + 1번째 부터 마지막으로, 만약 중앙값 보다 작다면 첫 번째 부터 중앙값 - 1번째로 범위를 줄인다.
3. 데이터를 찾을 때까지 반복한다.

 

1. 탐색 범위의 (첫 번째 인덱스 + 마지막 인덱스) / 2 로 중앙값을 찾는다.

 

2. 중앙값과 비교해 탐색 범위를 줄인다.

 

 

3. 타겟을 찾을 때까지 반복한다.

 

 

위 그림을 그대로 옮겨 놓은 소스코드를 첨부하고 마치겠습니다.

 

이진 탐색 알고리즘 코드

#include <stdio.h>

int binary_search(int arr[], int len, int target)
{
    int first = 0;   // 배열 시작 인덱스 값
    int last = len - 1;   // 배열 마지막 인덱스 값
    int mid; 

    while(first <= last)
    {
        mid = (first + last) / 2;   // 중앙값 인덱스 구하기

        if(target == arr[mid])   // 타겟을 찾았다면
        {
            return mid;
        }
        else    // 타겟이 아니라면 
        {
            if(target < arr[mid])   
                last = mid - 1;   // 탐색 범위 중앙값 왼쪽
            else
                first = mid + 1;   // 탐색 범위 중앙값 오른쪽
        }
    }

    return -1;   // 찾지 못했을 때 -1 반환
} 

int main(void)
{
    int arr[10] = { 10, 20, 30, 40, 50, 60, 70, 80, 90, 100 };
    int idx;

    idx = binary_search(arr, 10, 90);

    if(idx==-1)
        printf("탐색 실패 \n");
    else
        printf("탐색 데이터 위치: %d \n", idx);

    return 0;
}

실행 결과

탐색 데이터 위치: 9