class 6https://www.acmicpc.net/problem/14725   # 문제# 필요개념이 문제는 결론적으로 노드들의 깊이를 오름차순으로 도출해야하는 문제이기 때문에 dfs를 사용하였다. 평소 그래프 문제를 풀 때에는 이중 리스트를 만들어 풀었지만, 이 문제는 이름이 같은 노드가 존재할 수 있고, 깊이라는 개념이 도입되기 때문에 이중리스트로 풀지 않았다.  A노드의 자식노드인 B노드에게 C라는 자식노드가 존재한다고 가정할 때, A노드에게 C라는 자식노드가 있을 수 있다. 이 두 노드는 이름만 같을 뿐, 아예 다른 노드이기 때문에 그래프문제처럼 풀면 안 된다. Node라는 클래스를 만들고, 여기에 자신의 값과 children을 넣어주었다. children에 값을 추가하는 것은 별도의 메소드 ..

class 5https://www.acmicpc.net/problem/1197  # 문제그래프가 주어졌을 때, 그 그래프의 최소 스패닝 트리를 구하는 프로그램을 작성하시오.최소 스패닝 트리는, 주어진 그래프의 모든 정점들을 연결하는 부분 그래프 중에서 그 가중치의 합이 최소인 트리를 말한다. # 예제입력 : 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 가중치 C인 간선으로 연결되어 있다는 의미이다. C는 음수일 수도 있으며, 절댓값이 1,000,000을 넘지 않는다.그래프의 정점은 1번부터 V번까지 번호가 매겨져 있고..

이번 챕터에서는 트리 중 가장 대표적인 binary tree (이진 트리)를 기록할 예정이다. 순서는 다음과 같다. binary tree - binary tree의 정의와 종류 - binary tree의 ADT - binary tree를 linked list로 나타내면? binary tree traversal - tree algorithm 종류 1. Binary Tree 1-1. Binary Tree 정의와 종류 Binary Tree는 각 노드가 최대 2개의 자식노드만 갖는 트리를 의미하며, 정확히 2개만 갖는 트리는 proper binary tree라고 부른다. 참고로 트리의 종류를정짓는 요소는 크게 2가지로 structural property, relational property가 있다. struct..

이번 챕터에서는 정말 중요한 자료구조 중 하나인 트리에 대해 공부하려고 한다. 정리 순서는 아래와 같다. 트리란 무엇인가? Linked Structure for Trees tree method & tree method's running time 그럼 시작! 1. 트리란 무엇인가? 트리는 그래프의 일종으로, 간단하게 이야기하면 노드로 이루어진 계층 구조를 나타낸다. tree라고 정의될 수 있는 조건은 루트노드가 필수로 존재해야 한다 루트 밑에 있는 노드들도 트리 조건을 만족해야한다 자식노드는 부모노드가 1개여야만 한다 정도로 정의할 수 있다. 위 조건을 모두 만족해야 tree라고 정의할 수 있다. 트리는 File systems, Web sites, Databases 등에서 활용하고, linked list로..