개발 및 기술 블로그

1. 이진 탐색 트리 -이진 탐색트리 :== 트리에서 특정 데이터의 효과적인 검색을 위해 제한점을 가지는 이진트리 -특정 데이터를 검색하고, 노드를 삽입/삭제하는 응용 문제에 가장 효과적인 트리 -탐색에 최적화된 이진 트리 -키: 이진 트리 노드의 데이터 이진 탐색 트리의 특징 - 왼쪽 서브트리에 있는 모든 노드의 자식 키값은 작다. - 반대로 서브트리에 있는 모든 노드의 자식 키값은 크다. 이진 탐색 트리의 단점 - BS 트리의 성능은 트리의 구조와 특정 노드에 접근할 확률에 영향을 받음 - 트리의 성능이 구조에 영향을 받기 때문에 최적의 BS 트리구조를 결정하기 어려움 좋은 성능의 BS 트리를 구축하는 방법(휴리스틱) - 자주 탐색하는 키를 가진 노드를 트리의 루트에 가깝게 놓는다. - 트리가 균형이..

선택 트리가 왜 필요할까?? 위 그림과 같이 정렬된 데이터 리스트 k개가 있다고 가정해 보자. 이 8개의 리스트를 전부다 합칠것인데 오름차순으로 정렬을 하여 합친다면 시간 복잡도는 k * k-1가 되는데 너무 많은 연산을 해야한다. 이러한 문제를 해결하기 위해 합병 정렬에 사용하는 특수한 트리가 있는데 그것을 선택트리 라고 한다. 선택 트리의 종류 2가지 1. 승자 트리 -승자 트리:== 부모 노드가 두 자식 노드보다 작은 값을 갖는 완전 이진 트리 -작은 값이 승자가 되어 올라가는 토너먼트 경기와 유사 -트리의 각 노드는 두 자식 노드 값이 승자를 자신의 값으로 함 -결과적으로 루트의 값이 트리에서 가장 작은값 2.패자 트리 -패자 트리:== 각 노드가 두 자식 노드보다 더 작은 값을 갖는 완전 이진 ..

힙을 설명하려면 먼저 우선순위 큐를 알아야 한다. 우선순위 큐 큐: 먼저 들어간 데이터가 먼저 삭제되는 자료구조 (FIFO: First In First Out) 우선순위 큐: 대기 리스트에서 항상 우선순위가 높은 사람이 먼저 서비스를 받는 구조 삽입과 삭제 삽입: 기존 큐와 같이 rear에 데이터를 삽입한다. 삭제: 기준 큐와 달리 우선순위를 고려하여 우선수위가 가장 높은 데이터를 삭제한다. -삭제 명령이 실행되면 저장된 데이터 중에서 가장 우선 순위가 높은것이 삭제된다. -나머지 데이터는 어떤 순서로 저장되든 문제가 되지 않는다. 그렇다면 힢을 한번 알아보자 힢의 정의 -피라미드 모양으로 쌓아 올린 더미 -무엇인가를 쌓아놓은 더미이고 항상 가장 위에 있는것을 우선 꺼내는 구조 -부모-자식 노드사이에서 ..

#include #include struct NODE { struct NODE *next; //다음 노드의 주소를 저장할 포인터 int data; }; void addFirst(struct NODE *target, int data) { struct NODE *newNode = malloc(sizeof(struct NODE)); newNode->next = target->next; newNode->data = data; target->next = newNode; } void removeFirst(struct NODE *target) { struct NODE *removeNode = target->next; target->next = removeNode->next; free(removeNode); } int..

트리란? 트리는 어떤 노드들의 집합인데 여러 노드가 한 노드를 가리킬 수 없는 구조이다. 폴더 디렉토리의 구조가 트리구조의 대표적인 예다. 관련 용어 Root Node : 트리 구조에서 최상위에 존재하는 A와 같은 노드 Node : 트리의 구성요소에 해당하는 A,B,C,D,E,F,G,H,I,J와 같은 요소 Edge : 노드와 노드를 연결하는 연결설 Terminal Node(Leaf Node) : 밑으로 또 다른 노드가 연결되어 있지 않은 H,I,J,F,G와 같은 노드 Sub-Tree : 큰 트리(전체)에 속하는 작은 트리 Level : 트리에서 각 층별로 숫자를 매김 Height : 트리의 최고 레벨 (3) 참고 자료:velog.io/@adam2/TREE

그래프란? 노드(Vertex)가 있고 그 노드를 연결하는 간선(edge)을 하나로 모아놓은 비선형 자료구조 그래프의 종류 무방향 그래프(undirected graph): 간선을 통해 양방향으로 이동하며, 정점A와 정점B를 연결하는 간선은 (A, B)와 같이 쌍으로 표현한다. 방향 그래프(directed graph): 간선에 방향성이 존재한다. A →B 로만 갈 수 있는 간선은 로 표시한다. 와 는 다르다. 가중치 그래프(weighted graph): 간선에 비용이나 가중치가 할당된 그래프로 ‘네트워크(Network)’라고도 한다. 그래프의 구현 방식 1. 인접 행렬 2. 인접 리스트 그래프 메서드 .addNode() : 새로운 node를 생성하여 그래프에 추가한다. .contains() : node.va..

해쉬테이블이란? 해쉬테이블은 키와 값을 한 쌍으로 저장하는 자료구조이다. 키를 입력받으면 숫자를 반환하는 Hash함수가 있다. 이 숫자는 인덱스 번호가 된다. 해쉬테이블 시간 복잡도 값을 가져올 때 : O(1) 값을 추가할 때 : O(1) 값을 삭제할 때 : O(1) 해쉬 충돌 해결방법 종류 Chaining 장점: 1)한정된 저장소를 효율적으로 쓸 수 있다. 2)해시 함수를 선택하는 중요성이 상대적으로 적다. 3)상대적으로 적은 메모리를 쓴다. 단점: 1)쏠림현상이 생긴다. 2)외부 저장 공간을 사용한다. Open Addressing(개방주소법) 개방주소법은 데이터의 해시(hash)가 변경되지 않았던 chaining과는 달리 비어있는 해시(hash)를 찾아 데이터를 저장하는 기법이다. 따라서 개방주소법에..

연결리스트란? 크기가 동적인 자료구조이다. 노드로 구성되어있으며, 내가 구현한 단일 연결리스트의 구성은 그림과 같다. 단일 연결리스트 메서드 addToTail: 꼬리에 노드 추가 remove: 주어진 값을 찾아서 연결 해제 getNodeAt: 주어진 인덱스의 노드를 찾아서 반환 Contains: 리스트에 주어진 값이 존재하는지 여부 확인 indexOf: 주어진 값의 인덱스를 반환 구현방법 1. 배열을 이용하는 방법 2. 구조체와 포인터를 이용하는 방법