Valgrind - 메모리 누수를 잡아주는 툴
http://www.valgrind.org/ C나 C++로 프로그래밍을 하다보면 동적할당을 해놓고는 해제를 해주지 않는 경우가 더러 생긴다. Valgrind를 사용하면 이러한 메모리 누수를 체크할 수 있다.
이 블로그의 인기 게시물
BOJ 7812 - 중앙트리
INC 2007 H번 https://www.acmicpc.net/problem/7812 루트를 하나 잡고 DFS를 통해 루트에서 다른 모든 정점으로 가는 비용의 합을 구해 놓는다. 이 때 정점 u(1 ~ n)를 루트로 하는 서브트리의 정점 갯수도 구해 놓는다. 다시 DFS를 돌리는데 이때 처음에 루트에서 아까 구한 비용의 합을 들고 시작하면서 최소답을 갱신시켜 나간다. cost(u, v) = 간선(u, v)의 비용 count(u) = u를 루트로 하는 서브트리의 정점의 갯수 라 하자. 간선(u, v)를 탈때 cost(u, v) * count(v) 만큼 답이 줄어들고 cost(u, v) * (n - count(v)) 만큼 답이 늘어나는걸 이용하면 된다. 시간 복잡도는 O(N). 답이 int범위를 벗어 날 수 있음에 주의한다.
댓글
댓글 쓰기