[Baekjoon,1339] 단어 수학
백트래킹을 하며 모든 경우의 수를 탐색할 수 있다. 탐색 하며 더 큰 값이 나오면 계속해서 갱신해 나가는 것이다. 하지만 이보다 더욱 간단한 방법이 있다. 바로 그리디한 수학적 방법이다.
최근 포스트
[Baekjoon,2213] 독립집합
트리의 루트에서 부터 DFS로 탐색하며 현재 정점을 선택하느냐 안 하느냐를 결정하여 최대 독립 집합을 구하는 문제이며 정점의 가중치가 있으니 정점의 개수가 아닌 정점의 가중치가 최대가 되는 독립 집합을 찾아야 한다. 독립 집합에 대한 자세한 설명은 이곳에서 볼 수 있다.
[Baekjoon,15681] 트리와 쿼리
트리 구조에서 DP를 이용하여 해결하는 문제이다. 주어진 정점을 서브트리로 했을 때 서브 트리의 정점의 개수를 반환하여야 한다. 이를 구현하기 위해서 루트에서 부터 DFS를 하였다. 서브트리의 정점 개수만 구하면 되므로 따로 트리구조를 형성하지 않아도 된다. ```cpp #inc...
[Baekjoon,2887] 행성 터널
자칫 잘못 생각하면 모든 행성을 서로 이어 간선을 형성하고 이 간선들로 최소 스패닝 트리를 찾아 해결할 것이다. 하지만 이러한 방법은 간선이 너무 많아 제한 시간 내에 해결할 수 없다. // 너무 많은 간선들로 인해 모든 정점을 탐색하다 시간초과가 난다. int V; int p...
[Baekjoon,1197] 최소 스패닝 트리
간선의 가중치 합이 최소인 스패닝 트리를 만들어야 한다. 이를 위해서 나는 크루스칼의 알고리즘을 이용했다. 크루스칼 알고리즘은 아주 간단하다. 선택 후 사이클이 되지 않는 간선을 선택한다. 이때 간선의 가중치가 작은 것부터 차례로 선택한다. 이를 최소 스패닝 트리가 될 때까지 ...