CS26 [자료구조] 이진탐색트리 1. 이진탐색트리란? 이진탐색트리란 이진탐색(Binary Search)와 연결리스트(Linked List)를 결합한 자료구조의 일종이다. 이진 탐색 연결 리스트 장점 탐색에 소요되는 시간복잡도가 O(logN) 로 빠르다 삽입과 삭제에 걸리는 시간 복잡도가 O(1)로 빠르다 단점 삽입과 삭제가 불가능하다 탐색의 시간 복잡도가 O(N) 이다 위와 같은 이진 탐색과 연결리스트의 장점을 고안하기 위해 만들어졌으며, 이진 탐색의 효율적인 탐색 능력을 유지하면서도 빈번한 자료 입력과 삭제가 가능하기 위해 사용된다. 2. 이진탐색트리 특징 이진탐색트리는 이진트리의 일종으로 다음과 같은 규칙으로 구성한다. 모든 노드는 유일한 키를 갖음. (중복된 노드 X) 각 노드의 왼쪽 서브 트리에는 해당 노드의 값보다 작은 값.. 2023. 2. 16. [자료구조] 힙(Heap) 에 대하여 힙이란? 힙(Heap)이란, 완전 이진 트리에 있는 노드 중에서 키값이 가장 큰 노드나 키값이 가장 작은 노드를 찾기 위해서 만든 자료구조이다. 키 값이 가장 큰 노드를 찾기 위한 힙을 최대 힙(Max Heap)이라 하고, 키 값이 가장 작은 노드를 찾기 위한 힙을 최소 힙(Min Heap)이라고 한다. 아래 그림은 최대 힙과 최소 힙의 예시이다. 힙의 연산 힙에는 새로운 원소를 추가하는 삽입 연산, 루트 노드에 있는 원소를 삭제하는 삭제 연산 두가지가 존재한다. 다만, 힙은 항상 부모노드를 최대 힙일 경우 최대, 최소 힙일 경우 최소로 유지해주어야 하는 특성이 있다. 최대 힙 : 부모노드의 키 값 >= 자식노드의 키 값 최소 힙 : 부모노드의 키 값 2023. 2. 16. [자료구조] 스택(Stack), 큐(Queue) Stack의 정의 Stack이란, Stack이란 단어의 의미처럼 쌓아 올린다는 뜻이다. 한쪽에서만 원소를 삽입하고 삭제가 가능한 자료구조이다. 한쪽에서만 원소를 쌓아 올리고 꺼내고 하기 때문에 LIFO(Last In First Out) 구조로 되어있다. Stack의 기술 내용 Stack에는 두가지 중요한 기술인 Push와 Pop이 있다. 위 그림과 같이 입구와 출구가 동일한 바구니가 있다. Push를 하게 되면 바구니에 원소를 집어넣게 되며, 또 한번 Push를 하게 되면 첫 원소 위에 두번째 원소가 위치하게 된다. 여기서 첫번째 원소를 꺼내고 싶다면 Pop을 두번해야 한다. 결국 삽입을 할 때에도 맨 위(Top)에 삽입을 하게 되고 꺼낼때에도 맨 위에 있는 원소를 꺼내게 된다. 주로 문자열의 역순을.. 2023. 2. 15. [자료구조] 트리(Tree) 트리(Tree) 란? 트리는 노드로 이루어진 자료 구조 트리는 하나의 루트 노드를 갖음 루트 노드는 0개 이상의 자식 노드를 갖고 있음. 그 자식 노드 또한 0개 이상의 자식 노드를 갖고 있음. 노드와 노드는 서로를 연결하는 간선들로 구성. 트리에는 사이클(cycle)이 존재할 수 없음. 노드들은 특정 순서로 나열될 수도, 아닐 수도 있음. 각 노드는 부모 노드로의 연결이 있을 수도 있고 없을 수도 있음. 각 노드는 어떤 자료형으로도 표현 가능함. 비선형 자료구조로 계층적 관계를 표현함. 그래프의 한 종류 사이클(cycle)이 없는 하나의 연결 그래프(Connected Graph) DAG(Directed Acyclic Graph, 방향성이 있는 비순환 그래프)의 한 종류. 트리의 특징 그래프의 한 종.. 2023. 2. 15. 데이터베이스 정규화(Normalization)란 데이터베이스 정규화(Normalization) 란? 관계형 데이터베이스의 설계에서 중복을 최소화하게 데이터를 구조화하는 프로세스를 정규화라고 한다. 정규화의 기본 목표는 관련이 없는 함수 종속성은 별개의 릴레이션으로 표현하는 것이다. 정규화된 결과를 정규형이라고 하며, 정규형은 기본 정규형 고급 정규형으로 나뉜다. 기본 정규형 : 제1정규형, 제2정규형, 제3정규형, BCNF(보이스/코드 정규형) 고급 정규형 : 제4정규형, 제5정규형 정규화의 장점으로는 이상 현상의 발생 가능성을 줄이지만, 단점으로는 연산 시간이 증가한다. 제 1 정규형 릴레이션에 속한 모든 속성의 도메인이 더 이상 분해되지 않는 원자값으로만 구성된 정규형이다. 제2정규형 릴레이션이 제1정규형에 속하고, 기본키가 아닌 모든 속성이 기본.. 2021. 11. 11. 데이터베이스 조인(Join) 정리 JOIN(조인) JOIN이란 '연결하다' 라는 뜻을 지닌 단어이다. 이 단어의 뜻처럼, 데이터베이스에서는 둘 이상의 테이블을 연결해서 테이블을 검색하는 방법을 이야기 한다. JOIN의 종류 INNER JOIN OUTER JOIN CROSS JOIN SELF JOIN 그렇다면, 이제 다음과 같은 테이블 두 개를 가지고 각각의 조인에 대해 알아보자. [Star 테이블] ID Name DepNo 1 강호동 10 2 이수근 10 3 유재석 20 4 박명수 20 5 안재현 30 6 송민호 30 7 이병헌 NULL [Dep 테이블] DepNo DepName 10 1박2일 20 무한도전 30 신서유기 40 이경규가간다 1. INNER JOIN (이너조인) 이너조인은 위의 그림처럼 두 개의 테이블에서 공통된 요소들을 .. 2021. 11. 10. 이전 1 2 3 4 5 다음
