devbelly

문제 www.acmicpc.net/problem/2720 알고리즘 구현 풀이 이 문제는 제가 파이썬 구현 연습을 위해 풀다가 마주한 문제입니다. 구현 외에 짚고 넘어갈 점이 있어 포스팅하겠습니다. 저는 브론즈3이라는 점에서 구현 외에 별 다른 부분은 신경쓰지 않고 풀었던 문제입니다. 하지만 조금 생각해본다면 수상한 점을 발견할 수 있습니다. 문제 내용은 거슬러 주는 동전의 갯수를 최소화 하는 문제입니다. 그리디 또는 다이나믹 프로그래밍을 다룰 때 많이 등장하는 주제중 하나입니다. 그리디로 문제를 해결하려고 동전의 값을 보았지만 거슬러 줄 수 있는 동전의 값은 25원 10원 5원 1원 입니다. 동전들 끼리 배수관계를 만족하지 못하므로 (25원과 10원) 다이나믹 프로그래밍을 이용해 해결하자! 라고 생각할 ..

문제 www.acmicpc.net/problem/10999 알고리즘 lazy propagation 풀이 구간 갱신, 구간 쿼리를 요구하는 문제입니다. 일반적인 점 갱신, 구간 쿼리를 이용하는 세그먼트 트리를 활용한다면 구간 갱신을 처리할 때, 구간의 길이에 비례한 시간복잡도를 요구합니다. 하지만 lazy propagation을 활용하면 구간 갱신또한 $O(logN)$에 훌륭하게 처리가능합니다. 자세한 설명은 다른 좋은 글들이 많으니 참고 바랍니다. 구현 포인트만 짚고 마치겠습니다. 1. $lazy$를 업데이트 하는 것은 쿼리와 업데이트 둘 다 해당이 된다. 2. 조상노드에서 자식노드로 재귀적으로 $lazy$를 업데이트 해야한다. 3. 자식노드의 $lazy$는 조상노드를 고려해야한다. 4. 세그먼트 트리를..

문제 www.acmicpc.net/problem/5419 알고리즘 스위핑, 세그먼트 트리 풀이 북서풍으로 인해 동쪽과 남쪽에 있는 섬으로만 항해가 가능할 때, 가능한 쌍의 수를 묻고 있습니다. 이전에도 소개했던 문제들 중 inversion count 문제가 있습니다. 그 문제도 inversion이 발생하는 쌍을 count 하는 문제입니다. 브루트 포스로 $O(N^2)$에 해결 가능하지만 세그먼트 트리를 활용하면 $O(NlogN)$에 해결 가능합니다. 이 문제또한 가능한 쌍을 묻고 있으며, 지금까지 지나온 섬들을 세그먼트 트리에 업데이트를 하면 보고 있는 섬마다 $O(logN)$에 지나온 섬의 개수를 알 수 있습니다. 섬을 정렬한 후 순차적으로 쿼리와 업데이트를 진행합니다. x좌표가 같을 때는 y좌표가 큰..

문제 www.acmicpc.net/problem/18870 알고리즘 좌표압축 풀이 상대적인 크기 관계는 유지한 채, 숫자의 크기만 줄이는 테크닉입니다. 이를 위해선 두 개의 배열이 필요합니다. 하나는 원래의 원소를 담고 있는 배열, 나머지는 중복제거를 한 후의 배열입니다. 중복제거를 한 배열의 인덱스가 좌표압축의 결과가 됩니다. 코드 #include #define rep(i,n) for(int i=0;i N; rep(i, N) { cin >> arr[i]; vt.emplace_back(arr[i]); } sort(vt.begin(), vt.end()); vt.erase(unique(vt.begin(), vt.end()), vt.end()); rep(i, N) { cout

문제 https://www.acmicpc.net/problem/1280 알고리즘 세그먼트트리 풀이 나무 인덱스 순서대로 나무를 심어나갑니다. 나무를 심을 때 필요한 비용은 지금까지 심은 나무들과의 거리만큼이 필요합니다. 먼저 떠오르는 풀이는 나무를 심을 때 마다, 지금까지 심은 나무들과의 거리를 일일이 탐색해 브루트 포스로 해결하는 것 입니다. 나무당 $O(N)$을 요구하므로 총 시간복잡도는 $O(N^2)$ 입니다. 역시 $N$의 최대는 20만이므로 시간초과 입니다. 하지만 펜윅트리를 활용하게 되면 나무당 쿼리를 $O(logN)$으로 줄일 수 있습니다. 지금까지 심은 나무들은 총 두가지로 나눌 수 있습니다. 현재나무보다 왼쪽에 있는 나무들과 오른쪽에 있는 나무들 입니다. 각각의 정보를 구하기 위해서 필요..

문제 https://www.acmicpc.net/problem/3006 알고리즘 세그먼트트리 풀이 터보소트라는 방법으로 소팅을 할 때, 필요로 하는 교환 횟수를 묻고 있습니다. 일반적인 inversion counting문제는 작은 수부터 inversion들을 세어나가는 문제입니다. 하지만 이 문제에서는 첫 번째로 작은 수, 첫번째로 큰 수, 두 번째로 작은 수, 두번째로 큰 수 와 같이 inversion을 세어나갑니다. 다른 여러 문제들에서도 설명드렸지만, 일반적인 방법으로는 $O(N^2)$의 시간 복잡도가 필요하지만 세그먼트 트리를 이용하게 되면 자신보다 앞에 있는 수, 자신보다 뒤에 있는 수들을 한 임의의 수당 $O(logN)$의 시간 복잡도로 해결 가능합니다. 펜윅트리에는 쿼리를 진행해야 할 인덱스..

문제 https://www.acmicpc.net/problem/6549 알고리즘 스택 풀이 문제 이름에 이미 문제 내용이 적혀 있습니다. 이와 동일한 문제를 이미 분할정복으로 풀이 한 바 있습니다. 여러 가지 풀이가 가능하므로 이번에는 스택으로 풀어보도록 합시다. 문제에서 주어지는 직사각형 $N$개에 대해 다음과 같은 사각형을 정의하겠습니다. $i$번째 직사각형을 최대 높이로 하고 가장 넓은 사각형을 최대 사각형이라고 합시다. 이 최대 사각형이란 녀석은 다음과 같은 특징을 갖고 있습니다. 이 사각형의 가장 왼쪽과 오른쪽은 $i$번째 직사각형보다 낮은 사각형들로 막혀있습니다. 즉 $i$번째 최대사각형을 막는 제일 왼쪽과 오른쪽을 left [i]와 right [i]라고 할 때, 이들을 구하기 위해선 사각형 ..

문제 https://www.acmicpc.net/problem/1615 알고리즘 세그먼트 트리 풀이 간선들이 주어질 때, 교차점의 개수를 묻고 있습니다. 교차 조건은 두 개의 에지를 (A1, B1), (A2, B2)라 한다면 A1 B2 또는 A1> A2, B1 M; while(M--) { cin >> a >> b; edge.emplace_back(a, b); } sort(edge.begin(), edge.end()); for (auto [A, B] : edge) { ans += query(N) - query(B); update(B,1); } cout