1. 풀이 (1) 인접해있는 두 행렬부터 비교해가면서 점차 길이를 늘려간다. (2) dp[i][j] : i번째 행렬에서 j번째 행렬까지 곱했을 때 나올 수 있는 최소연산 (3) 점화식(3중포문) for l : i와 j의 차이. 1차이나는 것(인접한것) 부터 시작하여 늘려나간다 for i : 시작점 찾기 (j는 끝점) for k : i와 j 사이에 구분점 선택 (ex l이 4이고, 2~6을 탐색할 때 (2,3:6),(2:3,4:6),(2:4,5:6) 중 가장 작은것을 (2:6)으로 선택) ​ 2. 소스코드 #include #include #include #include using namespace std; // dp[i][j] : i에서 j행렬까지의 곱중 최소연산 int dp[501][501]; // li..

0. 문제 Finn은 편의점에서 야간 아르바이트를 하고 있습니다. 야간에 손님이 너무 없어 심심한 Finn은 손님들께 거스름돈을 n 원을 줄 때 방법의 경우의 수를 구하기로 하였습니다. 예를 들어서 손님께 5원을 거슬러 줘야 하고 1원, 2원, 5원이 있다면 다음과 같이 4가지 방법으로 5원을 거슬러 줄 수 있습니다. 1원을 5개 사용해서 거슬러 준다. 1원을 3개 사용하고, 2원을 1개 사용해서 거슬러 준다. 1원을 1개 사용하고, 2원을 2개 사용해서 거슬러 준다. 5원을 1개 사용해서 거슬러 준다. 거슬러 줘야 하는 금액 n과 Finn이 현재 보유하고 있는 돈의 종류 money가 매개변수로 주어질 때, Finn이 n 원을 거슬러 줄 방법의 수를 return 하도록 solution 함수를 완성해 주세..

제한시간 내에 최대의 모금액으로 이동할 수 있는 방법? ​1. 풀이 (1) dp의 의미 행은 구간, 열은 시간이 되어서 dp[1][1]부터 시작. dp[i][j]의 의미는 i구간안에서 j시간까지 최대 모금액 (2) 점화식 dp[i][j]=max(dp[i-1][j- (i구간에서 도보이동 시간)]+ i 구간에서 도보이동으로 받는 기부금 , dp[i-1][j- (i구간에서 자전거 이동시간)] + i 구간에서 자전거이동으로 받는 기부금) (3) 유의사항 1. [j - (i구간에서 도보이동 시간)]이 음수가 나오면 안된다. 이러면 시작도 전에 출발한게 된다. 2. 2구간이 이상일때부터 dp[i-1][j- (i구간에서 이동시간)] ==0 이되면 안된다. 이는 아직 이전구간에서 이동을 완료하지 않은 상태이기 때문이다..

1. 상하 뒤집기 문제를문제에서는 왼쪽아래부터 오른쪽위 지점까지 이동하는것으로 되어 있으나, 어차피 경우의 수만 구하면되고, 대칭이므로 리스트의 형태에 맞게 왼쪽위(0,0)에서 오른쪽아래(R,C)로 가는것으로 생각한다. ​ 2. 가능한 경우를 삼차원에 저장 연속으로 꺾는것은 안된다. 이는 (이전)과 (이전전)의 이동에 따라 현재의 이동이 제한된다는 것을 말한다. 이를 고려해주기 위해 (i,j)위치에 이전 이동과 이전전 이동을 저장해야한다. 이를 위해 삼차원 배열을 활용한다. 다행히 이동은 최단거리로만 하기 때문에 오른쪽 or 아래로만 이동한다. 즉 가능한 경우의 수는 1) 아래 오른쪽 2) 오른쪽 오른쪽 3) 오른쪽 아래 4) 아래 아래 총 4가지로 볼 수 있다. 만약 상하좌우 모두 움직일 수 있다면 1..

배낭문제의 linear seacher는 다음과 같은 코드로 작성할 수 있다. def maxiValue(volume,index,value): global maxForPrune if index==N: if maxForPrune

1.풀이 재귀로 풀었을때 시간초과가 발생했다 (소스코드1). O(NM)이고 제한시간 5초(C++기준) 이므로 살짝 애매한데 최적화가 잘 안된것 같다. stack으로 풀었고 pypy로 제출하여 정답. (소스코드2) ​ 2.소스코드 (1) 소스코드1 (시간초과) import sys from collections import deque N,M=map(int,input().split()) graph={} for i in range(1,N+1): graph[i]=[] for i in range(M): A,B=map(int,sys.stdin.readline().rstrip().split()) graph[B].append(A) hackCom=0 ans=[] for start in range(1,N+1): visite..

1. 풀이 일반적인 mst문제이고, N개의 노드를 모두 연결하는 edge를 만들어서(nC2개) 크루스칼을 적용하면 정답은 맞지만 시간초과가 발생한다. (소스코드1)​ 시간초과를 줄일 수 있는 방법은 아래의 조건을 이용해서 사용하는 edge의 개수를 줄이는것. (소스코드2) 더보기 행성은 3차원 좌표위의 한 점으로 생각하면 된다. 두 행성 A(xA, yA, zA)와 B(xB, yB, zB)를 터널로 연결할 때 드는 비용은 min(|xA-xB|, |yA-yB|, |zA-zB|)이다. 그리고 위조건을 이용하는 방법은 아래와 같다. (1) 1차원 좌표에서 N개의 점이 있고, 이때 N개의 점으로 mst를 만드는 방법은 왼쪽부터 i번째 점을 i+1번째 점과 연결해나가는 방법이다. (n-1개) (2) 3차원에서도 똑..

1.풀이 (1) 주어진 선후관계만으로 q와 graph를 구성한다 (2) q에 있는 요소 중 가장 작은(가장 쉬운)것을 pop하면서 진행한다 => heap을 쓴다. ​ * 두가지풀이 - 소스코드1(시간초과) : toNode와 fromNode를 사용. fromNode를 하나씩 삭제하고 fromNode가 비어있을때 pq에 넣음 - 소스코드2 (통과) : toNode와 들어오는 노드의 개수(cntParent)를 사용. cntParent 0이 될때 pq에 넣음 ​ 2. 소스코드 (1) 소스코드1 (python3 시간초과) import heapq N,M=map(int,input().split()) fromNode={} toNode={} for i in range(1,N+1): fromNode[i]=[] toNode..

1. 풀이 (1) 늦게 끝낼 수 있는 일부터 탐색하여 최대한 늦게 시작한다. (2) (1)에서 탐색한 일이 이전의 일의 데드라인에 영향을 주면, 이전의 일을 영향받는만큼 늦게 시작한다. 2. 소스코드 N=int(input()) L=[] for i in range(N): L.append(list(map(int,input().split()))) def returnSecond(L): return L[1] L.sort(key=returnSecond) preStart=L[N-1][1]-L[N-1][0] for i in range(N-2,-1,-1): if preStart

1. 풀이 모든 문제는 푸는데 1시간이 걸리기 때문에, 컵라면을 가장 많이주는걸 그리디하게 고르면 된다. 이때 문제마다 데드라인이 다르기 때문에 시간을 뒤에서부터 1시간 단위로 탐색하면서 먼저 끝나는 일 중에 컵라면을 많이 주는 것부터 차례대로 수행하면 된다. 2. 소스코드 from collections import deque import heapq N=int(input()) L=[] for i in range(N): L.append(list(map(int,input().split()))) # t시간까지 해야되는거 pq에추가 def addPQ(t): while(L): dead,cup=L.pop() if dead==t: heapq.heappush(cupPQ,-1*cup) else: L.append([dea..

1. 풀이 (1) 주유소의 위치를 기준으로 가까운 순으로 정렬을 한다. (2) 현재위치에서 최대로 갈 수 있는 위치를 확인한다 - 갈 수 있는 위치가 도착지점을 넘으면 -> 종료 - 넘지 않으면 -> 갈 수 있는 위치까지의 주유소 중 가장 주유를 많이 할 수 있는 곳에서 주유 (3) 주유한 만큼 위치이동 (4) (2),(3)을 반복 2. 소스코드 import heapq import sys from collections import deque N=int(input()) point=[] for i in range(N): a,b=map(int,sys.stdin.readline().rstrip().split()) point.append([a,b]) L,P=map(int,input().split()) point...

1. 풀이 어떤 node의 k번째 최단경로는 아래의 다익스트라구조에서 [구역1]에 해당하는부분에 k번째로 방문됐을때에 해당된다. while(dij): nowDist,nowNode,isCon=heapq.heappop(dij) if nodeDist[nowNode]

1. 풀이 플로이드와샬을 이용해서 사이클을 구한다. 처음에 i->i로 가는 가중치를 INF로 주고, 플로이드와샬을 한번 수행한 뒤, i->i 값이 변해있으면 i->i로 가는 사이클이 존재한다는 뜻. 이때 가중치가 사이클 도로의 합이므로 그중 최소를 찾는것이 정답이 된다. ​ 2. 소스코드 import sys INF = 9876543210 V, E = map(int, input().split()) L=[[0 for j in range(V)] for i in range(V)] for i in range(V): for j in range(V): L[i][j]=INF for i in range(E): a, b, c = map(int, sys.stdin.readline().rstrip().split()) L[a-..

1. 풀이 * 오일러 경로 : 모든 edge를 정확히 1번만 방문하는 연속된 경로 차수가 홀수인 정점이 2개(출발점과 도착점은 각각 차수가 홀수개) ​ * 오일러 회로 : 오일러 경로 중 시작점과 끝점이 같은것 차수가 홀수인 정점이 0개(나갔으면 들어오는 점(or 들어왔으면 나가는점)이 있어야 함) ​ 오일러 회로를 구하는 문제이므로 (1) 모든 정점에서 차수가 짝수임을 확인하고 ​(2)짝수임이 확인되었으면 반드시 오일러 회로가 (어느 정점에서 시작하든) 가능하므로 아무정점이나 시작점으로 잡고 dfs돌림. ​ (2) dfs를 돌릴 때 - 어느방향으로 돌리든 답은 나온다. 따라서 L[nowNode][conNode]-=1을 해주고 다시 +=1을 해줄 필요가 없다. 즉 탐색은 무조건 edge의 개수만큼 한다...

1. 풀이 (1) 입력값 아래의 두 리스트로 그래프를 관리한다 parent[i] : i 노드로 들어오는 노드들을 저장한 리스트 garph[i]: i노드에서 향하는 노드들을 저장한 리스트 이후 정석대로 간선을 삭제한 후, parent[i]가 비어있는 노드들을 차례대로 q에 넣어서 탐색한다. ​ (2) 위상정렬 이때 각 노드의 최소완료시간을 구해야 하기 때문에 ans[toNode]=max(ans[nowNode]+time[toNode],ans[toNode])를 수행해 주어야 한다. ans[i] : i건물까지 만드는데 드는 최소시간 time[i] : i건물을 만드는데 드는 시간 q에서 뽑힌 노드 i의 ans[i]는 최소시간으로 보장된상태이다. 그리고 ans[nowNode]+time[toNode]가 ans[toN..

1.풀이 (1) 플로이드와샬을 이용하여 연결되어있는지를 확인한다. (2) bfs를 통해 연결되어있는 컴포넌트에서 경찰서 건설비용이 가장 작은곳에 경찰서를 짓는다. ​ 위의 방법으로 어거지로 풀었지만 아래와 같이 최적화하여 푸는 방법을 찾아본다. *최적화 풀이 (1) dfs(강연결요소)를 통한 풀이 (2) 유니온-파인드를 이용. ​ 2. 소스코드 (플로이드와샬, bfs) INF=9876543210 N=int(input()) cost=list(map(int,input().split())) L=[] for i in range(N): L.append(list(map(int,list(input())))) def floid(): #초기값 설정 for i in range(N): for j in range(N): if..

1.풀이 모든쌍의 최단거리가 나타나 있고, 간선의 개수를 최소로 해야 한다. 따라서 모든 도시간의 최단거리를 가진 간선이 존재한다고 생각을 하고, L[i][j]=L[i][k]+L[k][j]를 만족하는 간선 i - j 는 k를 거쳐가면 되기 때문에 없애주는 방식으로 진행. 불가능한 경우는 도시i와 도시j의 최단거리 L[i][j] 보다 k를 거쳐가는 L[i][k]+L[k][j] 가 더 작은 경우가 존재하는 경우 ​ 2. 소스코드 import sys N=int(input()) L=[] for i in range(N): L.append(list(map(int,input().split()))) edge=[[1 for j in range(N)] for i in range(N)] for k in range(N): f..

1.풀이 거쳐가는 노드수의 최솟값을 계산해야한다. 하이퍼튜브는 k가지 노드를 모두 연결해주는, 즉 1의 가중치를 가지게 해주는 장치이다. 따라서 아래와 같이 가중치를 주면 하이퍼튜브를 통해서 노드를 연결해주는 그래프를 만들 수 있다. 노드 -> 하이프튜브 : 가중치 1 하이퍼튜브 -> 노드 : 가중치 0​ 이렇게 하면 (노드a->하이퍼튜브->노드b) 의 cost가 1이 되어서 다익스트라 처럼 풀 수 있다. ​ 2.소스코드 import heapq maxNum=9876543210 N,K,M=map(int,input().split()) graph={} for i in range(1,N+M+1): graph[i]=[] for i in range(M): temp=list(map(int,input().split()..