GOLD23 [백준/C++] #2263 트리의 순회 (divide and conquer) 문제https://www.acmicpc.net/problem/2263 구상트리의 전위, 중위, 후위 순회와 관련한 문제였는데, 1년 전에 자료구조를 배웠던게 가물가물해서 다시 찾아서 공부해보았다. 아래 포스팅에 너무 잘 나와있어 풀이에 도움이 되었다. https://ldgeao99.tistory.com/402 챕터7-2. 트리 | 순회방법(전위, 중위, 후위)트리의 순회(Tree Traversal) - 트리도 그래프이기 때문에 DFS와 BFS 방식 모두 가능하다. - 그런데 트리에서만 가능한 아래의 3가지 방법이 있다.(각각의 차이는 루트 노드의 방문을 언제 하냐의 차이)ldgeao99.tistory.com 우선, 세가지 순회의 특성에 대해 간략히 말해보자면, 전위 순회는(Preorder) 루트 -> 왼.. 2024. 8. 24. [백준/C++] #14938 서강그라운드 (Dijkstra) 문제https://www.acmicpc.net/problem/14938구상수색 범위 때문에 낙하지점마다 갈 수 있는 지역들이 다르고, 각 지역들에서 얻을 수 있는 아이템 수가 다르다. 이때, 어떤 지점에 낙하를 해서, 얼마나의 아이템을 얻을 수 있는지 묻는 문제였다. 즉, 한 지점에서 출발을 하면, 최단거리가 수색 범위 이하인 곳들을 추출하고, 그렇게 갈 수 있는 지역들에서 얻을 수 있는 아이템들을 다 더하면 하나의 출발지에서 얻을 수 있는 아이템 수들을 구할 수 있다. 그래서 결국 이문제의 키 포인트는 최단거리가 수색 범위 이하인 곳들을 추출하는 것이고, 각 길마다 거리가 다르므로, 결국 가중치가 있는 그래프에서 시작 노드로부터 다른 모든 노드까지의 최단 경로를 찾는 데에 사용되는 Dijkstra 알.. 2024. 8. 21. [백준/C++] #1005 ACM Craft (DP) 문제https://www.acmicpc.net/problem/1005구상문제를 보다가 문득 그래프는 없겠지..?라는 생각이 들었다. 만약 그래프에 사이클이 존재한다면, 사이클을 이루는 건물들 간에는 순환 의존 관계가 형성된다. 즉, 건물 A를 짓기 위해 건물 B가 필요하고, 건물 B를 짓기 위해 건물 C가 필요하며, 건물 C를 짓기 위해 다시 건물 A가 필요하게 되는 모순이 발생한다. 이러한 상황에서는 어떤 건물도 완성될 수 없으므로 건물 건설이 불가능하다. 문제에서 모든 건물이 완성될 수 있다고 나와있었기에 그래프에 사이클이 포함되지 않는다는 것을 확증할 수 있었다.!! 구한 이전 건물의 건설 소요시간을 구했다면 다음 건물의 소요시간을 구하는 로직만 짜면 되기에 dp 알고리즘을 사용하는 문제라는 생각이.. 2024. 8. 9. [백준/C++] #10026 적록색약 (BFS/DFS - Flood Fill) 문제https://www.acmicpc.net/problem/10026 구상기본적 flood fill문제였다. 몇개의 섬이 있는지 판단하면 되는, 정말 간단한 문제였다. 그냥 문제 읽자마자 flood fill이라는 걸 알 수 있었다. 그리고, 아래를 보면 알 수 있다 싶이 bfs로 풀게 되면 메모리 초과가 났다. dfs로 풀어야 한정된 메모리 안에서 풀렸다. 코드 + 풀이1) 메모리초과 난 BFS 풀이BFS가 너비 우선 탐색으로 인해 많은 노드를 메모리(큐)에 저장해야 해서 노드의 연결이 많을 경우, 저장되는 노드 수가 많아져, 메모리 초과의 가능성이 있다. #include#include#include#define MAX 101#define endl "\n"using namespace std;/*1.. 2024. 7. 31. 이전 1 2 3 4 5 6 다음
