[코드스테이츠] 05_15_TIL : 알고리즘/자료구조 _ Tree / Graph
2023. 5. 16. 09:09
728x90
반응형
Today I Lean
알고리즘/자료구조 _ Tree / Graph
또 다른 구조를 배우다 보니 또 헷갈리지만..
앞으로 나아가다보면 이것또한 이해할 날이 올거라고 생각한다.
배운 것
# Tree
1. Tree 란?
- 단방향 그래프의 한 구조
- 하나의 뿌리로부터 가지가 사방으로 뻗은 형태
- 데이터가 바로 아래에 있는 하나 이상의 데이터에 무방향으로 연결된 계층적 자료구조
- 하나의 데이터 아래에 여러개의 데이터가 존재할 수 있는 비 선형 구조
- 아래로만 뻗어나가기 대문에 사이클이 없음
2. Tree의 구조와 특징
- 구조와 특징
: 루트(Root)라는 하나의 꼭짓점 데이터를 시작으로 각각의 노드(Node)를 연결
→ 자식이 없는 노드는 나무의 잎과 같다고 하여 리프 노드(Leaf Lode) 라고 함
- 깊이 (Depth)
: 루트로부터 하위 계층의 특정 노드까지의 깊이 표현 가능
→ 루트노드는 0, 한 칸씩 아래로 내려갈수록 1씩 더해짐
- 레벨 (Levle)
: 같은 깊이를 가지고 있는 노드를 묶어서 레벨로 표현 가능
→ 같은 레벨에 나란히 있는 노드를 형제노드 라고 함
- 높이 (Height)
: 리프노드를 기준으로 루트까지의 높이를 표현
→ 자식노드중 하나는 자식이 있고, 하나는 리프노드 일때, 부모노드는 자식노드의 가장 높은 height+1의 값을 가짐
- 서브 트리 (Sub Tree)
: 큰 트리의 내부에 트리구조를 갖춘 작은 트리를 지칭
- 용어
* 노드 (Node) : 트리구조를 이루는 모든 개별 데이터
* 루트 (Root) : 트리 구조의 시작점이 되는 노드
* 부모 노드 (Parent node) : 두 노드가 상하관계로 연결되어 있을 때 상대적으로 루트에서 가까운 노드
* 자식 노드 (Child node) : 두 노드가 상하관계로 연결되어 있을 때 상대적으로 루트에서 먼 노드,
* 리프 (Leaf) : 트리 구조의 끝 지점, 자식노드가 없는 노드
3. Tree 구현
package Recursion.TreeGraph;
import java.util.*;
public class TreeEx {
private String value;
private ArrayList<TreeEx> children;
public TreeEx() { // 매개변수가 없는 생성자
this.value = null; // value를 null로 초기화
this.children = null; // children을 null로 초기화
}
public TreeEx(String data) { // data라는 매개변수가 있는 생성자
this.value = data; // value를 data로 초기화
this.children = null; // children을 null로 초기화
}
public void setValue(String data) { // 현재 노드의 데이터 값을 설정하는 메서드
this.value = data; // 전달된 data를 현재노드의 value로 설정
}
public String getValue() { // 현재 노드의 데이터를 반환
return value; // 현재노드의 value를 반환
}
// addChildNode(value): 입력받은 value를 Tree에 계층적으로 추가할 수 있어야 합니다.
public void addChildNode(TreeEx node) { // 자식노드를 추가하는 메서드
if(children == null) { // children이 null인 경우
children = new ArrayList<>(); // 새로운 ArratList 인스턴스를 생성해서 자식노드를 저장
}
children.add(node); // 전달된 node를 현재 노드의 children목록에 추가
}
// removeChildNode(node): 입력받은 node를 Tree에서 삭제할 수 있어야 합니다.
public void removeChildNode(TreeEx node) { // 자식노드를 제거하는 메서드
String data = node.getValue();
if(children != null) {
for(int i = 0; i < children.size(); i++) {
if(children.get(i).getValue().equals(data)) {
children.remove(i);
return;
}
if(children.get(i).children != null) children.get(i).removeChildNode(node);
}
}
}
// getChildrenNode(): 현재 트리에서 존재하는 children을 리턴합니다.
public ArrayList<TreeEx> getChildrenNode() { // 현재 노드의 자식 노드들을 담고 있는 ArrayList 객체를 반환하는 메서드
return children;
}
// contains(value): 트리에 포함된 데이터를 찾을 수 있어야 합니다.
public boolean contains(String data) { //재귀를 사용하여 값을 검색합니다.
if(value.equals(data)) return true; // 전달된 data 값이 현재 노드의 value와 일치하는지 확인, 일치하면 ture 반환
boolean check;
if(children != null) { // children이 null이 아닌경우
for(int i = 0; i < children.size(); i++) { // 자식노드를 순회하면서
check = children.get(i).contains(data, false); // 각각에 대해 contains(data, false)메서드를 재귀적으로 호출
// check 변수를 false로 전달해 이전까지 검색된 결과가 없을을 나타냄
if(check) return true; // 만약 check가 ture일 경우 ture를 반환
}
}
return false; // 아닐경우 false 반환
}
public boolean contains(String data, boolean check) { //재귀를 사용하여 값을 검색합니다.
if(value.equals(data)) return true;
if(children != null) {
for(int i = 0; i < children.size(); i++) {
check = children.get(i).contains(data, check);
}
}
return check;
}
}
4. 이진 탐색 트리 (Binary Search Tree)
- 이진 탐색 이란?
- 정렬된 데이터 중에서 특정 값을 찾기 위한 탐색 알고리즘
- 오름차순으로 정렬된 데이터를 같은 크기의 두 부분으로 나누고, 두 부분중 탐색이 필요한 부분만 탐색하도록 범위를 제한하는 알고리즘
- 이진 탐색 트리의 탐색 과정
- 전체 데이터 에서 중간(Root)에서 내가 찾는 값이 있는지 확인 (찾는 값 이라면 탐색 종료)
- 중간값이 찾는 값이 아닐 경우, 찾는 값이 중간값보다 큰지 작은지 확인
- 중간값보다 작을 경우, 데이터의 맨 앞부터 중간값 전까지의 범위를 탐색 범위로 잡고 왼쪽 서브트리 반복탐색
- 중간값보다 클 경우, 데이터의 맨 뒤부터 중간값 바로 뒤까지의 범위를 탐색 범위로 잡고 오른쪽 서브트리 반복탐색
→ 트리 안에 찾는 값이 있을 경우 무조건 트리의 높이(h) 이하의 탐색이 이뤄짐
→ 트리 안에 찾는 값이 없을 경우 최대 h만큼의 연산및 탐색이 진행됨
- 이진 탐색 트리의 종류와 특징
- 정 이진 트리 (Full Binary tree) : 각 노드가 0개/2개의 자속 노드를 가짐
- 포화 이진 트리 (Perfect Binary tree) : 정 이진트리 && 완전 이진트리 (모든 리프노드의 레벨이 같고, 모든 레벨이 가득 채워져 있음)
- 완전 이진 트리 (Complete Binary tree) : 마지막 레벨을 제외한 노드가 가득 차 있어야 함 (마지막레벨의 노드는 왼쪽이 채워져 있어야 함)
- 이진 탐색 트리에서 노드의 추가 / 삭재
: 추가
→ 노드의 값이 현재 노드보다 작으면 왼쪽, 크면 오른쪽 서브 트리에 추가
: 삭제
→ 리프노드 삭제 (그냥 삭제)
→ 자식 노드가 하나인 경우 (해당 노드의 부모 노드와 자식 노드를 연결)
→ 자식 노드가 두 개인 경우 (해당 노드를 대체할 자식노드를 찾고, 해당 노드와 자식노드 위치를 변경 후 재귀적 실행)
*****이진트리*****
- 이진 탐색 트리 (Binary Search Tree, BST)
: 이진트리의 일종 (자식 노드가 최대 두개인 노드들로 구성된 트리)
→ 왼쪽 서브트리는 해당노드보다 작은 값 / 오른쪽 서브트리는 해당노드보다 큰 값
- 힙 (Heap)
: 완전 이진트리의 일종
→ 각 노드의 값이 자식노드의 값보다 작거나 큰 특정 순서를 유지
→ 최소 힙 = 부모노드의 값 <= 자식노드의 값 / 최대 힙 = 부모노드의 값 >= 자식노드의 값
- 트라이 (Trie)
: 문자열을 저장하고 검색하는데 특화된 트리구조
→ 각 노드가 여러 자식노드를 가질수 있음
→ 각 노드는 문자열의 한 문자를 저장
→ 문자열 검색, 자동 완성, IP 라우팅 등의 목적으로 사용됨
- 레드-블랙 트리
: 이진 탐색 트리의 또 다른 확장
→ 노드에 색 부여, 특정 규칙을 만족하며 균형을 유지
→ 이 규칙 덕분에 탐색, 삽입, 삭제 연산의 시간 복잡도가 O(log N)을 유지
5. Binary Search Tree 구현
package Recursion.TreeGraph;
import java.util.ArrayList;
public class BinarySearchTreeEx {
// 트리를 구성하는 노드 클래스입니다.
public static class Node {
private int data;
private Node left;
private Node right;
/* 생성자 */
public Node(int data) {
this.setData(data);
setLeft(null);
setRight(null);
}
public int getData() {
return data;
}
public Node getLeft() {
return left;
}
public Node getRight() {
return right;
}
public void setData(int data) {
this.data = data;
}
public void setLeft(Node left) {
this.left = left;
}
public void setRight(Node right) {
this.right = right;
}
}
//이진 탐색 트리의 클래스입니다.
public static class binarySearchTree {
public Node root;
public binarySearchTree(){
root = null;
}
// tree에 value를 추가합니다.
// insert(value): 입력받은 value를 Binary Search에 맞게 Tree에 계층적으로 추가할 수 있어야 합니다.
public void insert(int data) {
Node newNode = new Node(data); // 왼쪽, 오른쪽 자식 노드가 null 이며 data 의 값이 저장된 새 노드 생성
if (root == null) {// 루트 노드가 없을때, 즉 트리가 비어있는 상태일 때,
root = newNode;
return;
}
if(root.data == data) return; //중복일때 정지
Node currentNode = root;
Node parentNode = null;
while (true) {
parentNode = currentNode;
if (data < currentNode.getData()) { // 해당 노드보다 작을 경우
currentNode = currentNode.getLeft();
if (currentNode == null) {
parentNode.setLeft(newNode);
return;
}else if(currentNode.data == newNode.data) return;
} else { // 해당 노드보다 클 경우
currentNode = currentNode.getRight();
if (currentNode == null) {
parentNode.setRight(newNode);
return;
}else if(currentNode.data == newNode.data) return;
}
}
}
// tree의 value값을 탐색합니다.
// contains(value): 트리에 포함된 데이터를 찾을 수 있어야 합니다.
public boolean contains(int data) {
Node currentNode = root;
while (currentNode != null) {
// 찾는 value값이 노드의 value와 일치한다면, true를 리턴합니다.
if (currentNode.data == data) {
return true;
}
if (currentNode.data > data) {
// 찾는 value값이 노드의 value 보다 작다면, 현재 노드를 left로 변경후 다시 반복합니다.
currentNode = currentNode.left;
}else {
// 찾는 value값이 노드의 value 보다 크다면, 현재 노드를 right로 변경후 다시 반복합니다.
currentNode = currentNode.right;
}
}
return false;
}
/*
트리의 순회에 대해 구현을 합니다.
지금 만드려고 하는 이 순회 메서드는 단지 순회만 하는 것이 아닌, 함수를 매개변수로 받아 콜백 함수에 값을 적용시킨 것을 순회해야 합니다.
전위 순회를 통해 어떻게 탐색하는지 이해를 한다면 중위와 후위 순회는 쉽게 다가올 것입니다.
*/
// 이진 탐색 트리를 전위 순회하는 메서드를 만듭니다.
// preorder(root, depth, list): 전위 순회를 통해 트리의 모든 요소를 정렬하여 ArrayList 타입으로 반환합니다.
public ArrayList<Integer> preorderTree(Node root, int depth, ArrayList<Integer> list) {
if (root != null) { // root(현재 노드)가 null이 아닐때
list.add(root.getData()); // list에 root 데이터 추가
preorderTree(root.getLeft(), depth + 1, list); // left노드의 깊이를 +1 하고, 재귀호출하여 list에 추가
preorderTree(root.getRight(), depth + 1, list); // Right노드의 깊이를 +1 하고, 재귀호출하여 list에 추가
}
return list;
}
// inorder(root, depth, list): 중위 순회를 통해 트리의 모든 요소를 정렬하여 ArrayList 타입으로 반환합니다.
public ArrayList<Integer> inorderTree(Node root, int depth, ArrayList<Integer> list) {
if (root != null) {
inorderTree(root.getLeft(), depth + 1, list);
list.add(root.getData());
inorderTree(root.getRight(), depth + 1, list);
}
return list;
}
// postorder(root, depth, list): 후위 순회를 통해 트리의 모든 요소를 정렬하여 ArrayList 타입으로 반환합니다.
public ArrayList<Integer> postorderTree(Node root, int depth, ArrayList<Integer> list) {
if (root != null) {
postorderTree(root.getLeft(), depth + 1, list);
postorderTree(root.getRight(), depth + 1, list);
list.add(root.getData());
}
return list;
}
}
}
# Graph
1. Graph 란?
- 여러 개의 점들이 서로 복잡하게 연결되어 있는 관계를 표현한 자료 구조
- 자료구조의 그래프는 여러개의 점들이 선으로 이어져 있는 복잡한 네트워크망과 같은 모습을 가짐
2. Graph의 구조
- 구조
- 직접적인 관계 : 두 점 사이를 이어주는 선이 있음
- 간접적인 관계 : 몇 개의 점과 선에 걸쳐 이어짐
- 하나의 점 : 정점 (vertex)
- 하나의 선 : 간선 (edge)
3. Graph의 표현방식
- 인접 행렬
: 두 정점을 이어주는 간선이 있다면 이 두 정점은 인접한다 라고 함
→ 두 정점이 이어져 있다면 1(ture), 이어져 있지 않다면 0 (false)
int[][] matrix = new int[][]{
{0, 0, 1}, // A정점에서 이동 가능한 정점을 나타내는 행
{1, 0, 1}, // B정점에서 이동 가능한 정점을 나타내는 행
{1, 0, 0}. // C정점에서 이동 가능한 정점을 나타내는 행
};
A의 진출차수는 1개 A → C
[0][2] == 1
B의 진출차수는 2개 B → A, B → C
[1][0] == 1
[1][2] == 1
C의 진출차수는 1개 C → A
[2][0] == 1
- 인접 리스트
: 각 정점이 어떤 정점과 인접하는지를 리스트의 형태로 표현
→ 각 정점마다 하나의 리스트를 가짐
→ 이 리스트는 자신과 인접한 다른 정점을 담고 있음
→ 메모리를 효율적으로 사용해야 할때 사용
(인접행렬은 연결 가능한 모든 경우의 수를 저장하기 때문에 상대적으로 메모리를 많이 차지함)
- 용어
- 정점 (vertex) : 노드(node)라고도 함, 데이터가 저장되는 그래프의 기본 원소
- 간선 (edge) : 정점 간의 관계를 나타냄 (정점을 이어주는 선)
- 인접 정접 (adjacent vertex) : 하나의 정점에서 간선에 의해 직접 연결되어 있는 정점
- 관계 없음 : 간선으로 연결되지 못한 정점들의 관계
- 가중치 그래프 (weighted Graph) : 연결의 강도가 얼마나 되는지 적혀 있는 그래프 (추가적인 정보 파악 가능)
- 비가중치 그래프 (unweighted Graph) : 특정 정점 두개가 연결되어 있지만, 연결의 강도가 얼마나 되는지 적혀있지 않는 그래프(추가적인 정보를 파악 불가능)
- 무향(무방향) 그래프 (undirected Graph) : 양방향으로 오고갈 수 있는 그래프
- 단방향 그래프 (directed Graph) : 한쪽 방향으로만 갈 수 있는 그래프
- 진입차수 (in-degree) / 진출차수 (out-detree) : 한 정점에 진입하고 진출하는 간선의 수를 나타냄
- 자기 루프 (self loop) : 정점에서 진출하는 간선이 곧바로 자기 자신에게 진입하는 경우 (다른 정점을 거치지 않음)
- 사이클 (Cycle) : 한 정점에서 출발하여 다시 출발정점으로 돌아갈 수 있는 경우
4. Graph 구현
package Recursion.TreeGraph;
public class GraphEx {
private int[][] graph; //graph 라는 빈 2차원배열 생성
// setGraph(size): 그래프에 size만큼의 버텍스를 추가해야 합니다.
public void setGraph(int size) {
graph = new int[size][size]; // graph 변수를 크기가 size인 2차원 정수 배열로 초기화
for(int i = 0; i < size; i++) {
for(int j = 0; j < size; j++) {
graph[i][j] = 0; // 정점 i와 정점 j가 연결되어있지 않음을 나타냄, 간선의 개수를 초기화
}
}
}
// getGraph(): 인접 행렬 정보가 담긴 배열을 반환합니다.
public int[][] getGraph() {
return graph;
}
// addEdge(from, to): fromVertex와 toVertex 사이의 간선을 추가합니다.
public void addEdge(int from, int to) {
if(from >= graph.length || to >= graph.length) return;
graph[from][to] = 1;
}
// hasEdge(from, to): fromVertex와 toVertex 사이의 간선이 존재하는지 여부를 Boolean으로 반환해야 합니다.
public boolean hasEdge(int from, int to) {
if(from >= graph.length || to >= graph.length) return false;
else if(graph[from][to] == 1) return true;
else return false;
}
// removeEdge(from, to): fromVertex와 toVertex 사이의 간선을 삭제해야 합니다.
public void removeEdge(int from, int to) {
if(from >= graph.length || to >= graph.length) return;
graph[from][to] = 0;
}
}
5. 그래프 인접리스트(Graph Adjacency List) 구현
package Recursion.TreeGraph;
import java.util.ArrayList;
public class GraphAdjacencyListEx {
private ArrayList<ArrayList<Integer>> graph;
public GraphAdjacencyListEx() {
graph = new ArrayList<>();
}
// TODO: 정점을 추가합니다.
// 넘겨받은 size만큼 빈 ArrayList를 값으로 할당합니다.
// setGraph(size): 그래프에 size 만큼의 버텍스를 추가해야 합니다.
public void setGraph(int size){
for(int i = 0; i < size; i++) {
graph.add(new ArrayList<>());
}
}
//그래프를 반환합니다.
public ArrayList<ArrayList<Integer>> getGraph() {
return graph;
}
// TODO: 간선을 추가합니다.
// addEdge(fromVertex, toVertex): fromVertex와 toVertex 사이의 간선을 추가합니다.
public void addEdge(int from, Integer to) {
//from, to가 그래프의 크기보다 크거나, 음수일 경우 아무것도 추가하지 않습니다.
if(from < 0 || to < 0 || from >= graph.size() || to >= graph.size()) return;
//from, to가 정확하게 입력되었을 경우
// - from의 인접 리스트에 to를 추가하고
// - to의 인접 리스트에 from를 추가합니다.
graph.get(from).add(to);
graph.get(to).add(from);
}
// hasEdge(fromvertex, toVertex): fromVertex와 toVertex 사이의 간선이 존재하는지 여부를 Boolean으로 반환해야 합니다,
public boolean hasEdge(int from, int to) {
//from, to가 그래프의 크기보다 크거나, 음수일 경우 아무것도 추가하지 않습니다.
if(from < 0 || to < 0 || from >= graph.size() || to >= graph.size()) return false;
//ArrayList에서 제공하는 contains를 사용하여 boolean 타입의 값을 반환합니다.
else return graph.get(from).contains(to);
}
// removeEdge(fromVertex, toVertex): fromVertex와 toVertex 사이의 간선을 삭제해야 합니다.
public void removeEdge(int from, int to) {
//from, to가 그래프의 크기보다 크거나, 음수일 경우 아무것도 제거하지 않습니다.
if(from < 0 || to < 0 || from >= graph.size() || to >= graph.size()) return;
//from의 인접 리스트가 to로 이어지는 간선이 존재하는 경우
if(graph.get(from).contains(to)) {
//from의 인접 리스트에서 to를 삭제합니다.
graph.get(from).remove((Integer) to);
}
//to의 인접 리스트가 from으로 이어지는 간선이 존재하는 경우
if(graph.get(to).contains(from)) {
//to의 인접 리스트에서 from을 삭제합니다.
graph.get(to).remove((Integer) from);
}
}
}
*****
1. 여러가지 트리구조
Tomorrow Chapter
# Tree Serach Algorithm
# Graph Search Algorithm
# 알아두면 좋은 자료구조
↓ 이전 글 ↓
[코드스테이츠] 05_12_TIL : 알고리즘/자료구조 _ Stack/Queue
Today I Lean 알고리즘/자료구조 _ Stack/Queue 생각보다 개념은 쉬웠지만, 이것을 또 적용하여 문제를 푸는것은 쉬운일이 아니었다. 이전의 개념도 확실히 자리잡지 못해서 더 어려웠던것 같다. 학습
theflower01.tistory.com
↓ 코트스테이츠 부트캠프 관련 글 한번에 보기 ↓
'IT/코드스테이츠 부트캠프' 카테고리의 글 목록
Flower, Plant, Study
theflower01.tistory.com
728x90
반응형
'Study > 코드스테이츠 부트캠프' 카테고리의 다른 글
| [코드스테이츠] 05_17_TIL : 알고리즘/자료구조 _ Greedy/Algorithm (1) | 2023.05.17 |
|---|---|
| [코드스테이츠] 05_16_TIL : 알고리즘/자료구조 _ Tree, Graph Search Algorithm (1) | 2023.05.16 |
| [코드스테이츠] 05_12_TIL : 알고리즘/자료구조 _ Stack/Queue (0) | 2023.05.13 |
| [코드스테이츠] 05_11_TIL : 알고리즘 / 자료구조 _ 재귀함수 실습과제 (0) | 2023.05.11 |
| [코드스테이츠] 05_10_TIL : 알고리즘 / 자료구조 _ 재귀함수 이론 (0) | 2023.05.10 |
