https://www.acmicpc.net/problem/17668 17668번: 시험 $N$명의 학생이 수학 부문과 정보 부문이 있는 시험을 쳤다. $i$번째 ($1 \le i \le N$) 학생은 수학에서는 $S_i$점을, 정보에서는 $T_i$점을 받았다. T교수와 I교수는 각 학생이 시험을 통과할지 말지를, www.acmicpc.net 이 문제 세그 스위핑이라는 방법이 있다고는 하지만 그 방법이 아닌 2차원 머지 소트 트리를 박는 방법으로 했다. 방법은 생각보다 간단한다. A에서 이분 탐색을 해 입력값 이상인 값들의 위치에 있는 B에서 이분 탐색을 또 하고 거기서도 이상인 값들의 위치 중 합이 입력값 이상인 값을 찾아주면 된다. 말만 간단한거 같지만 이 방법을 그대로 머지 소트 트리에 해주면 된다...
https://www.acmicpc.net/problem/17274 17274번: 카드 공장 (Large) 진서는 CTP 카드 공장의 노동자이다. 공장에는 N개의 카드가 있으며 각 카드에는 앞면과 뒷면에 숫자가 쓰여있다. 공장장 노진의 명령에 따라서 진서는 카드를 뒤집어야 한다. 명령은 M번 내려지 www.acmicpc.net 생각보다 어려웠던 문제였다 구현 자체는 오래 걸리지는 않았는데 생각하는데 오래 걸린 거 같다. 처음엔 앞면 기준 정렬된 순서로 앞면 머지 소트 트리와 뒷면 머지 소트 트리 이렇게 두 개의 트리를 만들고 구간을 다른 트리와 바꾸고 합치는 그런 방법을 생각했었는데 그럴 경우 한번 쿼리당 NlogN이라는 시복이 나와서 MNlogN으로 터지게 된다. 문제를 잘 생각해보면 M개의 입력 중에..
- Total
- Today
- Yesterday
- Python
- 그래프 이론
- 수학
- 다이나믹 프로그래밍
- 세그먼트 트리
- 최소 스패닝 트리
- 개발
- 느리게 갱신되는 세그먼트 트리
- 이분매칭
- 자료 구조
- discord bot
- A Dance of Fire and Ice
- BOJ
- 트리에서의 다이나믹 프로그래밍
- 정렬
- 알고리즘
- 그래프 탐색
- 누적 합
- codeforces
- 잡봇
- 자료구조
- 완전 탐색
- 구현
- 깊이 우선 탐색
- 선분 교차 판정
- C++
- 이분 탐색
- 트리
- 그리디 알고리즘
- KOI
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | |||
5 | 6 | 7 | 8 | 9 | 10 | 11 |
12 | 13 | 14 | 15 | 16 | 17 | 18 |
19 | 20 | 21 | 22 | 23 | 24 | 25 |
26 | 27 | 28 | 29 | 30 | 31 |