with with

Graph 그래프는 트리와 마찬가지로 비 선형적 자료구조로 node와 노드를 잇는 link의 집합으로 구성된다. 트리와 가장 큰 차이점은 그래프의 노드는 어떠한 패턴으로 연결되도 상관 없다는 것이다. (심지어 비어있거나, 연결이 아예 안된 노드도 존재할 수 있음) 노드의 구현과 탐색에 앞서 노드의 용어부터 정리하고 가자. Path: vertex들의 순서나열. e.g. path of v0 to v2: e0 e1 / e0 e2 e3 e5 / e4 e5 / e4 e3 e2 e1 Cycle: 출발 vertex = 도착 vertex인 path Multiple edges: 같은 두 vertex 사이 2개 이상의 edge가 연결된 것. Simple Graph: loop, multiple edges가 없는 graph ..

메모리에 저장된 데이터를 탐색하는 방법은 여러 개가 있지만, 오늘은 아래 세 가지 경우만 고려해보자. 1. Serial Search 382759461 위 숫자에서 6을 탐색해보자. 순차탐색은 0번째 인덱스부터 6이 등장하는 7번째 인덱스까지 총 8번의 탐색과정을 거쳐야 6을 찾을 수 있다. 정렬되어 있지 않은 데이터 조합에 대해 사용할 수 있지만, n개의 데이터에 대해 최대 n번의 탐색 시간이 걸린다는 치명적인 단점이 있다. 2. Binary Search 123456789 위 숫자에서 6을 탐색해보자. 이진 탐색의 경우 검색을 시작할 인덱스와 종료할 인덱스의 중간을 우선 탐색한다. arr[(0+8)/2] = arr[4] = 5 이때, 6은 5보다 크기 때문에 4번째 인덱스의 왼쪽에서 다시 탐색한다. ar..

Heap Heap은 complete binary tree의 일종으로 추가로 아래의 조건을 만족하는 tree이다. 모든 노드는 그 자식노드(나아가 Descendant)보다 반드시 크거나 같아야 한다. 즉, 데이터를 넣을 때 마다 루트노드쪽으로 갈수록 큰 값이 저장되도록 정렬되는데, 이런 특징일 이용해 priority queue를 구현할 때 heap 구조가 사용된다. 데이터의 추가와 삭제를 살펴보자. push() 1. 일단 complete binary tree가 되게끔 노드를 맨 아래 왼쪽에 추가한다. 2. heap을 만족하는 적절한 위치가 될 때까지 부모노드와 위치를 바꾸며 올라간다. (reheapification upward) pop() heap에서 특정 값 pop은 생략한다. 가장 큰 값, 즉, 루트노..

Binary Tree 중, 아래의 조건을 만족하는 Tree이다. 1. 루트노드의 왼쪽 서브트리의 노드는 루트노드보다 작거나 같아야 한다. 2. 루트노드의 오른쪽 서브트리의 노드는 루트노드보다 커야한다. BST로 언제나 그랬 듯 가방을 만들건데, 이 부분은 코드보단 개념과 데이터 추가/삭제를 이해하는 편이 좋기 때문에 pseudo code로 작성하겠다. 생성자 루트 포인터를 NULL로 초기화. 복제 생성자 인자로 들어온 루트 포인터를 복사하고, 그 결과를 루트 포인터로 가리키게 한다. 앞서 구현한 tree_copy함수를 사용 파괴자 모든 노드를 해제한다. 앞서 구현한 tree_clear함수를 사용 size() 모든 노드의 갯수를 세는 함수 1 + size(왼쪽 서브트리) + size(오른쪽 서브트리) 이렇..

트리구조는 아주 중요한 알고리즘이라 세 번에 나누어서 진행할 예정이다. Tree... 이게 얼마나 사기(?)냐 하면은 트리를 이용하여 데이터를 관리할 경우 데이터 탐색에 필요한 시간이 O(n^2)에서 O(nlogn)까지 감소할 수 있다. 즉, array는 최악의 경우 특정 데이터를 찾는데 100만 번의 비교(약 16.6분)가 필요하다면, Tree(그 중에 binary heap)은 단 20번이면 비교(20밀리초)가 끝난다. 트리구조를 알아보기 앞서 용어부터 정리하자. Tree: node들의 무한 집합 Root: Parent node가 없는 최상단의 노드 Parent: node위에 연결된 노드 Child: node아래에 연결된 노드 Sibling: Parent node가 같은 노드 Leaf: Child no..

재귀 함수는 앞으로 다룰 Tree, Heap, Graph에서 사용할 뿐만 아니라, 메모리공간을 많이 사용할 지언정, stack으로 구현해야할 코드의 길이를 획기적으로 단축 시켜줄 고급 스킬 이기 때문에 짚어보고 넘어가겠다. 예로들어 -1234와 같은 입력이 들어오면 이를 세로로 출력하는 프로그램을 구현한다고 해보자. 평범한 발상으로는 -, 1, 2, 3, 4를 순서대로 출력한다고 생각할 것이다. 하지만, 재귀적인 발상은 -123을 출력한 뒤 4를 출력한다고 생각하는 것이다. 즉, 함수에서 할 일을 작게 나누어, 큰 일은 미래의 자신(함수)에게 떠넘기고, 본인은 작은 일을 처리한다는 발상이다. 재귀 함수를 달성하려면, stopping case와 일의 분할을 명확하게 해야한다. 일을 분할하고, 분할된 일이 ..

Queue는 FIFO(First In First Out) 형태의 자료구조이다. 대부분의 서비스업은 이런 Queue 구조로 동작한다. (대기열이 대표적인 예시) 다른 간단한 예시로 Queue와 Stack을 사용해 앞으로 읽든 뒤로 읽든 똑같은 단어인지 검사하는 프로그램을 만들 수 있다. 기러기 토마토 스위스 인도인 별똥별 우영우 역삼역(?!) #include #include #include #include int main() { queue q; stack s; char letter; int mismatches = 0; while (cin.peek() != ‘\n’) { cin >> letter ; if (isalpha(letter)) { q.push(toupper(letter)); s.push(touppe..

Stack 은 LIFO(Last In First Out) 형태의 자료구조이다. 대표적인 응용 예시로는 계산기를 예로 들 수 있다. 보통 수식은 Infix notation 형식으로 입력한다. (3+4)*7 stack을 활용하기 위해선 이를 Postfix notation으로 변환해야 하는데, 3 4 + 7 * 이 때, stack을 활용하면 쉽게 이를 달성할 수 있다. 입력으로 들어온 Infix notation은 총 4가지의 경우에 따라 다르게 처리된다. 1. 왼쪽 괄호인가? '(' 왼쪽 괄호의 경우에는 stack에 추가한다. 2. 숫자(변수와 같은 피연산자)인가? 숫자의 경우에는 출력한다. 3. 연산자인가? '+', '-', '*', '/' 연산자의 경우에는 아래의 세 조건을 만족할 때 까지 모든 연산자를 ..