백준 24262~24267. 알고리즘의 수행 시간 1~6 정리

이 문제들은 알고리즘 실행 시간에 대해서 알아보기 위한 문제이다.
한 개의 예시 알고리즘이 제시되며, 이 알고리즘이 입력 N이 있을 때, 수행 횟수를 계산하고 횟수를 다항식으로 나타냈을 때 최고차항의 차수를 출력한다.

코드로 짜야할 것은 없고, 다만 수행 횟수는 제시된 알고리즘에 맞게 계산되서 나오도록 식을 유도해서 입력받은 N을 나온 식에 넣어서 바로 계산해서 출력할 것이다.
물론 제시된 알고리즘을 코드로 구현해서 직접 돌려서 횟수를 세는 방법도 있겠지만…

참고로 주어지는 입력 N의 범위가 커서 수행 횟수가 int의 범위를 넘어서는 문제가 있으니 N은 long 형으로 입력받도록 한다.

24262. 알고리즘 수업 – 알고리즘의 수행 시간 1

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

위와 같은 알고리즘이 주어진다. 주석이 있는 라인이 실행되는 횟수는 몇 번일까?

이 알고리즘은 주어진 배열 A로 부터 특정 인덱스를 계산해서 값을 반환한다. 배열은 인덱스를 알면 순차적으로 앞에서 접근할 필요 없이 바로 그 위치에서 값을 꺼내올 수 있다.

1억개의 원소가 있는 배열에서 0번째 값을 꺼내오나 천만번째 값을 꺼내오나 걸리는 시간이 같다는 뜻이다.

즉, 시행 횟수는 N에 관계없이 1이 되며, 이는 상수항이므로 차수는 0이된다.

print(1)
print(0)

24263. 알고리즘 수업 – 알고리즘의 수행 시간 2

MenOfPassion(A[], n) {
    sum <- 0;
    for i <- 1 to n
        sum <- sum + A[i]; # 코드1
    return sum;
}

이 알고리즘은 1부터 n까지 for문을 한번 돈다. 실제로 무슨 일을 하는지는 신경 쓸 필요 없다. 단지 주석 처리된 저 라인이 총 n번 실행된다는 것을 알면 된다.

당연히 시행 횟수는 n이며, \(n = n^1\)이므로 최고 차항의 차수는 1이다.

print(N)
print(1)

24264. 알고리즘 수업 – 알고리즘의 수행 시간 3

MenOfPassion(A[], n) {
    sum <- 0;
    for i <- 1 to n
        for j <- 1 to n
            sum <- sum + A[i] × A[j]; # 코드1
    return sum;
}

이번에는 이중 for문이다. 바깥 for문이 n번 반복하며, 내부 for문 또한 n번 반복한다.

반복 횟수가 \(n^2\)인 것을 쉽게 알 수 있다.
즉, 실행 횟수는 \(n^2\), 최고 차항의 차수는 2이다.

print(n*n)
print(2)

만약 틀렸다고 뜨면 입력을 long이 아닌 int로 받고 있는것은 아닌지 체크해보자. 이 아래 문제도 모두 해당된다.

24265. 알고리즘 수업 – 알고리즘의 수행 시간 4

MenOfPassion(A[], n) {
    sum <- 0;
    for i <- 1 to n - 1
        for j <- i + 1 to n
            sum <- sum + A[i] × A[j]; # 코드1
    return sum;
}

이번에도 이중 for문이지만 for문의 범위가 다르다. 바깥 for문은 1~n-1까지, 안쪽 for문은 i+1~n까지이다.

이해하기 쉽게 n=7로 예시를 들어보자. 바깥 for문은 i=1~6까지 이므로 총 6번 반복한다.

i=1
    j: 2~7  # 6번
i=2
    j: 3~7  # 5번
i=3
    j: 4~7  # 4번
i=4
    j: 5~7  # 3번
i=5
    j: 6~7  # 2번
i=6
    j: 7~7  # 1번

보면 처음 n-1번 실행되고, 이후 실행 횟수가 1씩 줄면서 실행되다가 마지막에는 1번만 실행되는 것을 볼 수 있다.

이것들의 합은 결국 1부터 n-1까지의 합임을 알 수 있으며, 이를 공차가 1인 등차수열의 합의 공식을 이용하여서 계산할 수 있을 것이다.

\(S = {k(a+l) \over 2}\)

위 공식은 1부터 \(k\)번째 항 까지의 합을 구하며, \(a\)는 초항, \(l\)은 마지막 항을 의미한다.
우리는 1부터 \(n-1\)번째 항 까지의 합을 구해야 하므로

\(
k = n-1\\
a = 1\\
l = n-1
\)
이 되며, 이를 대입하면…

\(
{(n-1)(1+n-1) \over 2} = {n(n-1) \over 2}
\)
가 된다. 즉, 우리는 입력 받은 N을 위 공식에 넣어서 계산된 값을 출력하면 된다.

print(N*(N-1)/2)
print(2)

24266. 알고리즘 수업 – 알고리즘의 수행 시간 5

MenOfPassion(A[], n) {
    sum <- 0;
    for i <- 1 to n
        for j <- 1 to n
            for k <- 1 to n
                sum <- sum + A[i] × A[j] × A[k]; # 코드1
    return sum;
}

이번에는 삼중 for문이며, 각 for문은 모두 1부터 n까지, 즉 n번 반복한다.
이번 문제는 계산할 필요도 없이 실행 횟수는 \(n^3\)이며, 최고차항의 차수는 3임을 알 수 있다.

print(N*N*N)
print(3)

24267. 알고리즘 수업 – 알고리즘의 수행 시간 6

MenOfPassion(A[], n) {
    sum <- 0;
    for i <- 1 to n - 2
        for j <- i + 1 to n - 1
            for k <- j + 1 to n
                sum <- sum + A[i] × A[j] × A[k]; # 코드1
    return sum;
}

이번에도 삼중 for문이지만 뭔가 다르다.
첫번째 for문은 i가 1부터 n-2까지 반복된다.
두번째 for문은 j가 i+1부터 n-1까지 반복된다.
세번째 for문은 k가 j+1부터 n까지 반복된다.

두, 세번째 for문은 이전 for문의 변수의 값에 따라 반복횟수가 변하게 된다. 이 상황에서 반복 횟수를 구할 수 있는 공식을 어떻게 만들어낼 수 있을까?

먼저 n부터 m까지의 수의 합은 급수의 합을 나타내는 기호 시그마(\(\sum\))으로 나타낼 수 있다. 즉, 위의 for문의 경우도 시그마를 이용해서 나타내는 것이 가능하다.
시그마는 고등학교 교육과정에서 배울 것이다. 이 글에서는 시그마 계산이 가능하다는 것을 전제로 공식을 유도하겠다.

솔직히 이 문제는 공식 만드는데 시간을 많이 썼다. 오랜만에 시그마 계산하려니 머리가 아프더라…

\(\sum\limits_{i=1}^{n-2}\sum\limits_{j=i+1}^{n-1}\sum\limits_{k=j+1}^{n} 1\)

주어진 예제의 삼중 for문을 시그마를 이용해 식으로 바꾸면 위와 같다. 이제 이 식을 하나씩 풀어서 그냥 N만 바로 대입했을 때 식이 하나 나오도록 만들어보자.

공식 유도 첫번째

먼저 \(\sum\limits_{k=j+1}^{n} 1\)를 풀어보자.

이는 단순히 j+1부터 n까지 1을 더했다는 뜻이다. 만약 3부터 5까지 1을 더한다면 1은 5-3+1=3으로 세 번 더해지는 것이다.

정리하면 \((윗끝 – 아래끝+1) \times 1\)이다. 곱해지는 1은 위 시그마 식에서의 1이다.
한 번의 for 루프에 코드가 한 번 실행 되므로 1인 것이다.

여기서는 \((n)-(j+1)+1=n-j\)이므로, 아래와 같이 정리된다

\(\sum\limits_{i=1}^{n-2}\sum\limits_{j=i+1}^{n-1} (n-j)\)

공식 유도 두번째

이 식에서 \(n\)은 상수임을 기억하고 있자! 알파벳으로 되있어 마치 변수인 것 같은 느낌이 들어서 계산시 헷갈릴 수 있는데, 이놈은 상수다!!!

위 정리된 식에서 두번째 시그마 부분만 보면 j가 i+1에서 n-1까지 변할 때, n-j의 합이다.

\((n-i-1)+(n-i-2)+…\) 이렇게 더해지다가 마지막에 \(j=n-1\)이 되면

\(\begin{align}n-j&=n-(n-1)\\
&=1\end{align}\)

이므로, \((n-i-1)+(n-i-2)+…+1\)이되며, 이는 초항이 \((n-i-1)\)이고 공차가 \(-1\)이며, 마지막 항이 \(1\)인 등차수열의 합을 구하는 것과 같다.
이 공식은 24265번 설명 문단에서 소개했다.

\(a=n-i-1\)
\(\begin{align}k&=(n-1)-(i+1)+1\\
&=n-i-1\end{align}\)
\(l=1\)

\(
{k(a+l) \over 2} = {(n-i-1)(n-i-1+1) \over 2}
={(n-i)(n-i-1) \over 2}
\)

그러므로 아래와 같이 정리된다

\(\sum\limits_{i=1}^{n-2} {(n-i)(n-i-1) \over 2}\)

공식 유도 세번째

일단 위에서 정리한 공식을 더 정리해보겠다.

\(\begin{align}
\sum\limits_{i=1}^{n-2} {(n-1)(n-i-1) \over 2}&={1 \over 2}\sum\limits_{i=1}^{n-2} (n-i)(n-i-1)\\
&={1 \over 2}\sum\limits_{i=1}^{n-2} (n^2-ni-n-ni+i^2+i)\\
&={1 \over 2}\sum\limits_{i=1}^{n-2} (n^2-2ni+i+i^2-n)\\
&={1 \over 2}\sum\limits_{i=1}^{n-2} \{i^2+(1-2n)i+(n^2-n)\}\\
&={1 \over 2}\sum\limits_{i=1}^{n-2} i^2+{1-2n \over 2} \sum\limits_{i=1}^{n-2} i+{1 \over 2}\sum\limits_{i=1}^{n-2} (n^2-n)
\end{align}\)

이렇게 세 개의 부분으로 분리했다. 이제 시그마 공식을 이용하여 다시 정리해보자. 시그마 공식은 아래와 같다

\(
\sum\limits_{k=1}^{n} k={n(n+1) \over 2}\\
\sum\limits_{k=1}^{n} k^2={n(n+1)(2n+1) \over 6}
\)

위 공식을 이용하여 마저 정리해보면

\(\begin{align}
{1 \over 2}\sum\limits_{i=1}^{n-2} i^2+{1-2n \over 2} \sum\limits_{i=1}^{n-2} i+{1 \over 2}\sum\limits_{i=1}^{n-2} (n^2-n)&={1 \over 2}{(n-2)(n-1)(2n-3) \over 6}+{1-2n \over 2}{(n-2)(n-1) \over 2}+{1 \over 2}(n^2-n)\{(n-2)-1+1\}\\
&={1 \over 2}{(n-2)(n-1)(2n-3) \over 6}+{1-2n \over 2}{(n-2)(n-1) \over 2}+{1 \over 2}n(n-1)\{(n-2)\}\\
&={(n-1)(n-2) \over 2}\{{2n-3 \over 6}+{1-2n \over 2}+n\}\\
&={(n-1)(n-2) \over 2}\{{2n-3+3-6n+6n \over 6}\}\\
&={(n-1)(n-2) \over 2}{2n \over 6}\\
&={n(n-1)(n-2) \over 6}
\end{align}\)

이렇게 되고, 드디어 우리가 찾던 정리된 공식인 \({n(n-1)(n-2) \over 6}\) 을 찾을 수 있다. 이걸 그대로 코드로 바꿔 제출하면 된다.

print(N*(N-1)*(N-2)/6);
print(3);

후기…수식 옮겨서 입력하는게 노가다이다…