일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | 7 |
8 | 9 | 10 | 11 | 12 | 13 | 14 |
15 | 16 | 17 | 18 | 19 | 20 | 21 |
22 | 23 | 24 | 25 | 26 | 27 | 28 |
29 | 30 | 31 |
- 캐치카페
- 데이콘
- dacon
- 코로나19
- github
- Docker
- programmers
- 더현대서울 맛집
- 편스토랑
- ChatGPT
- Baekjoon
- AI 경진대회
- 백준
- 맥북
- 프로그래머스 파이썬
- 금융문자분석경진대회
- hackerrank
- ubuntu
- 파이썬
- Git
- SW Expert Academy
- Real or Not? NLP with Disaster Tweets
- gs25
- 자연어처리
- leetcode
- 우분투
- 편스토랑 우승상품
- PYTHON
- 프로그래머스
- Kaggle
- Today
- Total
솜씨좋은장씨
[BaekJoon] 10425번 : 피보나치 인버스 (Python) (feat. ChatGPT) 본문
[BaekJoon] 10425번 : 피보나치 인버스 (Python) (feat. ChatGPT)
솜씨좋은장씨 2023. 3. 30. 23:55
코딩 1일 1문제! 오늘의 문제는 백준의 피보나치 인버스 입니다.
👨🏻💻 문제 풀이
피보나치 수열을 만드는데
내가 현재 입력 받은 수 중에서 가장 큰 수 보다 더 큰 수가 만들어지면 수열 생성을 종료하였습니다.
이렇게 만들어진 피보나치 수열을 활용하여
각 피보나치 수열의 숫자 값을 Key 로 해당 숫자가 피보나치 수열에서 몇번째 값인지 나타내는 값을 Value 로 하는
fibo_dict 를 만들어주었습니다.
이렇게 미리 피보나치 수열을 구해둔 이유는 매숫자 입력 요청마다 피보나치 수열을 다시 구하게 되면
너무 비용이 큰 것 같아서 미리 피보나치 수열을 구해서 저장해두도록 하였습니다.
마지막으로 입력 받은 각 숫자를 key 값으로 아까 만들어 둔 fibo_dict 에서 값을 하나씩 꺼내오면 끝!
이렇게 푸니 792ms 의 시간을 사용했습니다.
👨🏻💻 코드 ( Solution ) - SOMJANG
def fibo_nums(max_n):
fibo_dict = {}
fibo = [0, 1, 1]
idx = 3
while True:
fibo_num = fibo[idx-1] + fibo[idx-2]
if fibo_num > max_n:
break
fibo.append(fibo_num)
idx += 1
for v, k in enumerate(fibo):
fibo_dict[k] = v
return fibo_dict
def fibo_inverse(fibo_dict, n):
return fibo_dict[n]
if __name__ == "__main__":
fibo_dict = fibo_nums(max_n=pow(10, 21000))
for _ in range(int(input())):
fibo_num = int(input())
print(fibo_inverse(fibo_dict=fibo_dict, n=fibo_num))
👨🏻💻 문제 풀이 - ChatGPT - 1회차 - 그냥 풀어줘
그제까지는 영어로 영어문제를 풀어달라고 했으면 이번에는 한글로 한글 문제를 풀어달라고 요청해보았습니다.
ChatGPT 의 풀이와 코드는 아래와 같습니다.
해당 문제는 주어진 피보나치 수열에서 n을 찾는 문제이다. 이를 해결하기 위해서는 각 피보나치 수열을 계산해가면서 n과 일치하는 경우 해당 인덱스를 출력하면 된다.
먼저 피보나치 수열을 계산하는 함수를 구현해보자.
def fibonacci(n):
if n == 0:
return 0
elif n == 1:
return 1
else:
return fibonacci(n-1) + fibonacci(n-2)
위 함수는 재귀적으로 피보나치 수열을 계산하는 함수이다. 그러나 이 함수는 입력 범위가 크기 때문에 시간 복잡도가 매우 크다. 따라서 더 효율적인 방법을 찾아야 한다.
피보나치 수열의 각 항은 이전 두 항의 합이므로, 현재 항을 계산하기 위해서는 이전 두 항의 값을 알고 있어야 한다. 따라서 이전 두 항의 값을 저장하고 있으면서 계산해나가는 방법이 더 효율적이다. 이를 위해 리스트를 사용할 수 있다.
def fibonacci(n):
fib_list = [0, 1] # 초기값 설정
while True:
# 리스트에 저장된 마지막 두 항의 합을 계산하여 리스트에 추가
next_fib = fib_list[-1] + fib_list[-2]
if next_fib > n: # 찾고자 하는 값보다 크면 종료
break
fib_list.append(next_fib)
return len(fib_list) - 1 # 인덱스는 0부터 시작하므로 1을 빼줌
위 함수는 입력으로 주어진 값보다 작거나 같은 피보나치 수열을 계산하면서 리스트에 추가하다가, 주어진 값보다 커지면 종료하고 리스트의 길이에서 1을 빼서 인덱스를 출력한다
이제 주어진 입력에 대해서 위 함수를 적용하여 출력하면 된다.
t = int(input()) # 테스트케이스 개수 입력
for _ in range(t):
n = int(input()) # 피보나치 수열 값 입력
print(fibonacci(n))
👨🏻💻 코드 ( Solution ) - ChatGPT - 1회차 - 그냥 풀어줘
def fibonacci(n):
fib_list = [0, 1] # 초기값 설정
while True:
# 리스트에 저장된 마지막 두 항의 합을 계산하여 리스트에 추가
next_fib = fib_list[-1] + fib_list[-2]
if next_fib > n: # 찾고자 하는 값보다 크면 종료
break
fib_list.append(next_fib)
return len(fib_list) - 1 # 인덱스는 0부터 시작하므로 1을 빼줌
if __name__ == "__main__":
for _ in range(int(input())):
fibo_num = int(input())
print(fibonacci(n=fibo_num))
이 방법은 입력 받은 수가 있을때마다 피보나치 수열을 다시 구하므로 소요되는 시간이 훨씬 더 길었습니다.
제가 풀었을때는 792ms -> ChatGPT 의 첫번째 풀이는 1464ms!
👨🏻💻 문제 풀이 - ChatGPT - 2회차 - 더 효율적인 코드 부탁해
위에서 제시한 함수는 간단하지만, 입력 범위가 커질수록 계산 속도가 느려질 수 있다는 단점이 있습니다. 더 효율적인 알고리즘으로는 "행렬 거듭제곱"을 이용하는 방법이 있습니다.
피보나치 수열을 다음과 같이 행렬로 나타낼 수 있습니다.
[F_n ] [1 1]^n-1 [F_1 ]
[F_n-1] = [1 0] x [F_0 ]
위 행렬식에서 n 번째 피보나치 수열 값을 구하기 위해서는 n-1 번 거듭제곱을 구한 후
F_1 과 F_0 값을 행렬에 곱하면 됩니다. 이를 행렬 거듭제곱 알고리즘을 이용하여 빠르게 게산할 수 있습니다.
import numpy as np
def fibonacci(n):
# 피보나치 수열의 초기값을 행렬로 나타냄
fib_matrix = np.array([[1, 1], [1, 0]])
# (n-1)번 거듭제곱을 구함
fib_matrix_n = np.linalg.matrix_power(fib_matrix, n-1)
# 결과값을 계산하여 반환
fib_n = fib_matrix_n[0][0]
return fib_n
위 코드에서 numpy 모듈의 array 와 linalg.matrix_power 함수를 사용하여 행렬 거듭제곱을 구합니다.
linalg.matrix_power 함수는 행렬과 거듭제곱 횟수를 입력으로 받아 행렬 거듭제곱 값을 반환합니다.
👨🏻💻 코드 ( Solution ) - ChatGPT - 2회차 - 더 효율적인 코드 부탁해
import numpy as np
def fibonacci(n):
# 피보나치 수열의 초기값을 행렬로 나타냄
fib_matrix = np.array([[1, 1], [1, 0]])
# (n-1)번 거듭제곱을 구함
fib_matrix_n = np.linalg.matrix_power(fib_matrix, n-1)
# 결과값을 계산하여 반환
fib_n = fib_matrix_n[0][0]
return fib_n
if __name__ == "__main__":
for _ in range(int(input())):
fibo_num = int(input())
print(fibonacci(n=fibo_num))
이렇게 numpy 와 행렬 곱을 활용하여 문제를 풀어주었습니다.
하지만 백준이 numpy 와 같은 라이브러리가 존재하는 코드는 처리가 불가하므로
이 코드가 문제안에 존재하는 모든 케이스를 만족할 수 있는지 체크할 수는 없었습니다.
'Programming > 코딩 1일 1문제' 카테고리의 다른 글
[Programmers] 2차원으로 만들기 (Python) (feat.ChatGPT) (0) | 2023.04.02 |
---|---|
[BaekJoon] 3107번 : IPv6 (Python) (feat. ChatGPT) (1) | 2023.04.01 |
[leetCode] 796. Rotate String (Python) (feat.ChatGPT) (0) | 2023.03.28 |
[leetCode] 2490. Circular Sentence (Python) (feat.ChatGPT) (0) | 2023.03.27 |
[leetCode] 2215. Find the Difference of Two Arrays (Python) (feat.ChatGPT) (0) | 2023.03.26 |