본문 바로가기

분류 전체보기

 (74)
[BOJ 2379] 트리 탐색하기 https://www.acmicpc.net/problem/2379 2379번: 트리 탐색하기 n개의 정점으로 이루어진 트리가 있다. 이와 같은 트리를 DFS와 비슷한 방식으로 탐색하려 한다. 탐색을 시작할 때에는 트리의 한 정점에서 시작하여, 한 번도 지나지 않은 간선을 따라서 다음 정 www.acmicpc.net Tag : hash 문제요약 트리가 이진수의 형태로 주어졌을 때 두 트리가 동형인지 판별하라. 풀이 서브트리들을 재귀적으로 어떠한 기준에 의해 잘 정렬하면 두 트리가 같은지 판별할 수 있다. ( (XXX) (X) (XXXX) ) 에서 X들을 감싸는 서브트리의 내부가 잘 정렬되어있다고 가정하면 (XXX), (X), (XXXX)를 동일한 기준으로 정렬해서 나온 결과는 한가지 형태의 트리에서 유일할..
[BOJ 20930] 우주 정거장 https://www.acmicpc.net/problem/20930 20930번: 우주 정거장 첫 번째 줄에는 우주 정거장 개수 $N$과 질문의 개수 $Q$가 주어진다. ($2 \le N \le 200\,000$, $1 \le Q \le 200\,000$) 다음 $N$개의 줄에는 $i$번 우주 정거장의 양 끝점을 나타내는 $x_{i,1}$, $y_{i,1}$, $x_{i,2}$ www.acmicpc.net Tag : dsu, greedy 문제요약 이차원 평면 상의 선분이 N개 주어진다. x축 또는 y축과 평행한 방향으로는 마음대로 이동할 수 있을 때 쿼리마다 각 선분을 오갈 수 있는지 구하는 문제다. 풀이 x축으로 한번, y축으로 한번 정렬하고 현재 컴포넌트에서 가장 오른쪽인 점 >= 다음 점의 x 중 ..
[BOJ 22954] 그래프 트리 분할 https://www.acmicpc.net/problem/22954 22954번: 그래프 트리 분할첫 번째 줄에 정점의 개수 $N$, 간선의 개수$M$이 주어진다. ($1 \le N \le 100\,000$, $0 \le M \le 200\,000$) 두 번째 줄부터 $M$줄에 걸쳐서 간선을 나타내는 정수 $u$와 $v$가 주어진다. ($1 \le u, v \le N$, $uwww.acmicpc.netTag : case work, dsu, constructive 문제요약무향 그래프 \(G(N, M)\)이 주어진다. 간선을 원하는 만큼 삭제해 서로 다른 크기의 트리 2개로 분할하라.불가능한 경우는 -1을 출력한다. 풀이새벽에 심심해서 tony9402님이 골라온 문제를 풀었다.일단 일반 그래프인 것이 거슬린..
[BOJ 20532] 정점 간 통신 네트워크 https://www.acmicpc.net/problem/20532 20532번: 정점 간 통신 네트워크주식으로 엄청난 돈을 벌어들인 영욱이는 그 돈으로 나라를 세우고 나라의 통신을 담당하는 통신탑을 설치했다. 다들 알다시피 영욱이의 나라는 $N$개의 지역과 이를 잇는 $N-1$개의 도로로 이www.acmicpc.netTag : tree dp, number theory 문제요약조상과 자손 관계인 정점 쌍(x, y) 중 a[x]와 a[y]가 약수와 배수 관계인 것의 개수를 구해라. 풀이dfs가 어떻게 돌아가는지 잘 알고 있다면 쉽게 풀 수 있다. 자손의 입장에서 조상을 세주도록 하겠다. 일단 루트부터 자신까지의 경로에서 숫자들의 등장 횟수를 구하는 방법은 다음과 같다.  현재 정점의 dfs가 시작되었을 때..
[BOJ 20929] 중간 https://www.acmicpc.net/problem/20929 20929번: 중간 입출력이 어떤 방식으로 이루어지는지 이해를 돕기 위해 의도적으로 개행 간격 등을 조절한 것으로, 실제 입출력과는 다르다. 위 예시는 $N=2$이고, $A=[1,2]$, $B=[2,3]$인 경우에 대한 입출력이다. www.acmicpc.net Tag : binary search 문제요약 정렬된 배열 a, b를 합쳤을 때 k번째 수를 2logn번 이하의 쿼리로 구해라. 풀이 https://kim1109123.tistory.com/48 위 문제의 시간복잡도가 \(O(logn)\)으로 강제된 문제다. 전체코드 #include "bits/stdc++.h" #define endl '\n' using namespace std; u..
[BOJ 23719] K번째 음식 찾기 1 https://www.acmicpc.net/problem/23791 23791번: K번째 음식 찾기 1한식 [1..3], 양식 [1..3]을 오름차순으로 나열하면 1 2 3 5 8 10이고 여기서 세 번째로 맛있는 음식 맛은 3이므로 첫 번째 질의 정답은 양식 2번이다.  한식 [1..3], 양식 [1..4]를 오름차순으로 나열하면www.acmicpc.netTag : binary search 문제요약정렬된 배열 a, b가 입력으로 주어지고 쿼리마다 a[1 : p], b[1 : q]에서 k번째 수를 찾는 문제다. 풀이먼저 a의 인덱스를 기준으로 이분탐색을 진행한다. 결정함수 chk(m) := a[1 : p], b[1 : q]에서 a[m]이 k번째 수 이상이면 true b에 k번째 수가 있으면 a, b를 뒤..
[BOJ 9576] 책 나눠주기 https://www.acmicpc.net/problem/9576 9576번: 책 나눠주기 백준이는 방 청소를 하면서 필요 없는 전공 서적을 사람들에게 나눠주려고 한다. 나눠줄 책을 모아보니 총 N권이었다. 책이 너무 많기 때문에 백준이는 책을 구분하기 위해 각각 1부터 N까지의 www.acmicpc.net Tag : greedy 문제요약 각 학생은 [a, b]에 있는 책을 하나씩 고를 수 있다. 책 한권은 한 사람만 고를 수 있다. 이 때 최대 매칭을 구하라. 풀이 이 문제를 처음봤을 땐 티어를 안보고 생각해서 이건 무조건 이분매칭 기본 문제다! 라고 생각했던 기억이 있네요. (http://boj.kr/2563bad26f364ee6aa5c04e9f97845b7 이분매칭 AC 코드) 정해로 돌아와서 생각..
[BOJ 21817] 포항항 https://www.acmicpc.net/problem/23817 23817번: 포항항 첫번째 예제의 경우 오른쪽 3칸, 왼쪽 1칸, 아래쪽 3칸, 오른쪽 1칸, 왼쪽 3칸으로 총 11칸 이동하여 5개의 식당을 방문할 수 있다. 두번째 예제의 경우 장애물에 가로막혀 5개의 식당을 방문할 수 www.acmicpc.net Tag : bfs 문제요약 2차원 격자에 시작점, 식당의 위치가 표기되어있다. 식당 중 5개를 골라 방문하는 최단거리를 구하라. 풀이 이 문제 너무한다. 나는 맵에 식당이 5개만 있는 줄 알았지... K = 식당의 개수 일 때 벡터에 K - 5개의 0과 5개의 1을 넣어서 next permutation을 돌리면 방문할 식당 5개가 골라진다. 중복된 원소의 개수 때문에 이는 실제로 \(O(..

티스토리툴바