[정보 처리] 8. 탐색 알고리즘 이론
- 이번 포스팅에서는 탐색 알고리즘에 대한 이론을 정리하겠습니다.
탐색 알고리즘의 실제 구현은 하지 않습니다.
[탐색의 개념]
- 탐색이란, 많은 양의 데이터에서 원하는 데이터를 찾아내는 작업입니다.
- 탐색에 이용되는 기억장치의 종류에 따라 아래와 같은 분류가 있습니다.
1. 내부 탐색 : 주기억 장치에서 데이터를 빠르게 탐색합니다.
2. 외부 탐색 : 보조기억 장치에서 데이터를 탐색합니다. 속도가 느릴 수 밖에 없습니다.
(복잡도)
- 탐색의 성능을 나타내는 성능지표로 복잡도라는 개념이 있습니다.
복잡도는 두가지 종류가 있으며, 아래와 같습니다.
1. 공간 복잡도
알고리즘이 연산을 수행하는 동안 사용되는 메모리 공간의 크기를 나타냅니다.
일반적인 경우 공간 복잡도가 알고리즘의 품질에 영향을 미치는 비중은 시간 복잡도에 비해 현저히 낮은 편인데,
극단적인 예시를 들자면, 검색 엔진에서 검색 속도를 높이고자 주메모리에 모든 데이터를 올려놓고 사용하거나,
빅데이터나 딥러닝 LLM 모델을 사용할 경우엔 주의해야 합니다.
2. 시간 복잡도
알고리즘의 연산 수행 횟수를 나타냅니다.
연산 횟수를 기준으로 한 이유는,
하드웨어 및 운영 시스템 환경에 따라 실행 시간이 달라지므로, 알고리즘의 품질을 나타낼 때에는 연산의 횟수가 보다 합리적인 기준이 되기 때문입니다.
(Big O 표기법)
- 시간 복잡도를 나타낼 수 있는 알고리즘 성능 지표 표현 방식입니다.
처리 데이터 개수가 많아질 때 알고리즘의 시간 복잡도가 어떻게 증가하는지를 표현하는 방법으로,
컴퓨터는 입력 데이터가 많아질수록 처리 시간이 오래 걸리기 때문에,
어떤 알고리즘이 데이터가 커졌을 때 얼마나 효율적인지를 비교하기 위해 사용됩니다.
- 처리 데이터량의 증가에 따른 연산량의 증가폭을 빅오 표기법으로 표기할 때는,
큰 단위만을 표기합니다.
예를들어,
입력 데이터 수의 증가에 따라 N + 1 만큼 연산량이 증가한다 할 때는 그냥 N 이라고 표기하고,
N^2 + N 만큼 증가하면, 그냥 N^2 으로 표기하는 것입니다.
이유는, 단위가 달라지면 작은 단위의 수치가 증가폭에 끼치는 영향이 의미가 없을만큼 작아진다고 판단하기 때문에,
가독성 있는 간단한 표기와 더불어 알고리즘을 동일한 빅오 그룹으로 묶기 위해서입니다.
- 빅오 표기법의 대표적 유형은 아래와 같습니다.
1. O(1)
입력 데이터 수와 관계 없이 일정한 수행 횟수를 가지는 시간 복잡도입니다.
여기선 1을 적었으므로 1이고, 2를 적거나 100 을 적으면 그 숫자만큼 고정된 연산 횟수가 실행되는 것입니다.
입력 데이터가 얼마가 되었건 고정 연산 횟수를 수행하므로 가장 빠른 알고리즘을 뜻합니다.
2. O(logN)
입력 데이터 수에 따라 연산 횟수 증가폭이 점차 줄어드는 시간 복잡도입니다.
말 그대로 처리하면 처리할수록 효율이 높아지는 경우로,
고정값 빅오를 제외하고 가장 좋은 성능의 알고리즘으로 볼 수 있습니다.
이분 탐색, 이진 트리 탐색의 시간 복잡도입니다.
3. O(N)
입력 데이터 수에 따라 연산 횟수가 일정하게 증가하는 정직한 시간 복잡도입니다.
수열 계산, 순차 탐색 등의 시간 복잡도입니다.
4. O(NlogN)
입력 데이터의 수가 늘어날수록 연산 횟수는 늘어나지만 원만하게 증가하기에 현실적이면서 용납될 수준의 시간 복잡도입니다.
퀵 정렬, 힙 정렬, 병합 정렬 등의 시간 복잡도입니다.
5. O(N^2)
입력 데이터의 수에 따라 연산 횟수가 데이터 수의 제곱만큼 증가하는 시간 복잡도입니다.
연산 횟수 증가폭이 크기 때문에 비효율적입니다.
버블 정렬, 선택 정렬 등의 시간 복잡도입니다.
6. O(2^N)
입력 데이터 수에 따라 연산 횟수가 데이터 수의 지수승만큰 증가하는 시간 복잡도입니다.
피보나치 수열 등의 연산을 재귀 호출을 통해 연산하는 경우가 대표적이며, N^2 보다도 나쁜 시간 복잡도입니다.
7. O(N!)
입력 데이터 수가 커질수록 연산 횟수가 굉장히 늘어나는 시간 복잡도입니다.
빅오 유형중 최악이라 할 수 있습니다.
- 참고 : 빅오 표기법 그래프 그리기 코드(Python)
import matplotlib.pyplot as plt
import numpy as np
# 입력 크기 n (1~30)
n = np.arange(1, 31)
# 각각의 시간 복잡도 계산
O_1 = np.ones_like(n)
O_logN = np.log2(n)
O_N = n
O_NlogN = n * np.log2(n)
O_N2 = n ** 2
O_2N = 2 ** n
# 그래프 그리기
plt.figure(figsize=(12, 8))
plt.plot(n, O_1, label="O(1)")
plt.plot(n, O_logN, label="O(log N)")
plt.plot(n, O_N, label="O(N)")
plt.plot(n, O_NlogN, label="O(N log N)")
plt.plot(n, O_N2, label="O(N^2)")
plt.plot(n, O_2N, label="O(2^N)")
# 그래프 설정
plt.ylim(0, 1000) # 너무 커지는 O(2^N)을 제한해서 보기 좋게
plt.title("Big-O Time Complexity Graphs")
plt.xlabel("Input Size N")
plt.ylabel("Operations Count")
plt.legend()
plt.grid(True)
plt.tight_layout()
# 그래프 출력
plt.show()
[탐색의 종류]
(선행 탐색)
- 대상 데이터를 처음부터 순차적으로 비교하며 탐색하는 방법입니다.
하나하나 데이터를 전부 탐색하기 때문에 데이터 개수나 정렬 여부를 알지 못해도 사용이 가능하며 단순하고 간단해서 어느 상황에서도 적용 가능하지만,
성능이 좋지 않으므로 데이터 수가 적을 때 활용할 수 있습니다.
시간 복잡도는 최악의 경우를 산출하므로 O(N)이며,
정답을 찾아낼 수 있는 평균 비교 횟수는,
sum(1..N)/N = (N(N+1)/2)/N = (N+1)/2
입니다.
수식을 설명하자면,
탐색 횟수는 정답이 위치한 개수만큼 진행되므로, 처음에는 1, 두번째는 2,... 이렇게 늘어납니다.
고로 N 번째에는 N번을 탐색하므로, 최대 N 번 탐색할 때의 평균 탐색 개수는, 1+2+...+N 까지 더한 값에 N 을 나누는 것이고,
N까지 더한 값을 구하는 sum 공식은 가우스 방식으로 (N+1) / 2 이므로, 수식을 정리하면 위와 같이 되는 것입니다.
(이분 탐색, 이진 탐색)
- 정렬된 대상 데이터를 절반씩 나누는 방식으로 탐색하는 방법입니다.
1. 데이터가 정렬된 상태에서 먼저 중간 데이터와 비교
2. 비교 결과 배열 데이터가 더 크다면 정답은 배열의 좌측에 있는 것이니 배열의 좌측을 떼어내어 중간 데이터와 비교,
배열 데이터가 더 작다면 정답은 배열의 우측에 있는 것이니 배열의 우측을 떼어내어 중간 데이터와 비교
3. 위와 같은 작업을 반복해서, 정답을 발견하거나, 혹은 정답이 없어서 더이상 배열이 나뉘지 않을 때 까지 반복
위와 같은 프로세스의 알고리즘으로,
보다시피 절반씩 탐색 범위를 줄여나가는 방식으로 진행하기에 시간 복잡도는 O(logN)으로, 선행 탐색보다 성능이 좋습니다.
이 알고리즘을 적용하기 위해선 선행 조건이 필요한데,
반드시 데이터가 정렬되어 있어야 합니다.
정렬 되어있지 않은 데이터는 추가적으로 정렬 작업을 수행해야합니다.
(블록 탐색)
- 대량의 데이터를 그룹별로 블록화하여 인덱싱을 통해 탐색하는 방법입니다.
정렬이 되어 있어야 할 필요는 없지만, 아래와 같이 블록 테이블을 만들어야 합니다.
1. N 개의 데이터를 가진 배열을 sqrt(N) 개의 단위로 나눕니다.
2. 블록별 가장 큰 값을 찾아내 이를 모아서 색인 테이블을 만듭니다.
이처럼 탐색 시점에 사용할 블록 테이블을 만들어야 합니다.
전체 정렬이 아니라 최대값만 바뀌는 것이므로 배열 수정시 성능이 나쁘지 않습니다.
그리고 탐색 알고리즘은 아래와 같습니다.
1. 찾아내야하는 값을 블록별 가장 큰 값과 비교합니다.
각 블록의 값은 블록별 가장 큰 값보다 작으므로, 찾으려는 값이 블록의 가장 큰 값보다 크다면 해당 블록은 대상에서 제외됩니다.
2. 후보 블록에서 순차탐색을 진행합니다.
성능은 O(sqlt(N)) 으로, 이진탐색에 비해 느리지만, 정렬하기 어려운 환경에서 사용할 수 있습니다.
(보간 탐색)
- 찾을 값의 위치값을 예상하여 검색하는 사전식 탐색 방법입니다.
이진 탐색처럼 정렬된 배열에서 값을 찾는 것인데,
딱 중간을 찾는 것이 아니라 있을 만한 곳을 예측해서 찾는, 보다 스마트한 알고리즘입니다.
- 이진 탐색에서 중간값이 예측값으로 대체된 개념입니다.
고로 예측이 가능한 환경이어야 하므로 배열의 정렬은 필수이며,
'예측이 가능한 환경' 즉, 값의 분포가 균등 분포가 되어있을수록 효과적입니다.
균등 분포 상황에서 성능이 O(log(logN)) 으로 이진 탐색보다 좋을 수 있습니다.
- 예측 위치의 계산 공식은,
int pos = low + ((double)(key - arr[low]) * (high - low)) / (arr[high] - arr[low]);
입니다.
위는 선형 보간법의 수식을 c언어로 나타낸 것으로,
(key - arr[low]) / (arr[high] - arr[low])
이 부분은,
값이 arr[low] ~ arr[high] 의 범위에 있을 때,
key 가 이 범위 중 어느 위치쯤 있을지를 비율로 계산한 것입니다.
예를들어 arr[low] = 10, arr[high] = 100, key = 70 이라면,
(70 - 10) / (100 - 10) = 0.666
입니다.
값의 비율을 알아냈으므로 이를 위치값으로 투영하면 되는데,
위치는 high - low 이므로, 이를 곱한 개념인 것입니다.
이외에는 이진 탐색과 동일합니다.
(이진 트리 탐색)
- 검색 대상 데이터를 이진 트리로 변형한 뒤에 탐색하는 방법입니다.
이진 탐색이 정렬된 배열에서 탐색하는 것이라면,
이진 트리 탐색은, 정렬된 이진 트리 구조에서 탐색하는 것입니다.
탐색시에는 트리 구조에 따라 작은 값은 왼쪽, 큰 값은 오른쪽으로 간선을 타고가기만 하면 되므로 간편하고 O(logN)으로 빠릅니다.
- 값을 입력시 이진 트리에 입력하는 규칙은,
처음 입력된 값을 루트 노드로 두고,
새로 데이터가 들어오면 루트노드에서부터 작은 값은 왼쪽, 큰 값은 오른쪽으로 타고가며 단말 노드 부분에서 데이터가 작으면 좌측, 크면 우측에 데이터를 삽입하면 됩니다.
(해시(Hash) 탐색)
- 해시 탐색은,
데이터 입력 시점에 입력 데이터를 특정한 방법으로 변환시킨 후, 그 값을 탐색시 사용할 key 로 하여 데이터를 저장하는 해시 테이블을 두고,
데이터 탐색 시엔 입력 시점에 key 를 변화시킨 방식 그대로 데이터를 변환시켜, 이 값을 기준으로 key 에서 데이터를 가져오는 방식입니다.
- 해싱 함수에 관련된 용어는 아래와 같습니다.
1. Home Address : 해시 테이블의 해싱 값(양의 정수이며, 인덱스와 동일한 역할)
2. Key : 데이터 레코드 중 해싱 함수의 입력값이 되는 데이터이자 탐색 기준이 되는 데이터(입력시점엔 이것이 해싱되어 홈 주소가 되고, 탐색 시점엔 이것을 해싱하여 홈 주소에 찾아갑니다.)
3. Slot : 하나의 데이터를 저장할 수 있는 공간(fruit, color, owner 라는 정보를 한꺼번에 입력한다면, fruit, color, owner 각각의 데이터를 슬롯이라 함)
4. Bucket : Slot 의 묶음
5. 해시 테이블 : 다수의 홈 주소와 그에 연결된 데이터들로 이루어진 테이블.
- 해시 탐색 프로세스를 예를 들어 설명하겠습니다.
만약 우리가 {fruit : apple, color : red, owner : me} 이런 버킷 데이터를 저장한다고 합시다.
이 중 fruit 슬롯을 해싱하여 Key 로서 홈 주소에 저장한다고 가정하고,
해시 함수는 입력값의 첫 번째 문자의 아스키 코드 값을 10으로 나눈 나머지로 계산된다고 가정하겠습니다.
apple의 첫 번째 문자인 'a'의 아스키 코드 값은 97입니다.
97 % 10 = 7이므로, apple은 해시 테이블의 7번이라는 홈 주소에 저장됩니다.
이러한 해시 테이블이 있을 때,
다음에 apple 이라는 데이터로 검색을 한다고 하면,
위와 같은 해시 함수를 적용해 7을 얻게 되고, 해시 테이블에서 인덱스 7에 바로 접근해 저장된 데이터를 가져오면 끝입니다.
- 보다시피 O(1) 로 매우 빠른 성능을 가지지만,
해싱을 어떻게 할지를 결정하는 해싱 함수를 잘 선택해야 합니다.
서로 다른 데이터를 입력했지만 우연이라도 같은 해시값이 나타나는 중복 문제가 일어날 수도 있습니다.(apple 과 apricot 은 다른 단어지만 위 예시의 해싱 함수로 계산하면 둘다 7 이 됩니다.)
- 서로 다른 슬롯이 같은 키를 가지는 현상을 충돌이라 부릅니다.
이를 해결하기 위해서는 Chaining이란 방법을 사용할 수 있습니다.
홈 주소에 연결된 데이터를 애초에 리스트 형태로 저장하여, 입력 시점 충돌이 일어나면 리스트에 값을 추가하고,
탐색 시점 키가 겹치면 홈 주소의 리스트 형태 데이터를 순회하는 방식으로 데이터를 조회하는 것입니다.
충돌을 해결하는 다른 방식으로는 Probing 이라는 방법이 있는데,
이는 Open Addressing 이라고도 부르며, 충돌이 발생할 때 다른 빈 슬롯을 찾아서 데이터를 저장하는 방식입니다.
충돌 후 프로빙시에 대한 처리가 복잡하고 개발자 친화적이지 않기에 여기서 설명은 생략합니다.
- 해시 함수의 종류
해시 탐색에 사용되는 해시 함수는 충돌을 최소화하고, 복잡하지 않고, 빠른 계산 속도가 요구됩니다.
일반적으로 사용되는 해시 함수는 아래와 같은 종류가 있습니다.
1. 제산법(Division) :
원리: 주어진 키를 특정 값(주로 소수)으로 나눈 후 나머지 값을 해시 값으로 사용합니다. 이 방법은 간단하고 계산이 빠르지만, 특정 키들의 분포에 따라 충돌이 일어날 수 있습니다.
식: hash(K) = K % p 여기서 p는 소수입니다.
장점: 계산이 간단하고 빠르다.
단점: 나누는 값 p가 잘못 선택되면 충돌이 자주 발생할 수 있습니다. 예를 들어, p가 키 값들과 관련이 있으면 충돌이 자주 발생할 수 있습니다.
2. 폴딩법(Folding) :
원리: 키를 여러 개의 부분으로 나눈 후, 각 부분의 숫자나 비트 값을 더하거나 XOR 연산을 하여 해시 값을 생성합니다. 주로 키 길이가 길거나 숫자 범위가 클 때 유용합니다.
식: hash(K) = (부분1 + 부분2 + ... + 부분n) % M 또는 hash(K) = 부분1 XOR 부분2 XOR ... XOR 부분n
장점: 긴 키를 잘 처리할 수 있습니다. 연산도 단순하고 빠릅니다.
단점: 키의 분포에 따라 연산 결과가 고르게 나누어지지 않으면 충돌이 발생할 수 있습니다.
3. 제곱법(Square) :
원리: 키를 제곱한 후, 그 제곱의 일부분을 해시 값으로 사용하는 방법입니다. 제곱은 숫자의 특성상 충돌을 방지할 수 있는 특성이 있지만, 선택할 부분이 중요합니다.
식: hash(K) = 부분(K^2) 여기서 K는 키 값이고, K의 제곱에서 원하는 부분을 추출하여 해시 값으로 사용합니다.
장점: 숫자의 특성을 활용해 키의 패턴을 고려하여 해시 값을 생성할 수 있습니다.
단점: 제곱 연산이 필요한 만큼 계산에 시간이 소요될 수 있으며, 키 분포에 따라 충돌이 발생할 수 있습니다.
4. 숫자분석법(Digit Analysis) :
원리: 키를 숫자 분포를 기반으로 분석하여 해시 값을 결정하는 방법입니다. 예를 들어, 키의 각 자리수를 분석하여 그 특성에 맞는 해시 값을 계산합니다.
식: 특정 자리 수나 특정 범위의 숫자를 선택하여 해시 값을 만듭니다.
장점: 숫자의 분포를 잘 활용할 수 있어서 특정 조건에 맞게 충돌을 줄일 수 있습니다.
단점: 키 값이 숫자가 아닐 경우 변환 작업이 필요할 수 있으며, 분포 분석을 잘못하면 충돌이 발생할 수 있습니다.
5. 기수변환법(Radix Conversion) :
원리: 키 값을 다른 진법(예: 10진법에서 2진법, 16진법 등)으로 변환하여 저장 위치를 결정하는 방법입니다. 주로 숫자 키에 대해 적용됩니다.
식: hash(K) = 변환된 진법 값 예를 들어, 10진수를 2진수로 변환하여 특정 비트를 해시 값으로 사용할 수 있습니다.
장점: 숫자 데이터의 특성을 이용하여 간단한 연산으로 해시 값을 계산할 수 있습니다.
단점: 기수 변환이 복잡해질 수 있으며, 충돌을 피하기 위해 적절한 비트 수나 자릿수를 선택하는 것이 중요합니다.
6. 무작위법(Random) :
원리: 난수를 사용하여 키에 대한 해시 값을 생성하는 방법입니다. 키를 랜덤하게 매핑하여 해시 값을 결정합니다. 예를 들어, 무작위로 생성된 해시 값을 키에 대응시킬 수 있습니다.
장점: 충돌을 예측하기 어렵고, 해시 테이블에서 매우 고르게 분포할 수 있습니다.
단점: 난수 생성이 필요한데, 난수 생성기의 품질이 떨어지면 성능이 나빠질 수 있으며, 해시 테이블의 크기와 충돌 처리 방식에 따라 성능이 달라질 수 있습니다.