https://www.acmicpc.net/problem/9370 9370번: 미확인 도착지 (취익)B100 요원, 요란한 옷차림을 한 서커스 예술가 한 쌍이 한 도시의 거리들을 이동하고 있다. 너의 임무는 그들이 어디로 가고 있는지 알아내는 것이다. 우리가 알아낸 것은 그들이 s지점에서 www.acmicpc.net 풀이 다익스트라 알고리즘을 사용했으며 문제에서 목적지까지 최단경로로 이동하는데 주어진 교차로를 무조건 지나야한다. 출발지 - g - h - 목적지 혹은 출발지 - h - g - 목적지가 출발지 - 목적지까지의 최단경로와 동일하다면 교차로를 지나가는것이다. 다만 교차로를 지나가지않는데도 최단경로 값이 같을 수 있지않나 싶다.(입력값이 그렇게 주어진다면..) 다른분들의 풀이를 보니 지나가야하는 ..

https://www.acmicpc.net/problem/10282 10282번: 해킹 최흉최악의 해커 yum3이 네트워크 시설의 한 컴퓨터를 해킹했다! 이제 서로에 의존하는 컴퓨터들은 점차 하나둘 전염되기 시작한다. 어떤 컴퓨터 a가 다른 컴퓨터 b에 의존한다면, b가 감염되면 www.acmicpc.net 풀이 시작값이 주어졌기에 다익스트라 알고리즘으로 풀어주었다. # 10282번 해킹 import sys import heapq input = sys.stdin.readline INF = sys.maxsize # 다익스트라 알고리즘 def dijkstra(start): q=[] heapq.heappush(q, (0, start)) distance[start]=0 while q: dist, now = he..

https://www.acmicpc.net/problem/18352 18352번: 특정 거리의 도시 찾기 첫째 줄에 도시의 개수 N, 도로의 개수 M, 거리 정보 K, 출발 도시의 번호 X가 주어진다. (2 ≤ N ≤ 300,000, 1 ≤ M ≤ 1,000,000, 1 ≤ K ≤ 300,000, 1 ≤ X ≤ N) 둘째 줄부터 M개의 줄에 걸쳐서 두 개 www.acmicpc.net 풀이 다익스트라 알고리즘 사용 # 18352번 특정 거리의 도시 찾기 import sys import heapq INF = sys.maxsize def dijkstra(start): q = [] heapq.heappush(q, (0, start)) distance[start] = 0 while q: dist, now = he..

https://www.acmicpc.net/problem/1676 1676번: 팩토리얼 0의 개수 N!에서 뒤에서부터 처음 0이 아닌 숫자가 나올 때까지 0의 개수를 구하는 프로그램을 작성하시오. www.acmicpc.net 풀이 팩토리얼 함수 작성 이후에 나온 숫자를 문자열로 만들어서 뒤부터 계산해준다. # 1676번 팩토리얼 0의 개수 def factorial(n): if (n

https://www.acmicpc.net/problem/4150 4150번: 피보나치 수 피보나치 수열은 다음과 같이 그 전 두 항의 합으로 계산되는 수열이다. 첫 두 항은 1로 정의된다. f(1) = 1, f(2) = 1, f(n > 2) = f(n − 1) + f(n − 2) 정수를 입력받아, 그에 해당하는 피보나치 수를 출력 www.acmicpc.net 풀이 1 피보나치 수를 점화식을 사용해서 문제를 풀어준다. # 4150번 피보나치 수 n = int(input()) # dp 생성 fibo = [0, 1] for i in range(2, n+1): fibo.append(fibo[i-1] + fibo[i-2]) print(fibo[n]) 출력결과 풀이 2(시간초과) 재귀함수 사용하게되며 시간초과 일..

https://www.acmicpc.net/problem/1026 1026번: 보물 첫째 줄에 N이 주어진다. 둘째 줄에는 A에 있는 N개의 수가 순서대로 주어지고, 셋째 줄에는 B에 있는 수가 순서대로 주어진다. N은 50보다 작거나 같은 자연수이고, A와 B의 각 원소는 100보다 작거 www.acmicpc.net 풀이 A의 정렬을 내림차순으로 만들어준 뒤 A의 앞부터 끝까지 B의 최댓값과 곱해주는 방법을 이용한다. B의 최댓값은 한번 뽑으면 pop을 통해 지워준다. # 1026번 보물 import sys input = sys.stdin.readline n = int(input()) a_li = list(map(int, input().split())) b_li = list(map(int, input(..

https://www.acmicpc.net/problem/10159 10159번: 저울 첫 줄에는 물건의 개수 N 이 주어지고, 둘째 줄에는 미리 측정된 물건 쌍의 개수 M이 주어진다. 단, 5 ≤ N ≤ 100 이고, 0 ≤ M ≤ 2,000이다. 다음 M개의 줄에 미리 측정된 비교 결과가 한 줄에 하나씩 www.acmicpc.net 풀이 플로이드 워셜 알고리즘을 사용해서 풀어주었다. 블로그 글 참고. https://sunghyun98.tistory.com/66 [알고리즘] 플로이드 워셜 최단경로 알고리즘이며 모든 노드에서 모든 노드로부터 최단경로를 구할 때 사용하는 알고리즘이다. 플로이드 워셜 vs 다익스트라 저번 시간에 다뤘던 한 지점에서 모든 노드로의 최단경로를 sunghyun98.tistory...

https://www.acmicpc.net/problem/13913 13913번: 숨바꼭질 4 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 풀이 숨바꼭질 문제 시리즈의 4편이다. 다른점이 있다면 거쳐온 경로를 출력해야한다는것이다. move 리스트를 만들어서 새로운 점으로 도달하기전에 거쳐온 점을 저장해서 for문으로 출력해준다. 대신 값은 시작점부터 출력해야하기에 reveres를 해주었다. # 13913 숨바꼭질 from collections import deque def bfs(): queue = ..