[leetcode] 787 cheapest flight within stops (벨만포드)

문제설명최대로 거칠 수 있는 노드의 수가 제한되어 상태에서 출발지부터 목적자까지 최단거리를 구한다. 예를 들어  아래와 같은 그래프에서 노드0에서 노드3까지 최대 1노드만 거쳐서 갈 수 있는 최단거리는 0->1->3 의 경로로 가는 700이 정답이다.(0->1->2->3 으로 가면 400으로 더 적지만, 이는 두개의 노드를 거쳐야 한다) 문제풀이밸만포드를 이용한다.벨만포드는 음의 가중치가 있는 그래프에서 최단거리를 구할 수 있는 알고리즘인데, 다음과 같은 특징으로 이 문제에서 사용할 수 있다.1. 노드 수 만큼 반복을 진행할 떄,  k번째 반복에서 k번째로 가까운 노드의 최단거리가 찾아짐이 보장된다.2. k보다 더 멀리있는 노드에 대해서는 k개의 노드를 거쳐서 갈 수 있는 최단거리가 찾아짐이 보장된다...

그래프알고리즘 - minium height trees리트코드 310번 minimum height trees, 그래프 알고리즘 문제트리가 주어질 때 최소자식래밸을 가지는 루트노드를 모드 찾는다.ex1)위와 같은 트리에서, 최소 자식레벨(2)을 가지는 루트노드는 1 ex2)위와 같은 트리에선, 최소 자식래밸을(2)를 가지는 루트노드는 3,4. 나머지 노드가 루트노드가 되면 래밸 3이상을 가지게 된다. 풀이이 문제의 핵심은 leaf노드들 부터 하나씩 없애 주는 것이다.그렇다면 리프노드는 어떻게 알 수 있는가?바로 모든 노드들에 대해서 연결된 노드의 개수를 저장하는 리스트(indegree)를 만들고, 연결된 노드가 1이 leaf노드가 된다.이렇게 하나씩 없애주다가 마지막으로 삭제되는 노드들이 정답노드가 된다.따..

문제해석리트코드 685번 문제.rooted tree를 만들기위해 어떤 edge를 제거해야 하는가? (입력값은 항상 rooted tree에서 간선하나가 더 추가된 상태로 들어옴. 만약 제거할 수 있는 edge가 여러개 있다면 입력으로 늦게들어온 edge를 제거함)* rooted tree ? : 루트노드를 제외한 모든 노드가 하나의 부모만을 가지는 트리 생각의 오류처음엔 단순히 유향그래프의 사이클 발견즉시 해당 edge를 정답으로 찾는 알고리즘을 생각했다. 하지만 해당 방법으로는 아래와 같이 사이클이 없는 그래프에서 정답을 찾지 못한다(실제로는 1->3 or 2->3 edge중 나중에 들어온 edge를 찾아야 한다)따라서 이 문제는 문제의 조건을 이용하여 문제를 새롭게 정의해서 알고리즘을 ..

시간복잡도 정리 최악 평균 최선 1. 삽입정렬 n^2 n^2 n 2. 선택정렬 n^2 n^2 n^2 3. 버블정렬 n^2 n^2 n^2 4. 퀵정렬 n^2 nlog(n) nlog(n) 5. 힙정렬 nlog(n) nlog(n) nlog(n) 6. 병합정렬 nlog(n) nlog(n) nlog(n) 1. 삽입정렬 - 앞에서 부터 순차적으로 선택하고 적절한 위치에 삽입 하는 정렬 방법 - 시간복잡도 최악 평균 최선 n^2 n^2 n 2. 선택정렬 - 가장작은(혹은큰) 값부터 선택해서 순차적으로 나열하는 것 - 시간복잡도 최악 평균 최선 n^2 n^2 n^2 3. 버블정렬 - 인접한 두 값을 서로 비교하여 교체하는 작업을 앞에서 부터 순차적으로 진행 - 시간복잡도 최악 평균 최선 n^2 n^2 n^2 4. 퀵정..

주의점 1. dp구성은 다음과 같다 dp[i][j] : 알고력이 i, 코딩력이 j를 얻기위해 걸리는 최소시간 2. 1시간 이후일 때 if now_alp != max_alp: dp[now_alp + 1][now_cop] = min(dp[now_alp][now_cop] + 1, dp[now_alp + 1][now_cop]) if now_cop != max_cop: dp[now_alp][now_cop + 1] = min(dp[now_alp][now_cop] + 1, dp[now_alp][now_cop + 1]) 3. 문제를 이용할 때 * 문제를 통해 개선된 알고력과 코딩력이 max를 넘어가면 안되는것에 주의 for alp_req, cop_req, alp_rwd, cop_rwd, cost in problems:..

다익스트라 응용 문제 다익스트라 알고리즘만 정확히 이해하고 있으면 조금만 응용해서 풀 수 있다. 핵심은 다음과 같다. 1. 경로중 가장 긴 거리를 pq로 관리한다. 기존의 다익스트라는 경로의 합의 최소를 찾지만, 이 문제에서는 경로중 가장 긴 거리의 최소를 찾는다. 즉 기존에 다음과 같이 경로의 합을 pq에 넣는 방식을 addedD=toD+d if addedD

풀이 https://sosoeasy.tistory.com/540 에서 숫자 두개의 특정합을 구했다면 이번문제는 세 숫자를 구한다. 풀이법은 다음과 같다. 1. 제일 왼쪽 숫자(first)를 잡는다 2. first 오른쪽 부분에서 투포인터를 적용한다 first left right -2 6 -97 -6 98 3. 1. first를 전체에 대해서 O(N)번, 2.투포인터 부분이 O(N)이므로 O(N^2)으로 풀린다. (N은 최대 5000이므로) 소스코드 import sys N=int(input()) L=list(map(int,sys.stdin.readline().split())) L.sort() min_sum = 9876543210 ans=[0,0,0] for i in range(N-2): first = ..

풀이 정렬되어 있는 수열에서 특정합을 구하는 문제류는 투포인터를 떠올리자 1. 숫자를 정렬한다. 2. 양쪽 끝에 숫자를 시작 left, right로 잡는다 3. 두 숫자의 합의 절댓값이 min보다 작으면 min을 갱신 4. 두 숫자의 합이 음수이면 left를 +1, 양수이면 right를 -1, 0이면 바로 종료 소스코드 import sys N=int(input()) L=list(map(int,sys.stdin.readline().split())) L.sort() left = 0 right = N-1 min_sum = 9876543210 ans=[0,N-1] while(left

upperbound, lowerbound 1. 정의 upperbound : 처음으로 target 초과의 값이 나오는 것! lowerbound : 처음으로 target 이상의 값이 나오는 것! 2. 예시 target이 3일때 lowerbound numbers upperbound 5 v 3 3 v 3 2 1 3. 문제에서의 활용 대부분의 lowerbound, upperbound 문제는 trade-off 관계에 있는 두 값(1.최소최대화 조건, 2.제한조건)이 주어진다. 이를 표로 정리하면 다음과 같다 lowerbound 1. 최소최대화 조건 2.제한 조건 upperbound c 5 v b 3 3 v a 3 2 1 제한조건=3에서 최솟값을 찾아야 하면 lowerbound를 사용하여 최솟값인 a를 찾고, 최..

풀이 일반적인 dfs문제인데 재귀를 타는 함수의 파라미터의 타입에 따라 시간초과가 발생하는 문제였다. 소스코드1 (시간초과) dfs로 재귀가 들어갈때, visited라는 리스트를 파라미터로 쓰면 함수를 호출할때 계속 리스트를 달고 다녀야 한다 이 부분이 시간이 오래 걸린것으로 보인다 import sys N,M = map(int,input().split()) graph={i:[] for i in range(N)} for i in range(M): a,b = map(int,sys.stdin.readline().rstrip().split()) graph[a].append(b) graph[b].append(a) ans=0 def dfs(node,visited): global ans # print(node,vis..

문제풀이 스벅까지의 거리와 맥날까지의 거리의 합이 최소가 되는 곳을 구하면 된다. 스벅, 맥날은 하나 이상이 있다. 따라서 각각의 집에서 그 집과 가장 가까운 스벅, 맥날까지의 거리를 구하고 그 합이 최소가 되는 집을 찾으면 된다. 도로는 양방향이고 노드사이의 서로 다른 양의 가중치가 존재하므로 다익스트라를 이용하면 된다. 이때 각각의 집에서 가장 가까운 스벅, 맥날까지의 거리만 구하면 된다. 따라서 아래와 같은 순서로 진행한다. 0. 예제 1. 모든 맥날과 가중치 0으로 이은 맥날NODE, 모든 스벅과 가중치 0으로 이은 스벅NODE를 만든다. 2. 맥날NODE에서 각 집까지의 거리, 스벅NODE에서 각 집까지의 거리를 구한다. 주의할점 모든 맥날점과 모든 스벅점을 0의 가중치로 이어서 만든 맥날NOD..

1. 풀이 visit 리스트를 갱신을 queue에서 pop된 다음 해주면 된다. 그렇게 하면 x위치까지 최단시간에 도착하는 경로의 수 만큼 큐에서 pop이 된다. 그러니까 임의의 위치까지 가는 최단경로(최단시간)는 q에 계속 보존이 된다. 일반적인 bfs문제처럼 조건확인후 아래와 같이 visited[loc]==-1일때 visited[loc]=visited[loc+x]+1 하면 처음으로 찾은 최단경로 외에 다른 최단경로는 q에 안들어간다. 2. 소스코드 from collections import deque maxNum=100000 N,K=map(int,input().split()) visited=[-1 for i in range(maxNum+1)] q=deque([(N,0)]) case=0 T=maxNum..

그냥 하라는대로 하면 되는문제인데 인덱스 장난이 심한 문제. 그래서 코딩에서 가장 중요한건 차분히 침착하게 푸는것 이라는것을 다시한번 상기시키는 문제. 침착해 침착해 from copy import deepcopy N=int(input()) P=list(map(int,input().split())) S=list(map(int,input().split())) #카드덱 dq=[i for i in range(N)] #현재 플레이어상태 player=[[] for i in range(3)] for i in range(N): p=i%3 player[p].append(i) ini=deepcopy(player) #목표값 target=[[] for i in range(3)] for i in range(N): target[..

1. 풀이 제일왼쪽열, 제일 위쪽 행의 값이 주어지고, 다른 자리는 왼,왼위,위 중 가장 큰 수가 들어오면 되는 조건을 보면 아래와 같은 점화식이 만들어진다. L[i][j]=max(L[i-1][j],L[i-1][j-1],L[i][j-1]) 위의 점화식을 만든것 만으로 뭔가 대단한걸 생각해낸 것 같아서 정답인줄 알았지만 시간초과이다. (N=1,000,000) 핵심은 주어지는 왼쪽열, 위쪽행의 값들이 순차적으로 커진다는 것이다. 즉 점화식의 결과는 반드시 아래와 같아진다는 것이다. max(L[i-1][j],L[i-1][j-1],L[i][j-1])=L[i-1][j] 그러니까 0열을 제외한, 즉 1열보다 뒤에 있는 모든 행들은 0행의 값들을 그대로 받을 수 밖에 없다. 따라서 0열과 0행을 다 누적해서 더해주고..

1. 첫번째 풀이 당연히 아래처럼 itertool써서 모든 조합을 전부 구하면 그냥 짜면 시간초과가 난다 from itertools import combinations N=int(input()) L=list(map(int,input().split())) ans=0 for i in range(2, N+1): comb=list(combinations(L,i)) for tup in comb: ans+=max(tup)-min(tup) print(ans) 2. 두번째 풀이 문제에서 주목할 점은 "가장 큰 수"와 "가장 작은수"의 차 만을 구해주면 된다는것. 따라서 숫자를 두개씩 뽑아서 하나는 가장 큰수, 하나는 가장 작은수 로 두고, 그 사이의 숫자의 개수만큼 경우의 수를 곱해주는 식으로 구한다. 아래의 예를 통..

1. 풀이 최대유량을 구해주기 위해선, 시점부터 종점까지 (1)가능한 경로와 경로상의 최소 유량 찾기, (2)현재상태를 업데이트 하는 과정을 더이상 가능한 경로가 없을 때 까지 해주면 된다. 각각의 과정에 대한 구체적인 설명은 다음과 같다. (1) 가능한 경로와 그때의 유량 찾기 - bfs 경로를 찾을 때는 bfs로 탐색을 한다. 이때 한번 탐색한 노드는 다시 탐색하지 않기 위해 (흔히 bfs문제를 풀 때 하는) visited노드로 관리를 해줘야 한다. 이때 단순히 방문하면 1, 그렇지 않으면 0으로 하는게 아니라 해당 노드의 경로상의 직전의 노드를 저장해놓는다 (그래서 이름도 visited가 아니라 prev로 한다). 왜냐하면 (2)현재상태를 업데이트 에서 경로를 따라가며 상태를 업데이트 해야 하기 때..

1. 풀이 아래와 같은 2번조건이 네트워크를 복구해서 통신이 가능하도록 만드는 것도 중요하지만, 해커에게 공격을 받았을 때 보안 패킷을 전송하는 데 걸리는 시간도 중요한 문제가 된다. 따라서 슈퍼컴퓨터가 다른 컴퓨터들과 통신하는데 걸리는 최소 시간이, 원래의 네트워크에서 통신하는데 걸리는 최소 시간보다 커져서는 안 된다. 위와같이 충족되어야 하기 때문에, 다익스트라를 이용하여 그래프를 만들어 나간다. 다익스트라에서 노드들의 거리를 업데이트 할 때, 특정노드의 이전노드도 같이 업데이트 해주며 edge들을 파악해 준다. 다익스트라를 이용해서 mst를 만드는건 어렵지 않은데, 위의 알고리즘을 적용하기 위해선, "다익스트라를 이용해 이은 간선들이 항상 MST를 만든다" 라는 전제조건이 있어야 한다. (1) 이는..

1. 풀이 A열에 있는 기계들을 왼쪽부터 차례대로 B와 매칭시킨다. 이때 매칭된 B의 오른쪽에 있는 기계중에 매칭된 기계의 수가 겹치는 선의 수가 된다. 그 이유는, A의 왼쪽기계부터 차례대로 매칭을 시키기 때문에, B의 왼쪽 기계는 매칭이 되었어도 선이 겹칠일이 없기 때문이다. 이를 그림으로 표현하면 아래와 같다. 따라서 예시를 순서대로 진행하면 아래와 같다. 따라서 답(겹치는 선의 수)은 3이다. 이때 수행해야 할 작업은 아래와 같이 두가지이고 각각을 다음과 같이 해결한다. (1) 현재 매칭중인 기계의 B에서의 위치 => dictionary 자료형 이용 (2) B의 오른쪽에서 이미 매칭이 된 기계의 개수 => 세그먼트트리(구간합) 이용 2. 소스코드 import math import sys N=int..