공부 기록

✏️ 문제 문제 파악11726번 2xn 타일 의 업그레이드(?)된 문제이다. 11726번 문제와 같이 점화식을 찾는 것이 중요한데 시간 좀 걸렸다... 그래도 풀었으니..!직접 n이 1, 2, 3, 4 일 때 dp(n)의 값을 찾았을 때 1, 3, 5, 11이 나왔다.n = 3일 때 dp(n) = 5인데 이는 dp(n-1) + dp(n-2) + dp(n-2) 의 값과 같은 것을 알 수 있다. 이를 토대로 점화식은 dp(n) = dp(n-1) + (dp(n-2) * 2) 이다.  알고리즘다이나믹 프로그래밍   코드n = int(input())dp = [0, 1, 3, 5, 11]for i in range(len(dp), n+1): dp.append(dp[i-1] + dp[i-2]*2)print(dp[n]..

✏️ 문제 문제 파악이 문제는 출발점을 기준으로 다음을 계산하는 거 보다 도착점을 기준으로 계산하는 게 더 편하게 풀 수 있다.도착점을 기준으로 계산하기 위해 도착점으로 오는 경우는 생각하면 다음과 같다.직전 칸에서 온 경우 (직전 칸을 밟은 경우 필히 3칸 전 칸을 꼭 밟음)stair[n] + stair[n-1] + dp[n-3]전전 칸에서 온 경우stair[n] + dp[n-2]이 두 경우 중 최대가 되는 값을 선택하면 된다.이때 0 도 생각해야 한다. 아니면 IndexError가 발생한다. (내 얘기) 알고리즘다이나믹 프로그래밍   코드n = int(input())stair = [0]for _ in range(1, n+1): stair.append(int(input()))if n == 1: pr..

✏️ 문제 문제 파악n이 1일 때부터 4일 때까지 직접 해보면 다음과 같이 나온다.여기서 점화식을 찾을 수 있는데 피보나치 수열과 같다는 것을 알 수 있다.점화식을 기준으로 코드를 짜면 쉽게 풀 수 있다! 알고리즘다이나믹 프로그래밍   코드n = int(input())ary = [0, 1, 2, 3]for i in range(4, n+1): ary.append(ary[i-1] + ary[i-2])print(ary[n] % 10007)

✏️ 문제 문제 파악문제에서 나온 연산은 3가지이다.3으로 나누어 떨어지면 3 배수로 가는 방법2로 나누어 떨어지면 2 배수로 가는 방법1 차이로 가는 방법연산하는 횟수의 최솟값을 구하므로 해당 값으로 가는 3가지 방법 중 연산이 최소로 되는 값을 출력해야 한다.위의 그림을 기준으로 코드를 짜면 된다.  알고리즘다이나믹 프로그래밍   코드n = int(input())d = [0] * (n + 1) for i in range(2, n + 1): d[i] = d[i - 1] + 1 # 1 차이로 가는 방법, 3번 방법 if i % 3 == 0: d[i] = min(d[i], d[i // 3] + 1) # 3번 방법으로 나온 값과 1번 방법으로 나온 값 중 최솟값을 대입 if i % 2 == 0:..

✏️ 문제 문제 파악처음에는 이중 반복문을 쓸 생각을 못했어서 너무 헤맸다 ㅠㅠㅠ 얼마나 더 풀어야 다이나믹을 쉽게 풀거니!! 이 문제는 단순히 현재 요소에서 앞뒤 요소들과만 비교해야하는 것이 아니라 현재 요소를 기준으로 이전 모든 요소와 현재 요소를 비교해야 하는 문제이다. 특히 기준을 맨 앞 요소로 잡으면 절대 안됨. 맨 앞 요소를 기준으로 삼는다는 말이 전혀 없기 때문!이전의 모든 요소와 비교했을 때 현재 요소가 제일 크면 부분 수열의 요소로 추가할 수 있다. 문제 파악을 기준으로 풀이해보면 다음과 같다.dp는 가장 긴 증가하는 부분 수열의 길이를 저장한다. ary[j]는 ary[i] 이전의 모든 요소를 거쳐가는 변수이다.ary[i] > ary[j] : 현재 요소 ary[i]가 이전 요소들보다 크다..

✏️ 문제 문제 파악조건이 3가지가 있는데 축약해보면 n번 집은 n-1의 집과 색만 같지 않으면 된다. n-1의 집과 n+1의 집의 색은 같아도 상관없다.이전 집의 색만 겹치지 않는 걸 조건으로 문제를 풀이하면 다음과 같다.ary 배열은 하나의 집에 대한 색 비용을 각각 담은 배열이고 dp 배열은 하나의 집에 대한 최소 색 비용의 총 합을 담은 배열이다. 다음 집의 색은 현재 선택할 색의 비용과 다음 선택할 색의 비용의 합이 최소로 되는 것으로 선택해야 한다.이게 무슨 말이냐면 dp 배열의 2행 색을 선택할 때 최소 비용을 고르려고 한다면 1번째 집이 R을 선택했을 시 경우의 수는 2가지R-G : 26 + 60 = 86 R-B : 26 + 57 = 83G와 B 중에 최소인 B를 선택할 것이므로 R-B값을..

✏️ 문제 문제 파악직접 넣어보면 다음과 같이 나온다. ndp(n)개수1dp(1)12dp(2)23dp(3)44dp(4)75dp(5)13 위의 표를 보면dp(n)일 때, 개수 =  dp(n-1) + dp(n-2) + dp(n-3)라는 규칙이 있다는 것을 알 수 있다.이 점화식을 활용하여 코드를 짜면 쉽게 풀 수 있다!  알고리즘다이나믹 프로그래밍   코드t = int(input())dp = [0, 1, 2, 4]for i in range(4, 12): dp.append(dp[i-1] + dp[i-2] + dp[i-3]) for i in range(t): n = int(input()) print(dp[n])

✏️ 문제 문제 파악피보나치 수열은 f(n) = f(n-1) + f(n-2) 이다.이는 즉 f(n)의 f(0) 호출 횟수과 f(1) 호출 횟수는 f(n-1)의 f(0) 호출 횟수과 f(1) 호출 횟수 + f(n-2)의 f(0) 호출 횟수과 f(1) 호출 횟수 라는 것을 의미한다.  직접 값을 찾아보면 다음과 같이 나온다. nf(n)f(0) 호출 횟수f(1) 호출 횟수2f(2)113f(3)124f(4)235f(5)356f(6)58 위의 표를 보면f(n)일 때, f(0) 호출 횟수 =  f(n-1)의 f(0) 호출 횟수 + f(n-2)의 f(0) 호출 횟수 f(n)일 때, f(1) 호출 횟수 =  f(n-1)의 f(1) 호출 횟수 + f(n-2)의 f(1) 호출 횟수이전에 설명한 것과 같이 값이 잘나온다.이..

✏️ 문제  문제 파악인접리스트를 활용해 예제 1과 같은 경우 1과 연결된 2, 3를 배열[1]에 대입하고 2와 연결된 1, 3, 4, 5를 배열[2]를 넣으면서 풀면 된다.처음 찾는 1번을 기준으로 각 숫자의 거리를 visited의 배열에 담는다.그 후 배열의 메소드인 index(), max(), count()를 활용해서 결과를 출력한다. 알고리즘그래프 이론그래프 탐색너비 우선 탐색  코드from collections import dequeimport sysinput = sys.stdin.readlinen, m = map(int, input().split())graph = [[] * (n+1) for _ in range(n+1)]visited = [0] * (n+1)d = 0for _ in range(..

✏️ 문제 문제 파악상하좌우로 인접한 흰색 격자들로 전달될 수 있으므로 다음과 같이 방향 배열을 구성했다.d = [(1, 0), (0, 1), (-1, 0), (0, -1)] 문제에서 전류가 섬유 물질의 가장 바깥쪽 흰색 격자들에만 공급된다고 했으므로 첫 째줄을 돌면서 첫 째줄의 흰색 격자들과 인접해 있는 격자들만 전류가 흐른 것으로 바뀌도록 코드를 짜면 된다.또한 나는 안쪽까지 침투된 건지 아닌 지에 대한 기준을 잘 이해 못했었는데 찾아보니 다들 맨 아래줄의 흰색 격자가 전류가 흘렀는 지 아닌 지를 구분하여 출력하는 것을 볼 수 있었다. 알고리즘그래프 이론그래프 탐색너비 우선 탐색깊이 우선 탐색  코드from collections import dequem, n = map(int, input().spli..