CS log

import sysinput = sys.stdin.readlinen = int(input())arr = list(map(int, input().split()))dp = [[0] * (n + 1) for _ in range(n + 1)]for i in range(1, n + 1): for j in range(1, n + 1): if arr[-i] == arr[j - 1]: dp[i][j] = dp[i - 1][j - 1] + 1 else: dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])print(n - dp[-1][-1])

https://www.acmicpc.net/problem/11726  이 문제에서는 이런 식으로 타일 그림을 그려봤는데, 솔직히 규칙성을 찾기는 어려웠다 ㅠ 그런데 이렇게 마구잡이로 찾지 말고그 직전에 했던 것에 박스를 추가하는 방식을 사용하는 것이다.그래서 발견한 규칙성은 dp[i] = 2*i 길이 직사각형 만드는 방법 수 = dp[i-1] + dp[i-2]*2 N = int(input())# dp 배열 초기화dp = [0]*(N+1)dp[1], dp[2] = 1,3for i in range(3,N+1) : dp[i] = dp[i-1] + dp[i-2]*2ans = dp[N]print(ans%10007)

https://www.acmicpc.net/problem/14501  처음 접근 방식- 수기로 작성해보면서 해보니 "가능한 모든 경우를 다 실행해보고 그 중에서 max를 찾으면 될 수도 있겠다" 싶어서 완전탐색(백트래킹)도 생각났고, - "그림처럼 큰 문제를 여러 방식으로 쪼개는 느낌"이라 dp 도 적용가능하겠다. 라는 생각이 들었다.➡️ 최대 15일까지로 정해져있기 때문에 연산량이 생각보다 그렇게 크지 않을 것이므로 완전탐색과 dp 모두 가능! 상담이 가능한 조건 : 항상 7일 내에 상담이 끝나야 하고, 만약 i일차에 상담을 했다면 T[i]일 동안은 상담이 불가즉, 식으로 표현하면 n 그리고 가장 중요한 수익 ans는 갱신해주면 됨 여기까지는 생각했는데 코드로 구현하는 것이 헷갈렸었음 방법 1) 백트래..

DP란메모리 공간을 약간 더 사용하면 연산 속도를 더 비약적으로 증가시킬 수 있는 방법top down과 bottom up 방식이 있다. + 메모이제이션 기법 대표적인 문제로는 피보나치 수열이전 두 항의 합을 현재의 항으로 설정하는 수열점화식(인접 3항간 점화식)을 이용하여 표현하면, a_n+2 = f(a_n+1 , a_n) = a_n+1 + a_n최종적인 피보나치 수열은 프로그래밍에서는 이를 배열이나 리스트로 표현가능. 수열 자체가 여러 개의 수가 규칙에 따라 배열된 형태를 의미하기 때문이다.f(n)을 표현할 때 f(2),f(1)은 항상 1이므로 호출을 정지한다. 이를 코드로 표현하면 아래와 같다.def fibo(n) : if n==1 or n==2 : return 1 else : fi..

✔️ 풀이 방법n,m을 받은 후 n*n의 graph 표를 만든다.이후 u와 v를 받아서 어떤 간선끼리 연결되어 있는지 graph에 기록한다.연결 요소의 개수를 구하는 것은 인접한 정점으로 이루어진 그래프 개수를 세는 것과 같다. ✔️ 코드import syssys.setrecursionlimit(10**6)n,m = map(int, sys.stdin.readline().split())graph = [[]for _ in range(n+1)]visited = [False]*(n+1)cnt=0for _ in range(m) : u,v = map(int, sys.stdin.readline().split()) graph[u].append(v) graph[v].append(u)# DFSdef dfs..