자료구조 기초

선형 탐색

선형 탐색(Linear Search)이란 int[] arr = {1, 2, 5, 4, 8, 10, 9, 3, 6, 7} 라는 배열이 있을 때, 왼쪽에서 오른쪽으로 한 번에 한 셀씩 확인하는 방법을 말합니다.
선형 탐색은 arr의 길이가 총 10 이므로 최악의 경우에는 총10번을 확인해야 결과를 얻을 수 있습니다.

다음은 선형 탐색의 코드입니다.

public class Main {
    public static void main(String[] args) {
        int[] arr = {1, 2, 5, 4, 8, 10, 9, 3, 6, 7};
        int num = 5;
        System.out.println("횟수: " + Linear.linearSearch(arr, num));
    }
}

class Linear {
    public static int linearSearch(int[] arr, int num) {
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == num) {
                return i;
            }
        }
        return -1; // 일치하는 값이 없음
    }
}

그리고 선형 탐색보다 훨씬 빠른 것이 있는데, 이진 탐색(Binary Search)입니다.

이진 탐색

이진탐색은 선형탐색보다 훨씬 빠르지만 조건이 있습니다. 배열이 있을 때 반드시 정렬이 되어있어야 합니다. 탐색은 어렵지 않습니다. 만약 7이라는 숫자를 찾으라고 합니다.
int[] arr = {1, 2, 3, 4, 5, 6, 7, 8, 9} 라는 배열이 있을 때, 가운데 숫자(5)를 정한 후에 찾으려는 숫자(7)이 더 크므로 범위를 {6, 7, 8, 9} 로 좁힙니다. 그리고 다시 가운데 숫자를 정한다음 반복하면 됩니다.

이진 탐색의 코드는 다음과 같습니다.

public class Main {
    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4, 5, 6, 7, 8, 9};
        int num = 6;
        System.out.println("횟수: " + Binary.binarySearch(arr, num));
    }
}

class Binary {
    public static int binarySearch(int[] arr, int num) {
        int mid;
        int left = 0;
        int right = arr.length - 1;
        int count = 0;

        while (left <= right) {
            mid = (right + left) / 2;

            if (num == arr[mid]) {
                count++;
                return count;
            }
            if (num < arr[mid]) {
                right = mid - 1;
                count++;
            } else {
                left = mid + 1;
                count++;
            }
        }
        return 0;
    }
}

선형 탐색과 이진 탐색의 속도 차이는 배열의 길이가 10, 100 작을 때는 이진 탐색이 조금 빠르지만, 배열의 길이가 무수히 많을 때 예를 들어 데이터가 10,000,000 천만개 있을 때는 이진 탬색이 훨씬 빠릅니다.

---

내용을 정리하면서 알고리즘 파트와 자료구조 파트에서 비슷하게 다루는 내용들이 많아서 더 많은 알고리즘 코드들은 모두 알고리즘 카테고리에서 정리할 예정입니다.
이 파트에서는 기본적인 개념부분만 다루겠습니다^^

지금까지 선형 탐색과 이진 탐색의 속도 차이를 알아보았습니다.
이진 탐색이 훨씬 빨랐고, 이진 탐색보다 빠르 것이 있을까요? (있습니다ㅎㅎ)
그것은 단 한번에 찾을 수 있는 해시 테이블 입니다.

해시 테이블

해시 테이블(Hash Table)은 쌍으로 이뤄진 값들의 리스트입니다. menu = {"kimchi" : 500, "bulgogi" : 5000} 같은 메뉴가 있습니다. 여기서 첫 번째 항목인 kimchi나 bulgogi 는 키(Key) 라 부르고, 두 번째 항목인 500, 5000(단위는 원 입니다.)은 값(Value)이라 부릅니다. 이러한 형태를 딕셔너리(Dictionary)라고 하는데 파이썬 다루시는 분들은 익숙하실 것 같습니다.
해시 테이블이 어떻게 바로 한번에 찾을 수 있을까??
그것은 바로 키(Key)를 조회하기 때문에 바로 알 수 있습니다. 우리가 원하는 값(Value)을 찾기 위해 일일이 탐색안해도 이 키만 알면 바로 조회가 가능합니다.

지금 보면 키값은 문자열 "" 로 되었습니다. 그럼 이 문자열만 보고 찾을 수 있다는 것인가??
사실 이 문자열을 보고 판단하는 것이 아니라 문자열인 키값을 해시함수(Hash function)를 통해 해시(Hash)로 변환 되며, 이 해시는 값(Value)과 매칭되어 저장소에 저장이 됩니다.

천천히 봅시다.
컴퓨터는 0과 1로 이루어져 있고, 연산 또한 이 0과 1로만 가능합니다. 따라서 컴퓨터 문자열을 보고 바로 알 수가 없습니다. 이를 연산 가능한 숫자 형태로 변환해주어야 하는데 이렇게 문자열을 숫자로 변환하는 데 사용한 코드를 해시함수 라고 이해하시면 됩니다.

해시 같은 경우는 그냥 주소라고 생각하시면 편하실 것 같습니다. 고유한 번호입니다.
그리고, 문자열을 숫자로 변환하는 과정을 해싱(Hashing) 입니다.

하지만 이러한 해시 테이블의 강점에도 단점은 있습니다.
하나의 값(Value)에 두 개의 키(Key)가 접근하는 것입니다. 그럼 그 값에 대한 고유한 번호를 지정할 수가 없습니다. 서로 겹치게 되는 해시충돌(Hash Collision)이 발생합니다.

좋은 해시 테이블이란 많은 메모리를 낭비하지 않으면서 균형을 유지하며 충돌을 피하는 것입니다.
이러한 단점을 보완한 방법이 있습니다.

• 체이닝(Chaining)
  저장소에 연결리스트(Linked List)를 할당하여, 다음에 저장된 자료를 기존의 자료 다음에 위치시키는 것입니다. 이러면 메모리의 낭비를 줄일 수 있습니다.
• 개방 주소법(Open Addressing)
  개방 주소법은 데이터의 해시가 변경되지 않았던 체이닝과는 달리 비어있는 해시를 찾아 데이터를 저장하는 기법입니다. 따라서 개방 주소법의 해시테이블은 1개의 해시와 1개의 값(value)이 매칭되어 있는 형태로 유지됩니다. 이러면 다른 저장공간 없이 해시테이블 내에서 데이터 저장이 가능합니다.

배열과 연결리스트

두 자료구조는 다르기때문에 어떤 알고리즘에 적용해야 적당한지는 직접 판단을 해야합니다.
그러기 위한 개념을 정리해보았습니다.

1. 배열

배열의 크기는 처음에 결정하고, 결정되면 변경을 할 수 없습니다. 따라서 중간 삽입하거나 삭제할 때는 연산 횟수가 많아져 속도가 지연됩니다. 다만 검색은 빠릅니다. 배열에는 인덱스 를 가지고 있어서 이 인덱스로 접근을 하게되면 굉장히 빠릅니다.

2. 연결리스트

배열은 처음부터 크기를 결정해야 하고 메모리를 순차적으로 할당해야 했습니다. 예를 들어 영화관에 갔는데 친구들끼리 가서 예매하려는 순간 자리가 다 띄엄띄엄 되어있다면 배열의 경우에는 영화를 볼 수 없습니다. (영화는 붙어서 봐야하는데..)
만약 영화를 무조건 봐야한다는 조건이 있다면 연결리스트를 사용하면 됩니다.
연결리스트는 메모리를 순차적으로 할당할 필요없이 자리가 남는데로 배정받으면 됩니다. 이렇게 할 수 있는 이유는 각 셀마다 서로 연결이 되어 있기 때문에 누가 누군지 알 수가 있습니다.
이러면 삽입, 삭제가 원활히 할 수 있겠죠.
다만 검색은 느립니다. 왜냐하면 인덱스를 알지못하기 때문에 데이터에 접근하기 위해서는 각각의 연결되어 있는 위치들을 따라 접근해야 합니다. 따라서 검색/조회에는 속도가 느린편입니다.

재귀 함수

마지막으로 재귀 함수에 대해 알아보고 내용 정리를 마치겠습니다.
재귀 함수(recursive function)란 어떤 함수에서 자신을 다시 호출하여 작업을 수행하는 방식을 말합니다.
즉, a() 라는 함수안에 a() 함수를 호출하여 작업하는 것을 말합니다. (어렵지 않습니다__)

재귀 함수의 대표적인 예인 팩토리얼 코드를 보면 이해해봅시다.

public class Main {
    public static void main(String[] args) {
        int num = 5;
        System.out.println("결과: " + Factorial.factorialFunc(num));
    }
}

class Factorial {
    public static int factorialFunc(int num) {
        if (num <= 1)
            return num;
        else
            return factorialFunc(num-1) * num;
    }
}

코드를 보시면 factorialFunc() 함수안에 자신의 함수 factorialFunc()를 또 호출하여 사용했습니다. 이러면 이러면 결국 Loop 반복이 됩니다. 계속 자신의 함수를 호출하게 됩니다.
반복이 되기 때문에 재귀함수는 위의 코드처럼 if()문 처럼 조건을 달아줘야 빠져나올 수 있습니다. 조건을 달아두지 않으면 stackoverflow 에러가 발생합니다.
재귀 함수는 이게 답니다.

그러면 "반복문을 사용하면 되지 않느냐, 왜 재귀함수를 굳이 써야하나"
할 수 있습니다.

*Loops may achieve a performance gain for your program. Recursion may achieve a performance gain for your programmer
출처 : https://stackoverflow.com/questions/72209/recursion-or-iteration

이것으로 자료 구조 기초를 마치겠습니다.
이외에도 사실 힙, 스택, 퀵 등등 많지만 이 부분들은 알고리즘 카테고리에서 다루도록 하겠습니다.
정리한 내용은 제이 웬그로우 저자, 심지현 옮김, 누구나 자료구조와 알고리즘 이라는 책을 바탕으로 정리하였으며, 구글 검색을 통해서도 자료를 참고하였습니다.
감사합니다. (__)