접근 최대값을 구하는 문제. 배열을 만들어서 dp[i][j]일때의 최대값을 dp[i][j]에 저장하자. dp[i-1][j-1], dp[i-1][j]가 각각 해당자리의 최대값이라면 dp[i][j] = max(dp[i-1][j-1], dp[i-1][j]) + cost[i][j] 가 된다. 해당 점화식을 보면 dp[i][j]를 구하기위해 dp[i-1] 만 필요하니 dp테이블을 모두 만드는것이아닌 1차원 2개만 만들면 메모리를 아낄 수 있다. 속도적인 측면에서는 그냥 배열을 쓰는게 좋겠지만 메모리를 절약하기 위해 1차원 배열 2개만을 이용해서 구현할 생각을 했다. 나의 코드 import sys input = sys.stdin.readline n = int(input()) dp = list(map(int,inpu..

접근 처음 설명에 나와있는대로 식이 주어질때 식에 괄호를 치고 연산자를 빼낼생각을 했다. 하지만 이렇게 구현할 생각을 하니 연산자를 빼낼 때 관호의 개수도 세면서 너무 코드가 복잡해지고 시간복잡도도 매우 안좋을거같다고 생각했다. 두 번째로 생각한 방법은 알파벳과 연산자를 따로 모아 이를 더해서 결과를 만들어낼 생각을 했다. 시간복잡도와 구현면에서 매우 좋을거같아서 이방법을 깊게 생각하기 시작했다. 일단 괄호를 생각하면 너무 복잡해서 괄호 없이 생각했다. 1.A*B+C+D (((A*B)+C)+D) AB*C+D+ 2.A+B+C*D ((A+B)+(C*D)) AB+CD*+ 3.A+B*C*D (A+((B*C)*D)) ABC*D*+ 4. A+B-C+D (((A+B)-C)+D) AB+C-D+ 5. A+B*C+D ((..

접근 특정한 노드에서 특정 노드까지 가는 최소 비용을 구하는 문제이다. 출발점에서 도착점까지 갈 수 있는 경우만 입력으로 오니 따로 예외처리를 신경쓰지 않고 다익스트라 알고리즘을 사용할 생각을 했다. 나의코드 import sys from heapq import heappush, heappop input = sys.stdin.readline n = int(input()) m = int(input()) INT = int(10e9) G = [[] for _ in range(n+1)] for i in range(m): s, f, value = map(int,input().split()) G[s].append((value,f)) def dik(start,finish): d = [INT] *(n+1) H = [] ..

접근 기존 문제를 풀면서 다익스트라 알고리즘에 익숙해졌다. 익숙해진 다익스트라 알고리즘으로 접근했다. 해당 문제에서 내가 주의있게 본 부분은 웜홀은 시간이 줄어든다는 것, 즉 음수의 가중치가 있다는 점이었다. 다익스트라 알고리즘에 대해 생각해보면 전통적인 방법, heap을 사용하는 방법, heap을 사용하는 방법에서 재방문을 허용하는지, 하지않는지 3가지 정도 방법을 나뉜다. 나는 보통 heap을 사용하며 재방문을 허용하는 방식으로 변형해서 다익스트라 알고리즘을 사용한다. 가중치가 그리디한 방식으로 주어질 때 동일한 성능을 보이고 만약 가중치가 무작위로 주어지는 경우까지 답을 구할 수 있기 때문이다. 음의 가중치가 주어지는 경우에도 성능은 좋지 않지만 (처음 최단거리라고 생각하고 관련된 edge를 모두 ..

접근 다익스트라 알고리즘을 이용해 특정 노드에서 특정 노드까지의 최단거리를 구한다. 나의 코드 import sys input = sys.stdin.readline from heapq import heappop,heappush v,e = map(int, input().split()) INF = sys.maxsize start = int(input()) G = [[] for _ in range(v+1)] def dik(start): d = [INF] * (v+1) H = [] heappush(H,(0,start)) d[start] = 0 while H: value,v1 = heappop(H) if d[v1] < value: continue for value2,v2 in G[v1]: nv = value+val..

접근 큰수의 제곱문제. 연산 횟수를 줄이는 문제인데 12^4 을 (12^2)^2 이런식으로 연산 횟수를 줄일 생각을 했다. 또 중요한 부분이 수를 줄이는 것인데 A**B의 결과에 C를 나누는 것이나. A%C **B나 결과가 같게 나온다는 것을 이용해야겠다는 생각을 했다. 예시 12*12 = 144 144%7 = 4 (12%7) * (12%7) = 25 25 % 7 = 4 나의 코드 import sys input = sys.stdin.readline A,B,C = map(int,input().split()) count = 1 cnt = 0 while B >= 5: if B%2 == 1: count *= A A = (A**2) %C B = B//2 print(((A**B)*count)%C)