Red Blacke Tree는 Binary Search Tree(이진 탐색 트리)에서 skewed tree(편향된 트리) 한마디로 균형이 잡히지 않고 한쪽으로만 노드가 다 몰리게 되면 시간복잡도가 O(n)이 되는데 이러한 점을 해결하기 위해 나왔다. => 이 트리는 search , insert, delete 모두 O(log n)의 시간 복잡도를 가진다. Red Black Tree의 특징 1. 이 트리의 노드들은 모두 red이거나 black이다. 2. Root 노드와 leaf노드들은 black 이다. 3. 만약 노드가 red이면 그 노드들의 child노드들은 모두 black이다. 4. 자식노드가 없는 노드의 경우(leaf node)를 Nil 노드라고 부른다. 5. 한 노드에서 nil노드까지 갈때 나오는 B..

우선 Trie Tree를 설명하기 전에 Binary Search Tree(이진탐색 트리)를 이용해 문자열을 사용한다 가정하면 기본 이진트리의 검색 시간인 O(log n)과 더불어 각 노드에 들어 있는 문자열(문자열의 최대길이를 M이라 가정)을 찾는 시간 O(M log n)의 시간이 걸린다. 그래서 이 문제를 해결하기 위해 사용하는 것이 Trie tree이다. Trie Tree 이 트리의 경우 node에 문자열을 한자씩만 저장한다. 문자열이 다 같은 문자로 시작하는게 아니기에 Root node의 경우 비워준다. 모든 노드는 최대 26개의 노드를 허용한다. (알파벳이 26개) 단, 대, 소문자 구별시 더 길어진다. 시간 복잡도는 O(M)이된다. (M은 문자열의 최대 길이) 참고자료 https://www.yo..

Heap이란? 최대값이나 최솟값을 빠르게 찾기 위해 고안된 완전 이진트리를 기본으로 한 자료구조이다. 기본적인 종류에는 Min Heap과 Max Heap이 존재한다. Min Heap과 Max Heap Min Heap은 작은값이 항상 위에 있게 그리고 Max Heap은 가장 큰값이 위에 있는 힙이다. 기본적으로 노드 삽입이나 노드 꺼내오는 방식은 Min Heap이나 Max Heap은 같다. Min Heap노드 삽인 1. Tree가 Complete BInary의 형태를 잃지 않게 노드를 왼쪽부터 채워나감 2. 처음 삽입시 정렬된 상태가 아니다. 3. 삽입된 노듣가 값이 작으면 부모노드와 자리를 바꾼다. 4. 3번의 작업을 부모노드 값이 삽입된 노드의 갓ㅂ보다 작을 때까지 혹은 Root에 도달할때 까지 진행한..

트리의 특징 1. Tree는 비선형 자료구조 이다. 이 말은 linear(선형)인 자료구조들 즉 스택과 배열 처럼 자료들간 앞뒤관계가 1:1인 것들과 다르게 하나의 자료 뒤에 여러개의 자료가 존재한다는 뜻이다. 2. 트리는 계층적 관계를 표현하는 자료구조이다. 즉 level 이 있다는 뜻이다. tree는 층별 숫자를 매긴다. Root노드 부터 0으로 시작해서 아래로 내려갈수록 커진다. 이때 트리의 최고레벨을 가리켜 height라고 한다. 트리의 구성요소 - node(노드): 트리를 구성하고 있는 각각의 요소이다. - edge(엣지): 간선 (즉 노드와 노드를 연결하는 선이다.) - root node(루트노드): 트리의 최상위에 있는 노드이다. - terminal node,leaf node (단말노드): ..

1. IoC(Inversion of Control) 제어의 역전, 이 말인 즉, 인스턴스 생명주기 관리를 개발자가 아닌 컨테이너가 해준다는 말이다. 라이브러리와 프레임워크를 비교해보면 조금 더 이해가 쉽다. 라이브러리의 경우 개발자가 라이브러리를 호출한다(주도권은 개발자한테 있음) 프레임워크의 경우 IoC가 적용된경우 프레임워크가 개발자가 작성한 코드를 호출(주도권이 프레임워크한테 있음) Spring의 경우에도 Spring 컨테이너는 IoC를 지원하고 xml을 통해 bean관리 및 어플리케이션 형성한다. 또 Spring컨테이너는 관리되는 bean들을 DI(의존성 주입)을 통해 IoC지원한다. 2. Class Library 프레임워크의 기술적인 구현을 라이브러리 형태로 제공한다. 2. 디자인패턴 프레임워크..

우리가 코드를 짜다 보면 반복적으로 사용하게 되는 코드의 양이 상당하다는 것을 깨닫게 된다. 요즘은 여러가지 방법으로 코드를 재사용할 수 있도록 만들었지만 옛날에는 코드를 일일이 다 짜줘야 해서 아주 피곤한일이 반복되었다. 그러면 어떻게 코드를 재사용할 수 있게 변해왔는지 확인해보자. 1. Copy and Paste 첫 시작은 말 그대로 복사 붙여넣기였다. 학교 시스템을 개발하는 프로그램을 짠다고 생각해보면 각 선생님들과 수업에 대한 코드는 상당히 겹칠 가능성이 크다. 하지만 이때는 별도의 방법이 없어 그저 복사해서 붙여 넣기를 해주었다. 일단 코드를 복사 붙여넣기 하는 것도 귀찮을 뿐더러 코드를 수정하는 일이 생기면 일일이 모든 코드들을 수정해주어야하니 생각만 해도 복잡하다. 2. Method 그래서 ..