문제를 간단하게 요약하면 처음부터 i를 증가하며 카운팅을 하는데 i번째 값이 i 라면 그 값을 지우고 카운팅을 1부터 다시 한다. 이렇게 계속 반복해서 값을 계속 지우는데 지워지는 값이 1부터 차례대로 지워지게 하는 크기가 K이 배열에서 n개의 인덱스가 주어지면 그 위치의 값을 출력하는 문제이다. K=5 일 때 [1, 3, 2, 5, 4] 이렇게 배열을 만들면 차례로 값을 지울 수 있다. 처음에는 i가 1이고 값도 1이므로 1을 지우고 3부터 다시 i=1을 시작해서 카운팅 해 나가면 2가 지워지고 계속 반복하게 되면 1, 2, 3, 4, 5 순서대로 지워지게 된다. 여기서 한가지 알 수 있는 사실은 i 번째 값이 지워졌다면 다음 값은 i+(i+1) = 2i+1 위치에 있어야 한다. 그러므로 1부터 K까지..
문제 설명이 이게 다인 문제 설명은 간단한 문제이다. 이 문제를 처음 볼 때 이상한 수학으로 풀어야 되는 건가 싶을 수 있지만 사실 세그를 사용해서 풀 수 있다. 일단 |p [i]-p [j]| 를 1번이라고 하고 |q [i]-q [j]| 를 2번이라고 하겠다. 이 문제는 1번과 2번 중 작은 값을 골라야 하기 때문에 1번이 작은 경우와 2번이 작은 경우 이렇게 2개로 나눌 수 있다. 1번이 작거나 같은 경우부터 생각해보자. 1번이 작거나 같을려면 (j = p[j] 일때 p[i] < p[j] 일때 p[i]-p[j]
(한별이가 나오는 몇 안 되는 희귀한 문제이다.) 이 문제는 한가지 관찰만 하면 쉽게 풀 수 있다. 그 관찰은 바로 많아도 3개의 용기만 있으면 꽉 찬 용기를 만들 수 있다는 것이다. 만약 a 용기에 0ml가 있고 b 용기에 1ml가 있고 총용량이 10ml 일 때 a와 b를 합치면 1+5=6ml가 된다. 그리고 c 용기에 2ml가 있다고 하고 앞에서 구한 6ml 용기와 c를 더하면 6+2+5로 10ml를 넘어간다. 이걸 하나의 식으로 나열하면 a+b+c+10/2+10/2 가 된다. 즉 a, b, c 모두 0ml 이어도 10/2 가 두 번 더해져 10으로 꽉 찬 용기가 되기 때문에 최대 3개의 용기만 있으면 꽉 찬 용기를 만들 수 있는 것이다. 맨 처음에 정렬을 해준 뒤 C[i]가 X와 같다면 혼자서도 꽉..
문제를 요약하면 기존 입력에 N-M+1 개의 가중치가 L 인 간선을 추가로 만들어 모든 점끼리 갈 수 있게 할 때 두 빌라봉을 오가는데 드는 비용 중 가장 큰 값이 가장 작도록 N-M+1 개의 간선을 만드는 것이다. 즉 그래프가 1개 이상이라는 것인데 이때 각 그래프에서 점 하나를 골랐을 때 그 점과 한 그래프의 나머지 점들끼리의 거리의 최댓값이 가장 작은 점을 고른 뒤 한 그래프를 한 점이라고 했을 때 점들을 연결했을 때 점들 간의 거리의 최댓값이 가장 작아야 되기 때문에 점이라고 정의한 그래프의 값 중 가장 큰 값을 중앙에 두고 중앙을 중심으로 다른 점들이 중앙 점과 연결을 할 때 가장 작은 값을 찾을 수 있다. 맨 처음 그래프 내에서 거리의 최댓값이 가장 작은 값을 고르는 방법은 이전에 설명했던 사..
https://www.acmicpc.net/problem/1005 1005번: ACM Craft 첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N과 건물간의 건설순서 규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부 www.acmicpc.net dfs를 사용해서 거꾸로 탐색하는 방법을 사용했다. 문제를 보면 자신에게 오는 간선이랑 연결되어있는 점까지의 delay가 가장 큰 값을 골라야 된다. 그러므로 마지막부터 거꾸로 탐색하면서 max값을 저장한 뒤 현재 노드의 값을 더해서 출력해주면 된다. 문제에 있는 그림으로 예시를 들면 4번 노드에서 2,3번 노드로 탐색을 하고 2,3번 노드에서 1번노드로 탐색을 한다. 1번 노드에서는 갈 수..
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/7812 7812번: 중앙 트리 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫 줄에는 트리의 정점의 수 n이 주어진다. (1 ≤ n ≤ 10,000) 각 정점은 0번부터 n-1번까지 번호가 붙여져 있다. 다음 n-1개 줄 www.acmicpc.net 이 문제는 전에 올렸던 사무실 이전과 같은 방식의 문제이다. https://joseph0528.tistory.com/77 BOJ 16121(사무실 이전)풀이 https://www.acmicpc.net/problem/16121 16121번: 사무실 이전 첫 번째 줄에 모든 사무실 후보에 대한 모든 직원의 출근 경로 길이의 제곱을 모두 합한 값을 998,244,353으로 나눈 나..
https://www.acmicpc.net/problem/16121 16121번: 사무실 이전 첫 번째 줄에 모든 사무실 후보에 대한 모든 직원의 출근 경로 길이의 제곱을 모두 합한 값을 998,244,353으로 나눈 나머지를 출력한다. www.acmicpc.net 티어에 비해? 간단했지만 구현 때문에 말아먹은 문제이다. 인접한 두 점의 거리는 모두 1이기 때문에 제곱수의 규칙을 알면 쉽게 할 수 있다. 1부터 5까지만 표시해보자면 1^2=1,2^2=4,3^2=9,4^2=16,5^2=25 나열하면 1 4 9 16 25 이렇게 나오는 걸 알 수 있다. 여기서 규칙을 찾아보면 3,5,7,9 씩 커진다. 즉 전에 커진 수+2만큼을 전수에 더하면 (n+1)^2를 구할 수 있는 것이다. 그렇기 때문에 전 노드에서..
https://www.acmicpc.net/problem/2405 2405번: 세 수, 두 M n개의 정수 A[1], A[2], …, A[n]이 있다. 서로 다른 세 정수 i, j, k에 대해서 a = A[i], b = A[j], c = A[k]라 하자. 세 수의 중위(Median)값은 정렬했을 때 가운데에 오는 수가 된다. 세 수의 평균(Mean)값은 (a+b+c) www.acmicpc.net 생각보다 간단한 문제다 평균과 중윗값의 차가 최대한 크게 하려면 일정한 중윗값에 대해서 평균이 최대한 크거나 작을 때의 차 중 가장 큰 차를 구하면 된다. 값을 정렬했을때 양끝 값은 중윗값이 될 수 없으니 제외해주고 1~n-1에서 i번째 값이 중위 값이라고 했을 때 평균값이 가장 작게 나오게 하려면 i번째 값+i..
- Total
- Today
- Yesterday
- A Dance of Fire and Ice
- 구현
- 정렬
- 그리디 알고리즘
- Python
- 자료 구조
- 그래프 탐색
- 자료구조
- KOI
- 트리
- 세그먼트 트리
- 개발
- BOJ
- 잡봇
- 깊이 우선 탐색
- 완전 탐색
- C++
- 알고리즘
- 트리에서의 다이나믹 프로그래밍
- discord bot
- 다이나믹 프로그래밍
- 수학
- 그래프 이론
- 느리게 갱신되는 세그먼트 트리
- 이분 탐색
- 누적 합
- 선분 교차 판정
- codeforces
- 이분매칭
- 최소 스패닝 트리
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |