본문 바로가기

알고리즘/Baekjoon

 (196)
트리. [4803] [1. 문제 설명] 그래프는 정점과 간선으로 이루어져 있다. 두 정점 사이에 경로가 있다면, 두 정점은 연결되어 있다고 한다. 연결 요소는 모든 정점이 서로 연결되어 있는 정점의 부분집합이다. 그래프는 하나 또는 그 이상의 연결 요소로 이루어져 있다. 트리는 사이클이 없는 연결 요소이다. 트리는 정점이 n개, 간선이 n-1개 있다. => 정점이 n 개 간선이 n-1 개 인 그래프는 트리이다? => FALSE 트리에서 임의의 두 정점에 대해서 경로는 유일하다. 그래프가 주어졌을 때, 트리의 개수를 세는 프로그램을 작성하시오. [2. 풀이 접근] A. DFS 무방향 연결 그래프에서 임의의 트리를 하나 만들 수 있다. 어떤 정점에서 DFS 로 그래프를 한번 순회하면 된다. (혹은 BFS) 트리에서 임의의 두 ..
트리. [5639] [1. 문제 설명] 이진 검색 트리는 다음과 같은 세 가지 조건을 만족하는 이진 트리이다. 노드의 왼쪽 서브트리에 있는 모든 노드의 키는 노드의 키보다 작다. 노드의 오른쪽 서브트리에 있는 모든 노드의 키는 노드의 키보다 크다. 왼쪽, 오른쪽 서브트리도 이진 검색 트리이다. (재귀적임) 이진 트리의 전위 순회 결과가 있을 때, 후위 순회 결과를 출력한다. [2. 풀이 접근] 전위 순회 결과가 주어졌을 때, 트리의 구조를 대강 알 수 있다. Root [... Left sub tree....] [....Right sub tree....] 여기서 Right sub tree 의 시작점은 root 보다 큰 값이 시작하는 위치이므로, 간단한 탐색으로 알 수 있다. Left sub tree 와 Right sub tr..
트리. [2263] [1. 문제 설명] n개의 정점을 갖는 이진 트리의 정점에 1부터 n까지의 번호가 중복 없이 매겨져 있다. 이와 같은 이진 트리의 중위 순회와 후위 순회가 주어졌을 때, 전위 순회를 구한다. [2. 풀이 접근] 각 순회를 보면 트리의 대략적인 구조를 알 수 있다. 중위 순회: [.... Left sub tree...] Root [.... Right sub tree....] 후위 순회: [.... Left sub tree...] [.... Right sub tree....] Root 후위 순회의 마지막 원소는 전체 tree 의 root 임을 알 수 있다. 이렇게 알아낸 root 를 통해 중위 순회에서 해당 root 의 left sub tree 와 right sub tree 를 알 수 있다. 이제, Left..
트리. [1991] [1. 문제 설명] 이진 트리를 입력 받아 전위 순회, 중위 순회, 후위 순회 결과를 출력하도록 한다. (tree 에서 node 의 값은 알파벳이며, child 가 없는 경우 '.' 으로 표시한다.) [2. 풀이 접근] A. 재귀로 푸는 방법 전위 순회(inorder traverse) 를 예로 들면, root left_sub_tree right_sub_tree root 를 먼저 방문하고, 왼쪽 sub tree 를 그 다음으로 방문하며, 오른쪽 sub tree 를 가장 마지막에 방문한다. 여기서, left_sub_tree, right_sub_tree 에 대해서 동일하게 각 sub tree 에 root 를 먼저 방문해야 하는데, 이는 전체 문제의 부분 문제로 다룰 수 있다. 따라서 재귀적으로 접근 할 수 있..
트리. [1967] [1. 문제 설명] Tree 는 Cycle 이 없는 무방향 그래프이다. Tree 에서는 어떤 두 노드 간 경로는 항상 하나만 존재한다. 트리의 지름은 트리에 존재하는 모든 경로 중 가장 긴 것의 길이이다, [2. 풀이 접근] 다음과 같은 문제 (https://testkernelv2.tistory.com/351) [3. 코드]
트리. [1167] [1. 문제 설명] 트리에서 임의의 두 점 사이의 거리 중 가장 긴 것의 길이를 출력한다. (트리의 지름을 구한다.) [2. 풀이 접근] A. 잘못된 접근 방식 1 => 모든 노드에서 DFS 를 수행한다. => 당연히 시간 초과 발생 (정점의 최대 개수는 200,000 개이므로, V^3 의 시간은 2초내에 풀 수 없다.) B. 잘못된 접근 방식 2 => 모든 edge 중 가중치가 가장 긴 것을 찾는다. => 이 edge 에 속한 노드 중 하나를 root 로 하여, bfs 수행 ## 보통 트리의 지름은 leaf 에서 leaf 이므로, 가장 긴 edge 가 이 지름에 속할 것으로 생각함 ## bfs 순회 중, root 에서 가장 먼 정점을 구할 수 있다. ## 방문 순서가 늦을 수록 root 에서 멀리 존재..
트리. [11725] [1. 문제 설명] 루트가 1인 트리가 입력으로 주어질 때, 각 노드의 부모노드를 구하도록 한다. [2. 풀이 접근] Tree 자료구조 특징) A. 하나의 노드는 여러 개의 자식을 가질 수 있어도, 부모는 하나만 가질 수 있다. => 아래와 같은 형태는 트리가 아니다. => B, C, D 는 A 라는 하나의 노드를 부모로 갖지만, => E, F 는 여러개의 부모 노드를 갖는다. => 이로 인해 아래 성질을 만족하지 못한다. B. 루트에서 어떤 노드로 가는 경로는 유일하다. => 임의의 두 노드 간의 경로도 유일 하다 => 두 개의 정점 사이에 반드시 1개의 경로만을 갖는다. C. Root 노드는 다른 모든 노드들을 자손으로 갖는 노드로, Tree 에서 딱 하나 존재 D. Leaf 노드는 자식이 하나도 없..
최단 경로. [1956] [1. 문제 설명] 임의의 방향 그래프 내 Cycle 경로 중 길이가 가장 짧은 것을 출력하도록 한다. 없을 경우 -1 을 출력 [2. 풀이 접근] A. Cycle => 그래프에서 Cycle 은 시작점에서 출발하여 다시 자기자신으로 돌아오는 것을 말한다. 문제에서 지정한 출발지점이 없으니, 모든 시작정점에서 사이클이 있는지 없는지 판별하고, 있다면 그 중 최소 경로를 반환해야 하는데, 사이클을 찾는 것은 둘째치고, 각 시작정점에서 최단 경로를 찾는 것만으로도 시간초과가 발생할 수 있다. (관련 예제=> https://testkernelv2.tistory.com/348) 문제 입력에서 정점의 개수가 400 개이므로 플로이드-와샬 알고리즘 사용을 고려해볼 수 있다. 플로이드-와샬 알고리즘 사용 시 사이클을 ..
최단 경로. [11404] [1. 문제 설명] N 개의 정점에 M 개의 edge 가 있을 때, 모든 도시 쌍 (A, B) 에 대해서 A에서 B로 가는데 필요한 최소비용을 출력한다. [2. 풀이 접근] 다익스트라 알고리즘 => 정점의 개수는 edge 의 개수에 비해 무시할 수 있으므로 (계산 편리성을 위해), 이 문제에서 다익스트라 시간 복잡도는 O(ELogV), 최대 O(100000*7) => 필요한 전체 경로 개수 N^2, 최대 10000 => 전체를 구해야 할 때, (10^4)*(10^5)*7 == 7*10^9 => 대략 7초, 시간 초과 발생 가능성이 높음 플로이드-워셜 알고리즘 (위키피디아 참조) [A. 개요] edge 의 가중치가 음이거나 양인 (음수 사이클이 없는) 가중 그래프에서 최단 경로들을 찾는 알고리즘 (문제 입..
최단 경로. [11657] [1. 문제 설명] 그래프 내 음수 가중치가 있을 때, 1번 정점에서 각 정점으로의 최단 경로를 출력 음수 사이클이 발생하는 경우는 -1 하나만 출력 특정 노드를 도달 할 수 없는 경우에 -1 출력 [2. 풀이 접근] edge 에 음수 가중치가 있는 경우는 다익스트라 알고리즘을 이용하여 최단 경로를 구할 수는 없다. 다익스트라 알고리즘은 정점을 지날 수록 경로의 가중치가 커지는 것을 기반으로 하기 때문이다. (정점을 여러 개 지났는데, 오히려 가중치가 작아지는 경우...) 이 경우, 벨만포드 알고리즘을 이용하여 최단 경로를 계산하는데, 여기서 중요한 것은 음수 사이클이 발생하는 것을 판단하는 것이다. A -> B -> C 로 갈 때, A -> B 의 weight 가 +2 이고, B -> A 의 weigh..

티스토리툴바