★[python_파이썬_시간복잡도 고민 중요]백준_2485번_가로수_풀이

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

문제가 어렵다.

처음에 머리속으로는 간격을 구해서 최소값인 간격을 다시 더해서 넣어주면 되지... 라고 생각했으나

이걸 반복해야한다.

일단 시간복잡도의 개념을 복습해서 보면 조금 더 이해가 수월할 수 있다 : https://heodinkcodingdiary.tistory.com/31

[python_파이썬] 정렬의 종류 (선택정렬, 삽입정렬, 퀵정렬, 병합정렬, 힙정렬, 기수정렬, 계수정렬)

 

유클리드호제법 설명 : https://heodinkcodingdiary.tistory.com/56

[python_파이썬_공배수 시간복잡도_유클리드호제법]백준_1934번_최소공배수_풀이

 

 

<첫번째 시도 : 시간초과>

생각하는대로 코드를 만들었다. 일단 답은 나오지만 시스템에서 시간초과가 나온다....젠Jxng...

import sys

import math

input = sys.stdin.readline

N = int(input())

already = []

already.sort()

for _ in range(N):

    temp = int(input())

    already.append(temp)

cnt = []

for i in range(1, len(already)):

    cnt.append(already[i] - already[i - 1])

answer = math.gcd(min(cnt), max(cnt))

temp = already[0]

while temp < already[-1]:

    temp += answer

    if temp not in already:

        already.append(temp)

    already.sort()

print(len(already) - N)

 

<두번째 시도 : 메모리 초과_시간복잡도 : O(N + log M + K>

최대한 간결하게 코드를 작성했는데 메모리 초과가 나왔네.....already와 after2개를 1개로 줄여봐야 겠다.

import sys

import math

input = sys.stdin.readline

N = int(input())

already = list(int(input()) for _ in range(N))

cnt = set()

for i in range(1, len(already)):

    cnt.add(already[i] - already[i - 1])

answer = math.gcd(min(cnt), max(cnt))

after = [i for i in range(already[0],already[-1] + 1,answer)]

print(len(after) - N)

 

<세번째 시도 : 시간 초과>

after를 컴프리헨션으로 해봤다.

아... 어떻게 할 방법을 모르겠네.....

import sys

import math

input = sys.stdin.readline

N = int(input())

already = list(int(input()) for _ in range(N))

cnt = set()

for i in range(1, len(already)):

    cnt.add(already[i] - already[i - 1])

answer = math.gcd(min(cnt), max(cnt))

after = [i for i in range(already[0],already[-1] + 1,answer) if i not in already]

print(len(after))

 

<네번째 시도 : 시간 초과>

새로운 리스트를 만드는 것이 아닌 cnt변수를 초기화 해서 already에 없는 수가 나오면 cnt += 1을 해서 차이분을 바로 구했다.

import sys

import math

input = sys.stdin.readline

N = int(input())

already = list(int(input()) for _ in range(N))

cnt = set()

for i in range(1, len(already)):

    cnt.add(already[i] - already[i - 1])

answer = math.gcd(min(cnt), max(cnt))

cnt = 0

first = already[0]

while first < already[-1]:

    first += answer

    if first not in already:

        cnt += 1

print(cnt)

 

<다섯번째 시도 : 시간초과_시간복잡도 : O(K * N)>

단순하게 min(already), max(already)로 변경 후 진행했다.

import sys

import math

input = sys.stdin.readline

N = int(input())

already = list(int(input()) for _ in range(N))

cnt = set()

for i in range(1, len(already)):

    cnt.add(already[i] - already[i - 1])

answer = math.gcd(min(cnt), max(cnt))

cnt = 0

first = min(already)

while first < max(already):

    first += answer

    if first not in already:

        cnt += 1

print(cnt)

 

<여섯번째 시도 : 시간 초과_시간복잡도 : O(k*L^2)>

뭐지? for문을 하나 없앴는데 시간초과가 나온다는 것은 gcd를 삭제해야 하나???

import sys

import math

input = sys.stdin.readline

N = int(input())

already = list(int(input()) for _ in range(N))

a = already[-1] - already[-2]

b = already[1] - already[0]

answer = math.gcd(min(a, b), max(a, b)) # => min과 max를 삭제해도 시간초과

cnt = 0

first = min(already)

while first < max(already):

    first += answer

    if first not in already:

        cnt += 1

print(cnt)

 

이정도 했으면 답을 봐야지....일단 답을 스쳐 지나가듯 보고 4일 후....

<일곱번째 시도 : 시간 초과>

이번에는 while문을 만들어서 gap이 1개만 나올때까지 반복을 돌렸다. 물론 중간에 print로 진행사항을 체크 했을때

중복으로 도는 부분이 있어 시간초과가 나올 것으로 예상은 했다.

import sys

input = sys.stdin.readline

N = int(input())

already = list(int(input()) for _ in range(N))

while True:

    gap = set()

    for i in range(1, len(already)):

        gap.add(already[i] - already[i - 1])

   

    for i in already:

        if i + min(gap) not in already and i + min(gap) < already[-1]:

            already.append(i + min(gap))

   

    already.sort()

   

    if len(gap) == 1:

        break

   

print(len(already) - N)

 

다른 사람 풀이 참고해서 방향을 다시 잡았다.

 

<여덟번째 시도 : 맞았습니다._와 이거 어렵네.... : 시간복잡도 : O(N*logM) >

기존 내가 만들었던 코드는 최소 O(K*N)의 복잡도가 생성되었다. 최대공약수 계산까지는 O(N + log M)으로 괜찮았으나 추가 가로수 계산사 O(k*N)이 되었다.

import sys

import math

input = sys.stdin.readline

N = int(input())

first  = int(input())

gap = []

for i in range(N - 1):

    num = int(input())

    gap.append(num - first)

    first = num

GCD = gap[0]

for i in gap:

    GCD = math.gcd(GCD, i)

answer = 0

for i in gap:

    answer += i // GCD - 1

print(answer)

 

<시간복잡도 분석 from chat gpt>

시간 복잡도 분석

1. 입력 읽기:
   • N = int(input()): O(1)
   • first = int(input()): O(1)
   • for i in range(N - 1): num = int(input()) ...: O(N)
   여기까지의 시간 복잡도는 O(N)입니다.
2. 간격 계산:
   • gap.append(num - first): O(1) (각 호출마다)
   • 총 N-1 번의 호출: O(N)
   따라서, 간격 계산 부분의 시간 복잡도는 O(N)입니다.
3. 최대공약수 계산:
   • GCD = gap[0]: O(1)
   • for i in gap: GCD = math.gcd(GCD, i): 각 gcd 호출은 O(log M), 여기서 M은 간격 값입니다.
   • 총 N-1 번의 호출: O((N-1) * log M) = O(N * log M)
   따라서, 최대공약수 계산 부분의 시간 복잡도는 O(N * log M)입니다.
4. 추가 가로수의 수 계산:
   • for i in gap: answer += i // GCD - 1: 각 i // GCD 계산은 O(1)
   • 총 N-1 번의 호출: O(N)
   따라서, 추가 가로수의 수 계산 부분의 시간 복잡도는 O(N)입니다.

총 시간 복잡도

각 부분의 시간 복잡도를 합치면 다음과 같습니다:

• 입력 읽기: O(N)
• 간격 계산: O(N)
• 최대공약수 계산: O(N * log M)
• 추가 가로수의 수 계산: O(N)

따라서, 총 시간 복잡도는: O(N)+O(N)+O(N⋅log⁡M)+O(N)=O(N⋅log⁡M)O(N) + O(N) + O(N \cdot \log M) + O(N) = O(N \cdot \log M)O(N)+O(N)+O(N⋅logM)+O(N)=O(N⋅logM)

여기서 N은 주어진 가로수의 수, M은 최대 간격 값을 의미합니다. 이 시간 복잡도는 대부분의 경우 효율적이며, 주어진 입력 크기에 대해 잘 작동할 것입니다.

 

<코드 분석>

chatgpt분석시 시간복잡도가 조금씩 상이하지만 일단, 마지막 코드의 시간복잡도가 가장 효율적인 것으로 나온다.

두번째 코드와 여덟번째 코드 비교 시 아래와 같은 비교가 된다.

 

[chat gpt설명]

효율성 비교

1. 첫 번째 코드:
   • 각 가로수 사이의 간격을 집합에 저장하고, 이 간격들의 최대공약수를 계산합니다.
   • 이후, 가장 처음 가로수부터 가장 마지막 가로수까지 최대공약수 간격으로 추가 가로수를 생성하고, 이를 이용하여 추가 가로수의 수를 계산합니다.
   • 시간 복잡도는 O(N log M)입니다.
2. 두 번째 코드:
   • 각 가로수 사이의 간격을 리스트에 저장하고, 이 간격들의 최대공약수를 계산합니다.
   • 각 간격을 최대공약수로 나누어 추가 가로수의 수를 계산합니다.
   • 시간 복잡도는 O(N)입니다.

결론

두 코드 모두 시간 복잡도가 선형에 가까운 효율을 가지고 있습니다. 그러나 두 번째 코드가 더 효율적인 것으로 보입니다. 왜냐하면 두 번째 코드는 중복되는 계산을 피하고 최대공약수를 더 효율적으로 계산하기 때문입니다. 따라서, 두 번째 코드가 더 효율적입니다.

 

<가로수문제와 최대공약수의 관계>

1. 주어진 가로수 사이의 간격들의 최대공약수는 이 가로수들 간의 공통적인 간격을 나타낸다. 즉, 주어진 가로수 사이의 모든 간격들의 최대공약수의 배수인 상황에서, 최대공약수는 이들 간의 가장 작은 공통 간격을 나타낸다.

2. 최대공약수를 이용하여 가로수를 추가하면 추가되는 가로수들 간의 간격이 최대공약수의 배수가 된다. 이는 최대공약수의 배수로 가로수를 추가하면, 추가되는 가로수들 간의 간격이 최대공약수의 배수로 일정하게 유지된다.

3. 최대공약수를 배수로 가지는 간격으로 가로수를 추가하면 추가되는 가로수들 간의 간격이 최대공약수의 배수가 되어 일정한 간격을 유지할 수 있다. 이는 가로수 사이의 간격들의 최대공약수를 이용하여 일정한 간격을 가지는 가로수를 추가할 때의 핵심 아이디어이다.

 

즉, 최대공약수가 일정한 간격을 유지하는 이유는 주어진 가로수 사이의 간격들이 최대공약수의 배수인 상황에서, 최대공약수를 이용하여 가로수를 추가하면 추가되는 가로수들 간의 간격이 최대공약수의 배수로 유지되어 일정한 간격을 가지게 되기 때문이다.