문제 해결 패턴

현대 소프트웨어 엔지니어링의 문제 해결에 관한 블로그 시리즈에 다시 오신 것을 환영합니다!

1부에서는 요소의 빈도를 효율적으로 계산하여 알고리즘을 최적화하는 강력한 기술인 주파수 카운터 패턴을 살펴보았습니다. 놓치셨거나 빠르게 복습하고 싶으시다면 계속하기 전에 꼭 확인해 보세요.

이 부분에서는 또 다른 필수 패턴인 멀티포인터 패턴을 살펴보겠습니다. 이 패턴은 여러 요소를 동시에 비교, 검색 또는 탐색해야 하는 시나리오를 처리할 때 매우 중요합니다. 코드 효율성을 높이기 위해 어떻게 작동하고 어디에 적용할 수 있는지 살펴보겠습니다.

02. 멀티포인터 패턴

다중 포인터 패턴은 여러 포인터(또는 반복자)를 사용하여 배열이나 연결 목록과 같은 데이터 구조를 탐색하는 알고리즘 설계에 사용되는 기술입니다. 단일 포인터나 루프에 의존하는 대신 이 패턴은 서로 다른 속도 또는 서로 다른 시작점에서 데이터를 이동하는 두 개 이상의 포인터를 사용합니다.

예제 문제

정렬된 정수 배열을 받아들이는 sumZero라는 함수를 작성하세요. 함수는 합이 0인 첫 번째 쌍을 찾아야 합니다. 그러한 쌍이 존재하는 경우 두 값을 모두 포함하는 배열을 반환합니다. 그렇지 않으면 정의되지 않음을 반환합니다.

sumZero([-3,-2,-1,0,1,2,3]) //output: [-3, 3]
sumZero([-2,0,1,3]) //output: undefined
sumZero([-4, -3, -2, -1, 0, 1, 2, 5]) //output: [-2, 2]

기본 솔루션

function sumZero(arr){
    for (let i = 0; i < arr.length; i++) {
        for (let j = i+1; j < arr.length; j++) {
            if (arr[i] + arr[j] === 0) {
                console.log(arr[i] + arr[j])
                return [arr[i], arr[j]]
            }
        }
    }
}

시간 복잡도 - O(N^2)

멀티포인터 패턴을 이용한 솔루션

1단계: 문제 이해
**정렬된 배열에서 합이 0이 되는 두 개의 숫자를 찾아야 합니다. 배열이 정렬되어 있으므로 이 순서를 활용하여 보다 효율적으로 해를 찾을 수 있습니다.

2단계: 두 포인터 초기화
두 개의 포인터를 설정합니다. 하나(왼쪽)는 배열의 시작 부분에서 시작하고 다른 하나(오른쪽)는 끝에서 시작합니다.

예:

Array: [-4, -3, -2, -1, 0, 1, 2, 5]
Left Pointer (L): -4
Right Pointer (R): 5

3단계: 포인터 값의 합 계산
합계를 구하려면 왼쪽과 오른쪽 포인터에 값을 더하세요

Sum = -4 + 5 = 1

4단계: 합계와 0 비교

• 합계가 0보다 큰 경우: 합계를 줄이려면 오른쪽 포인터를 왼쪽으로 한 단계 이동하세요.

Sum is 1 > 0, so move the right pointer left:

Array: [-4, -3, -2, -1, 0, 1, 2, 5]
Left Pointer (L): -4
Right Pointer (R): 2

• 합계가 0보다 작은 경우: 합계를 늘리려면 왼쪽 포인터를 오른쪽으로 한 단계 이동하세요.

New Sum = -4 + 2 = -2
Sum is -2 < 0, so move the left pointer right:

Array: [-4, -3, -2, -1, 0, 1, 2, 5]
Left Pointer (L): -3
Right Pointer (R): 2

5단계: 과정 반복
포인터가 만나거나 쌍을 찾을 때까지 계속 포인터를 움직여 합계를 계산합니다.

New Sum = -3 + 2 = -1
Sum is -1 < 0, so move the left pointer right:

Array: [-4, -3, -2, -1, 0, 1, 2, 5]
Left Pointer (L): -2
Right Pointer (R): 2

합이 0이므로 함수는 [-2, 2]를 반환합니다.

그러한 쌍을 찾지 못한 채 루프가 완료되면 정의되지 않음을 반환합니다.

최종 코드

function sumZero(arr) {
  let left = 0;                         // Initialize the left pointer at the start of the array
  let right = arr.length - 1;           // Initialize the right pointer at the end of the array

  while (left < right) {                // Continue until the pointers meet
    const sum = arr[left] + arr[right]; // Calculate the sum of the values at the pointers

    if (sum === 0) {                    // If the sum is zero, return the pair
      return [arr[left], arr[right]];
    } else if (sum > 0) {               // If the sum is greater than zero, move the right pointer left
      right--;
    } else {                            // If the sum is less than zero, move the left pointer right
      left++;
    }
  }

  return undefined;                     // If no pair is found, return undefined
}

참고:
시간 복잡도: O(n) – 이 함수는 효율적이며 배열 크기에 따라 선형적으로 확장됩니다.
공간 복잡도: O(1) – 이 함수는 최소한의 추가 메모리를 사용합니다.

결론

멀티포인터 패턴은 정렬된 데이터 구조의 요소 검색, 비교 또는 조작과 관련된 문제를 해결하는 강력한 기술입니다. 서로를 향해 이동하는 여러 포인터를 사용하면 알고리즘의 효율성을 크게 향상시켜 많은 경우 시간 복잡도를 O(n²)에서 O(n)으로 줄일 수 있습니다. 이 패턴은 다목적이며 다양한 문제에 적용할 수 있으므로 코드 성능을 최적화하기 위한 필수 전략입니다.

다음 게시물을 기대해 주세요. 여기서는 동적 데이터 세그먼트와 관련된 문제를 해결하기 위한 또 다른 필수 도구인 슬라이딩 윈도우 패턴에 대해 자세히 알아보겠습니다. 훨씬 더 복잡한 문제를 쉽게 해결하는 데 도움이 되는 매우 유용한 패턴입니다!

위 내용은 문제 해결 패턴의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!