Algorithm & Data structure

Red-Black 트리 가장 유명하고 많이 사용되는 균형이진탐색트리이다. 예시 그림을 통해 보자. 이 그림에서 처음 보는 NIL이라는 단어는 Null, None을 의미하는 노드이다. 그 전까지는 없는 값을 그리지 않았지만 해당 트리에서는 독립된 노드로 표현한다. 또한 NIL 노드는 모두 리프노드라고 부르고, 나머지 노드는 내부노드라고 부른다. Red-Black 트리 조건 Red-Black 트리는 5가지 조건을 만족해야 한다. 조건1. 각 노드는 red/black의 색을 갖는다 조건2. 루트노드는 black 조건3. 리프노드인 NIL 노드의 색은 black으로 정의 조건4. 어떤 노드가 red라면, 두 자식노드는 모두 black 조건5. 각 노드에서 서브트리의 리프 NIL노드까지의 모든 경로에 포함된 bl..

균형이진탐색트리(Balanced Binary Sarch Tree, BBST) 이전에 살펴보았던 이진 탐색 트리는 닉값처럼 탐색에 최적한 트리이다. 우리가 어떤 key 값을 찾고 싶을 때 각 노드마다 값을 비교해서 내가 원하는 key값이 비교하는 key값보다 작다면 왼쪽, 크다면 오른쪽으로 가는 식으로 계속 밑으로 탐색하여 찾는 방식이었다. 하지만 이런 경우 루트 노드부터 시작해 계속 내려가고 결국 트리 높이 h에 의해 연산 시간이 결정되는데, 최악의 경우 O(h)가 되어 탐색이 느리고 탐색을 포함하는 삽입, 삭제 연산 또한 느려진다는 단점이 있다. 그렇기 때문에 연산 속도를 빠르게 만들기 위해서는 직접적으로 연산 시간에 영향을 주는 트리의 높이를 되도록 작게 유지하는 것이 중요하다. 연산시간을 가장 작게..

정의 전에 했던 것처럼 노드의 자식 노드가 없거나, 1개 혹은 2개까지 있을 수 있는 트리이다. 일반적으로 자식이 많으면 유용한 면도 있지만 연산이 복잡해지기 때문에 이진트리를 주로 많이 사용한다. 표현법 1. 이진트리 → 배열 or 리스트에 저장 배열과 리스트에 저장하는 방식으로 표현한 대표적인 자료구조가 앞에서 보았던 heap이다. 그런데 이렇게 배열과 리스트에 표현하면 메모리에 낭비하는 부분이 있다. 3. 노드와 링크를 직접적으로 표현 연결리스의 노드에 해당되는 클래스를 선언하고, 연결리스트를 나타내는 한방향, 양방향 리스트로 표현했듯이 Node 클래스와, BT(Binary Tree) 클래스를 선언해서 직접적으로 표현할 수 있다. 예를 들어 이렇게 노드들이 있다고 생각해보면 각 노드들은 key값이 ..

heap의 표현방식 앞에서 트리 중에서도 이진트리에 대해서 알아봤고, 표현하는 방법에는 3가지가 있었다. 이 중에서 첫 번째 표현 방식인 리스트에 대해서 더 알아보려고 한다. 앞에서 이런 트리 구조를 가지고 리스트로 표현했다. H = [a, b, c, None, d, e, f] #level 0부터 level 1, 2...로 내려가면서 각각의 노드를 리스트에 저장(좌->우 순서대로) #만약에 자식 노드중에 왼쪽 노드가 없다면 None으로 채워놓는다. 각각의 레벨마다 노드가 모두 차 있다는 생각을 하고 리스트를 작성하기 때문에 none으로 빈 자리를 채워주었다. 이를 레벨별로 나누어 보면 level 0 - a level 1 - b,c level 2 - None, d, e, f 이 된다. 이렇게 리스트로 표현..

트리구조 소개 이제까지 살펴본 것들은 순차적 자료구조로 순서에 따라 저장되어 있는 것들을 의미했다. 배열의 경우 인덱스 i = 0, 1, 2....이런 식으로 순서에 따라 인덱스에 따로 저장되어 있고 인덱스를 알면 거기에 저장된 값을 알 수 있었다. 연결 리스트의 경우 링크에 따라서 다운 노드의 값을 알 수 있었으므로 저장되어 있는 순서가 있었다. 그런데 이 연결리스트에서 헤드노드를 위에 그리고 테일노드를 아래쪽으로 그리는 식으로 세워서 그리면 하나의 부모가 자식노드를 하나씩 가지고 밑으로 내려가는 방식이 된다. 이러한 모양에서 각각 노드들은 키값을 가진다. 이렇게 부모와 자식이 관계를 갖고 자료를 구성하는 자료구조를 트리라고 한다. 그래서 어찌보면 연결리스트의 경우도 트리의 관점으로 본다면 자식 노드가..

Quadratic Probing 앞에서 설명한 Linear probing의 경우 한 칸씩 밑으로 내려가면서 탐색,삭제,삽입 연산을 진행했다. 여기서 coliision이 일어날 때마다 밑으로 한 칸씩 내려가기 때문에 collision이 발생할 때마다 클러스터의 길이가 1씩 증가한다는 특징이 있다. 클러스터의 길이에 따라서 성능이 좌지우지되므로 그리 좋은 방식은 아니었는데 이 한 칸씩 밑으로 내려가는 것의 단점을 보완하여 밑으로 바로 내려가는 것이 아닌 몇 칸씩 띄워서 보는 방식인 Quadratic probing을 사용할 수 있다. 여기서 이 Quadratic은 제곱을 의미하는데, 처음에 k를 보고 다음에 k+1^2번째, 다음엔 k+2^2번째.. 이렇게 차례대로 1부터 순차적으로 수의 제곱만큼 건너가서 해당..

앞에서 설명했듯 해시 함수의 경우 아무리 잘 설계하더라도 그 해시 함수가 완벽하지 않다면 아이템들을 살피다가 충돌이 발생할 수밖에 없다. 그렇다면 충돌이 발생했을 때 다른 곳에 저장시키기 위해 충돌 회피 방법(Collision resolution method)을 정해줘야 한다. 이 충돌 회피 방법에도 여러가지가 존재하는데, 가장 대표적인 것은 Open Addressing이다. Open Addressing은 내가 충돌이 일어났을 때 그 주위의 빈칸을 찾아서 저장시키는 방법이다. Open Addressing에도 여러 방법이 있는데, - Linear probing - Quadratic probing - Double hashing 이 있다. Porbe는 찌른다(살피다)는 의미로 내가 가려고 하는 칸에 다른 값이..

해시테이블은 다양한 분야에서 사용되고 있는 강력한 자료구조이다. 장점으로는 삽입,삭제,탐색 연산이 매우 빠르다 파이썬에서는 딕셔너리의 구조로 해시테이블을 만들 수 있는데 key 값과 value값으로 나눠 따로 저장한다. dict_example = {} # 빈 딕셔너리 선언 dict_example['201912345'] = "김철수" # 딕셔너리에 추가하기 # key값 : 201912345, value값 : 김철수 dict_example = {201912345:"김철수", 201912346 : "김민수"} # 딕셔너리 초기화 이런 식으로 딕셔너리에 저장하게 된다면 key값에 저장하는 값이 있고 value값에 저장하는 값이 따로 있다 주로 key값에는 아이템들의 분류를 위해 중복이 없고, value값에는 k..

양방향 연결 리스트(Doubly Linked List) 한방향 연결 리스트의 경우 prev 노드를 찾기 위해 while문을 사용해서 앞에서부터 찾아야 했으므로 최대 O(n)의 시간복잡도를 가지기에 조금 더 오래 걸린다는 단점이 있다. 양방향 연결 리스트는 이 한방향 연결 리스트의 단점을 보완한 버전. 양쪽에서 접근이 가능하여 더 빨리 찾을 수 있다는 장점이 있다. 이렇게 찾아야 했던 연결리스트에서 양쪽으로 접근이 가능하게 되어 바로 tail 노드로의 접근이 가능하고 tail노드의 전 노드가 Prev노드이기 때문에 상수시간밖에 걸리지 않는다. 삭제 또한 상수개의 링크만 수정하여 삭제연산을 실행할 수 있다. 우리가 이제까지 가질 수 있는 노드는 총 세가지가 있다. 여기서 한방향리스트는 방향이 오른쪽으로 가는..

연결리스트(Linked List)는 데이터 요소들을 순차적으로 연결한 자료구조이다. 이 자료구조는 각 요소들이 메모리 상에서 연속적으로 위치하지 않고, 각 요소가 데이터와 다음 요소를 가리키는 포인터(링크)로 연결되어 있는 특징이 있다. 연결리스트를 통해 데이터의 삽입, 삭제, 검색 등을 유연하게 처리할 수 있다. 연결리스트는 보통 노드(Node)라고 불리는 작은 단위로 구성 각 노드는 데이터 필드와 다음 노드를 가리키는 링크 필드로 구성된다. 첫 번째 노드는 헤드(Head) 노드라고 불리며, 마지막 노드는 테일(Tail) 노드라고 한다. 헤드를 통해 연결리스트의 시작 지점을 찾을 수 있고, 테일은 다음 노드를 가리키는 포인터가 NULL인 노드를 가리킨다. 연결리스트는 한방향 연결리스트(Singly Li..