https://www.acmicpc.net/problem/1005 1005번: ACM Craft 첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N과 건물간의 건설순서 규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부 www.acmicpc.net 풀이 문제를 읽고나서 위상정렬 알고리즘임을 어렵지않게 알 수 있었다. 최소 건설 시간을 측정하기 위해 다이내믹 프로그래밍을 사용할 것이다. 건물 완성까지의 최소 시간을 구하기 위해서는 다음과 같은 말이 성립된다. - 선행 건설 되어야하는 건물이 존재한다면 후행 건설을 실시 할 수 없다. - 이를 위해서는 선행 건설 되어야하는 건물이 모두 건설되어야 한다는 얘기이다. - 선행 건설이 없는 건물..

https://www.acmicpc.net/problem/2473 2473번: 세 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 3 이상 5,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 www.acmicpc.net 풀이 투포인터 문제인 용액 시리즈이다. 3개의 용액의 값을 합한 값이 최대한 0에 가깝게 나오도록 용액을 고른 뒤. 값을 오름차순으로 출력하는것이 문제의 목표이다. 1개의 용액은 완전탐색을 통해서 뽑고 나머지 2개의 용액은 투 포인터로 뽑아줄 것이다. 투 포인터 알고리즘 https://sunghyun98.tistory.com/25 [알고리즘] 투 포인터 투 포인터 알고리즘은 ..

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