C# 프로그래밍 기초 실습 전자책

C# / .NET 알고리즘과 퀴즈
본 알고리즘 퀴즈 문제는 C#/.NET 개발자를 위한 알고리즘 인터뷰 혹은 C# 프로그래밍을 통한
문제 해결 알고리즘을 연구해 보는데 도움이 되고자 작성되었습니다.


퀴즈 질문


예상답변/설명

가장 단순한 솔루션으로 각 배열 요소들의 쌍을 지어 순차적으로 모든 요소를 비교하여 최대값을 구하는 것이다. 하지만, 이는 O(n^2)의 시간을 소요하게 된다.

보다 최적화된 방식으로 아래와 같이 배열 처음부터 현재 요소 i 까지 최소 구매 가격 및 위치를 배열 min[]과 minPos[]에 각각 저장하는 것이다. 즉, 처음 요소부터 순차적으로 최소값을 현재 위치와 다시 비교, 현재값이 더 적으면 최소값을 현재값으로 재지정하고, 더 크면 이전 최소값을 그대로 유지한다. 이렇게 모든 요소에 대해 각 싯점에서의 최소 구매값을 구해 두고, 나중에 전체 루프를 다시 돌며, 배열요소 i 에서의 현재값과 최소값의 차이를 구하여 이 중 최대가 되는 범위를 구한다. 이 방식은 O(N)으로 보다 효율적이다.

void GetMaxProfit()
{
    int[] A = { 10, 15, 11, 8, 9, 20, 0, 19 };
    int[] min = new int[A.Length];
    int[] minPos = new int[A.Length];

    for (int i = 0; i < A.Length; i++)
    {
        if (i == 0)
        {
            min[i] = A[0];
            minPos[i] = i;
            continue;
        }

        if (A[i] <= min[i - 1])
        {
            min[i] = A[i];
            minPos[i] = i;
        }
        else
        {
            min[i] = min[i - 1];
            minPos[i] = minPos[i-1];
        }
    }

    int max = int.MinValue;
    int pos = -1;
    for (int i = 0; i < A.Length; i++)
    {
        if (A[i] - min[i] > max)
        {
            max = A[i] - min[i];
            pos = i;
        }
    }

    Console.WriteLine("Max Range : {0}-{1}", minPos[pos], pos);
    Console.WriteLine("Max Value : {0}", max);
}