효율적인 알고리즘 기초패턴

1. Two Pointers

• 주로 배열이나 리스트와 같은 선형 데이터 구조에서 사용되며, 두 개의 포인터를 동시에 움직여가며 문제를 해결합니다.
• 적용 예시: 한 쌍의 값이나 조건을 충족시키는 문제에 사용할 수 있습니다.

예제: 합이 0이 되는 두 값 찾기

• 주어진 정렬된 정수 배열에서 합이 0이 되는 첫 번째 쌍을 찾는 함수를 작성합니다.

무식한 방법

def find_sum_zero(arr):
    for i in range(len(arr)):
        for j in range(i + 1, len(arr)):
            if arr[i] + arr[j] == 0:
                return [arr[i], arr[j]]
    return None

• 시간 복잡도: $O(N^2)$
• 공간 복잡도: $O(1)$

Two Pointer 접근법

def find_sum_zero(arr):
    left = 0
    right = len(arr) - 1

    while left < right:
        total = arr[left] + arr[right]
        if total == 0:
            return [arr[left], arr[right]]
        elif total > 0:
            right -= 1
        else:
            left += 1
    return None

• 시간 복잡도: $O(N)$
• 공간 복잡도: $O(1)$

2. Sliding Window

• 개념: 연속된 데이터에서 일정한 크기의 구간(윈도우)을 움직이며 문제를 해결하는 패턴입니다. 주로 배열이나 문자열과 같은 데이터 구조에서 사용합니다.
• 적용 예시: 연속된 하위 집합에서 최대 합 또는 최소 합을 구하는 문제에 사용됩니다.

예제: 연속된 n개의 원소의 최대 합 찾기

• 주어진 정수 배열에서 연속된 n개의 원소의 최대 합을 계산하는 함수를 작성합니다.

무식한 방법

def max_subarray(arr, n):
    if n > len(arr):
        return None

    max_sum = float("-inf")

    for i in range(len(arr) - n + 1):
        temp_sum = sum(arr[i:i + n])
        max_sum = max(max_sum, temp_sum)

    return max_sum

• 시간 복잡도: $O(N^2)$
• 공간 복잡도: $O(1)$

Sliding Window 접근법

def max_subarray(arr, n):
    if n > len(arr):
        return None

    max_sum = temp_sum = sum(arr[:n])

    for i in range(n, len(arr)):
        temp_sum = temp_sum - arr[i - n] + arr[i]
        max_sum = max(max_sum, temp_sum)

    return max_sum

• 시간 복잡도: $O(N)$
• 공간 복잡도: $O(1)$

3. Divide and Conquer

• 개념: 큰 문제를 작은 서브 문제로 나눈 다음, 각 서브 문제를 재귀적으로 해결하고 이들의 해결책을 결합하여 원래 문제를 해결하는 알고리즘 패턴입니다.
• 적용 예시: 이진 탐색, 병합 정렬, 퀵 정렬과 같이 분할 정복 알고리즘에 사용됩니다.

예제: 정렬된 배열에서 값 찾기 (이진 탐색)

• 주어진 정렬된 정수 배열에서 특정 값의 인덱스를 찾는 함수를 작성합니다.

이진 탐색 접근법

def search(arr, val):
    left = 0
    right = len(arr) - 1

    while left <= right:
        mid = left + (right - left) // 2

        if arr[mid] == val:
            return mid
        elif arr[mid] < val:
            left = mid + 1
        else:
            right = mid - 1

    return -1

• 시간 복잡도: $O(\log N)$
• 공간 복잡도: $O(1)$