코딩이 재밌냐

BFS/DFS 좋은 문제 추천 https://won-percent.tistory.com/34?category=1145094 문제 https://www.acmicpc.net/problem/1303 풀이 dfs - 재귀 bfs - 큐 를 이용해서 푸는 것이 일반적이라고 저번 첫 문제 풀때 이야기했다. 이번건 사실 dfs로 푸는줄 알았는데 bfs 였다. 주변에 아군인지 적군인지 알아야하기에 bfs 로 부는것 같다. 저번에 사용했던 *list 를 사용해서 변수를 받아보려했는데 다른 더 편한 방법이 있었다. strip() 를 사용하면 list로 했을때 받아와지는 '/n' 를 없애줬고 편하게 입력값을 원하는 방식으로 받았다. import sys from collections import deque input = s..

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 은 시간 초과가 나와서 크누스 알..

문제 모의고사 수포자는 수학을 포기한 사람의 준말입니다. 수포자 삼인방은 모의고사에 수학 문제를 전부 찍으려 합니다. 수포자는 1번 문제부터 마지막 문제까지 다음과 같이 찍습니다. 1번 수포자가 찍는 방식: 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, ... 2번 수포자가 찍는 방식: 2, 1, 2, 3, 2, 4, 2, 5, 2, 1, 2, 3, 2, 4, 2, 5, ... 3번 수포자가 찍는 방식: 3, 3, 1, 1, 2, 2, 4, 4, 5, 5, 3, 3, 1, 1, 2, 2, 4, 4, 5, 5, ... 1번 문제부터 마지막 문제까지의 정답이 순서대로 들은 배열 answers가 주어졌을 때, 가장 많은 문제를 맞힌 사람이 누구인지 배열에 담아 return 하도록 solution 함수를..

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 ..