브루트포스 알고리즘과 슬라이딩 윈도우 알고리즘

브루트포스 알고리즘

 

가능한 모든 경우의 수를 전부 탐색하여 문제를 해결하는 방식

 

단순하고 구현이 쉬우며, 특정 상황에서는 효과적일 수 있지만, 일반적으로 시간이 많이 걸릴 수 있습

특히 입력 데이터가 클 경우에는 비효율적

 

예를 들어, 문자열에서 특정 패턴을 찾는 문제에서

문자열 s와 패턴 p가 주어졌을 때, 패턴이 문자열에 포함되어 있는지를 확인하는 코드

 

def brute_force_search(s, p):
    n = len(s)
    m = len(p)
    
    for i in range(n - m + 1):
        j = 0
        while j < m and s[i + j] == p[j]:
            j += 1
        if j == m:
            return True
    return False

s = "hello world"
p = "world"
print(brute_force_search(s, p))  # 출력: True

 

위 코드는 문자열 s의 모든 위치에서 패턴 p와 일치하는지를 확인하는 방식

s의 길이가 n, p의 길이가 m이라면, 최대 O(n * m)의 시간 복잡도를 가짐

 

 

슬라이딩 윈도우 알고리즘

 

슬라이딩 윈도우 알고리즘은 윈도우 크기 만큼의 부분 문자열을 이동하면서 문제를 해결하는 방식

예를 들어, 배열에서 연속된 k개의 숫자의 합이 최대가 되는 값을 찾는 문제를 생각해보자

 

def max_sum_subarray(arr, k):
    n = len(arr)
    if n < k:
        return None
    
    # 처음 윈도우의 합 계산
    max_sum = sum(arr[:k])
    window_sum = max_sum
    
    # 슬라이딩 윈도우
    for i in range(n - k):
        window_sum = window_sum - arr[i] + arr[i + k]
        max_sum = max(max_sum, window_sum)
    
    return max_sum

arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
k = 3
print(max_sum_subarray(arr, k))  # 출력: 27 (8 + 9 + 10)

 

위 코드는 처음 k개의 숫자의 합을 계산한 후, 윈도우를 오른쪽으로 한 칸씩 이동하면서 새로운 합을 계산하고, 최대 값을 갱신하는 방식임. 시간 복잡도는 O(n)으로 매우 효율적

 

이처럼 브루트포스 알고리즘은 모든 경우를 탐색하는 단순하지만 느린 방법인 반면, 슬라이딩 윈도우 알고리즘은 특정 크기의 부분 문제를 효율적으로 해결하는 방법