Problem solving70 누적합과 구간합 알고리즘 배열에서 특정 구간의 합을 구할 때 시간 복잡도를 O(1)로 만들 수 있는 방법 누적합 배열에서 순차적으로 누적해서 합을 저장한다. 1차원 배열 1 2 3 4 5 1 3 6 10 15 for(int i = 1; i > S[i]; S[i] = S[i-1] + S[i]; } 2차원 배열 for (int i = 1; i S[i][j]; S[i][j] += S[i][j - 1] + S[i - 1][j] - S[i - 1][j - 1]; // 중복되는 부분을 한번 제거 } } 예를들어 14의 경우 6(왼쪽) + 3(위쪽) + 6(자신) - 1(대각선)으로 계산해서 나온 결과이다. 구간합 위에서 구한 누적합 배열을 바탕으로 구간합을 구할 수 있다. 1차원 배열 i에서 j까지 구간합 S[j] - S[i-1] 2차원 .. 2023. 7. 31. [BOJ] 1005. ACM Craft (C++) 문제 건설 순서 규칙이 주어졌을 때, 특정 건물을 가장 빨리 지을 때까지 걸리는 최소시간 구하기 생각할 것 순서 규칙이 있으므로 위상정렬 사용해보기 처음 시작할 때 진입차수가 0인 것이 여러개 있다면 여러번 실행해봐야하는가!? 이런식으로 하면 진입차수 0인것과 연결된 정점 모두 판단 못함 정점번호마다 누적된 건설 시간을 더하고 비교하면서 최댓값을 넣기 코드 #include #include #include using namespace std; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int T, N, K, X, Y, W; cin >> T; while (T--) { // 입력 cin >> N >> K; vector time(N .. 2023. 7. 31. [BOJ] 1774. 우주신과의 교감 (C++) 문제 2차원 좌표에서 이미 연결된 통로가 존재한다. 모든 우주선끼리 연결해야하는데, 추가로 연결해야 할 통로의 길이 합이 최소가 되도록 통로 연결하기 생각할 것 중복된 데이터가 들어갈 수 있음 반례 4 2 1 1 3 1 2 3 4 3 1 4 4 1 정답 : 4.00 union연산을 할 때만 count를 올리도록 코드를 변경했더니 정답이었다 코드 #include #include #include #include #include using namespace std; struct Edge { int start, end; double cost; }; struct cmp { bool operator()(Edge &e1, Edge &e2) { return e1.cost > e2.cost; } }; int find(i.. 2023. 7. 28. [BOJ] 1647. 도시 분할 계획 (C++) 문제 마을은 N개의 집과 M개의 길로 이루어져 있다. 두 개의 분리된 마을로 분할하려고 할 때, 각 분리된 마을 안에 있는 임의의 두 집 사이에는 경로가 항상 존재해야 한다. 나머지 길의 유지비 합의 최솟값은? 생각할 것 모든 마을을 최소값으로 연결하고 가장 긴 하나의 길만 분리하자 크루스칼을 N-2번만 실행하기 코드 #include #include #include using namespace std; struct Edge { int cost, start, end; }; struct cmp { bool operator()(Edge &e1, Edge &e2) { return e1.cost > e2.cost; } }; int find(int a, vector &parent) { if (parent[a] ==.. 2023. 7. 27. 이전 1 ··· 4 5 6 7 8 9 10 ··· 18 다음
