c# 백준 24262 알고리즘 수업 - 알고리즘 수행 시간

문제 링크

풀이 과정

수행 횟수니, 수행 횟수의 최고차항이니 처음보는 단어가 있어서 대체 무슨소리인지 몰라 찾아보니 시간 복잡도에 대한 개념이 필요했다.

시간 복잡도는 간단히 말해 입력값에 코드의 작동시간이 얼마나 걸리나를 말한다.

수행 횟수는 시간 복잡도를 나타내는 개념으로 써 몇번 수행되었나를 의미한다.
다음 코드를 봐보자

for (int i = 0; i < 3; i++)
{
    Console.Write(i);
}

이 코드의 경우 3번 반복되는 반복문이다.
이 경우 수행 횟수는 3번이다.

다음 코드를 봐보자

for (int i = 0; i < n; i++)
{
    Console.Write(i);
}

이번에는 입력값(n)에 따라 반복 횟수가 늘어난다. 즉, 수행 횟수가 n이 된다.

만야 for문이 2중, 3중 늘어난다면 수행 횟수의 차수가 증가하게 된다. n^2, n^3, n^4…

for (int i = 0; i < n; i++)
{
    for (int j = 0; j < n; j++)
    {
        Console.Write(j); // n^2의 수행시간
    }
}

여기서 문제에서 말하는 최고차항이 가장 큰 차수를 말하는 것이다.

그럼 이제 문제를 봐보자. 문제는 다음같은 함수를 보여준다.

MenOfPassion(A[], n) {
    i = ⌊n / 2⌋;
    return A[i];
}

이 함수는 입력값(n)에 영향을 받지 않고 무조건 1번 실행된다.
이는 수행횟수가 1임을 알 수 있고 최고차항이라 할 것도 없이 n에 영향을 받지 않으니
최고차항의 계수는 0임을 알 수 있다.

전체 코드

class Program
{
    static void Main(string[] args)
    {
        Console.WriteLine("1\n0");
    }
}