[백준] 99클럽 코테 스터디 2일차 TIL + 피보나치 비스무리한 수열

오늘의 학습 키워드

메모이제이션, 시뮬레이션

 

오늘의 회고

🌱 오늘의 문제

피보나치 문제의 변형된 문제이다. 피보나치 문제가 특정 위치 n의 값에 대하여 n-1, n-2 연속된 두 값의 합으로 구해나갔다면, 이 문제는 n-1, n-3과 같이 한 칸을 띄운 두 값의 합으로 구하는 문제이다.

이 외의 조건이 크게 달라지는 부분은 없어 기존의 피보나치 구하는 방식으로 구하면 크게 문제될 것이 없다.

 

🌱 나의 시도

입력 값의 최대값이 116으로 크지 않아 복잡한 알고리즘을 사용하기 보다는 짧고 가독성 좋은 코드를 사용하는 것이 좋다는 판단을 했다. 동일한 연산을 반복하지 않으므로 재귀 함수가 불필요하며, 이전 연산 값을 저장해두고 사용할 수 있는 메모이제이션 정도면 충분하다.

 

현재 단계적으로 문제를 풀기 때문에 시간 복잡도는 O(n)으로 계산된다.

'''
- 풀이 방법: 입력 값의 범위가 크지 않아 빠르고 가독성 좋게 푸는 것이 Best
- 풀이 순서
1. 이전 값을 배열에 넣어 둔다. -> O(1)
2. 4번째 값부터 n번째 값까지 순차적으로 값을 구한다 -> O(n)
3. 마지막 값을 출력한다. -> O(1)

-> 최종 시간 복잡도: O(n)
'''
n = int(input())

answer = [0, 1, 1, 1]

for i in range(4, n+1):
    answer.append(answer[i-3]+answer[i-1])

print(answer[-1])

 

 

🌱 새롭게 알게 된 점

뒤늦게 다른 분이 푼 풀이를 보다가 이전 값들을 저장할 필요가 없다는 것을 알게 되었다.

최근 세 개의 값만을 이용하면 되는데, 배열에 모든 값을 저장해 두는 코드는 메모리 측면에서 비효율적일 수 있다는 생각이 들었다.

앞으로는 작은 부분이더라도 꼼꼼하게 코드를 짜려고 노력해야겠다.

 

 

🚀 내일 학습할 것

오늘 정리한 내용에서는 크게 어려운 내용이 없었다.

어제 우선순위 큐 내용이 아직 정리가 덜 되어서 내일은 그 내용을 마무리 한 후, 시간이 남으면 아래 내용을 추가해야겠다.

 

1. 정렬 알고리즘

특히 선택 정렬, 삽입 정렬, 퀵 정렬, 계수 정렬 4가지에 대해서 중점적으로 정리해 볼 예정이다.

2. 이진 탐색

오늘 간단히 탐색이 무엇인지, 그리고 BFS/DFS 가 무엇인지 개념을 정리했다(아직 포스팅은 안 했지만..).

내일은 이진 탐색을 이어서 공부해보려고 한다.

 

 

오늘의 후기

지금까지의 생각으로는 이 문제에 대해 O(n) 보다 더 효율적으로 짤 수는 없을 것 같다. 상수항으로 풀 수식을 도출하기 위해 고민해봤지만 그럴 듯한 규칙성이 없어 보였다. 그럼에도 이상하게 찝찝한 느낌과 함께 더 효율적인 방법이 있었으면 좋겠다는 생각이 든다. ㅋㅋㅋㅋ.

 

예전엔 개념에 대해 제대로 공부하지 않고 코드부터 짰는데, 요즘은 개념 공부를 하다 보니 내가 푸는 풀이에 이름을 붙이고 복잡도를 계산할 수 있게 되었다. 이 과정이 꽤 유익하고 재미가 있다. 조금 더 "안다"고 말 할 수 있게 된 것 같다.

 

욕심내다가 중간에 그만 두는 게, 게으르게 조금씩 꾸준히 하는 것보다 못 하다.

조금 아쉽게 꾸준히, 오래 하자. 그래! 오래 하자! 화이팅이다!