공부공간

https://www.acmicpc.net/problem/1806 1806번: 부분합 문제 10,000 이하의 자연수로 이루어진 길이 N짜리 수열이 주어진다. 이 수열에서 연속된 수들의 부분합 중에 그 합이 S 이상이 되는 것 중, 가장 짧은 것의 길이를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. 출력 첫째 줄에 구하고자 하는 최소의 길 www.acmicpc.net 역시 이어서 투포인터 유형1번문제이다. https://algorithmstudy-mju.tistory.com/120 BOJ - 2003 )..

https://www.acmicpc.net/problem/1644 1644번: 소수의 연속합 문제 하나 이상의 연속된 소수의 합으로 나타낼 수 있는 자연수들이 있다. 몇 가지 자연수의 예를 들어 보면 다음과 같다. 3 : 3 (한 가지) 41 : 2+3+5+7+11+13 = 11+13+17 = 41 (세 가지) 53 : 5+7+11+13+17 = 53 (두 가지) 하지만 연속된 소수의 합으로 나타낼 수 없는 자연수들도 있는데, 20이 그 예이다. 7+13을 계산하면 20이 되기는 하나 7과 13이 연속이 아니기에 적합한 표현이 아니다. 또한 한 www.acmicpc.net 투포인터를 이용해 연속한 소수의 합으로 목표숫자를 만들수 있는지? 없는지 확인하는 문제이다. 만들어야하는 숫자를 N이라고 할때에, N..

https://www.acmicpc.net/problem/2470 2470번: 두 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 1,000,000,000 이하이다. N개의 용액들의 특성값은 모두 다르고, 산성 용액만으로나 알칼리성 용액만으로 입력이 주어지는 경우도 있을 수 있다. www.acmicpc.net 두 용액은 이전 포스트 https://algorithmstudy-mju.tistory.com/120 BOJ - 2003 ) 수들의 합 2 https://www.acmicpc.net/problem/2003 2003번: 수들의 합 2..

https://www.acmicpc.net/problem/1005 1005번: ACM Craft 첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N 과 건물간의 건설순서규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부� www.acmicpc.net 위상정렬과 다이나믹프로그래밍(약간?)이 결합된 문제이다. 빌드와 시간이라는 개념이 등장하여 1 ->2 ->3 , 11->10->3 의 노드 연결정보에서 3의 진입차수가 0 이될때 1->2 / 11->10의 비용중 큰것을 골라야지 다른 빌드에서 걸리는 시간을 커버하면서 진행 할 수 있다. 중간중간 첫 건물이 목표건물인 경우와같이 예외사항을 처리해주면서 진행하면 풀리는 문제.. 위상정렬을 DF..

https://www.acmicpc.net/problem/2003 2003번: 수들의 합 2 첫째 줄에 N(1≤N≤10,000), M(1≤M≤300,000,000)이 주어진다. 다음 줄에는 A[1], A[2], …, A[N]이 공백으로 분리되어 주어진다. 각각의 A[x]는 30,000을 넘지 않는 자연수이다. www.acmicpc.net 투포인터 알고리즘 (Two-Pointer Algorithm)은 배열에 특정 구간에 대해 접근하여 처리할 경우, 시간복잡도를 O(n^2) 에서 O(n) 까지 단축하는 알고리즘이다. 사실 알고리즘 자체는 어렵지 않다. 문제에서 원하는 특정 값을 m이라할때 배열의 인덱스를 가리키는 두개의 포인터변수를 선언한다. 그리고 특정 값보다 크면 첫번째 포인터변수를 증가시키고, 작으면 ..