KKanging

우선 그래프 이론과 큐와 스택을 모른다면 그래프 큐 스택 을보고 오시기 바랍니다. 그래프를 탐색하는 방법 DFS (깊이 우선 탐색) BFS (너비 우선 탐색) DFS(Depth-First-Search) 관련 있는 노드를 최대한 깊이 있게 탐색하는 방법 구현 방법 stack 재귀함수 구현 방법 우선 방문한 정점을 다시 방문하는 일이 없도록 visited 배열을 만들어 준다. 0은 아직 방문하지 않았다는 의미 시작 정점 하나부터 stack에 넣는다. 그리고 stack의 있는 원소를 pop 한다 pop 된 정점과 연결되어 있는 정점을 stack에 push 한다. pop 된 정점과 연결되어 있는 visited 원소를 1로 바꾼다. 이제 핵심 로직을 반복하면 된다. 4가 pop 되고 4와 연결되어 있는 정점을 찾..

그래프란 정점끼리의 연결을 나타내는 자료구조이다. 정점과 간선으로 이루어져 있다. 정점(vertex): data를 표현하는 단위(node) 간선(edge): data 끼리의 연결을 나타내는 선 vertex는 총 6개이고 edge는 총 8개의 간선이 있다. 그래프와 트리의 차이점 트리와 그래프 둘 다 정점끼리의 연결구조를 가지고 있다. 하지만 cycle의 유무에 따라 그리고 계층적인 구조를 가지냐에 따라 나뉜다. 그래프(graph) cycle을 가짐 계층 구조를 가지지 않음 → 오로지 정점끼리의 연결만 나타낸다. 트리(tree) cycle을 가지지 않음 계층 구조를 가지고 있음 → root로부터 다른 정점들이 계층적임 cycle이란 if vertex의 집합을 {v1,v2,v3,v4,v5,v6}가 있다면 특..

이진 탐색트리(Binary Search Tree) 이진 탐색트리는 이진 트리의 종류로 부모노드의 오른쪽자식은 자신보다 크고 왼쪽자식은 자신보다 작다 연결리스트로 표현한다. 이진 탐색트리 연산 삭제 삽입 삭제 이진 탐색트리의 탐색 만약 15라는 수를 찾는다면 root node 부터 탐색한다. 비교하는 수와 현재 노드의 수를 비교해 크면 오른쪽 작으면 왼쪽에서 찾는다. 15는 10보다 크므로 오른쪽으로 간다. 15는 20보다 작으므로 왼쪽으로 간다. 15를 찾았으므로 true 반환 만약 못찾으면 null을 만나므로 false 반환 이진 탐색트리의 삽입 삽입은 무조건 맨아래 노드에 삽입한다 어디에 삽입할지는 이진 탐색을 통해 이루어진다 위 예시에서 13을 삽입하고 싶으면 우선 13이 어디에 삽입 해야하는지 탐..

이진트리 많아야 두 개의 자식 노드를 가짐 왼쪽 자식과 오른쪽 자식으로 구분 완전이진트리처럼 트리의 균형이 유지가 되지 않음 균형이 없는 트리이기 때문에 연결리스트로 표현하는 게 적합 root node로부터 이진트리를 표현한다. 연결리스트로 표현 돼서 배열처럼 트리의 원소를 찾기 힘들다. 그래서 이진트리는 순회 알고리즘을 이용해서 노드의 수나 정점을 찾는다. 이진트리의 순회 방법 전위 (VLR) 중위 (LVR) 후위 (LRV) 기준은 visit을 기준으로 전위 중위 후위를 나눈다 전위(Preorder traversal) root node부터 시작한다. Visit 하고 왼쪽(left)으로 가고(visit)한다. 왼쪽이 없으면 오른쪽으로 간다.(Right) 위 순서대로 방문한다. 중위(Inorder trav..

python에는 heap트리를 구현하는 표준 라이브러리 heapq라는 라이브러리가 있다. 만약 heap 트리를 아직 모른다면 아래 링크를 보는 것을 추천합니다. [자료구조] 힙트리의 정의와 구현 (Java) [자료구조] 힙트리의 정의 와 구현 (Java) 힙이란 완전이진 트리로 구성되었다. 트리의 구성이 균형을 이룬다 부모노드와 자식 노드 관계에 특징을 이룬다. 힙의 종류 최대 힙 트리 (Max heap) 완전이진트리로 구성 부모 노드의 키 값은 자 kkangmg.tistory.com heap트리 import import heapq heapq 특징 요소는 0부터 센다. 비교를 위해, 존재하지 않는 요소는 무한으로 간주. 최소 힙(Min heap)을 디폴트로 가진다는 점 즉, heap[0]이 리스트 중 제..

힙이란 완전이진 트리로 구성되었다. 트리의 구성이 균형을 이룬다 부모노드와 자식 노드 관계에 특징을 이룬다. 힙의 종류 최대 힙 트리 (Max heap) 완전이진트리로 구성 부모 노드의 키 값은 자식 노드의 키 값보다 크거나 같음 왼쪽 오른쪽 자식의 크기 구분 없음 최소 힙 트리(Min heap) 완전 이진트리로 구성된 트리 부모 노드의 키 값은 자식 노드의 키 값보다 작거나 같음 왼쪽 오른쪽 자식의 크기 구분 없음 힙의 응용 우선 순위 큐, 프린터 스풀러 등등 힙 정렬: 최대 힙 (내림 차순 정렬) , 최소 힙 ( 오름차순 정렬) 최대 힙 구조 이 글에서는 최대 힙의 예시와 구현만 하였습니다. 최대 힙의 예 배열 표 삽입 연산 그리고 heapify 연산을 한다 heapify 연산이란 ? 위 그림과 같이..

완전 이진트리란? 완전 이진트리 자식 노드가 왼쪽부터 순서적으로 채워진 이진트리 높이가 균형을 유지 완전 이진트리 표현 배열로 표현한다. 이유는 완전이진트리의 속성인 균형이 유지되기 때문 완전 이진트리 자료구조 0부터 시작해도 되지만 노드의 인덱싱의 조금 더 가시성이 좋기 때문에 1부터 시작해도 된다. 1부터 시작할 경우 배열 인덱스 i의 부모노드: i/2의 바닥함수(내림) 노드 배열 인덱스 i의 왼쪽 자식: 2i의 노드 배열 인덱스 i의 오른쪽 자식: 2i + 1의 노드 완전 이진트리의 레벨 i에서 노드의 수는 2^(i-1)개 완전이진트리의 높이가 h일 경우 최대 노드의 수는 2^h -1개 완전 이진트리에서 노드의 수 n일 경우 트리의 높이는 O(logn) 완전이진트리를 사용한 알고리즘의 수행시간은 트..

트리란 트리는 계층적인 구조를 표현할 때 사용할 수 있는 자료구조 cycle을 가지지 않는 그래프 트리 관련 용어 노드(node) : 트리 자료구조에서 data의 단위 간선(edge): 트리나 그래프에서 정점이나 노드끼리 연결되어 있는 선 루트 노드(root node): 부모가 없는 최상위 노드 단말 노드 or 말단 노드(leaf node): 자식이 없는 노드 크기(size): 트리에 포함된 모든 노드의 개수 깊이(depth): 루트 노드로부터의 거리 높이(height): 깊이 중 최댓값 차수(degree): 각 노드의 (자식 방향) 간선 개수 이런 형태도 트리일까? 이 형태는 cycle이 발생하기 때문에 트리가 아니다. 기본적으로 트리의 크기가 N일 때, 전체 간선의 개수는 N-1 이유는 cycle이 ..

덱(Deque, Double-Ended Queue)은 양쪽 끝에서 삽입과 삭제가 모두 가능한 자료구조를 말합니다. 이 이름은 Double-Ended Queue에서 나왔습니다. 스택과 큐의 일반적인 특성을 모두 가지고 있어서 스택처럼 LIFO(Last In First Out) 구조, 큐처럼 FIFO(First In First Out) 구조로 사용할 수 있습니다. 덱이란? 양쪽 끝에서 삽입과 삭제가 모두 가능한 자료구조를 말함 스택과 큐의 일반적인 특성을 모두 가지고 있음 덱이란 앞쪽 뒤쪽 모두 삽입 삭제가 많이 이루어지는 작업에 적합 인덱스 조회 후 삽입 삭제에는 불리함 덱의 구현 원형 배열 연결 리스트 이 글에선 원형 배열로만 구현하겠습니다. 덱의 자료구조 설계 add_front: 덱의 앞쪽에 요소를 추..

queue란 자료구조에 대해 알아보겠습니다. 큐(Queue)는 스택과 마찬가지로 컴퓨터 과학에서 핵심적인 개념입니다. 어떤 표를 사기 위해 줄서는 걸 생각해보면 이해하기 쉽습니다. 줄 서는 것과 같이 먼저 들어간 항목이 먼저 나오는 (First In First Out) 원칙을 따르는 자료구조입니다. 큐란? 데이터의 삽입과 삭제가 서로 다른 위치에서 일어나는 자료구조 FIFO: First-In-First-Out 큐의 응용 은행 대기, 식당 대기, 항공기 이착륙 다양한 분야의 시뮬레이션 등 큐 구현 방법 단순 배열 원형 배열 연결리스트 이 글에선 원형 배열 큐만 다룹니다. 배열 큐의 자료구조 설계 삽입(enqueue) , 삭제(dequeue) isFull(가득 찼는지 검사) isEmpty(비었는지 검사) 자..