https://www.acmicpc.net/problem/2252 2252번: 줄 세우기 첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의 www.acmicpc.net 풀이 위상정렬 알고리즘은 다음과 같다. https://sunghyun98.tistory.com/249 [알고리즘] 위상 정렬 위상 정렬은 방향 그래프의 모든 노드를 방향성을 거스르지 않게 순서대로 나열하는 것입니다. 즉, 어떤 작업을 먼저 해야 다른 작업을 할 수 있는 상황과 같은 "의존성"을 갖는 문제를 표현하고 sunghyun98.tistory.com..

위상 정렬은 방향 그래프의 모든 노드를 방향성을 거스르지 않게 순서대로 나열하는 것입니다. 즉, 어떤 작업을 먼저 해야 다른 작업을 할 수 있는 상황과 같은 "의존성"을 갖는 문제를 표현하고 해결할 때 사용됩니다. 위상 정렬의 전제와 조건 방향 그래프: 위상 정렬은 방향성을 가진 간선으로 이루어진 그래프에서만 수행됩니다. 사이클이 없어야 함: 위상 정렬을 수행할 그래프는 순환이 없어야 합니다. 순환이 있는 경우, 어떤 노드를 먼저 방문해야 하는지 정할 수 없기 때문입니다. 위상 정렬 설명 진입 차수 계산: 각 노드의 진입 차수(들어오는 간선의 수)를 계산합니다. 진입 차수가 0인 노드 찾기: 진입 차수가 0인 노드를 찾고 큐에 넣습니다. 이 노드들은 의존성이 없는 작업이므로 먼저 수행될 수 있습니다. 노..

풀이 플로이드워셜, 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..