1223v

https://www.acmicpc.net/problem/1504  2개의 세계선이 존재하는 최단경로 문제이다.다익스트라로1 -> p1 -> p2 -> N1 -> p2 -> p1 -> N의 최단경로를 구하여 최솟값이 최단경로가 된다.import sysinput = sys.stdin.readlineimport heapqN, M = map(int,input().split())graph = [[] for _ in range(N+1)]for _ in range(M): s,e,cost = map(int,input().split()) graph[s].append((e,cost)) graph[e].append((s,cost))p1,p2 = map(int,input().split())def dijkst..

https://www.acmicpc.net/problem/17270 다익스트라를 통한 최단거리 비교 문제이다.여러 조건에 맞추어 진행해야하는 다중 조건 다익스트라 문제이다import sysimport heapqinput = sys.stdin.readlineV, M = map(int,input().split())graph = [[] for _ in range(V+1)]visited = [False] * (V+1)for _ in range(M): start, end, cost = map(int,input().split()) graph[start].append((end,cost)) graph[end].append((start,cost))J,S = map(int,input().split())de..

https://www.acmicpc.net/problem/1253  투포인터 문제이다. 배열에 있는 모든 수를 판단해야 하므로, 모든 수를 for문을 돈다. 이후, 두포인터로 시작점과 끝점을 잡는다.선택된 수의 값을 기준으로 while문을 돌며 투포인터로 해당되는 값을 찾는다찾는중에 만약 target의 index와 겹치지 않는다면 count 값을 늘려주고,만약 둘중 하나라도  target의 index와 start, end중 하나가 겹친다면 ( start, end 중 겹친)값을 늘려준다.import sysinput = sys.stdin.readlineN = int(input())s = sorted(list(map(int,input().split())))count = 0for i in range(N): ..

https://www.acmicpc.net/problem/2211 다익스트라를 통한 최단경로 갱신 가능 여부를 보는 문제이다. 다익스트라의 시작점인 1부터 탐색을 진행한다.heapq를 통해 비용과 시작점을 추가하고, 다익스트라를 진행합니다이때 최소거리로 갱신되는 경우에만 parent 배열에 그 자리를 갱신합니다.import sysinput = sys.stdin.readlineimport heapqN,M = map(int,input().split())graph = [[] for _ in range(N+1)]distance = [float('inf')] * (N+1)parent = [0]*(N+1)for _ in range(M): A,B,C = map(int,input().split()) grap..

https://school.programmers.co.kr/learn/courses/30/lessons/60060?language=python3 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 카카오 블라인드테스트 Lv.4이분 탐색 문제 or 트라이 알고리즘 문제이다.이분탐색은 우선 "?" 때문에 원본 배열과 뒤집은 배열을 나누어 단어의 길이에 맞게 배열을 생성한다.이후, data[len(word)] 처럼 단어의 길이에 맞는 곳에 각각 단어를 넣어준다.이후 이 두 배열을 모두 길이에 맞는 단어들의 배열을 정렬한다.정렬된 배열을 길이에 맞는 곳에 ?는 a와 z로 채운다 이진 탐색을 돌려준다. 이진탐색은 왼..

https://www.acmicpc.net/problem/11657 전형적인 음수 간선 판단 문제이다.벨만포드를 이용하여 내부에서 음수 간선으로 인해 비용 감소가 계속 발생할 경우 -1을 출력하면 된다.import sysinput = sys.stdin.readlineN,M = map(int,input().split())edges = []distance = [float('inf')] * (N+1)def bf(start): distance[start] = 0 for i in range(N): for j in range(M): s,e,cost = edges[j] if distance[e] > distance[s] + cost: ..

https://www.acmicpc.net/problem/13565 위 문제는 아래까지 도착이 가능한지를 확인하는 탐색 문제이다. 해당 문제는 bfs, dfs로 모두 풀 수 있다.dfs 방식import syssys.setrecursionlimit(10**5)input = sys.stdin.readlineN,M = map(int,input().split())s = [list(map(int,input().rstrip())) for _ in range(N)]di = [1,-1,0,0]dj = [0,0,1,-1]def dfs(n,pi,pj): if pi == N-1 and s[pi][pj]==2: print("YES") exit() for i in range(4): ..

https://www.acmicpc.net/problem/10282 기본적인 다익스트라 알고리즘 문제이다.import sysinput = sys.stdin.readlineimport heapqdef dijkstra(graph, start): time = [int(1e9)] * (N+1) time[start] = 0 hq = [] heapq.heappush(hq,(0,start)) while hq: c_time, c_com = heapq.heappush(hq) for s, a in graph[c_com]: if c_time+s endTime: endTime = t return ..

https://www.acmicpc.net/problem/11054 부분 수열 시리즈 문제이다. 당연히 dp 문제이다. 하지만 추가로 조건이증가하는 부분수열 + 감소하는 부분 수열을 더해서 가장 긴 부분 수열을 찾는 것이다.import sysinput = sys.stdin.readlineN = int(input())s = list(map(int,input().split()))reverse_s = s[::-1]dp = [1] * Nreverse_dp = [1] * Nfor i in range(N): for j in range(i): if s[j]  회고.반대로 된 배열을 만들어 하나의 for문으로 하는 것은 좋았으나, 거꾸로 만든 배열을 증가하는 부분수열 + 감소하는 부분 수열 하는 과정..