[python_파이썬]백준_알고리즘 수업 - 알고리즘의 수행 시간 1, 2, 3, 4, 5, 6_풀이

공부하는허딩크 : https://www.youtube.com/live/qRYajWJrQv8?feature=shared

문제를 처음 본 순간 전혀 이해를 못했다. 이건 내가 이해할 수 있는 수준이 아니구나.....

바로 구글링.....

<시간복잡도의 개념>

https://hanamon.kr/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-time-complexity-%EC%8B%9C%EA%B0%84-%EB%B3%B5%EC%9E%A1%EB%8F%84/

[알고리즘] Time Complexity (시간 복잡도) - 하나몬

 

내가 이해한 바로는 코드에 따라 시간 복잡도가 있다는 개념이다.

for문을 한번 돌리느냐, 두번 돌리느냐에 따라 또는 재귀함수에 따라 시간 복잡도가 다르다는 개념이다.

 

지금 정리를 하고는 있지만 100%이해는 되지 않는다. 이걸 이해하려면 시간이 많이 걸릴 듯 하여 일단 pass

 

이 문제는 변수 n을 받아서 MenofPassion에서 코드가 실행될때 출력값이 속도가 n의 값에 따라서 시간 복잡도가 어떻게 되는지를 물어보는 문제이다.

즉, n = 1일 경우에 i = 0.5가 되고 A[i]를 인덱싱하는건데.... 인덱싱에 0.5가 있나??? 딕셔너리에 Value값이면 가능한데...

이런 고민은 필요 없고 그냥 n이 1이 나오는 100이 나오는 return은 1번이기 때문에 수행 횟수는 무조건 1번이다.

 

근데 둘째 줄은 무슨 의미지? 이건 진짜 모르겠다.

그냥 모른채 pass : 대충 이 경우 0이다라고 하니 그냥 암기

즉 답은

print(1)

print(0)

 

 

여기서 문제의 코드를 분석해보자

sum <- 0;

for i <- 1 to n

    sum <- sum + A[i];

return sum;

 

위의 코드를 이렇게 추정해볼 수 있다,

sum = 0

for i in range(1, n) => n포함

    sum += A[i]

 

즉, 예시에서 7이 주어졌으니까 1부터 7까지 다 더하라는게 된다.

즉 7번 반복되니까 실행은 7번...

즉 어떤 숫자가 오던지 N번 반복함.

다항식? 으로 나타낸다는게 어떤 뜻인지는 모르겠으나 N앞에 1이 생략되어 있다고 추정 후 print(1)

print(input())

print(1)

 

 

이것도 한번 파이썬 코드로 이해해보자

sum = 0

for i in range(1, n):

    for j in range(1, n):

        sum += A[i] * A[j]

이중 for문이다.

i = 1일때 j = 1~7까지, i = 2일때 j = 1~7까지, ...........i = 7일때 j = 1~7까지 이렇게 반복된다,

즉, 어떤 정수가 주어진다면 N ** 2 제곱만큼 실행된다. 

 

다항식으로 표현한다면??? N ** 2 이니까 2로 그냥 암기하자.

print(int(input()) ** 2)

print(2)

이제 조금 복잡해 진다.

파이썬 코드로 변경해보자

sum = 0

for i in range(1, n - 1):

    for j in range(i + 1, n):

        sum += A[i] * A[j]

 

예제인 n = 7일 경우 i = 1~6까지 6번 반복되고, j = i의 숫자에 따라 횟수가 달라진다.

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번

총 21번 실행된다.

 

다항식은 일단 이중 for문이니까 N ** 2일때와 동일하다고 추정하고 2를 준다. 예시에도 2로 나와 있음

import sys

input = sys.stdin.readline

N = int(input())

answer = 0

for i in range(1, N):

    answer += i

print(answer)

print(2)

 

바로 파이썬으로 변경해보자

sum = 0

for i in range(1, n):

    for j in range(1, n):

        for k in range(1, n):

            sum += A[i] * A[j] * A[k]

삼중for문이 나온다. N ** 3이 예상된다.

예시를 봤더니 N = 7일 경우 출력은 343이고 두번째도 3이다.

print(int(input()) ** 3)

print(3)

 

 

바로 파이썬으로 변경해보자

sum = 0

for i in range(1, n -2):

    for j in range(i+1, n-1):

        for k in range(j + 1, n):

            sum += A[i] * A[j] * A[k]

 

일단 3중 for문이니까 둘째 줄은 3이 확정.

n = 7이 주어질때

i = 1~5

i = 1일때 j = 2, 3, 4, 5, 6인데 

i = 1일때 j = 2일때 k = 3, 4, 5, 6, 7

i가 증가하면서 j의 반복숫자와 k의 반복숫자가 달라짐.

아래 엑셀로 다시 정리해보자. 헷갈린다....

즉, 15번, 10번, 6번, 3번, 1번이 실행되면서 총 35번이 실행된다.

 

이제 이걸 코드로 작성해보자.

k의 횟수를 기준으로 15번은 5 + 4 + 3 + 2 + 1을 더한 값이고

                                  10번은 4 + 3 + 2 + 1이다.

동일하게 삼중for문으로 구해볼까?

<첫번째 시도 시간초과>

import sys

input = sys.stdin.readline

N = int(input())

answer = 0

for i in range(1, N - 2 + 1):

    for j in range(i + 1, N - 1 + 1):

        for k in range(j + 1, N + 1):

            answer += 1

print(answer)

print(3)    

 

삼중for문이 돌아가면서 1씩 더하는 개념으로 접근했으나 시간 초과라면 수학적 공식으로 접근해보자.

 

<두번째 시도 런타임에러>

import sys

input = sys.stdin.readline

def temp(N):

    if N == 1:

        return 1

    return N + temp(N - 1)

N = int(input())

answer = 0

for i in range(2, N):

    answer += temp(N - i)

print(answer)

print(3)

 

이런 방향으로 해결하는게 아닌 것 같다. 수학적으로 다시 접근해보자. 그런데 수학적으로 접근이 안되서 재귀로 접근한건데....

 

정답을 봐야겠네...근데 정답을 봐도 이해는 안간다.... 내가 스스로 한번 찾아보자.

5 4 3 2 1

4 3 2 1

3 2 1

2 1

1

이거를 한꺼번에 더해주면 되는데.....

이거 1 + 1 + 2 + 1 + 2 + 3 + 1 + 2 + 3 + 4 + 1 + 2 + 3 + 4 + 5 이게 보인다.

즉 7이 나오면 7-2해서 1~5까지 나오게 해서 1은 5를 곱해주고, 2는 4를 곱해주고 3은 3를 곱하고 4는 2, 5는 1을 곱해주면

답이 나오겠다.

 

<세번째 시도 맞춤>

import sys

input = sys.stdin.readline

N = int(input())

answer = 0

for i in range(1, N - 1):

    answer += i * (N - i - 1)

print(answer)

print(3)

 

<다른 사람 풀이>

아래와 같이 된 공식은 이해가 안간다. 이건 나중에 다시 봐야겠다.

n= int(input())

print((n-2) * (n-1) * (n) // 6)

print(3)