무딘붓의 코딩기록

🤔 문제 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..

📜 문제 https://www.acmicpc.net/problem/2482 🔍 문제 풀이 과정 일단 규칙성을 찾아보기 위해 n=4부터 7, k=1부터 4까지의 값을 손으로 계산해 보았습니다.  풀면서 찾게 된 점화식은 다음과 같습니다.dp[n][k] = dp[n-2][k-1] + dp[n-1][k]예를 들어, 각 색상을 1번부터 n번까지의 번호라고 가정하고 1번과 n번이 연결되었다고 해보겠습니다.n=7, k=3 인 상황에서 가능한 경우는 다음과 같습니다.1 3 61 4 62 4 72 5 73 5 71 3 52 4 6위의 경우를 잘 살펴보면 n=5, k=2일 때 가능한 값에6과 7이 추가된 경우의 수가 있고1 3 + 61 4 + 62 4 + 72 5 + 73 5 + 7n=6, n=3일..

🤔 문제 https://www.acmicpc.net/problem/11726  🔍 문제 풀이 과정  예전에 풀었던 2xn 타일링 문제와 비슷해서 바로 dp 문제라는 것을 떠올릴 수 있었습니다. dp 테이블은 dp[n]이 3*n 크기의 벽을 채울 수 있는 경우의 수로 가정하고 만들었습니다. 규칙을 찾기 위해서 위의 그림처럼 하나씩 경우의 수를 그려가며 풀어보았습니다. 그 결과n=홀수 인 벽은 채울 수 없다.n=2인 경우에는 3가지 경우가 가능n=4인 경우부터는 기존의 조합을 사용하지 않는 2개의 새로운 경우와, 기존의 조합을 활용한 경우의 수가 존재한다.라는 규칙을 찾았습니다. 조금 더 구체적으로 설명하면, n=4 이상일 때 가능한 경우의 수는 다음과 같습니다.기존 경우의 수로 채우지 못하는 2가지 경..