🗒️ Data Structure (41)

1. 2022.06.29 [Python] 동적 계획법(DP: Dynamic Programming)

   동적 계획법(DP: Dynamic Programming) 동적 계획법(DP: Dynamic Programming) 불필요한 연산을 줄이고, 최적의 답안을 구하는 알고리즘 동적 계획법의 등장 배경 ① 배낭 문제(Knapsack Problem) 무게와 가격이 다른 여러 물건 중에서, 가장 효율적으로 배낭에 채우기 위한 문제 예) 배낭에 넣을 수 있는 무게는 한정 되어 있고, 배낭에 넣을 수 있는 보석의 무게와 가치가 각각 다를 때 어떻게 해야 가방에 가장 큰 이익이 담길 수 있도록 보석을 채울 수 있을까? ② 브루트 포스 검색(Brute Force Search) 모든 경우의 수를 나열한 후, 그중에서 최선의 해결책을 찾는 방법 '짐승(Brute)처럼 무식한 힘(Force)으로 전체 경우의 수를 검색한다.'는..
2. 2022.06.29 [Python] 탐색(Search)

   탐색(Search) 탐색의 기본 개념 탐색(Search) : 어떤 집합에서 원하는 것을 찾는 것으로 검색이라고 한다. 탐색의 종류 순차 탐색(Sequential Search) 이진 탐색(Binary Search) 트리 탐색(Tree Search) 검색 결과로 특정 집합의 위치인 인덱스를 알려 준다. 검색에 실패하면(찾는 데이터가 집합에 없다면) -1을 반환하는 것이 일반적이다. 탐색 알고리즘의 종류 탐색은 데이터 상태에 따라 다양한 알고리즘을 사용할 수 있다. 탐색할 집합이 정렬되어 있지 않은 상태라면 순차 탐색을 해야 한다. 순차 탐색(Sequential Search) 순차 탐색은 처음부터 끝까지 차례대로 찾아보는 것으로, 쉽지만 비효율적인 탐색 방법이다. 하지만, 집합의 데이터가 정렬되어 있지 않다면..
3. 2022.06.28 [Python] 정렬(Sort) : 선택 정렬, 삽입 정렬, 버블 정렬, 퀵 정렬

   정렬(Sort) 정렬의 기본 정렬의 개념 정렬(Sort) : 자료들을 일정한 순서대로 나열하는 것 순서대로 나열할 때는 작은 것부터 나열하는 방법(오름차순)과 큰 것부터 나열하는 방법(내림차순)이 있다. 오름차순 정렬(Ascending Sort) : 작은 것부터 큰 순으로 나열된 방법 내림차순 정렬(Descending Sort) : 큰 것부터 작은 순으로 나열된 방법 정렬의 대표적인 예 : 사전 정렬 알고리즘의 종류 오름차순 정렬이든 내림차순 정렬이든 결과의 형태만 다를 뿐, 같은 방식으로 처리된다. 정렬하는 방법에 대한 알고리즘은 수십 가지이다. 이해하고 구현하기 쉽지만 속도가 느린 알고리즘 이해와 구현이 어렵지만 속도가 빠른 알고리즘 특수한 상황에서만 효율적인 알고리즘 메모리를 적게 사용하는 알고리즘..
4. 2022.06.05 [Python] 재귀 호출(Recursion)

   재귀 호출(Recursion) 재귀 호출의 기본 재귀 호출의 개념 재귀 호출(Recursion) : 자기 자신을 다시 호출하는 것 재귀 호출은 처음 접하면 상당히 혼란스럽지만 자료구조와 알고리즘을 학습할 때 매우 유용한 방법이므로 꼭 알아두어야 한다. 재귀호출의 동작 파이썬에서는 재귀 호출이 너무 많아지면 반복을 자동 종료한다. def openBox() : print("종이 상자를 엽니다.") openBox() openBox() # 처음 함수를 다시 호출 더보기 종이 상자를 엽니다. 종이 상자를 엽니다. ... RecursionError: maximum recursion depth exceeded while pickling an object 반환 조건을 추가할 경우, 무한 반복에서 빠져나올 수 있다. d..
5. 2022.06.04 [Python] 그래프(Graph)

   그래프(Graph) 그래프(Graph)의 기본 그래프의 개념 그래프(Graph) : 여러 노드가 서로 연결된 자료구조 루트에서 하위 노드 방향으로만 이어지는 트리와 달리, 여러 노드가 연결되어 있을 수 있다. 트리도 그래프의 일종이지만, 트리와 그래프를 구현하는 코드 등이 확연히 다르기 때문에 이 둘은 별도로 생각하는 편이 낫다. 그래프의 종류 그래프는 정점을 연결하는 간선의 방향성 여부에 따라 방향 그래프와 무방향 그래프로 나눈다. 간선에 가중치(Weight)를 부여하여 가중치 그래프도 만들 수 있다. 무방향 그래프 트리의 노드(Node)에 해당하는 용어가 그래프에서는 정점(Vertex)이다. 정점을 연결하는 선은 간선(Edge)이므로 그래프는 정점과 간선의 집합으로 볼 수 있다. 그래프에서 정점은 V..
6. 2022.06.04 [Python] 이진 트리(Binary Tree)

   이진 트리(Binary Tree) 이진 트리(Binary Tree)의 기본 이진 트리의 개념 트리(Tree) 자료구조는 나무를 거꾸로 뒤집어 놓은 형태이다. 트리의 맨 위를 뿌리(Root, 루트)라고 한다. 루트를 레벨 0으로 두고 나뭇잎(Leaf, 리프)에 해당하는 아래로 내려올 수록 레벨이 1씩 증가한다. 트리에서 각 위치를 노드(Node)라고 한다. 각 노드는 선, 즉 에지(Edge)로 연결되어 있다. 위 노드와 바로 아래 노드의 관계를 부모-자식 관계(Parent-Child Relationship)라고 한다. 자식 노드의 개수를 차수(Degree)라고 한다. 차수가 0인 노드를 리프(Leaf)라고 한다. 트리의 차수는 차수가 가장 높은 노드를 기준으로 정한다. 컴퓨터는 데이터를 0과 1로 표현하므..
7. 2022.06.03 [Python] 큐(Queue)

   큐(Queue) 큐(Queue) 선입선출(First In First Out, FIFO)의 특징을 갖는 자료구조 큐는 양쪽이 뚫려 있는 구조이다. 한쪽에서는 삽입만 진행되고, 다른 쪽에서는 추출만 진행된다. 큐에 데이터를 삽입하는 동작을 enQueue(인큐)라고 하며, 데이터를 추출하는 동작을 deQueue(데큐)라고 한다. 큐의 중요한 용어로 front(머리)와 rear(꼬리)가 있다. 머리는 저장된 데이터 중 첫 번째 데이터를 가리킨다. 꼬리는 저장된 데이터 중 마지막 데이터를 가리킨다. 첫 번째 데이터 앞을 front가 가리켜야 한다. 데이터 삽입 : enQueue 데이터 추출 : deQueue 큐의 간단 구현 큐는 배열 형태로 구현할 수 있다. 큐는 초기에 크기를 지정하고 배열로 생성할 수 있다. ..
8. 2022.05.30 [Python] 괄호 매칭 검사 프로그램

   괄호 매칭 검사 프로그램 들어가며 스택을 활용하여 간단하게 괄호의 매칭 검사를 수행할 수 있다. 여는 괄호를 만나면 push 하고, 닫는 괄호를 만나면 pop 한다 는 규칙을 적용한 후, push 또는 pop 하는 과정에서 다음의 조건을 확인하면 된다. ① 닫는 괄호를 만났을 때 스택은 비어 있지 않아야 한다. ② 닫는 괄호를 만났을 때 추출한 괄호는 여는 괄호여야 한다. ③ ②를 만족해도 두 괄호의 종류(소괄호, 중괄호, 대괄호)가 같아야 한다. ④ 모든 수식의 처리가 끝나면 스택은 비어 있어야 한다. 열린 괄호라면 무조건 push 한다. 닫는 괄호일 때는 스택에서 하나를 꺼내서 현재 괄호와 짝이 맞는지 확인한다. if '(', '[', '{', '' 중 하나면 열린 괄호 pop() if 두 괄호의 쌍..
9. 2022.05.30 [Python] 스택(Stack)

   스택(Stack) 스택(Stack) 선입후출(First In Last Out, FILO) 또는 후입선출(Last In First Out, LIFO)의 특징을 갖는 자료구조 스택은 한쪽만 뚫려 있는 구조이기 때문에 삽입과 추출이 한쪽에서만 진행된다. 스택에 데이터를 삽입하는 동작을 push(푸시)라고 하며, 데이터를 추출하는 동작을 pop(팝)이라고 한다. 스택에서는 top(톱)이라는 용어가 중요한데, 현재 스택에 들어 있는 가장 위의 데이터 위치를 가리키는 개념이다. 스택의 간단 구현 스택은 배열 형태로 구현할 수 있다. 스택은 초기에 크기를 지정하고 배열로 생성할 수 있다. 스택의 맨 위쪽을 표현하는 top은 아직 데이터가 없으므로 -1로 초기화한다. top이 -1이라는 것은 스택이 비었다는 의미로 해..
10. 2022.04.21 [Python] 원형 연결 리스트(Circular Linked List)

    원형 연결 리스트(Circular Linked List) 원형 연결 리스트의 개념 단순 연결 리스트(Singly Linked List) 끝까지 방문한 후에는 더 이상 방문할 곳이 없어 종료되므로 다시 방문하려면 헤드(head)부터 재시작해야 한다. 원형 연결 리스트(Circular Linked List)는 단순 연결 리스트의 마지막 노드가 다시 첫 번째 노드를 가리키도록 설정되어 리스트 형태가 원(Circle) 형태로 구성된다. 시작 위치와 다음 위치가 계속 이어진 후, 마지막에 다시 시작 위치로 돌아오는 형태 원형 연결리스트는 단순 연결 리스트와 마찬가지로 데이터 삽입에서 오버헤드가 발생하지 않는다. 원형 연결 리스트의 원리 원형 연결 리스트의 원리 및 구조도 단순 연결 리스트와 많은 부분이 비슷하다...
11. 2022.04.21 [Python] 단순 연결 리스트(Singly Linked List)

    단순 연결 리스트(Singly Linked List) 단순 연결 리스트의 개념 선형 리스트(Linear List) 장점 배열에 구성하였기 때문에 단순하다. 물리적인 순서와 논리적인 순서가 동일하여 데이터를 찾기 간단하다. 프로그램으로 구현하기 비교적 쉽다. 단점 : 데이터를 삽입하거나 삭제할 때 많은 작업이 필요하다. 예) 100만 개인 선형 리스트의 맨 앞에 데이터를 하나 삽입하려면 약 100만 개를 뒤로 이동시키는 작업을 해야 한다. (오버헤드(Overhead) 발생) 단순 연결 리스트(Singly Linked List) 선형 리스트(Linear List)와 달리, 저장된 노드들이 물리적으로 떨어진 곳에 위치한다. 각 노드의 번지도 100, 200, 130 등으로 순차적이지 않다. 데이터와 링크로 구..
12. 2022.04.21 [Python] 선형 리스트(Linear List)

    선형 리스트(Linear List) 선형 리스트의 기본 개념 데이터를 일정한 순서로 나열한 구조 순차 리스트(Ordered List)라고도 한다. 입력 순서대로 저장하는 데이터에 해당한다. 선형 리스트는 다양한 방법으로 구현할 수 있지만, 가장 기본적인 방법은 배열 을 이용하는 것이다. 선형 리스트는 메모리에서도 차례로 저장된다. 원리 데이터 삽입 1단계 : 맨 끝에 빈칸을 확보한다. 2단계 : 삽입하고자 하는 공간에 빈칸이 없으므로, 삽입하고자 하는 공간 뒤에 있는 요소들을 한칸씩 뒤로 옮긴다. 3단계 : 빈자리에 요소를 삽입한다. 데이터 삭제 원하는 요소가 삭제된 후 빈칸을 그대로 두지 않고 뒤의 요소들을 앞으로 한칸씩 이동시킨다. 선형 리스트의 구현 사용자가 입력하는 데이터가 가변적으로 작동하는 범..
13. 2022.04.02 [Python] 단순 연결 리스트(Singly Linked List) 프로그램

    단순 연결 리스트(Singly Linked List) 프로그램 # 단순 연결 리스트 프로그램 (삽입, 삭제, 검색) ## 클래스와 함수 선언 부분 ## class Node(): def __init__(self): self.data = None self.link = None def printNodes(start): current = start if current == None: return print(current.data, end = ' ') while current.link != None: current = current.link print(current.data, end = ' ') print() # 노드 삽입 함수 def insertNode(findData, insertData): global me..
14. 2022.03.26 [Python] 다항식(Polynomial) 선형 리스트 표현과 계산 프로그램

    다항식(Polynomial) 선형 리스트 표현과 계산 프로그램 다항식(Polynomial) $P(x) = a + bx + cx^2 + dx^3 + \cdots + zx^n$ $n$ 차 다항식 $P(x)$ : 다항식(Polynomial) $a, b, c, d, \cdots, z$ : 계수(Coefficient) $x$의 $1, 2, \cdots, n$ : 지수(Exponent) 코드 방법 1 ## 함수 선언 부분 def printPoly(p_x): term = len(p_x) - 1 # 최고차항 숫자 = 배열 길이 - 1 polyStr = "P(x) = " for i in range(len(px)): coef = p_x[i] # 계수 if (coef >= 0): polyStr += "+" polyStr +..
15. 2022.03.26 [Python] 선형 리스트(Linear List) 처리 프로그램

    선형 리스트(Linear List) 처리 프로그램 ## 함수 선언 부분 ## def add_data(friend): katok.append(None) kLen = len(katok) katok[kLen - 1] = friend # 선형 리스트에 데이터를 삽입하는 함수 def insert_data(position, friend): if position len(katok): print("데이터를 삽입할 범위를 벗어났습니다.") return katok.append(None) # 빈칸 추가 kLen = len(katok) # 배열의 현재 크기 for i in range(kLen - 1, position, -1): katok[i] = katok[i - 1] katok[i - 1] ..
16. 2021.06.26 [C++] 디스조인트-셋(Disjoint-Set) ; 유니언-파인드(Union-Find), 서로소 집합, 상호 배타적 집합

    디스조인트-셋(Disjoint-Set) 디스조인트-셋(Disjoint-Set) 또는 유니언-파인드(Union-Find) 자료구조 다음과 같이 불림. 서로소 집합 자료구조 상호 배타적 집합 자료구조 트리 형태로 구성된 포레스트(Forest) 각각의 원소는 숫자 ID 에 의해 표현됨. 랭크(Rank) 와 부모에 의한 포인터를 가짐. 초기화되면 랭크가 0인 N개의 독립적인 원소가 생성됨. 각각의 원소는 하나의 트리를 나타냄. 공통의 원소를 갖지 않는 원소 집합을 표현하기 위해 사용됨. 지원 연산 make-set(x) x를 ID로 갖는 원소를 디스조인트-셋 자료구조에 추가함. 새로 추가한 원소의 랭크 : 0 원소의 부모 포인터는 자기 자신을 가리키도록 설정함. 그림 설명 원 안에 적힌 숫자 : 원소 ID 괄호 ..
17. 2021.06.26 크루스칼 최소 신장 트리 알고리즘(Kruskal Minimum Spanning Tree Algorithm)

    크루스칼 최소 신장 트리 알고리즘(Kruskal Minimum Spanning Tree Algorithm) 최소 신장 트리(Minimum Spanning Tree) 정점(Vertex) 의 집합 V와 가중치를 갖는 에지(Edge) 의 집합 E로 구성된 그래프 G = 가 주어질 때, 모든 정점을 연결하고 연결된 에지의 가중치 합이 최소 인 트리 T 크루스칼 최소 신장 트리 알고리즘(Kruskal Minimum Spanning Tree Algorithm) 1956년에 발표됨. 알고리즘 ① 그래프 G의 모든 에지를 최소 힙 H에 추가함. ② H로부터 에지 e를 하나 꺼냄. e : 모든 에지 중에서 가장 가중치가 작은 에지 ③ e이 양 끝 정점이 이미 T에 있을 경우, e로 인해 T에서 사이클이 발생할 수 있음...
18. 2021.06.09 [C++] 맵(Map)과 리듀스(Reduce)

    맵(Map)과 리듀스(Reduce) 맵과 리듀스라는 용어는 Lisp와 같은 함수형 프로그래밍 언어에서 기원함. 맵(Map) 컨테이너 C를 입력으로 받아, 컨테이너의 모든 원소에 함수 f(x)를 적용하는 연산 예) f(x) = x² 함수를 사용할 경우에 대한 맵 연산 리듀스(Reduce) 컨테이너 C의 모든 원소 x에 함수 f(acc, x)를 적용하여 하나의 값으로 축약하는 연산 예) f(acc, x) = acc + x 함수를 사용할 경우에 대한 리듀스 연산 코드 #include #include #include #include #include void transform_test(std::vector S) { std::vector Tr; std::cout
19. 2021.06.07 선형 시간 선택(Linear Time Selection)

    선형 시간 선택(Linear Time Selection) 각 단계에서 문제를 2개 이상 분할하여 문제를 해결하는 알고리즘 ① 벡터 $V$가 주어지면, 여기서 i번째로 작은 원소를 찾으려고 함. ② 입력 벡터 $V$를 $V_{1}, V_{2}, V_{3}, ..., V_{n/5}$ 으로 분할함. 각각의 부분 벡터 $V_{i}$ 는 5개의 원소를 가지고 있음. 마지막 $V_{n/5}$ 는 5개 이하의 원소를 가질 수 있음. ③ 각각의 $V_{i}$ 를 정렬함. ④ 각각의 $V_{i}$ 에서 중앙값 $m_{i}$ 를 구하고, 이를 모아서 집합 M을 생성함. ⑤ 집합 M에서 중앙값 q를 찾음. ⑥ q를 피벗으로 삼아 전체 벡터 V를 L과 R의 두 벡터로 분할함. ⑦ 이러한 방식으로 분할하면 부분 벡터 L은 q보..
20. 2021.06.02 [C++] 퀵 정렬(Quick Sort)

    퀵 정렬(Quick Sort) 퀵 정렬은 분할 정복(Divide and Conquer) 알고리즘 을 이용하여 구현됨. 병합 정렬과 퀵 정렬의 비교 병합 정렬(Merge Sort) 대용량의 데이터 정렬 퀵 정렬(Quick Sort) 평균 실행 시간을 줄이는 것 기본 아이디어는 병합 정렬과 같음. 원본 입력 배열을 작은 크기의 부분 배열로 나눔. 각 부분 배열을 정렬함. 그 결과를 합쳐서 전체 정렬 배열을 생성함. 핵심 병합(Combine)이 아니라 분할(Split) 입력 배열이 주어지고, 입력 배열 중 피벗(Pivot) 원소 P를 선택했을 경우, 퀵 정렬을 위한 분할 연산 은 다음의 2단계로 이루어짐. ① 입력 배열을 2개의 부분 배열 R과 L로 나눔. L 입력 배열에서 P 보다 작거나 같은 원소를 포함하..
21. 2021.06.02 [C++] 병합 정렬(Merge Sort)

    병합 정렬(Merge Sort) 병합 정렬은 분할 정복(Divide and Conquer) 알고리즘 을 이용하여 구현됨. 병합 알고리즘은 다음과 같은 과정으로 정렬을 수행함. ① 많은 원소로 구성된 전체 집합을 작은 크기의 부분 집합 으로 나눔. ② 각각의 부분 집합을 정렬함. ③ 정렬된 부분 집합을 오름차순 또는 내림차순 순서를 유지함. ④ 각각의 부분 집합을 합침. 그림) 병합 정렬을 사용하여 정수 배열을 정렬하는 예 전체 배열을 여러 개의 부분 배열로 나누는 작업을 반복함. 각 부분 배열이 하나의 원소를 가질 때 멈춤. (1단계 ~ 4단계) 이후에는 다시 배열을 합치는 작업을 반복함. 합쳐진 배열의 원소 순서가 오름차순을 유지하도록 조정함. 코드 템플릿을 사용하여 정렬할 데이터 타입에 의존적이지 않..
22. 2021.05.29 [C++] 선형 탐색(Linear Search), 이진 탐색(Binary Search)

    선형 탐색(Linear Search), 이진 탐색(Binary Search) 선형 탐색(Linear Search) 시퀀스 전체 원소를 방문하면서 해당 원소가 N과 같은지 확인 다음과 같은 코드로 구현할 수 있음. bool linear_search(int N, std::vector& sequence) { for (auto i : sequence) { if (i == N) { return true; // 찾음! } } return false; } 장점 입력 시퀀스의 정렬 여부와 상관없이 항상 잘 동작함. 단점 효율적이지 않음. 주어진 배열이 정렬되어 있다는 점을 전혀 이용하지 못함. 시간 복잡도 : O(N) 이진 탐색(Binary Search) 주어진 시퀀스가 정렬되어 있다는 사실을 이용하여 검색하는 방법 ..
23. 2021.05.28 [C++] 블룸 필터(Bloom Filter)

    블룸 필터(Bloom Filter) 해시 테이블에 비해 공간 효율이 매우 높은 방법 결정적(Deterministic) 솔루션 대신 부정확한 결과를 얻을 수 있음. 거짓-부정(Fals Negative) 이 없다는 것은 보장하지만, 거짓-긍정(False Positive) 은 나올 수 있음. 특정 원소가 존재한다는 긍정적인 답변을 받을 경우, 이 원소는 실제로 있을 수도 있고 없을 수도 있음. 그러나 특정 원소가 존재하지 않는다는 부정적인 답변을 받았다면, 이 원소는 확실히 없음. 뻐꾸기 해싱과 마찬가지로 블룸 필터도 여러 개의 해시 함수를 사용함. 보통 2개의 해시 함수는 충분한 정확도를 기대하기 어렵기 때문에 3개 이상을 사용해야 함. 블룸 필터는 실제 값을 저장하지는 않음. 대신 특정 값이 있는지 없는지..
24. 2021.05.28 [C++] STL로 해시 테이블(Hash Table) 만들기 (std::unordered_map, std::unordered_set)

    STL로 해시 테이블(Hash Table) 만들기 서론 C++의 STL을 이용하여 해시 테이블(Hash Table)을 구현할 수 있다. std::unordered_map과 std::unordered_set을 이용한다. 이 방법으로 해시 테이블을 구현할 경우 원소의 순서가 보장되지 않으며, 원소의 순서를 보장하도록 만들기 위해서는 std::unordered_multimap 또는 std::unordered_multiset을 이용하여 구현하면 된다. 코드 #include #include #include void print(const std::unordered_set& container) { for (const auto& element : container) { std::cout
25. 2021.05.22 [C++] 뻐꾸기 해싱(Cuckoo Hashing)

    뻐꾸기 해싱(Cuckoo Hashing) 크기가 같은 2개의 해시 테이블을 사용함. 각각의 해시 테이블은 서로 다른 해시 함수 를 가짐. 모든 원소는 두 해시 테이블 중 하나에 있을 수 있음. 위치는 해당 해시 테이블의 해시 함수 에 의해 결정됨. 뻐꾸기 해싱이 다른 해싱 기법과 다른 점 원소가 두 해시 테이블 중 어디든 저장될 수 있음. 원소가 나중에 다른 위치로 이동할 수 있음. 다른 해싱 방법에서는 재해싱을 수행하지 않는 이상 원소가 최초 삽입된 위치에서 다른 위치로 이동할 수 없음. 그러나, 뻐꾸기 해싱 방법에서는 모든 원소가 2개의 저장 가능한 위치를 가지며, 상황에 따라 이동할 수 있음. 더 나은 성능을 얻고, 재해싱 빈도를 줄이기 위해 저장 가능한 위치 개수를 증가 시킬 수도 있음. 룩업 연..
26. 2021.05.20 [C++] 체이닝(Chaining)을 이용한 해시 테이블(Hash Table) 구현

    체이닝(Chaining)을 이용한 해시 테이블(Hash Table) 구현 체이닝(Chaining) 해시 테이블에 두 값을 모두 저장할 수 있는 여러 방법 중 하나 해시 테이블의 특정 위치에서 하나의 키 를 저장하는 것이 아니라 하나의 연결 리스트 를 저장함. 새로 삽입된 키에 의해 충돌이 발생하면 리스트의 맨 뒤에 새로운 키를 추가함. 따라서 다수의 원소를 원하는 만큼 저장할 수 있음. 벡터 대신 연결 리스트를 사용하는 이유? 특정 위치의 원소를 빠르게 삭제하기 위함. 코드 #include #include #include #include using uint = unsigned int; class hash_map { std::vector data; public: hash_map(size_t n) { dat..
27. 2021.05.19 [C++] 인접 리스트를 이용하여 그래프 구현하기

    인접 리스트를 이용하여 그래프 구현하기 서론 인접 리스트(Adjacent List)를 이용하여 그래프(Graph)를 구현해보자. 코드 #include #include #include enum class city : int { MOSCOW, LONDON, SEOUL, SEATTLE, DUBAI, SYDNEY }; std::ostream& operator
28. 2021.05.16 [C++] 이진 탐색 트리(Binary Search Tree)

    이진 탐색 트리(Binary Search Tree) 이진 탐색 트리(Binary Search Tree) 널리 사용되는 형태의 이진 트리(Binary Tree) BST의 속성 왼쪽 노드 ≤ 부모 노드 ≤ 오른쪽 노드 의 관계를 가짐. 부모 노드의 값 ≥ 왼쪽 자식 노드의 값 부모 노드의 값 ≤ 오른쪽 자식 노드의 값 부모 노드보다 작거나 같은 모든 원소는 항상 왼쪽에 이고, 부모 노드보다 크거나 같은 원소는 항상 오른쪽에 있게 됨. 원소 검색을 위해 루트 노드부터 차례대로 값을 비교하는 경우, 각 단계마다 검색 범위가 절반으로 줄어듦. BST가 마지막 레벨을 제외한 모든 노드에 2개의 자식 노드가 있을 경우 트리의 높이 : log₂N N : 원소의 개수 BST의 검색 및 삽입 동작의 시간 복잡도 : O(l..
29. 2021.05.15 [C++] 트리 순회(Tree Traversal)

    트리 순회(Traversal) 트리 순회 방법 트리 순회 방법은 다음과 같이 4가지가 있음. 전위 순회(Preorder Traversal) 중위 순회(In-Order Traversal) 후위 순회(Post-Order Traversal) 레벨 순서 순회(Level Order Traversal) 전위 순회(Preorder Traversal) 재귀적 인 방식으로 다음의 노드를 방문함. ① 현재 노드 (C) ② 현재 노드의 왼쪽 하위 노드 (L) ③ 현재 노드의 오른쪽 하위 노드 (R) 전위(Pre) 상위 노드를 하위 노드보다 먼저 방문한다는 뜻 전위 순회는 항상 부모 노드 를 방문한 다음, 왼쪽자식 노드, 오른쪽 자식 노드를 차례로 방문함. 이러한 방식의 순회를 루트 노드에서만 수행하는 것이 아니라, 루트 노..
30. 2021.05.15 [C++] 조직 구조도 만들기 (이진 트리 이용)

    조직 구조도 만들기 (이진 트리 이용) 서론 트리(Tree) 자료구조를 이용하여 조직 구조도를 만들어보자. 이진 트리(Binary Tree)를 이용하고, 1명의 상사 직원 밑에 2명의 부하 직원을 둘 수 있다고 가정한다. 상사 직원이 없을 경우, 부하 직원을 추가할 수 없다. 코드 #include #include struct node { std::string position; node* first; node* second; }; struct org_tree { node* root; static org_tree create_org_structure(const std::string& pos) { org_tree tree; tree.root = new node {pos, NULL, NULL}; return t..