Koi (6) 썸네일형 리스트형 [BOJ] 13309 트리 문제 링크: https://www.acmicpc.net/problem/13309 13309번: 트리 표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 트리의 정점의 개수와 질의의 개수를 나타내는 두 정수 N과 Q (1 ≤ N, Q ≤ 200,000)가 주어진다. 다음 N-1개의 줄의 i번째 줄에는 정점 i+1의 부모 정점을 나타내는 정수 a가 주어진다 (1 ≤ a ≤ N). 다음 Q개의 줄 각각에는 세 정수 b, c, d가 주어진다. d = 0이면, b와 c를 연결하는 경로가 존재하는 지 묻는 질의만 수행함을 의미한다. d = 1이면, b와 c를 연 www.acmicpc.net 문제 요약: 정점이 20만개인 트리가 주어진다. 이때 어떤 정점 a, b를 잇는 경로가 있는 지에 대한 쿼리 20만개에 응답.. [BOJ] 15977 조화로운 행렬 2018 KOI 고등부 3번이다. 정해는 2d segment tree래서 그렇게 짰는데 사실 set+이분탐색이 훨씬 짧고 깔끔하고 빠르고 메모리 사용량도 적다고 한다. 하여튼 "정해"는 첫째 열 기준으로 정렬한 다음 둘째 열과 셋째 열에서 2d segment tree를 이용해서 pair의 LIS를 구해주면 된다. 메모리 사용량이 문제고 $200000 * (lg200000)^2$ 개만큼 노드 잡았더니 MLE 뜨길래 적당히 줄여서 해봤더니 맞았다. 왜 맞는지 진짜 모르겠는데 실제로 돌리면 같은 노드도 여러번 탐색하고 그래서 최악의 경우에도 노드 개수가 많이 넘어가지는 않는다고 한다. 시간은 5초 제한에 낭낭하게 3.7초 나왔다. (...) 시간복잡도는 $O(n lg n^2)$, 공간복잡도도 마찬가지.다시는 .. [BOJ] 7579 앱 나는 사용가능한 최대 cost를 정해두고 0/1 knapsack을 돌리는걸 파라메트릭 서치로 해서 AC를 받았는데 보니까 아무도 이렇게 풀지 않았다 ㅠㅠ 억울해서 소스를 올린다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950#include using namespace std; int n,m;int arr[105];int cost[105];int cache[105][10005]; int dp(int idx, int remain){ if(idx==(n+1)) return 0; int& ret=cache[idx][remain]; if(ret!=-1) return ret; int ma=dp(id.. [BOJ] 2472 체인점 굉장한 학생 문제랑 다익스트라의 짬뽕이다. 덕분에 코드가 장난아니게 길다.각 정점이 최대 5개의 간선을 가지니 다익스트라의 $O(ElgV)$ 시간복잡도가 $O(VlgV)$로 바뀐다. 그러면 주어진 세 정점에 대해서 다익스트라를 한번씩 돌려볼 수 있고, 모든 정점에 대해 주어진 세 정점으로부터 각 정점으로부터의 거리 $dist_i$가 나오게 된다. 거리의 범위는 크지만 대소관계만을 비교하면 되므로 등위를 정렬을 통해 다시 매겨주자. 그러면 굉장한 학생 문제처럼 모든 정점에 대해 체인점을 세울수 있음/없음을 판별할 수 있다. 그 이후 들어오는 쿼리는 $O(1)$에 처리 가능하다. 수행 시간은 다익스트라, 정렬, RMQ 등이 다 섞여서 결과적으로 $O(NlgN)$이다. 개인적으로 문제 자체도 굉장한 학생 문제.. [BOJ] 13306 트리 문제: https://www.acmicpc.net/problem/13306 2016 KOI 중등부 3번 문제인 트리이다. 고등부 3번과 굉장히 비슷한 문제이기는 한데, 듣기로는 고등부 3번은 HLD라는 알고리즘을 써야 한다고 알고 있는데 이 문제는 상대적으로 깔끔하게 발상의 전환을 통해 문제를 해결할 수 있다. 실제로 대회장에 갔을 때도 모든 풀이는 다 생각해 놨는데 자료구조 구현을 못해서 실패했다. 웬만하면 풀이를 보기 전에 생각을 더 해봤으면 하는 좋은 문제. 내 해법은 Union-Find Tree로 알려져 있는 자료구조 (Disjoint Set)을 구현해서 문제를 역순으로 풀어 나가는 것이다. 어떤 정점과 그 정점의 부모 정점을 제거하면 그 두 트리는 분리되게 된다. 두 정점 사이에 경로가 존재하려.. [BOJ] 2439 탑 문제: https://www.acmicpc.net/problem/2493 2009년 초등부 지역본선 4번, 고등부 지역본선 2번 문제이다. 그만큼 난이도도 매우 쉬운 스택 문제기는 한데 처음 보면 스택 문제가 아니라고 생각할 수도 있을 거라 생각한다. 풀이는 다음과 같다. 이 문제를 푸는 가장 적절한 알고리즘은, 왼쪽부터 탑의 높이를 차례대로 보면서 스택의 맨 위와 비교해서, 스택의 수가 더 클 때까지 pop하고 그 때 숫자를 출력하는 것이다. 굉장히 단순하기 짝이 없지만 제대로 동작하는 알고리즘이다. 대략적으로라도 증명을 해보자. 1. 이 알고리즘을 썼을 때 원래 부딪혀야 하는 곳보다 왼쪽에서 부딪히는 경우는 없다.원래 부딪혀야 하는 것보다 왼쪽에서 부딪혔다고 가정해 보자. 스택에서 pop을 할 때 원.. 이전 1 다음