파이썬

지문이 길어서 찾아보고 한다고 이해하는데 반나절은 걸린듯한 문제. 요약하면 a*b^(-1) = a*b^(X-2)%1000000007이므로 a*b^(X-2)%1000000007를 시간 안에 해결해야 하는 문제다. 재귀로 해결했다. S=1000000007 def ans(n,s): return s*mul(n,S-2)%S def mul(b,t): if t==1: return b%S if t%2==0: tmp=mul(b,t//2) return (tmp*tmp)%S else: return b*mul(b,t-1)%S SUM=0 m=int(input()) for _ in range(m): n,s=map(int,input().split()) SUM+=ans(n,s) SUM%=S print(SUM)

행렬 곱셈 이해하는데 시간이 걸렸던 문제... 교육과정에 행렬이 없어서 마주했을때 당황했다. 1 2 3 4 를 제곱했는데 왜 저렇게 되지? 이 생각을 했다. 이 문제를 통해 알 수 있었던 것은 나는 반복문 이해도가 꽤나 떨어지는 편이라는 것이다. 2중까진 가능한데 3중부터 영 별로다. 그래서 플로이드 와샬도 거의 암기식으로 외웠다가 최근에 왜 경유점이 반복문 밖에 존재하는지 이해했다. 분할 정복을 통해서 해결했다. n,t=map(int,input().split()) orgin=[] for _ in range(n): orgin.append(list(map(int,input().split()))) def multiple(m1,m2): res=[[0 for _ in range(n)] for _ in range..

dp지만 4MB 메모리 제한이 있다. dp 배열을 선언하려면, 아니 애초에 입력한 값을 배열에 등록하려면 n의 제한이 100,000까지이므로 4*3*100,000byte가 필요하다. 이건 12MB이므로 진작에 메모리 초과가 일어난다. 3개짜리 배열을 선언해서 해결했다. import sys input = sys.stdin.readline n = int(input()) maxdp=[0,0,0] mindp=[0,0,0] tmp1=[0,0,0] tmp2=[0,0,0] for _ in range(n): a,b,c=map(int,input().split()) for x in range(3): if x==0: tmp1[0]= a+ max(maxdp[x],maxdp[x+1]) tmp2[0]= a+ min(mindp[x..

딱봐도 BFS 냄새가 진하게 나는 문제. 차이점은 외부공기와 내부공기의 구별이다. 힌트는 모눈종이 바깥쪽에는 치즈가 없다는 점이다. 코드 구성 0. (0,0)에서 bfs를 진행시켜 진행된 좌표를 vis에 표기한다. 1. vis와 기존 좌표배열(l)의 합이 0이라면, 내부공기에 해당하므로, 2로 변환해준다. 2. 치즈를 찾는다. 3. 치즈 좌표 중 위아래오른쪽왼쪽을 비교하여 1개 이상의 방향에서 외부공기(0)가 찾아지면 제거한다. 4. 내부공기에 해당하는 좌표를 0으로 바꾸어 준다. 5. 이하 t번 반복하여 합이 0이될때까지 계속한다. 코드 from collections import deque import sys sys.setrecursionlimit(10**5) input=sys.stdin.readlin..

어떤 문제든, 문제를 잘 읽는게 제일 중요하다. 문제를 제대로 안읽어서 BFS로 접근했던 문제 가로, 세로 상황에서 대각선으로 꺾는것을 기준점의 이동 없이 옮기는 줄 알고 여러가지 가능한 경우 중 최단거리의 갯수를 찾는 문제인 줄 알았다. 하지만 이건 DFS이다. 다중 조건 미로찾기라고 생각하면 될 것 같다. 기준점과 움직이는 점을 분리해서 푼 코드이다. import sys input=sys.stdin.readline def bfs(stdx,stdy,mvx,mvy): if mvx==n-1 and mvy==n-1: global c c+=1 return #가로 if stdx==mvx and stdy==mvy-1: if mvy+1

다익스트라 알고리즘에 대한 정확한 이해가 없어서 어려웠던 문제. 이 문제를 통해서 개념을 확실히 익혔다. 다익스트라는 dfs와 비슷한 방식으로 작동한다. 최단 경로는 최단 경로의 합이라는 알고리즘으로 작동한다. 따라서 힙을 통해 구현할 수 있다. 약간 조건이 잔뜩붙은 dfs같은 느낌이다. 시작점에서 최단경로를 찾는다 -> 최단경로를 힙에 넣는다 -> 최단경로를 꺼내어 시작점과 중간 경로까지의 값과 비교한 후에 최단 경로가 더 짧은 경우에만 더 진행한다.(이걸로 시간초과가 갈린다.) -> 현재 저장된 중간경로에서 또 다른 경유 지점까지의 합이 저장된 거리보다 짧을 경우, 저장된 거리를 갱신한다. -> 저장된 거리를 힙에 다시 넣는다. 그리고 이 문제의 경우, 특정한 경로를 지나야 하는데 그 발상을 떠올리지..

n을 입력하면 n줄에 해당하는 모양을 출력하면 되는 문제. 이전까지의 별찍기와는 달랐다. 나는 출력에만 고집해서 시간을 굉장히 많이 썼는데, 그게 상당히 어렵다는 것을 알게됐다. 모양을 배열로 접근해서 풀었어야 하는 문제. 예를 들어 n=3이면 3*5의 배열을 만들어야 한다. * * * * * * * * 그리고 다음 n=6이면, 6*11의 배열을 만들어야 한다. * * * * * * * * * * * * * * * * * * * * * * * * 중간을 기준으로 보면 첫번째 행의 *은 n=6일땐 5, n=3일때는 2이므로, n-1에 위치함을 알 수 있다. 그렇다면 다음 삼각형이 만들어지는 4번째 행의 위치는 어떤가? 첫번째 기준 값에서 각각 2만큼(n//2-1만큼) 떨어져 있음을 알 수 있다. 이를 통해..

플로이드 와샬 알고리즘을 통해 해결했다. 별거 없다. n=int(input()) m=int(input()) road=[[99999999 for _ in range(n+1)] for _ in range(n+1)] for _ in range(m): a,b,c=map(int,input().split()) if road[a][b]>c: road[a][b]=c for t in range(n+1): for x in range(n+1): for y in range(n+1): if road[x][y]>road[x][t]+road[t][y]: road[x][y]=road[x][t]+road[t][y] if x==y: road[x][y]=0 for x in range(1,n+1): for t in road[x][1:]: ..

동전으로 돈만들기. 1,2로 7을 만드는 경우를 살펴보면, 1+6을 만드는 경우의 수 2+5를 만드는 경우의 수가 있다. 그런데 이걸 1과 2를 동시에 진행시키면 중복되는 경우가 세지게 된다. 그래서 결론적으로는 피보나치수열처럼 된다. 아래는 잘못 작성한 코드이다. t = int(input()) for i in range(t): n = int(input()) l = list(map(int, input().split())) m = int(input()) dp = [0 for i in range(m + 1)] dp[0] = 1 for x in range(1, m + 1): for t in l: if x - t >= 0: dp[x] += dp[x - t] print(dp) 이것을 1과 2의 경우를 분리해서 진..

말만 번지르르하지 별거 없다. 파란 영역 중에 제일 큰 계단을 찾으라는 문제. 아직 스위핑을 안배워서 기본 점수만 받아 보았다. 경우에 따라 잘 나눠서 코딩해주면 된다. 1. 이전값 보다 큰 경우 이전 dp값 +1 2. 이전값과 같은 경우 이전 dp + 0 3. 이전값보다 작을 경우 이전 dp값이 현재 높이보다 작은 경우 : 이전 dp+1 이전 dp값이 현재 높이와 같은 경우 : 이전 dp +0 이전 dp값이 현재 높이보다 클 경우 : 현재 높이값 n=int(input()) h=[0] h.extend(map(int,input().split())) dp=[0 for _ in range(n+1)] dp[1]=h[1] for x in range(1,n+1): if h[x]>h[x-1]: dp[x]=dp[x-1..