[백준] 3653 영화 수집
2022. 1. 19. 22:59
Algorithm/BOJ
문제 링크 http://icpc.me/3653 3653번: 영화 수집 각 테스트 케이스에 대해서 한 줄에 m개의 정수를 출력해야 한다. i번째 출력하는 수는 i번째로 영화를 볼 때 그 영화의 위에 있었던 DVD의 개수이다. 상근이는 매번 영화를 볼 때마다 본 영화 DVD www.acmicpc.net 풀이 세그먼트 트리를 이용하여 풀 수 있다. 빼야 하는 dvd를 기준으로 위에 있는 dvd를 모두 세는 연산과 dvd를 하나 빼는 연산을 세그먼트 트리를 이용하여 할 수 있다. 이때 빼고 맨 위에 놓는 연산을 그냥 한다면 O(N)이 들기 때문에 배열을 M+N사이즈로 활용하여 아무것도 없는 곳은 0으로 dvd가 있는 곳은 1로 만들어 사용하며 특정 dvd의 인덱스는 따로 관리한다. 그렇기 때문에 dvd가 있는 ..
백준[2243] 사탕상자
2021. 11. 17. 14:31
Algorithm/BOJ
문제 링크 http://icpc.me/2243 2243번: 사탕상자 첫째 줄에 수정이가 사탕상자에 손을 댄 횟수 n(1 ≤ n ≤ 100,000)이 주어진다. 다음 n개의 줄에는 두 정수 A, B, 혹은 세 정수 A, B, C가 주어진다. A가 1인 경우는 사탕상자에서 사탕을 꺼내는 경우이 www.acmicpc.net 풀이 백준 12899 데이터 구조 이 문제와 거의 동일한 문제다. 세그먼트 트리를 이용하여 k번째 수를 빠르게 구하는 문제다. 업데이트는 일반 세그먼트 트리 업데이트와 비슷하게 하고, 쿼리를 약간 다르게 구현한다. k번째 수를 구할 때, 왼쪽 자식 노드의 값은 L이라 한다면, k L이라면 오른쪽 자식 중 k - L번째 수를 구하는 ..
백준[16978] 수열과 쿼리 22
2021. 11. 13. 23:20
Algorithm/BOJ
문제 링크 http://icpc.me/16978 16978번: 수열과 쿼리 22 길이가 N인 수열 A1, A2, ..., AN이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오. 1 i v: Ai = v로 변경한다. 2 k i j: k번째 1번 쿼리까지 적용되었을 때, Ai, Ai+1, ..., Aj의 합을 출력한다. www.acmicpc.net 풀이 세그먼트 트리를 이용하여 풀 수 있다. 쿼리를 입력받은 순서대로 하지 않고, i번째 1번 쿼리를 하기 전에 k n; for (int i = 1; i > ipt; update(1, 0, N, ipt, i); } vector a; vector b; int t = 0; int q; cin >> q; for (int i = 0; i < q; i++) ..
백준[14428] 수열과 쿼리 16
2021. 10. 14. 14:16
Algorithm/BOJ
문제 링크 http://icpc.me/14428 풀이 세그먼트 트리 문제다. 세그먼트 트리에 최솟값을 저장할 때, 인덱스도 포함하여 저장하면 된다. cf) 나는 min도 구현을 해서 사용했지만, stl에 있는 min()을 그냥 사용해도 된다. 코드 #include #include using namespace std; using pii = pair; int arr[100005]; pii tree[400005]; pii min(pii &a, pii &b) { if (a.first < b.first) return a; if (a.first == b.first) { if (a.second < b.second) return a; else return b; } else return b; } pii query(int..
백준[7626] 직사각형
2021. 9. 1. 13:43
Algorithm/BOJ
문제 링크 http://icpc.me/7626 풀이 백준[3392] 화성지도 이 문제와 거의 유사하다. 위 문제와 풀이는 모두 동일한데 값의 범위가 매우 크기 때문에 좌표압축을 해야한다. 코드 #include #include #include using namespace std; using ll = long long; using pll = pair; const ll MAX = 4e5 + 5; struct T { T(ll x, pll y, ll finish) : x(x), y(y), finish(finish) {} ll x; pll y; ll finish; }; vector v; vector ySet; ll seg[MAX * 4]; ll cnt[MAX * 4]; void update(ll node, ll s..
백준[3392] 화성지도
2021. 9. 1. 13:40
Algorithm/BOJ
문제 링크 http://icpc.me/3392 풀이 스위핑과 세그먼트 트리를 이용하여 풀이할 수 있다. 모든 점을 x축 기준으로 정렬을 하여 왼쪽부터 쓸면서 값을 구하면 된다. 이때 세그먼트 트리로 y축의 점들을 저장해놓는다. 만약 점이 시작하는 점이라면 세그먼트 트리에 1을 더하고, 끝나는 점이라면 -1을 더하면 된다. 하지만 겹치는 부분의 넓이는 구하면 안되기 때문에 위처럼 저장하여 넓이를 바로 계산하면 문제가 발생한다. 그렇기 때문에 세그먼트 트리를 2개 활용한다. 하나는 구간에 점이 몇개가 있는지를 저장하고, 하나는 점이 있는지 유무만 확인할 수 있게 저장한다. 코드 #include #include using namespace std; using pii = pair; struct T { T(int..
백준[2042] 구간 합 구하기
2021. 8. 29. 23:00
Algorithm/BOJ
문제 링크 http://icpc.me/2042 2042번: 구간 합 구하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 합을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄 www.acmicpc.net 풀이 세그먼트 트리 또는 펜윅 트리 기본 문제이다. 개념을 설명은 다른 분이 잘해놓으셔서 생략하겠다. 세그먼트 트리는 여기를 펜윅트리는 여기를 참고해라. 코드 세그먼트 트리 #include using ll = long long; ll arr[1000006]; ll tree[4000006]; ll init(ll node, ll start, ll end) { i..
백준[1168] 요세푸스 문제 2
2021. 8. 19. 18:01
Algorithm/BOJ
문제 링크 http://icpc.me/1168 1168번: 요세푸스 문제 2 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 100,000) www.acmicpc.net 풀이 이 문제를 응용하여 풀 수 있는 문제다. x = k라 할 때 처음엔 x번째 수를 제거하고 그다음은, x + k-1번째 수를 제거하고 다음은 x + 2*(k-1) 번째를 제거는 과정을 계속해서 반복한다. 이때 x + i(k - 1)이 남은 수의 개수보다 크다면 x + i(k-1) % (남은 수의 개수)를 취한다. 하지만 그 값이 0이 되면 안 되기 때문에 남은 수의 개수로 나누어 떨어질 때는 x = (남은 수의 개수)로 만든다. cf) 나는 출력 형식을 제대로 보지 않아서 시간을 약간 날렸다. 출..
백준[12899] 데이터 구조
2021. 8. 19. 13:15
Algorithm/BOJ
문제 링크 http://icpc.me/12899 12899번: 데이터 구조 첫째 줄에 사전에 있는 쿼리의 수 N 이 주어집니다. (1 ≤ N ≤ 2,000,000) 둘째 줄부터 N개의 줄에 걸쳐 각 쿼리를 나타내는 2개의 정수 T X가 주어집니다. T가 1이라면 S에 추가할 X가 주어지는 것입니 www.acmicpc.net 풀이 세그먼트 트리를 이용하여 k번째 수를 가져오는 문제이다. 세그먼트 트리를 만들 때 수의 범위가 아닌 수의 값으로 범위를 정해야 한다. 예를 들어, 5번째 수를 구할 때, 1 ~ N/2에 수가 6개 N/2 + 1 ~ N에 수가 3개가 있다고 한다면 왼쪽 노드로 이동하여 같은 작업을 반복해야 한다. 반면에 1 ~ N/2에 수가 2개 N/2 + 1 ~ N에 수가 5개가 있다고 하면, ..
백준[16975] 수열과 쿼리 21
2021. 8. 16. 17:35
Algorithm/BOJ
문제 링크 http://icpc.me/15655 15655번: N과 M (6) N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다. N개의 자연수 중에서 M개를 고른 수열 www.acmicpc.net 풀이 1 세그먼트 트리의 구간 업데이트를 하는 lazy propagation을 이용하여 풀이할 수 있다. lazy propagation에 대한 자세한 설명은 여기와 여기를 참고해라. 풀이 2 lazy propogation을 사용하지 않고, 세그먼트 트리만을 이용하여 풀이할 수도 있다. 아래 그림과 같이 업데이트하는 방식과 쿼리를 리턴하는 방식을 기존과 반대로 하면 구간 업데이트에 대해 O(logN)에 처리할..
백준[9345] 디지털 비디오 디스크(DVDs)
2021. 8. 15. 15:18
Algorithm/BOJ
문제 링크 http://icpc.me/9345 9345번: 디지털 비디오 디스크(DVDs) 손님이 DVD를 카운터에 가져왔을 때 손님이 원하는 DVD가 전부 존재하면, (A번 선반부터 B번 선반까지에 있는 DVD를 전부 가져왔을 때 순서에 상관없이 A번 DVD부터 B번 DVD까지 있다면) "YES"를 출력하 www.acmicpc.net 풀이 세그먼트 트리를 이용하여 풀이할 수 있다. a ~ b 사이에 a, a+1, ... , b 만 존재한다면 이때 최솟값은 a 최댓값은 b이다. 만약 저 구간에 다른 값이 들어간다면 최솟값, 최댓값은 a, b가 될 수 없다. 이 구간 최대, 최소값을 세그먼트 트리로 관리하면 쿼리당 O(logN)에 처리할 수 있다. 코드 #include #include using names..