시간복잡도 정리 최악 평균 최선 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..

1. 풀이 처음엔 아래와 같은 경우의 수만 생각했지만, 이는 일직선상에서만 적용되는 경우였다. (소스코드1) 즉 2차원의 경우엔 아래와 같은 예외가 존재한다. 따라서 2차원의 좌표평면의 경우는 아래와 같은 경우의 수를 생각할 수 있다. 2. 소스코드 (1) 소스코드1 (경우의 수 오류) import math X,Y,D,T=map(int,input().split()) L=math.sqrt(X**2+Y**2) if L>=D: jump=L//D print("%.10f"%min(jump*T+L-(jump*D),(jump+1)*T)) else: print("%.10f"%min(L,T+D-L,2*T)) (2) 소스코드2 import math X,Y,D,T=map(int,input().split()) L=math.s..

1. 풀이 (1) 숫자를 넣는 방법 숫자를 1부터 차례대로 적절한 위치에 집어넣는다. 숫자를 1부터 집어넣기 때문에 집어넣을 위치 앞에 아직 차지 않은 부분은 무조건 현재넣을 숫자보다 크고, 이미 차있는 숫자는 현재숫자보다 작다. (2) 세그먼트 트리 따라서 숫자가 들어갈 위치를 세그먼트트리를 이용해서 찾는다. 세그먼트트리를 이용해서 구간합을 구해주는데, 이를 이용하여 현재 위치앞에 몇개의 숫자가 있는지를 빠르게 확인해준다. * 처음에 update함수 따로, 위치를 찾는 함수를 따로 구현해서 시간 초과가 떳다(소스코드1). 위치를 찾으면서 바로 수정을 해야 통과한다. 2. 소스코드 (1) 소스코드1 (update함수, 쿼리함수 따로구현, 시간초과) import sys import math def init..

1. 풀이 이 문제에선 "붙어있는 수열에서 최솟값을 찾는 행위" 를 엄청 많이 해야 한다. (= 이를 쿼리라고 한다) 이때 "붙어있는 수열에서 최솟값을 찾는 행위"를 빠르게 하기 위해 세그먼트트리를 사용한다. 이 문제는 너비는 모든 직사각형이 같지만, 높이만 다르기 때문에 연속된 높이들 중 가장 작은 높이가 만들수있는 직사각형의 높이가 된다. 따라서 높이의 최솟값을 세그먼트 트리에 저장한다. 이때 주의할점은 분할 정복을 할 때 최소 높이를 기준으로 좌 우로 계속해서 탐색을 해야 하기 때문에, 최소높이의 인덱스를 알아야 한다는 것이다. 따라서 세그먼트 트리에는 최소높이와 함께 최소 높이의 인덱스도 저장해야 한다. 2. 소스코드 import math import sys sys.setrecursionlimit..