비선형 문제

계층적 문제

• 조직도가 예시다.
• 조직도와 같은 데이터는 배열, 벡터, 연결 리스트 같은 자료 구조로는 표현하기 어렵다.
• 또한, 대학 교과 과정 계층도를 검색해서 봤을 때, 다른 과목을 들으려면 미리 선수강해야하는 경우들이 있는데, 이러한 것을 표현하기에도 연속, 연결 자료 구조로는 표현하기 어렵다.
• 위와 같은 문제를 풀기 위해서는 다양한 유형의 연산을 수행할 수 있어야하는데, Tree 라는 자료 구조가 유용하다.
  • 데이터가 저장된 부분을 Node 라고 부른다.
  • Node와 Node 사이를 잇는 선은 Edge 라고 부른다.

순환 종속성

• 친구 관계도를 검색해서 보면, 그와 같은 구조는 graph 라고한다.
• 친구 관계도와 같은 구조는 친구 관계를 나타내는 용도로 사용이 가능하다.
  • 몇 다리 건너 친구 등등

Tree : 상하 반전된 형태

• Tree는 Node와 Node 사이 연결하는 Edge로 계층 구조를 나무 형태로 나타낼 수 있다.
  • Tree의 중심이 되는 Node : Root Node

#include <iostream>
#include <queue>

strcut node 
{
	std::string position;
    node* first;
    node* second;
}

• 하나의 node는 두 개의 자식 Node를 가지고 있으며 이러한 형태를 binary tree 라고 한다.

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 tree;
}

• 새로운 트리를 만드는 static function

static node* find(node* root, const std::string& value)
{
	if (root == NULL)
  		return NULL;
        
	if (root->position == value)
    	return root
        
	auto firstFound = org_tree::find(root->first, value);
    
    if (firstFound != NULL)
    	return firstFound
        
	return org_tree::find(root->second, value);
}

• node의 특정 position을 받아 해당 node를 찾아 반환하는 함수
• 현재 노드이거나 왼쪽, 오른쪽 subtree로 특정 원소들을 탐색해 나간다.
  • 가장 먼저 루트 노드 검사 -> 왼쪽 검사 -> 오른쪽 검사

bool addSubordinate(const std::string& manager, const std::string& subordinate)
{
	auto managerNode = org_tree::find(root, manager);
    
    if(!managerNode)
    {
    	return false;
	}
    
    if(managerNode->first && managerNode->second)
    {
    	return false;
	}
	
    if(!managerNode->first)
    	managerNode->first = new node {subordinate, NULL, NULL};
    else
    	managerNode->second = new node {subordinate, NULL, NULL};
        
	return true;
};

• find 함수를 활용한 원소 찾기
• 원소를 정상적으로 삽입하면 true, 아니면 false 반환

int main()
{
	auto tree = org_tree::create_org_structure("CEO");
    
    tree.addSubordinate("CEO", "부사장");
    tree.addSubordinate("부사장", "IT부장");
    tree.addSubordinate("부사장", "마케팅부장");

• 트리 구성하는 코드를 위처럼 main으로 만들어볼 수 있다.

트리 순회

• 트리는 원소를 다양한 방법으로 순회하며 원하는 노드에 접근할 수 있다.
• 전위 순회(preorder traversal) : 현재 노드 먼저 방문, 그 다음 현재 노드의 왼쪽 하위 노드, 마지막으로는 오른쪽 하위 노드를 재귀적인 방식으로 방문
  • 전위라는 뜻이 상위 노드를 하위 노드보다 먼저 방문한다는 뜻이다.
    - CEO, 부사장, IT부장 ..., 마케팅부장, ...

static void preOrder(node* start)
{
	if(!start)
    	return;
     
	std::cout << start->position << std::endl;
    preOrder(start->first);
    preOrder(start->second);
}

• 중위 순회(in-order traversal) : 왼쪽 노드 먼저 방문, 그 ㄷ음 현재 노드, 마지막으로 오른쪽 노드 방문
  • ..., IT부장, ..., 부사장, ... 마케팅부장,

static void inOrder(node* start)
{
	if (!start)
    	return;
        
	inOrder(start->first);
    std::cout << start->position << std::endl;
    inOrder(start->second);
}

• 후위 순회(post-order traversal) : 두 자식 노드를 먼저 방문 한 다음 현재 노드를 방문
  • ..., IT부장, ..., 마케팅부장, ..., CEO

static void postOrder(node* start)
{
	if(!start)
    	return;
        
	postOrder(start->first);
    postOrder(start->second);
    std::cout << start->position << std::endl;
}

• 레벨 순서 순회(level order traversal) : 트리 맨 위 레벨 부터 아래 레발까지 왼쪽 노드에서 오른쪽 노드 순서로 방문
  • 트리 루트 노드부터 단계별로 차례대로 나열하는 것과 같다.

CEO
부사장
IT부장 마케팅부장

static void levelOrder(node* start)
{
	if(!start)
    	return;
        
	std:;queue<node*> q;
    q.push(start);
    
    while(!q.empty())
    {
    	int size = q.size();
        for (int i = 0; i < size; i++)
        {
        	auto current = q.front();
            q.pop();
            
            std::cout << current->position << ", ";
            if (current->first)
            	q.push(current->first);
            if (current->second)
            	q.push(current->second);
		}
	}   
}

• 먼저 루트 노드 방문, 후 다음 자식 노드 방문 시 해당 노드의 자식 노드를 모두 queue에 추가
• 현재 레벨 모든 노드 방문이 끝나면 큐에 저장된 노드를 꺼내어 방문하면서 미리 다음 레벨 노드를 미리 큐에 추가하는 방식

다양한 트리 구조

이진 검색 트리

• BST, Binary Search Tree, 널리 사용되는 형태의 이진 트리
  • 부모 노드 값 >= 왼쪽 자식 노드 값
  • 부모 노드 값 <= 오른쪽 자식 노드 값
• 부모 노드보다 작거나 같은 모든 원소는 항상 왼쪽, 크거나 같은 원소는 항상 오른쪽에 있다는 특이한 속성을 갖게 된다.
• 마지막 레벨 노드를 제외하고 모두 두 개의 자식 노드가 있을 경우 높이는 log(2)N이 된다.
  • N : 원소 개수
• BST의 검색 및 삽입 동작은 O(logN)의 Time Complexity를 갖는다.
• 위의 설명의 이진트리를 Complete binary tree, 완전 이진 트리 라고 부른다.

원소 검색

• BST에서 원소 검색 시 트리의 모든 원소를 방문하지 않아도 된다.
• 현재 노드가 찾고자 하는 노드가 아닐 때마다 검색의 범위가 반으로 줄어든다. 이러한 특징은 선형 자료 구조에 대한 이진 검색에서도 유사하게 나타난다.

새 원소 삽입

• 먼저 원소가 삽입될 위치의 부모 노드를 찾아야한다.
• 원소 검색과 비슷하게 루트 노드에서 부터 각 노드를 추가할 운소와 비교하면서 원소가 삽입될 위치로 이동해야 된다.

원소 삭제

• 단순 노드 삭제로 끝나는게 아니라 노드 삭제 후 전체 트리가 BST 속성을 만족하도록 삭제된 노드를 대체하는 작업이 추가된다.
• 삭제할 노드를 먼저 찾고 세 가지 경우라 따져본다.
  • 자식 노드가 없는 경우 : 단순히 해당 노드 삭제
  • 자식 노드가 하나만 있는 경우 : 노드 삭제 후 부모 노드의 포인터가 해당 자식 노드를 가리키도록 조정
  • 자식 노드가 두개 있는 경우 : 노드 삭제 후 현재 노드를 successor(후속 노드)로 대체
    • 후속 노드 : 현재 노드 다음으로 큰 숫자를 가진 노드

균형 트리

N-항 트리

Heap

• Heap은 다음과 같은 시간 복잡도를 만족해야된다.
  • O(1) : 최대 원소 즉각적으로 접근
  • O(logN) : 원소 삽입에 대한 시간 복잡도
  • O(logN) : 최대 원소 삭제에 대한 시간 복잡도
• 원소 삽입/삭제 O(logN)을 갖기 위해서는 완전 이진 트리를 사용해야된다.
  • 완전 이진 트리 : 마지막 노드 제외 모두 자식 노드 2개 존재, 마지막 레벨은 왼쪽부터 차례대로 노드가 있는 트리
• 완전 이진트리는 배열 방식으로 저장할 수 있다.
  • 마지막 레벨에 추가하는 방식으로, 마지막 레벨이 모두 채워져있으면 새로운 레벨을 더 만들고 맨 왼쪽 위치에 노드를 추가한다.
  • 부모 노드에서 자식노드로 가는 것은 단순 배열 인덱스 계산으로 가능하다.
    • 부모 노드 i -> 자식노드, 2*i + 1, 2*i +2
    • 자식 노드 i -> 부무노드, (i - 1)/2
• 힙의 불변성 : 최대 원소에 즉각적 접근 (항상 고정된 위치여야한다. 루트에 있도록 설정)
  • 위 설명과 같이 구성한 힙읍 max heap이라한다. 그 반대가 min heap

Heap 연산

원소 삽입

• heap의 가장 중요한 불변성은 완전 이진 트리 유지이다.
  • 그래야 배열 자료 구조를 이용해 힙을 저장할 수 있음
• 새 원소 추가는 마지막 레벨 마지막 노드 바로 오른쪽에 새로운 노드를 추가하는 것과 같다.
  • 마지막 레벨이 꽉차 있으면 새로운 레벨 추가 후 노드 추가 !
• 또다른 불변 조건은 모든 노드는 자식 노드보다 더 큰 값을 가지고 있어야 한다는 것이다.
  • 부모 노드와 값 비교 후 더 크면, swap

원소 삭제

• Heap에서는 가장 큰 원소만 삭제할 수 있다.
• 루트 노드(최대 원소)삭제 시 어떤 노드로 대체할 것인지 결정이 필요하다.
  • 먼저, 루트 노드와 트리의 맨 마지막 노드를 서로 교환 후 마지막 노드 삭제
  • 부모 노드가 자식 노드보다 커야하는 불변성 만족을 위해 루트 노드와 두 자식 노드를 서료 비교하여 그 중 더 큰 노드와 서로 교환한다.
    • 점차 서브 트리에 대해서도 노드 교환작업이 재귀적으로 반복된다. -> 점점 아래로 내려간다.
    • 교환 작업의 최대 횟수는 트리의 높이와 같으므로 O(logN)이다.

힙 초기화

• heapification algorithm 사용해서 O(N)으로 힙을 초기화할 수 있다.
• 아래 서브 트리부터 힙 불변 속성을 만족하도록 힙을 업데이트 한다.
• C++에서는 std::make_heap() 함수를 제공(벡터 반복자를 받아 힙을 구성)

---

Graph

• Tree는 계층적 데이터를 표현하기 좋지만, 이동 경로가 하나만 존재하여 원형 또는 순환 종속성을 표현할 수 없다.

• 그래프는 노드 데이터뿐만 아니라 노드 사이 이제 데이터도 저장해야된다.

  • 모든 노드와 에지가 있는 그래프 : unweighted graph
  • 각 edge에 노드와 노드 사이 거리르 저장 : weighted graph (최단 거리 경로 탐색 문제)

• 그래프는 방향성, 무방형성 그래프로 구분할 수 있다.

  • undirected graph : 에지가 양방향임을 의미한다.
  • directed graph : 일방통행으로 제한된 도로인 경우 방향 그래프르 사용한다.

• adjacency matrix : data[1][2] 이런 식으로 1번 노드와 2번 노드를 잇는 에지의 가중치를 나타내는데, 이렇게 그래프를 표현하는 방식을 인접행렬이라한다.

  • 행렬을 이용한 그래프 표현 시 노드 개수가 증가함에 따라 메모리 사용량이 크게 늘어난다.

• adjacency list : 각 노드 마다 연결되어있는 노드의 ID만 저장하는 방식으로 표현한 그래프다.

  • node[0] = { 1, 2, 3, 4 }
  • 연결되어있지 않은 노드에 대해서는 정보를 저장하지 않아 메모리 사용이 적다.