코딩이 재밌냐

BFS/DFS 좋은 문제 추천 https://won-percent.tistory.com/34?category=1145094 문제 https://www.acmicpc.net/problem/1260 풀이 dfs - 재귀 bfs - 큐 를 이용해서 푸는 것이 일반적이라고 한다. 마지막 (* list) 에서 print(list) # [0, 1, 2] 이렇게 값이 출력된다면 print(*list) # 0, 1, 2 이렇게 값이 출력된다. 처음 알았다. 역시 파이썬 import sys input = sys.stdin.readline N,M,V = map(int,input().split()) graph = [[-1] * (N+1) for _ in range(N+1)] for i in range(M): a,b = ma..

이 알고리즘의 주요 사용- 행렬 곱셈의 연산의 경우의 수 중 최솟값를 구할 때- 꼭 행렬 문제가 아니더라도 각각의 합의 최소비용​행렬은 결합법칙이 존재하는데, 각각 연산횟수가 같으면 좋겠지만, 불행히도 다르다.ABC = (AB)CABC = A(BC)​연쇄행렬 최소곱셈 알고리즘은 아래 법칙을 통해 행렬곱셈의 횟수를 최소로 구할 수 있다.-DP[i][j] = minimum(DP[i][k]+DP[k+1][j]+d[i-1]*d[k]*d[j])​ex)A(20x1), B(1x30), C(30x10), D(10x10) 일때,d0=20, d1=1, d2=30, d3=10, d4=10​1.행렬 A~B까지의 곱의 횟수 : DP[1][2] = minimum(DP[1][k] + DP[k+1][2] + d0*dk*d2)​2.행..

DP 좋은 문제 추천 https://won-percent.tistory.com/entry/%EC%A2%8B%EC%9D%80-DP-%EB%AC%B8%EC%A0%9C%EB%93%A4-%EC%B6%94%EC%B2%9C 문제 https://www.acmicpc.net/problem/11066 풀이 정답 비율이 51.703 % ? 이건 사기다. 난 보자마자 불가능한 문제란 생각이 들었고 나중에 풀이를 봐도 이해가 가질 않았다. 연쇄행렬곱셈과 크누스 알고리즘 이라는 처음 들어보는 것들로 풀어야한다고 했다. 정말 정말 멘붕이었고 정답률도 높아서 더더 멘붕이었다. 무엇보다도 C++로 풀면 크누스 알고리즘으로 풀지 않고 연쇄행렬곱셈 풀이로 풀어도 시간 초과가 뜨지 않는다는데 python 은 시간 초과가 나와서 크누스 알..

DP 좋은 문제 추천 https://won-percent.tistory.com/entry/%EC%A2%8B%EC%9D%80-DP-%EB%AC%B8%EC%A0%9C%EB%93%A4-%EC%B6%94%EC%B2%9C 문제 https://www.acmicpc.net/problem/1520 풀이 이틀 걸려서 이 풀이 저 풀이 보면서 이해하려했던 문제이다. dfs 문제 풀이에 대해선 전혀 몰랐기 때문에 dp + dfs 인 이 문제를 혼자서 푸는건 불가능했을거라고 위로중. 일단 풀긴풀었는데 다음에 다시 보면 모를것 같으니까 다음에 다시 풀어볼 예정이다. 지금껏 놀았으니 힘든건 당연한거라 생각하고 공부해야겠다. import sys def dfs(i,j,m,n): if result[i][j] == 1 : # 이미 방문..

DP 좋은 문제 추천 https://won-percent.tistory.com/entry/%EC%A2%8B%EC%9D%80-DP-%EB%AC%B8%EC%A0%9C%EB%93%A4-%EC%B6%94%EC%B2%9C 문제https://www.acmicpc.net/problem/15486 풀이 max_p[i+1] = max ( max_p[i+1], max_p[i]) 이 부분을 추가 안해줘서 계속 헤맸다. 답 맞는것 같은데 시간 초과가 계속 뜬다.n = int(input()) t=[0 for _ in range(n)] p=[0 for _ in range(n)] max_p=[0 for _ in range(n+1)] for i in range(n): t[i],p[i] = map(int,input().split())..

DP 좋은 문제 추천 https://won-percent.tistory.com/entry/%EC%A2%8B%EC%9D%80-DP-%EB%AC%B8%EC%A0%9C%EB%93%A4-%EC%B6%94%EC%B2%9C 문제 https://www.acmicpc.net/problem/11722 풀이 a : [10, 30, 10, 20, 20, 10] 처음엔 if a[j] > a[i] : dp[i] = dp[j] + 1 로 풀었다. a[i] 보다 큰 것만 찾아서 +1 하다보니 맨 오른쪽 10의 경우, 20을 중복으로 더해서 원하는 답이 나오지 않았다. 이걸 어떻게 해결할까 고민하다가 max 로 풀긴했는데 손으로 일일히 for문을 돌려가면서 이해한거라 자존심 상한다. 아니 잘하는 사람들은 머리 속에서 다 돌아가려나?..

DP 좋은 문제 추천 https://won-percent.tistory.com/entry/%EC%A2%8B%EC%9D%80-DP-%EB%AC%B8%EC%A0%9C%EB%93%A4-%EC%B6%94%EC%B2%9C 문제 https://www.acmicpc.net/problem/11726 풀이 n=1,2,3... 경우의 수를 적다보니 규칙을 발견했다. 이렇게 규칙을 발견하고 푸는게 맞나 싶긴한데 물어볼데가 없다.다른 dp 문제를 더 풀어봐야 감이 올 것 같다.n = int(input()) dp=[1 for _ in range(n+1)] for i in range(2,n+1): dp[i] = dp[i-1] + dp[i-2] print(dp[n]%10007)

DP 좋은 문제 추천 https://won-percent.tistory.com/entry/%EC%A2%8B%EC%9D%80-DP-%EB%AC%B8%EC%A0%9C%EB%93%A4-%EC%B6%94%EC%B2%9C 문제https://www.acmicpc.net/problem/2579 두번째 고비였지만 다행히 넘겼다. 도저히 안풀려서 롤 두 판 했더니 풀렸다. (???) 풀이 n = int(input()) score=[] stair=[0 for _ in range(n)] for i in range(n): score.append(int(input())) stair[0] = score[0] for i in range(1,n): if i == 1: stair[1] = stair[0] + score[1] elif ..

DP 좋은 문제 추천 https://won-percent.tistory.com/entry/%EC%A2%8B%EC%9D%80-DP-%EB%AC%B8%EC%A0%9C%EB%93%A4-%EC%B6%94%EC%B2%9C 문제https://www.acmicpc.net/problem/9095 풀이문제에서 n은 양수이며 11보다 작다. 라고 주어져서 max = 11 로 설정했다.1, 2, 3 의 합으로만 구하면 되는데.... 문제를 대충 읽어서 규칙 찾느라 아주 오래 걸렸다. 그래도 규칙 찾으니까 꽤 간단한 풀이였다 ! 문제를 잘 읽자 ! t = int(input()) n=[] max = 11 # 0 < n < 11 dp=[1 for _ in range(max+1)] dp[2] = 2 dp[3] = 4 for i i..

DP 좋은 문제 추천 https://won-percent.tistory.com/entry/%EC%A2%8B%EC%9D%80-DP-%EB%AC%B8%EC%A0%9C%EB%93%A4-%EC%B6%94%EC%B2%9C 문제https://www.acmicpc.net/problem/1463 풀이문제 풀이 1일차 첫 고비였다. 솔직히 작심일일도 못가서 그만두고싶었다. 혼자 못풀고 다른 코드 참고하고 풀었는데도 이해가 잘 가지 않는다. 다시 와서 봐야지n = int(input()) dp=[0 for _ in range(n+1)] for i in range(2,n+1): dp[i] = dp[i-1] + 1 if i % 3 == 0:dp[i] = min(dp[i//3]+1, dp[i]) elif i % 2 == 0:dp..