w에 -1을 곱해 최단 경로를 구하는 문제로 바꾼다.벨만포드로 그래프를 순회하고 사이클이 있는 지 확인한다.출발지에서 사이클로 갈 수 있고, 사이클에서 도착지로 갈 수 있다면 무한루프가 발생해 답은 -1이 된다.벨만포드로 출발지에서 사이클로 갈 수 있는 지 알 수 있고,역방향 BFS로 사이클에서 도착지로 갈 수 있는 지를 알 수 있다.무한루프가 발생하지 않는다면 경로복원으로 경로를 찾아 출력한다. #include #define ll long long#define X first#define Y second#define fastio ios::sync_with_stdio(0), cin.tie(0);using namespace std;vector > > edges;vector > back_edges;int vi..
구간 합(Prefix sum) 의 응용 (부분 배열의 합 A 찾기)
코드포스 문제를 풀어보는 도중 구간합을 약간 응용한 문제를 발견했다.https://codeforces.com/contest/1915/problem/E 배열 A의 구간 합 S에서 S[X]=S[Y]라면, A[x+1] 부터 A[y] 까지의 합은 0이다. 이유 설명두 구간 합 S(X) 와 S(Y) 를 풀어쓰면 (X S(Y) - S(X) = 0 을 풀어쓰면 : 이것을 이용해서 부분 배열의 합이 0인 부분이 있는 지 O(N)에 찾을 수 있다.map 또는 unordered_map 을 이용해서 값 X를 저장하고,X가 이미 존재한다면 부분 배열의 합이 0인 부분이 존재한다는 것을 알 수 있다. 이것을 이용해서 부분 배열의 합이 A인 부분이 있는 지도 확인할 수 있다.S(Y)-S(X) = A라면,
https://www.acmicpc.net/problem/2104 https://www.acmicpc.net/problem/6549 2104 부분배열 고르기구간의 최솟값*구간합을 최대로 만들어야 한다.A[i]를 전체 구간의 최솟값이라고 했을 때, A[i]를 포함하여 최대값을 만들려면 A[i]*전체구간합이 최대값인 것은 자명하다.다른 최대값을 확인하려면 A[i]을 제외한 다른 구간을 봐야만 한다.(~A[i-1]) , (A[i+1]~) 이 두 구간으로 자를 수 있다.이를 반복하면 최대값을 얻을 수 있다. #include #define ll long long#define fastio ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);using namespace std;l..
사전 문제사전문제는 총 2문제가 출제되었다.두 문제의 AC 여부, AC 개수가 같다면 시간의 합으로 등수를 매기기에 최적화도 필요하다.1번은 구현문제였고, 2번은 자료구조를 사용하는 문제였다. 1번은 https://www.acmicpc.net/workbook/view/1152 시리즈와 유사한 빡구현 문제였다.나는 구현에 약했지만 문제 풀이 시간이 3일이나 주어졌기 때문에 몇 십번의 디버깅 끝에 해결하였다.난이도는 solved.ac 기준 골드 2~3 2번은 자료구조 응용 문제였다.난이도는 solved.ac 기준 골드 5~실버 2 일정과 문제 난이도5주간 교육이 진행된다.주말을 제외한 매일 개념강의를 들어야 한다.그 뒤, 해당 알고리즘/자료구조를 단순히 구현하는 문제와 응용 문제를 풀어야 한다.응용 문제는..