YJLee-devlog 🍎

1. 문제 2. 입출력 3. 입출력 예시 4. 문제 설계 특정 노드에서부터 시작해서 깊이 우선 탐색을 진행하게 되면, 특정 노드에서 다른 모든 노드까지의 거리를 알 수 있음 따라서 트리를 구성할 때 모든 부모 자식 관계의 노드는 서로 양방향으로 이어주고, X 노드에서 부터 깊이 우선 탐색을 진행하면서 별도의 배열에 거리를 저장함으로써 문제를 해결할 수 있음 5. 전체 코드 //MARK: - 트리에서의 거리 //MARK: - Framework import Foundation //MARK: - Type struct Node { //MARK: - Property private var edges: [Int] //MARK: - initializer init() { self.edges = [] } //MARK: -..

1. 문제 2. 입출력 3. 입출력 예시 4. 문제 설계 트리도 사이클이 없는 그래프 이므로, 깊이 우선 탐색을 할 수 있음 이 문제에서는 0번 노드가 무조건 루트 노드가 아니기 때문에, 간선 정보를 입력 받을 때 서로 이어 주어야 함 그렇게 트리를 구성하고, 입력 받은 r 노드 부터 시작해서 깊이 우선 탐색을 진행하면서 각 노드에 해당하는 높이를 별도의 배열에 저장함 깊이 우선 탐색을 마치고, 높이 배열의 최대값이 해당 트리의 높이임을 알 수 있음 5. 전체 코드 //MARK: - 트리의 높이 //MARK: - Framework import Foundation //MARK: - Type struct Node { //MARK: - Property private var edges: [Int] //MARK:..

1. 문제 2. 입출력 3. 입출력 예시 4. 문제 설계 트리를 직접 구현하기 보다는, 현재 노드의 부모 노드를 저장하는 배열을 만들어 부모 노드를 저장한 후 X의 부모 노드를 하나 씩 Bool 배열을 통해 체크해 나가고, Y의 부모 노드를 하나 씩 Bool 배열을 통해 체크해 나가면서 최초로 true인 노드가 가장 가까운 공통 조상이 되는 것을 알 수 있음 5. 전체 코드 //MARK: - 공통 조상 찾기 //MARK: - Framework import Foundation //MARK: - Function func solution() -> Void { //MARK: - Input guard let input: [String] = readLine()?.components(separatedBy: " ") ..

1. 문제 힙을 이용하여 우선순위 큐를 구현 2. 입출력 힙을 구현할 배열의 크기를 입력 받음(완전이진트리 이기 때문에 배열로 구현할 수 있음) 3. 문제 설계 힙의 경우 완전이진트리 이기 때문에, 배열로 구현할 수 있음 완전이진트리는 자식 노드가 2개 이하, 왼쪽부터 값이 차례대로 채워나가는 트리를 말함 삽입 연산의 경우 배열의 가장 끝에 원소를 추가하고, 우선순위를 비교하여 트리를 재구성함(문제에서는 최솟값이 우선순위가 높음) 트리의 높이는 노드가 N개일 때, 대략 log N 이므로, 최악의 경우(가장 우선순위가 높은 값이 삽입 됐을 경우, 문제에서는 최솟값) 루트노드 까지 비교해야 하므로 O(log N)의 시간복잡도를 가짐 삭제 연산의 경우 우선순위가 가장 높은 루트 노드를 제거하고 가장 끝 단말 ..

1. 문제 배열을 이용하여 우선순위 큐를 구현 2. 입출력 배열의 크기를 입력 받음 3. 문제 설계 삽입 연산의 경우 배열의 가장 끝에 원소를 추가하면 되므로 O(1)의 시간복잡도를 가짐 삭제 연산의 경우 우선순위가 가장 큰 값(문제에서는 최솟값)과 그 index를 찾고, 그 뒤에 인덱스를 전부 앞으로 옮기고 길이를 유지하는 변수를 하나 줄여줌으로써 삭제 연산을 수행, O(n)의 시간복잡도를 가짐 탐색 연산의 경우 우선순위가 가장 큰 값(문제에서는 최솟값)을 찾아 return, O(n)의 시간복잡도를 가짐 4. 전체 코드 //MARK: - 우선순위 큐(배열) //MARK: - Framework import Foundation //MARK: - Type struct PriorityQueue { //MARK..

1. 문제 2. 입출력 3. 입출력 예시 4. 문제 설계 이진 트리를 순회하는 방법은 여러가지가 있지만, 재귀적인 성질을 이용해 순회하는 방법이 가장 대표적임 그 중, 전위 순회, 중위 순회, 후위 순회가 대표적이며, 각각의 기저조건은 자식 노드가 없을 때(단말 노드일 때)이며, 이 문제에서는 자식 노드가 -1인 경우가 자식 노드가 없는 것으로 가정하며, 자세히 살펴보면 root의 움직임에 따라 순회하는 방식이 달라짐 전위 순회의 경우 Root-L-R, 중위 순회의 경우 L-Root-R, 후위 순회의 경우 L-R-Root(각각의 L, R은 왼쪽 서브 트리, 오른쪽 서브 트리를 뜻함)의 과정으로 트리를 순회하며 Root의 위치에 따라 전위, 중위, 후위로 구별됨을 알 수 있음 5. 전체 코드 //MARK:..