해시 알고리즘(Hash Algorithm)과 시간 복잡도(Time Complexity)

기초 알고리즘: 해시 알고리즘

해시 알고리즘은 기초 알고리즘 중 하나지만, 다른 알고리즘과는 달리 효율성을 극대화하는 데 중점을 둡니다. 특히 해시 알고리즘을 사용하면 데이터 검색 속도를 크게 향상시킬 수 있습니다. 대표적인 예로 백준의 "수 찾기" 문제를 살펴보겠습니다.

[1,4,5,2,3]

위와 같은 배열이 주어진 상태에서

[1,4,3,7,9]

위의 5개 요소가 첫번째 배열 요소에 포함되어있는지 검사하는 문제입니다.

 

단순히 생각할 때 for문을 2개 써서 각각의 요소를 모두 검사를 하면 되는데, 그렇게 되면 5x5 = 25번을 검색하는 비효율적임이 발생합니다.

 

시간 복잡도(Time Complexity)

1. O(1) - 1등

int[] array = {1, 2, 3, 4, 5};
int element = array[2]; // O(1) - 항상 같은 시간에 수행됨

알고리즘의 실행 시간이 입력 데이터의 크기에 관계없이 일정합니다.

 

2. O(log n) - 2등

이진 탐색, 이분 탐색이 대표적이며 업다운 게임을 예시로 들면 된다.

for (int i = 1; i < n; i = i * 2){
    System.out.println(i);
}

n이 8인 경우 for문은 3번만 돌게 되어 O(n)보다는 빠르다.

https://school.programmers.co.kr/learn/courses/30/lessons/43238

프로그래머스

3. O(n) - 3등

for (int i = 1; i < n; i = i++){
    System.out.println(i);
}

n의 데이터가 늘어날수록 처리 시간이 늘어나는 알고리즘이고 대표적으로 단순 for 반복문이다.

4. O(n^2) - 4등

for (int i = 1; i <= n; i++) {
    for(int j = 1; j <= n; j++) {
        System.out.println(i + " and " + j);
    }
}

이중 포문을 사용하는 경우고 4등부터는 효율이 점점 최악으로 치닫게 된다.

5. O(2^n) - 5등

최악의 알고리즘이고 피보나치 함수와 완전 탐색(Brute-Force : 무식하게 풀기)이 대표적이다. 완전 탐색은 모든 경우의 수를 다 찾아야 할 때 쓰는 알고리즘이다.

for (int i = 1; i <= Math.pow(2, n); i++){
    System.out.println("Hey - I'm busy looking at: " + i);
}

n값에 따라 무수하게 많이 돌아야 하는 예시 for문이다.

 

수 찾기에 대한 접근 방법과 그에 따른 시간 복잡도

[1,4,5,2,3]

[1,4,3,7,9]

O(n^2)

 

시간 복잡도를 봤으니 다시 문제로 넘어가자.

처음 아이디어인 이중 포문을 사용한다면 해당 알고리즘은 빅오 표기법 O(n^2) 4등에 해당하고 효율이 떨어진다는 걸 알 수 있다.

 

O(log n)

 

그다음으로 좋은 알고리즘은 이분 탐색이다. 이분 탐색을 사용하려면 위의 배열을 정렬을 해서 가운데 요소부터 찾아 나가야 한다는 것이다.(업다운 게임처럼)

 

아래는 이분 탐색 알고리즘을 짜기 위한 아이디어이고 필요하지 않으면 안 봐도 된다.

예시를 좀 더 확장해서 A[3,6,8,2,4,9,1,2,0,5,10]라는 10개 요소가 들어있는 배열이 있다고 가정하자.

일단 첫 번째는 배열을 정렬을 해야 한다. 그럼 가운데 값은 5가 들어갈 것이다.

만약에 찾아야 되는 요소가 8이라면 5 <8이므로 A[6~10]까지 다시 범위를 잡고 또 가운데부터 찾아가는 과정을 알고리즘으로 짜면 된다.

 

O(1)

 

가장 좋은 알고리즘은 해시 알고리즘을 이용하는 것이다. HashMap은 기본적으로 키와 쌍으로 이루어져 있어서 getKey를 통해 접근하면 전체를 뒤지지 않아도 1개의 데이터만 찾기 때문에 시간 복잡도가 O(1)로 가장 빠르다.

 

HashSet에 [1,4,5,2,3] 데이터를 넣고 contains를 통해 데이터를 찾으면 전체를 반복할 필요 없이 바로 해당 위치를 찾아서 O(1)이다.

HashSet은 키가 없어 보이지만 내부적으로 키가 index형식으로 할당되기 때문에 HashMap처럼 키를 이용해 찾는 것처럼 찾게 된다.

 

하지만 List 자료구조 형을 이용한다면 contains를 이용한다고 해도 전체를 다 검색하기 때문에 O(n)이다.

public class Solution {
    public boolean containsDuplicate(int[] nums) {
        Set<Integer> seen = new HashSet<>();
        for (int num : nums) {
            if (seen.contains(num)) {
                return true;
            }
            seen.add(num);
        }
        return false;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();

        // 테스트 케이스
        int[] nums1 = {1, 2, 3, 4, 5}; // 중복 없음
        int[] nums2 = {1, 2, 3, 2, 5}; // 중복 있음

        System.out.println(solution.containsDuplicate(nums1)); // 출력: false
        System.out.println(solution.containsDuplicate(nums2)); // 출력: true
    }
}

 

정리

수 찾기는 위의 배열 5개 요소를 예시로 들자면

 

O(n^2)를 이용한다면 요소 하나를 찾기 위해서 최악의 경우 5회 탐색하게 된다.

O(log n)를 대표하는 이분 탐색을 이용하면 최악이더라도 3회 탐색하게 된다.

O(1)를 이용하면 최악이더라도 1회 탐색하게 된다.