https://www.acmicpc.net/problem/1766 1766번: 문제집 첫째 줄에 문제의 수 N(1 ≤ N ≤ 32,000)과 먼저 푸는 것이 좋은 문제에 대한 정보의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 둘째 줄부터 M개의 줄에 걸쳐 두 정수의 순서쌍 A,B가 빈칸을 사이에 두고 주 www.acmicpc.net 풀이 조건을 다시 정리하자면 1) 문제 번호는 낮을수록 쉬운 문제이다. 최대한 쉬운 문제를 먼저 풀면서 모든 문제를 풀어야한다. 2) 최대한 쉬운 문제를 먼저 푼다는 얘기는 문제번호가 내림차순으로 풀어야하는 조건이 주어질 수 있다는 얘기이다. - 진입차수가 존재하는 노드가 있다는 얘기이다. 3) 진출차수와 진입차수가 존재하지않는 노드와 진출차수는 존재하지만 진입차수가..

https://www.acmicpc.net/problem/2470 2470번: 두 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 1,000,00 www.acmicpc.net 풀이 투 포인터 알고리즘을 사용해서 풀어주었습니다. 정렬되지않은 용액의 값들이 입력값으로 주어지기에 .sort()를 이용해서 정렬해주었습니다. 투 포인터 알고리즘 https://sunghyun98.tistory.com/25 [알고리즘] 투 포인터 투 포인터 알고리즘은 배열에서 두 개의 포인터를 사용하여 특정 목표를 달성하기 위한 기법입니다. 일반적으로 정렬된 배열..

https://www.acmicpc.net/problem/2467 2467번: 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 오름차순으로 입력되며, 이 수들은 모두 - www.acmicpc.net 풀이 투 포인터 알고리즘으로 문제를 풀어주었습니다. 정렬된 용액의 값들이 들어오기에 따로 정렬해줄 필요는 없습니다. 투포인터 알고리즘 https://sunghyun98.tistory.com/25 [알고리즘] 투 포인터 투 포인터 알고리즘은 배열에서 두 개의 포인터를 사용하여 특정 목표를 달성하기 위한 기법입니다. 일반적으로 정렬된 배열에서 특정 조건을 충족하는 요소를 찾거나 연속된 서브 배열..

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..

풀이 플로이드워셜, 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) 이전 누적합..