풀이 플로이드워셜, BFS, 다익스트라 전부가 가능한 문제. - BFS: 예은이의 수색범위를 생각하면서 노드를 방문해야한다. 두 점을 거쳐 지나갈 경우, 합산 필요. - 다익스트라: 한 노드에서 모든 노드까지의 최단거리를 계산하는 알고리즘이기에 for문을 통해서 모든 노드를 다익스트라 알고리즘에 넣어서 돌려야함. - 플로이드워셜: 모든 노드에서 모든 노드까지의 거리를 한번에 구해주는 알고리즘. 저는 플로이드워셜로 문제를 풀어주었습니다. https://sunghyun98.tistory.com/66 [알고리즘] 플로이드 워셜 최단경로 알고리즘이며 모든 노드에서 모든 노드로부터 최단경로를 구할 때 사용하는 알고리즘이다. 플로이드 워셜 vs 다익스트라 저번 시간에 다뤘던 한 지점에서 모든 노드로의 최단경로를 s..

https://www.acmicpc.net/problem/1002 1002번: 터렛 각 테스트 케이스마다 류재명이 있을 수 있는 위치의 수를 출력한다. 만약 류재명이 있을 수 있는 위치의 개수가 무한대일 경우에는 $-1$ 출력한다. www.acmicpc.net 풀이 문제를 읽어보면 두 원의 접점을 계산하는 문제인 것을 알 수 있다. 1) 두 원의 중점의 위치가 같을 경우. - 만일 두 원의 중점이 같은 경우, 반지름이 같다면 접점은 무한하다. 다른경우에는 접점은 0이다. 2) 두 원의 중점의 위치가 다를 경우. - 두 원이 외접하는 경우와, 내접하는 경우. -> 1개 - 두 원의 중점 사이의 거리가 두 원의 반지름을 합보다 클 경우. -> 0개 - 그 외 두 원이 만나는 경우. -> 2개 코드 # 100..

https://www.acmicpc.net/problem/12015 12015번: 가장 긴 증가하는 부분 수열 2 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000) www.acmicpc.net 풀이 기존의 dp로만 풀어주면 시간초과가 일어난다. dp풀이는 N^2의 시간 복잡도를 가지기 때문에 N의 크기가 최대 10^6이기에 1초를 넘어서는 시간초과가 일어난다. 그래서 이분탐색을 이용해서 풀어줘야하는 문제이다. DP 코드(시간초과) n = int(input()) arr = list(map(int, input().split())) dp = [1 for i in range(n)] for i ..

https://www.acmicpc.net/problem/11055 11055번: 가장 큰 증가하는 부분 수열 수열 A가 주어졌을 때, 그 수열의 증가하는 부분 수열 중에서 합이 가장 큰 것을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 인 경우에 합이 가장 큰 증가하는 www.acmicpc.net 풀이 누적합을 구하는 문제이고, 시간을 최소화하기 위해 다이내믹 프로그래밍을 사용할 예정이다. 다음과 같은 문제는 LIS알고리즘을 사용하여 풀 수 있다. 그러나 DP로 문제를 풀어보았습니다. 가장 큰 증가수열을 구하기 위해서 다음과 같이 고려된다. 1) 이전 누적합의 마지막 숫자보다 큰 숫자를 더해서 증가수열을 만든다. 2) 이전 누적합..

https://www.acmicpc.net/problem/9465 9465번: 스티커 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의 www.acmicpc.net 풀이 최대 누적값을 구하는 문제이기에 dp를 사용하여서 시간 소모를 최소화해야한다. 스티커를 찢는 방법은 다음과 같다. 1) 지그재그로 찢는 경우. 2) 한칸 띄고 다른 행의 스티커를 찢는 경우. A라는 스티커의 위치를 잡아놓고 어떤 스티커를 찢어야 A를 찢을 수 있는지 확인해보면 dp점화식을 만들 수 있다. 코드 # 9465번 스티커 t = int(input()) for _ in ra..

https://www.acmicpc.net/problem/18110 18110번: solved.ac 5명의 15%는 0.75명으로, 이를 반올림하면 1명이다. 따라서 solved.ac는 가장 높은 난이도 의견과 가장 낮은 난이도 의견을 하나씩 제외하고, {5, 5, 7}에 대한 평균으로 문제 난이도를 결정한다. www.acmicpc.net 풀이 구현문제로써 반올림을 구현하여 문제를 풀어주었습니다. 주의: round()를 쓰면 안됩니다. round()는 정확한 반올림을 해주는 함수가 아닙니다. 코드 # 18110번 solved.ac import sys def banollim(n): if n - int(n) >= 0.5: return int(n)+1 return int(n) t = int(input()) i..

https://www.acmicpc.net/problem/13549 13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 www.acmicpc.net 풀이 계획 - 가중치가 다르게 주어진 그래프 이동을 하는 문제 - 한 정점에서 다른 모든 정점으로부터의 최단거리 계산 - 다익스트라 알고리즘 적용 코드 # 13549번 숨바꼭질 3 import sys import heapq input = sys.stdin.readline INF = sys.maxsize def rangeValid(v): if 0 dist: if..

https://www.acmicpc.net/problem/1236 1236번: 성 지키기 첫째 줄에 성의 세로 크기 N과 가로 크기 M이 주어진다. N과 M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 성의 상태가 주어진다. 성의 상태는 .은 빈칸, X는 경비원이 있는 칸이다 www.acmicpc.net 풀이 처음에는 어떻게 풀지 고민해보았는데, 문제에서 요구하는 바는 행과 열마다 경비원이 하나씩 존재해야한다는 것이다. 어느 n행과 m열이 주어졌을 때 두 직선의 교점에 경비원이 위치한다면 한 경비원으로도 문제에서 원하는 바를 만족시킬 수 있다는 것이다. 그말은 즉슨 가장 긴 직선의 길이만큼 경비원을 배치해준다면 다른 직선의 경비원 문제는 자연스럽게 해결된다는 것이다. 코드 # 1236번..