반응형 그래프3 [C/C++] 백준 #1646 피이보나치 트리(동적 계획법) 피이보나치 트리 문제는 일견 어려워보일 수 있지만, 조성 방법이 정해져 있기 때문에, 그것을 이용해서 푸시면 됩니다. 정답자가 현재 90명정도로 적은 편의 문제입니다. 구현 자체가 어려워서라기보다는 문제 자체가 어려워서인 듯 합니다. N이 주어졌을 때, 루트는 최고층(가장 높은 레이어)에 위치하며 가장 먼 노드까지는 N-1번이면 도착하게 됩니다. 왼쪽 트리는 N-2에 대한 루트이고, 오른쪽 트리는 N-1에 대한 트리입니다. 이것을 이용하면 전체 트리에 대한 노드의 갯수 \(ft_N\)을 구할 수 있습니다. \[ ft_0 = 1, ~ ft_1 = 1 \] \[ ft_n = ft_{n-2} + ft_{n-1} + 1 \] 위의 점화식을 이용하면 우리는 손쉽게 노드의 갯수를 구할 수가 있습니다. 이제 이것을 .. 2022. 9. 18. [C/C++] 백준 #1613 역사(플로이드 와샬) 이번 문제는 역사적 사건의 전후 관계가 주어졌을 때, 그 관계를 이용해서 다른 두 사건의 선후관계를 유추하는 방법입니다. 선후 관계가 있으니, 위상 정렬을 사용할 수도 있는데, 저는 그것보다는 유향 그래프라고 생각하고 플로이드 와샬(Floyd Warshall) 알고리즘을 이용했습니다. 플로이드 와샬 알고리즘을 이용하면 모든 정점 사이의 연결관계를 파악할 수 있습니다. 하지만, 알고리즘의 점근적 분석이 \(O(V^3)\)이라는 단점이 있죠. 모순이 생기지 않는 연결관계이므로 사실 \(O(V^3)\)번 반복할 필요는 없습니다. 그렇지만 그냥 오리지날 플로이드 와샬 알고리즘을 이용해서 풀었습니다. https://www.acmicpc.net/problem/1613 1613번: 역사 첫째 줄에 첫 줄에 사건의 개.. 2022. 9. 13. #1303 전쟁 - 전투 (DFS) 이번 문제는 Silver I 문제로 기초적인 DFS 문제입니다. 핵심은 연결된 지역의 수를 알아내는 것으로, "섬의 개수" 등과 같은 문제와 동일합니다. MxN 지역(보통은 NxM인데, 여기서는 MxN입니다.)에 W로 마킹된 곳과 B로 마킹된 곳이 있습니다. 대각선으로는 이어질 수 없고, 상하좌우로만 이어집니다. 서로 이어진 곳을 하나의 집단이라고 한다면, 그 집단의 구성수의 제곱을 합한 것이 전투력이 됩니다. 이 전투력을 각각의 집단 'W'와 'B'를 표시하면 됩니다. DFS로 해결해도 되고, BFS로 해결해도 되는 문제입니다. 저는 개인적으로 DFS를 선호합니다. 결국 큐 자료구조를 선호하느냐 아니면 스택자료 구조를 선호하느냐의 차이겠죠. 또한 경계선 검사를 할 때, 미리 더 넓은 지역을 잡아놓고 새.. 2020. 1. 19. 이전 1 다음 728x90
