문제를 요약하면 기존 입력에 N-M+1 개의 가중치가 L 인 간선을 추가로 만들어 모든 점끼리 갈 수 있게 할 때 두 빌라봉을 오가는데 드는 비용 중 가장 큰 값이 가장 작도록 N-M+1 개의 간선을 만드는 것이다. 즉 그래프가 1개 이상이라는 것인데 이때 각 그래프에서 점 하나를 골랐을 때 그 점과 한 그래프의 나머지 점들끼리의 거리의 최댓값이 가장 작은 점을 고른 뒤 한 그래프를 한 점이라고 했을 때 점들을 연결했을 때 점들 간의 거리의 최댓값이 가장 작아야 되기 때문에 점이라고 정의한 그래프의 값 중 가장 큰 값을 중앙에 두고 중앙을 중심으로 다른 점들이 중앙 점과 연결을 할 때 가장 작은 값을 찾을 수 있다. 맨 처음 그래프 내에서 거리의 최댓값이 가장 작은 값을 고르는 방법은 이전에 설명했던 사..
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..
https://www.acmicpc.net/problem/17274 17274번: 카드 공장 (Large) 진서는 CTP 카드 공장의 노동자이다. 공장에는 N개의 카드가 있으며 각 카드에는 앞면과 뒷면에 숫자가 쓰여있다. 공장장 노진의 명령에 따라서 진서는 카드를 뒤집어야 한다. 명령은 M번 내려지 www.acmicpc.net 생각보다 어려웠던 문제였다 구현 자체는 오래 걸리지는 않았는데 생각하는데 오래 걸린 거 같다. 처음엔 앞면 기준 정렬된 순서로 앞면 머지 소트 트리와 뒷면 머지 소트 트리 이렇게 두 개의 트리를 만들고 구간을 다른 트리와 바꾸고 합치는 그런 방법을 생각했었는데 그럴 경우 한번 쿼리당 NlogN이라는 시복이 나와서 MNlogN으로 터지게 된다. 문제를 잘 생각해보면 M개의 입력 중에..
https://www.acmicpc.net/problem/2243 2243번: 사탕상자 첫째 줄에 수정이가 사탕상자에 손을 댄 횟수 n(1≤n≤100,000)이 주어진다. 다음 n개의 줄에는 두 정수 A, B, 혹은 세 정수 A, B, C가 주어진다. A가 1인 경우는 사탕상자에서 사탕을 꺼내는 경우이다. www.acmicpc.net 간단한 세그+이분 탐색 문제이다. 처음 봤을 땐 이게 어떻게 세그로 되는 건지 싶을 수 있지만 간단한 세그로 풀수 있다. 일단 1번쿼리는 나중에 생각하고 2번 쿼리부터 보자 2번 쿼리같은경우 b맛의 사탕을 c개 넣는 거니까 b, b구간에 c를 더하는 거와 같다 마이너스여도 코드에는 변화가 없으니 그냥 한 구간에 c를 더해주면 된다. 여기까진 쉬운데 1번 쿼리에서 b번째 사탕..
https://www.acmicpc.net/problem/6164 6164번: Hotel The cows are journeying north to Thunder Bay in Canada to gain cultural enrichment and enjoy a vacation on the sunny shores of Lake Superior. Bessie, ever the competent travel agent, has named the Bullmoose Hotel on famed Cumberland Street as their vacatio www.acmicpc.net 이문제는 일자로 나열된 방들이 있고 1번 쿼리는 소들은 n개가 연속되게 비어있는 방을 쓸려고 하는데 이때 그런 방이 있다면 연속된 n개..
https://www.acmicpc.net/problem/1126 1126번: 같은 탑 첫째 줄에 조각의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에 각 조각의 높이가 주어진다. 높이는 500,000보다 작거나 같은 자연수이고, 모든 조각의 높이의 합은 500,000을 넘 www.acmicpc.net 처음에 봤을 땐 그리디로 큰 값부터 작은 위치에 값을 더하는 방식으로 하고 싶지만 그러면 틀리게 된다. 이 문제는 dp 문제인데 i번째 블록을 움직일 수 있는 경우는 왼쪽 탑에 올린다, 오른쪽 탑에 올린다, 버린다 이렇게 3가지의 경우가 있다. 이때 왼쪽 탑과 오른쪽 탑으로 분리하지 말고 왼쪽 탑과 오른쪽 탑과의 높이 차로 dp 테이블을 만들 수 있다. 그럼 이렇게 정의하자 dp ..
solved.ac 티어 : 플5 https://www.acmicpc.net/problem/22348 22348번: 헬기 착륙장 각 테스트 케이스에 대해, 한 줄에 하나씩, 빨강 페인트 a통과 파랑 페인트 b통만을 이용해 만들 수 있는 서로 다른 헬기 착륙장의 수를 109 + 7로 나눈 나머지를 출력한다. www.acmicpc.net 이문제는 dp 문제있은데 dp인걸 알기 어렵다고 한다 이 문제는 빨강 페인트 a와 파랑 페인트 b 이렇게 두 개가 입력으로 들어오면 이 두 개의 양을 넘지 않는 선에서 만들 수 있는 모든 착륙장의 경우의 수를 출력하는 문제이다. k개의 동심원인 착륙장을 만든다고 했을 때 k번째 동심원을 파랑 페인트를 칠한다고 하면 파랑 페인트는 b-k가 되고 남은 k-1개의 동심원은 a와 b..
solved.ac 티어 : 골 5 https://www.acmicpc.net/problem/1915 1915번: 가장 큰 정사각형 첫째 줄에 n, m(1 ≤ n, m ≤ 1,000)이 주어진다. 다음 n개의 줄에는 m개의 숫자로 배열이 주어진다. www.acmicpc.net dp로 된다는걸 알면 쉬운데 dp인걸 알아채기가 어렵다고 해서 골 5라고 한다. 바로 문제풀이를 설명하자면 dp [i][j]=(i, j) 번째 점을 포함하는 정사각형의 한 변의 최대 길이 이게 끝이다. dp [i][j]를 구하려면 (i, j) 번째 점이 0일 때는 0이고 1일 때는 (i-1, j)==(i, j-1)==(i-1, j-1) 이면 셋 중 하나의 값+1이 dp [i][j]가 되고 아닐 떼 셋 중 가장 작은값+1을 해주면 된다..
solved.ac 티어 : 골드 3 https://www.acmicpc.net/problem/12784 12784번: 인하니카 공화국 인하니카 공화국은 1번~ N번까지 N개의 섬으로 이루어진 나라이다. 이 나라에서는 섬 간의 왕래가 매우 어려웠지만, 위대한 다리 설계자 ‘진’이 두 섬을 연결하는 다리를 최소한의 개수로 만들 www.acmicpc.net 이 문제의 풀이는 생각보다 간단하다. 1에서부터 시작해서 dfs으로 끝점(괴도 루팡이 있다는 곳)까지 탐색하면서 지나온 길의 가중 치중 가장 작은 값을 찾고 모아지는 부분에서 더해주면 된다. 문제에 있는 예시로 설명을 해보겠다 괴도 루팡이 있을 수 있는 곳은 3,4,6,7번 점이다. 1부터 3,4,6,7인곳으로 dfs으로 탐색하면 된다. 일단 3부터 시작하..
- Total
- Today
- Yesterday
- 트리에서의 다이나믹 프로그래밍
- A Dance of Fire and Ice
- 그리디 알고리즘
- 개발
- 세그먼트 트리
- 정렬
- 그래프 이론
- BOJ
- C++
- 선분 교차 판정
- 수학
- 잡봇
- Python
- 트리
- discord bot
- 이분매칭
- 알고리즘
- 누적 합
- 구현
- 자료구조
- 완전 탐색
- 깊이 우선 탐색
- 다이나믹 프로그래밍
- 이분 탐색
- 최소 스패닝 트리
- 느리게 갱신되는 세그먼트 트리
- codeforces
- 그래프 탐색
- 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 |