BinarySearchTree ⇒ 이진검색트리 안녕하세요! 오랜만에 자료구조에 대해서 글을 정리하는거 같습니다! 요즘 스프링, 스프링부트, MySQL을 공부하게 되면서 너무 자료구조랑 알고리즘에 소홀했던거 같아서, 주말에 시간이 좀 남아서 바로 정리를 해보고자 합니다! 이진검색트리? 이진검색트리는 말그대로, 트리형태의 자료구조인데 이진검색 방식을 활용하는것을 말합니다. 기본적으로 이진검색트리는 데이터가 들어가는 시점부터 정렬이 되어 들어가는 형태로 트리에 데이터를 넣고 따로 정렬을 해줄 필요가 없습니다! 또한 이진검색을 활용하기에 트리구조에서 필요한 데이터를 찾을때 걸리는 시간복잡도는 0(logN) 입니다! 한마디로 검색방식에 있어서 매우 효율적인 자료 구조라는 뜻이죠 🙂 이진검색트리의 특징 루트노드의 ..
Tree 구조의 3가지 순회방식 구현! 저번에 tree 구조에 대해서 막막했던 시절을 회상하며, 직접 tree를 구현하고 순회방식도 구현해보기로 했습니다! 일단 tree구조를 만들기 위해서는 Node클래스와 Tree클래스를 만들어야 겠지요? 바로 코드부터 봅시다! class Node{ // 데이터를 저장할 노드를 담당한 클래스 Node 를 생성하여 int data; // int형의 데이터, 노드의 왼쪽,오른쪽 주소를 생성합니다. Node left; Node right; } class tree{ public Node root; // Node의 root를 생성하고, getter,setter를 통해 루트를 설정하는 메소드를 만듭니다. public void setRoot(Node node) { this.root..
Tree, TreeMap, TreeSet. 이번에는 tree에 대하여 정리 해볼려고 합니다! Tree? what the fxxk?? tree 구조는 무엇일까요? 일반적으로 저희가 나무(tree) 를 생각하면 나무는 기둥에서 여러가지 가지로 나뉘어서 흩어져 있습니다. 이러한 의미를 그대로 계승하여 네이밍을 한것이라고 생각하면 좋습니다! tree 구조란 : 최상위 Root값을 기준으로 왼쪽과 오른쪽으로 데이터들이 뻗어나가 있는 형태를 말합니다. 어? 그러면 저희가 알고있는 선형적 자료구조(list,map,set,array) 의 개념이랑 다르게 비선형적 자료구조라고 할수 있겠죠?? 여기서 비선형구조란, 계층도를 떠올리면 이해가 가기 쉬울겁니다. 한가지의 값을 기준으로 아래로 계속 계층적으로 뻗어나가는것입니다...
Stack Queue 자료구조 너무 간단하다. Stack LIFO(Last In First Out) 구조, 마지막에 저장된 것을 제일 먼저 꺼냅니다. Stack 메서드 push Stack에 객체를 저장합니다. pop Stack의 맨 위에 저장된 객체를 꺼냅니다. peek Stack의 맨 위에 저장된 객체를 반환합니다. Stack에서 꺼내지는 않습니다. 비었을 때 null을 반환합니다. empty Stack이 비어있는지 알려줍니다. 있으면 true, 없으면 false를 반환합니다. search Stack에서 주어진 객체를 찾아서 그 위치를 반환합니다. (배열과는 달리 1부터 시작합니다.) 💡 쉽게 말하면 Array의 종류 중 하나일뿐이고, 단순히 누가 먼저 출력이 되냐 차이!!!! 근데 스택은 요즘은 거의..
QuickSort (퀵정렬) 퀵정렬은 구동방식이 생각보다 간단합니다! 일단 배열의 한 기준점을 기준으로 왼쪽에는 기준점보다 작은 값을, 오른쪽에는 큰 값을 정렬 하는것 입니다. 그리고 나서 왼쪽에는 기준점보다 작은값들이 모여있겠지요?? 다시 왼쪽에 있는 배열 데이터로만 하여금 위 과정을 반복하고 반복하다 보면, 더이상 기준점을 기준으로 비교할 대상이 남아있지 않게 되는겁니다. 그러면 배열정렬 끗!!! 이 방법을 곧 “분할 정복(Divide and Conquer) “ 이라고 합니다. 문제를 작은 2개의 문제로 분리하고 각각을 해결한 다음, 결과를 모아서 원래의 문제를 해결하는 전략이다. 분할 정복 방법은 대개 재귀 호출을 이용하여 구현한다. 퀵 정렬의 장단점: 장점: 당연히 속도가 빠르고, 시간복잡도가( ..
