woojin042의 블로그

한달만에 돌아왔네요! ㅠㅠ 사실 PS에 대한 흥미가 좀 떨어졌었는데, 입학하기 전까지 민트는 찍어야지(...) 하는 생각에 다시 문제를 풀게 되었습니다. 개인적으로 그리디를 어렵게 느끼고 있던 참이라서, 이번엔 백준 그리디 연습 문제집에 있는 문제들을 낮은 티어부터 쭉 돌아보았습니다. 11000: 강의실 배정(G5) 사용하는 최소 강의실의 개수는, 가장 많은 강의가 겹치는 시점에서의 강의 개수와 같다. 따라서 정렬을 통해 답을 O(NlogN)에 구할 수 있다. 2831: 댄스 파티(G4) 양수 남자 - 음수 여자, 혹은 음수 남자 - 양수 여자끼리만 짝지어 주어야 한다. 양수 남자와 음수 여자가 짝짓는 경우만을 생각해보자. 우선 키가 작은 순서대로 남자를 선택하면 최적해를 얻을 수 있다는 건 쉽게 알 수..

오랜만에 업다운랜디를 돌렸다. 21276: 계보 복원가 호석(G2, Tree) 시간 안엔 못 풀었다.. 자신의 조상 노드가 문제에서 주어지므로, 맵(map)에 자신의 조상 노드를 모두 담고, 조상 노드를 순회하면서 set의 크기가 자신보다 1 작은 것이 있으면 해당 노드가 자신의 부모 노드가 된다. 부모 노드가 없다면 루트 노드가 되고, 가문의 개수는 루트 노드의 개수와 같다. 이를 이용해 시간복잡도 O(N^2logN)에 계산할 수 있다. 별해) 입력받을 때, 자신보다 깊이가 깊은 노드들에 대해 위에서 아래로 가는 단방향 간선을 만들어준다. 이후 위상 정렬을 수행하면 역시 시간복잡도 O(N^2logN)에 해결할 수 있다! 2492: 보석(G3, Brute-Force) 풀이가 전혀 떠오르지 않아서 그냥 답..

이번에도 어김없이 업다운랜디를 돌렸습니다. 학교에서 할 게 없어서 하루종일 문제만 풀고 있네요 ㅋㅋㅋ 12784: 인하니카 공화국(G3, Tree, 16:00) dp[i]를 i번을 루트로 하는 트리에서 필요한 최소 다이너마이트의 개수로 잡고 트리 dp를 돌릴 수 있다. 사실 재사용되는 값이 없어서 메모이제이션은 필요하지 않다! 오랜만에 트리DP를 짜봐서 구현이슈가 좀 있었다... 11967: 불켜기(G2, BFS) 시간 초과... 새로운 방에 불을 킬 때마다 그 방의 상하좌우를 탐색해서, 이미 방문한 지점이 있다면 새로운 방을 큐에 넣어준다. 예전에 재채점으로 틀렸던 문젠데 드디어 풀었다 ㅎㅎ 15711: 환상의 짝꿍(G3, 정수론, 18:35) A+B가 짝수인 경우는 골드바흐의 추측(웬만큼 큰 정수까지..

오늘부터 PS 공부일지를 써 보려고 한다! 입시가 끝나서 PS를 자유롭게 할 수 있는 몸이 되었으므로,,, 앞으로 꾸준히 글을 쓸 예정이다. 오늘은 LCA 알고리즘과 희소 테이블을 공부했다. 15480번: LCA와 쿼리(P2) 케이스 분류가 정말 빡센 문제였다. 쿼리로 들어오는 두 정점이 일직선 상에 있는지 아닌지를 우선 나누고, 일반적인 트리의 형태를 그려서 각 정점별로 답이 될 수 있는 값을 찾는다. 이 때 판단의 기준을 1번 정점, u, v, lca(u, v), 그리고 각 정점의 depth 값으로 한다. 13511번: 트리와 쿼리 2(P3) lca, 그리고 희소 테이블(binary shifting)을 이용하는 문제이다. 1, 2번 쿼리 모두 lca를 찾는 과정에서 만든 이동 배열을 재사용해서 해결할..

정수 N이 주어졌을 때, N=k*k로 나타내어지는 정수 k가 존재하는지 판별하는 알고리즘이다. sqrt 함수의 시간복잡도가 O(logN)이라고 가정하면, 알고리즘의 시간복잡도는 O(logN)이 된다. int issqrt(int n){ int sq=(int)(sqrt(n)+0.5); if(sq*sq==n) return sq; else return -1; }