[알고리즘] 다중 포인터 패턴 설명! (에피소드 1)

이것은 요점을 뒷받침할 많은 이미지가 포함된 알고리즘에 대한 빠른 시리즈의 일부입니다. 배열을 검색하는 방법에는 여러 가지가 있습니다. 가장 간단하고 분명한 것은 루프를 사용하는 것입니다!



그러나 그것이 제기하는 우려는 반복이 과도하게 사용될 때입니다. 루프 내부의 루프는 프로그램이 대규모 데이터에서 실행되는 방식에 영향을 미칩니다. (N 제곱 시간 복잡도)

For Loop
    For Loop

따라서 정렬된 목록을 통해 검색하는 더 좋은 방법이 있어야 합니다.

배열 { 2, 3, 7, 9, 17, 1, 5 }의 예를 살펴보겠습니다. 여기에서 10을 제공하는 배열 요소의 두 합을 찾아야 합니다!

꽤 쉬운데?



배열의 구성 요소를 살펴보면



7 + 3 및 9 + 1은 모두 10을 제공합니다.

무엇보다도 먼저 0부터 시작하는 인덱스로 시작하여 전체 배열 목록을 검색합니다. 간단히 말해서 배열 목록의 모든 단일 요소와 0부터 시작하는 요소의 합입니다.

젠장! 우리는 그것을 보지 못했다!

.......다음 인덱스로 이동........



배열의 모든 요소를 ​​첫 번째 인덱스와 거의 합한 것인데 우리는 그것을 보지 못했습니다. 인덱스를 1씩 이동하고 배열을 다시 스캔하기로 결정했습니다.



예!! 우리는 그것을 찾았습니다.

그러나 배열에 100만 개에 가까운 요소가 있다고 가정하면 배열 목록을 스캔하고 시작/상관 인덱스를 1씩 이동한 다음 100만 개를 다시 스캔해야 합니다. ~반복.~ (그건 시간과 자원의 열악한 성능)

 class Program
    {
        static void Main(string[] args)
        {
           int[] result = SumArray(new int[] { 2, 3, 7, 9, 17, 1, 5 }, 10);

            Console.WriteLine($"{result[0]}, {result[1]}");

            Console.ReadLine();
        }

        private static int[] SumArray(int[] array, int luckySum)
        {
            for (int i = 0; i < array.Length; i++) //Use this to get the index of each element
            {
                for (int j = i+1; j < array.Length; j++) //use this loop to scan through the array
                {
                    int firstVal = array[i];
                    int secondVal = array[j];

                    int sum = firstVal + secondVal;

                    if (sum == luckySum)
                        return new int [] { array[i], array[j]};
                }
            }

            return new int[] { };
        }
    }

따라서 효율적이지 않으므로 해당 접근 방식을 폐기해야 합니다. (정렬되지 않은 목록으로 작업하지 않는 한)



그런 다음 다중/이중 포인터 접근 방식을 위한 공간을 제공합니다.

다음화에서 설명....