무딘붓의 코딩기록

🤔 문제 https://www.acmicpc.net/problem/7570  🔍 문제 풀이 과정N=100만이고, N log N ~ 2000만이므로 O(NlogN) 시간 내에 풀어야 하는 문제입니다. 처음 봤을 때 떠오른 방식은 최장 증가 부분수열(LIS) 이었습니다. (처음 풀이 코드 - 실패)import sysinput = sys.stdin.readlinen = int(input())data = list(map(int, input().split()))# target 보다 작은 값 중 가장 큰 값의 index 반환def binary_search(array, target): start, end = 0, len(array) - 1 result = -1 while start = len(dp..

🤔 문제 https://www.acmicpc.net/problem/1003  🔍 문제 풀이 과정 전형적인 dp 문제입니다. dp[n]에 fibonacci(n)을 호출했을 때, 0과 1이 각각 몇 번 출력되는지 저장하도록 해보겠습니다.배열의 첫 원소는 0이 출력되는 횟수, 두 번째 원소는 1이 출력되는 횟수를 저장하는 식으로 구현하겠습니다. 먼저 손으로 dp[0]부터 값을 채워보면서 규칙을 찾아보겠습니다. dp[0]과 dp[1]은 예시에서도 나와있듯이 [1,0]과 [0,1]입니다.dp[2]는 dp[0]과 dp[1]을 호출하므로 두 값을 합한 값인 [1,1]이 되고,마찬가지로 dp[3]도 dp[1]과 dp[2]를 합한 값이 됩니다. dp[i][0] = dp[i - 1][0] + dp[i - 2][0]dp..