해당 포스팅은 "코딩 테스트 합격자 되기 C++편" 의 책 및 강의를 보며 포스팅 한 내용입니다. 

 

 

 

[지금 무료] 코딩 테스트 합격자 되기 - C++ 강의 | dremdeveloper - 인프런

dremdeveloper | 코딩 테스트 합격을 위한 C++ 강의, 책 없이도 가능! 저자와 직접 소통 가능한 커뮤니티 제공!, [사진]여기에 문의 하세요https://open.kakao.com/o/gX0WnTCf📘 코딩 테스트 합격자 되기 - C++편

www.inflearn.com

 

 

 

 

💬주요 키워드

이진 트리 : 트리는 뿌리와 잎을 가진 나무를 상상하며 만들어낸 자료구조이며, 이진 트리는 노드라는 Element가 있으며 최대 두 개의 또다른 자식개념의 노드를 가질 수 있는 것이 특징이다.

 

노드 : 노드는 배열의 Element와 비슷한 역할을 하지만 트리구조는 부모와 자식이라는 관계성이 추가되기 때문에 Element에서 부모, 자식의 주소정보를 추가로 가진다. 

 

엣지 : 엣지는 간선이라고도 불리고 노드와 노드 사이를 이어주는 선의 개념이며, 노드와 엣지를 이용해 노드의 관계를 표현한다. 보통 이진 트리에서는 부모관계를 표현한다.

 

차수 : 차수는 degree 라고도 불리며 자식 노드가 2개 있으면 2차수, 1개 있으면 1차수라고 불린다.

 

높이 : 높이는 레벨이라고도 하며 노드의 상하관계에 따라 형성되는 노드의 높이가 되며 루트노드와 리프노드 사이의 엣지가 몇개가 있는지에 따라 결정된다.

 

루트 노드 : 트리의 최상위 노드로서, 트리의 최상단에 있는 시작위치 라고 보면 된다.

 

리프 노드 : 말단 노드라고도 하며, 트리의 최하단에 있는 노드들이라고 보면 된다.

 

자식 노드  : 노드의 하단에 뻗어나가는 엣지를 통해 연결된 노드들을 말하며, 보통 이진트리에는 2개의 자식노드까지 있을 수 있다.

 

서브 트리 : 자식노드를 통해 연결되있는 또다른 자식노드들과 통틀어 서브 트리 라고 한다.

 

포화 이진트리 : 이진트리의 최대 노드의 개수는 높이n에 따라 2^n-1개까지 생성할 수 있는데, 이 때, 최대 노드의 개수까지 늘어난 트리를 포화이진트리라고 한다.

 

완전 이진트리 : 이진트리에서 노드가 새로 생성될 때 노드에 붙어있는 순서가 좌측부터 정렬되어 붙어있다면 완전 이진트리라고 한다.

 

📝내용

 

이진트리(Binary Tree)

1. 정의

이진트리는 요소(Element)를 가지고 있는 노드와 요소와 요소 사이를 이어주는 엣지로 이루어져 있는 자료구조를 의미하며, 이 때 하나의 노드에는 2개의 자식노드를 가질 수 있다는 것이 주요 규칙인 자료형을 의미한다.

또한, 이진트리의 구조는 배열로도 손쉽게 표현할 수 있다.

 

또한 노드를 이동, 방문(Visit)한다는 개념을 가지고 있어, 노드에서 다른노드로 이동-> 현재 머물고 있는 노드를 방문 이라는 개념을 가지고 있다.

 

동작 방식은 링크 참조

https://www.youtube.com/watch?v=_ITudD2Cz9M&ab_channel=VisualHow

 

또한, 이진트리에는 다른 자료구조와 같이 모든 요소(Element)에 접근할 수 있는 순회의 방식이 여러가지가 있는데 크게

 

 

전위 순회 : 현재노드 방문 -> 좌측 자식노드로 이동 -> 좌측 자식노드가 없다면 우측 자식노드로 이동 -> 우측 자식노드가 없다면 부모노드로 되돌아가기

중위 순회 : 좌측 자식노드로 이동 -> 현재노드 방문 -> 좌측 자식노드가 없다면 우측 자식노드로 이동 -> 우측 자식노드가 없다면 부모노드로 되돌아가기 

후위 순회 : 좌측 자식노드로 이동 -> 좌측 자식노드가 없다면 우측 자식노드로 이동 ->  현재노드 방문 ->  우측 자식노드가 없다면 부모노드로 되돌아가기

 

가 있다.

 

2.  트리의 ADT

   1) empty : 트리의 루트노드가 비어있는지 확인

   2) sum : 트리의 전체노드 합을 구하기

   3) height : 트리의 높이 구하기

   4) visit : 트리의 방문,  여기서는 간단한 cout << node->item; 으로 대체

   5) clear : 변수의 수명이 다해 소멸자가 발동할 시, 동적할당을 해제하기 위한 노드의 삭제 구현

   6) PreOrder : 전위순회

   7) InOrder : 중위순회

   8) PostOrder : 후위순회

   9) LevelOrder : 높이의 좌측 순서대로 순회

   

보통 배열로 많이 구현하지만, 시각적으로 보았을 때에는 양방향연결리스트(Double Linked List)의 형태로 설명하기 때문에, 해당 형태로 구현해보았습니다.

배열로 구현할 때에는

부모노드 접근 : 현재 노드 / 2
자식노드 접근 : 현재 노드 * 2 , 현재 노드 *2 + 1

이라는 규칙을 통해 부모와 자식노드에 접근할 수 있다. 

 

 

   ADT를 바탕으로 구현한 코드(양방향연결리스트)

#include<bits/stdc++.h>

using namespace std;

template<typename T>
class BT
{
public:
	struct Node
	{
		T item = T();
		Node* left = nullptr; // Left child
		Node* right = nullptr; // Right child

		//Node* parents = nullptr; // parents

	};

	BT() {}

	BT(Node* root)
	{
		root_ = root;
	}

	bool empty()
	{
		return root_ == nullptr;
	}

	void visit() { return visit(root_); }
	void visit(Node* node)
	{
		using namespace std;
		cout << node->item << " "; // 수행하고 싶은 작업 구현(여기서는 출력)
	}

	int sum()
	{
		return sum(root_);
	}

	int sum(Node* node)
	{
		//* Doing
		if (!node) return 0;
		return node->item + sum(node->left) + sum(node->right); // TODO:
	}
	
	int height()
	{
		return height(root_);
	}

	int height(Node* node)
	{
		//* Doing
		if (!node) return 0;
		return 1 + std::max(height(node->left), height(node->right)); // TODO:
	}

	~BT()
	{
		DeleteTree(root_);
	}

	void DeleteTree(Node* node)
	{
		if (node)
		{
			DeleteTree(node->left);
			DeleteTree(node->right);
			delete node;
		}
	}

	void PreOrder() { PreOrder(root_); }
	void PreOrder(Node* node)
	{
		// TODO:
		if (node)
		{
			visit(node);
			PreOrder(node->left);
			PreOrder(node->right);
		}
	};

	void InOrder() { InOrder(root_); }
	void InOrder(Node* node)
	{
		// TODO:
		if (node)
		{
			InOrder(node->left);
			visit(node);
			InOrder(node->right);
		}
	}

	void PostOrder() { PostOrder(root_); }
	void PostOrder(Node* node)
	{
		// TODO:
		if (node)
		{
			PostOrder(node->left);
			PostOrder(node->right);
			visit(node);
		}
	}

	void LevelOrder()
	{
		std::queue<Node*> q;
		Node* current = root_; //루트에서
		while (current)
		{
			visit(current); // 루트 방문
			if (current->left) q.push(current->left); // 왼쪽 자식노드 푸시
			if (current->right) q.push(current->right); // 오른쪽 자식노드 푸시
			if (q.empty()) return; //q가 비었다면 리턴
			current = q.front(); //왼쪽 자식노드를 커런트로 만들고
			q.pop(); // 큐에서 빼준다.
			// TODO:
		}
	}

protected:
	Node* root_ = nullptr;
	//Node* last_ = nullptr; // complete Binary Tree에서 필요한 요소
};

int main()
{

	using Node = BT<int>::Node;

	Node* n1 = new Node{ 1, nullptr, nullptr }; // 물결괄호 초기값 나열 (생성자 아님)
	Node* n2 = new Node{ 2, n1, nullptr };
	Node* n3 = new Node{ 3, nullptr, nullptr };
	Node* n4 = new Node{ 4, nullptr, nullptr };
	Node* n5 = new Node{ 5, nullptr, n4 };
	Node* n6 = new Node{ 6, n2, n5 };

	n1->right = n3; // <- 연결관계 변경

	BT<int> tree(n6); // <- n6의 주소를 root node로 

	cout << "Empty: " << tree.empty() << endl;//Empty: 1 
	cout << "Sum: " << tree.sum() << endl;//Sum: 21
	cout << "Height: " << tree.height() << endl;//Height : 4

	{	//Visit: 6
		cout << "Visit: ";
		tree.visit();
		cout << endl;
	}

	// Tree traversal methods

	cout << "Preorder" << endl; // 6 2 1 3 5 4
	tree.PreOrder();
	cout << endl;

	cout << "Inorder" << endl; // 1 3 2 6 5 4
	tree.InOrder();
	cout << endl;

	cout << "Postorder" << endl; // 3 1 2 4 5 6
	tree.PostOrder();
	cout << endl;

	cout << "LevelOrder" << endl; // 6 2 5 1 4 3
	tree.LevelOrder();
	cout << endl;
}

 

 

3.  문제 풀이

   1) 트리 순회(연습문제)

더보기
더보기

a. 문제 설명

이진트리를 표현한 배열 nodes를 인수로 받습니다. 예를 들어서 nodes가 [1,2,3,4,5,6,7]이면 다음과 같은 트리를 표현한 것 입니다. 해당 이진트리에 대하여 전위,중위,후위 순회 결과를 각각 순서대로 문자열로 담은 배열을 반환하는 solution()함수를 구현하세요.

 

ex)

arr result
[1,2,3,4,5,6,7] [1,2,4,5,3,6,7] , [4,2,5,1,6,3,7] , [4,5,2,6,7,3,1]

 

b. 의사 코드

  1. 전위 순회는 현재 노드를 방문, 좌측노드 이동,좌측노드가 없으면 우측노드 이동으로 구현한다.
  2. 중위 순회는 좌측노드 이동, 좌측노드 없다면 현재노드를 방문, 우측노드로 이동으로 구현한다.
  3. 후위 순회는 좌측노드로 이동, 좌측노드가 없다면 우측노드로 이동, 좌측/우측도 없다면 현재노드 방문, 으로 구현한다.

c. 문제 풀이

#include <bits/stdc++.h>

using namespace std;

void forwardtraversal(vector<int>& arr, int start)
{
    if(start < arr.size())
    {
        cout << arr[start] << " ";
        
        forwardtraversal(arr, start*2);
    
        forwardtraversal(arr, start*2+1);
    }
}

int main()
{
    vector<int> arr = {0,1,2,3,4,5,6,7};
    
    forwardtraversal(arr,1);
    
    return 0;
}

 

d. 문제 후기

  • 시간복잡도 O(3n) : 각 원소들을 한번씩 순회하는 과정이 3번 일 어나기 때문에 3n의 시간복잡도를 가짐.
  • 트리는 비교적 재귀를 이용하는 문제들이 많은듯 하다.

 

   2) 이진 탐색 트리(연습문제)

더보기
더보기

a. 문제 설명

lst 배열에 있는 값을 통해 이진 탐색 트리를 생성하고, 이 이진 탐색 트리로 search_lst 배열의 각 원소가 있는지 확인합니다. 각 원소가 이진 탐색 트리에 존재하면 true, 없으면 false를 반환하는 함수 solution()을 작성하세요.

 

ex)

lst search_lst result
[5,3,8,4,2,1,7,10] [1,2,5,6] [true, true, true, false]
[1,3,5,7,9] [2,4,6,8,10] [false, false, false, false, false]

 

b. 의사 코드

  1. 검색하려는 값을 현재 노드와 비교해서 같으면 검색을 완료한다.
  2. 검색하려는 값을 현재 노드와 비교했을 때, 값이 작으면 왼쪽 서브 트리로 이동한다.
  3. 검색하려는 값을 현재 노드와 비교했을 때, 값이 크면 오른쪽 서브 트리로 이동한다.

c. 문제 풀이

#include <vector>
using namespace std;

// ❶ 노드를 정의
class Node 
{
public:
  int val;
  Node *left, *right;

  Node(int key) : val(key), left(nullptr), right(nullptr) {}
};

//❷ 이진 탐색 트리 정의
class BST 
{
private:
  Node* root;

  
  Node* insertNode(Node* node, int key) 
  {
    if (!node) 
    {
      return new Node(key);
    }
    //❸ 키 값과 현재 노드의 값을 비교해서 이진탐색트리 규칙에 맞는 위치로 이동
    if (key < node->val) 
    {
      node->left = insertNode(node->left, key);
    } 
    else 
    {
      node->right = insertNode(node->right, key);
    }
    return node;
  }

  bool searchNode(Node* node, int key) 
  {
    //❹ 찾는 키 값이 없는 경우 
    if (!node) 
    {
      return false;
    }
    //❺ 이진탐색트리에서 키 값을 찾은 경우
    if (key == node->val) 
    {
      return true;
    }
    //❻ 아직 값을 찾지 못한 경우, 현재 노드값과 key 값을 비교해서, 어느 노드에서 탐색할지 결정
    return key < node->val ? 
           searchNode(node->left, key) : 
           searchNode(node->right, key);
  }

public:
  BST() : root(nullptr) {}

  void insert(int key) 
  {
    root = insertNode(root, key);
  }

  bool search(int key) 
  {
    return searchNode(root, key);
  }
};

vector<bool> solution(vector<int> lst, vector<int> search_lst) 
{
  BST bst;
  // 이진 탐색 트리에 노드 삽입
  for (int key : lst) 
  {
    bst.insert(key);
  }

  vector<bool> result;
  // 이진 탐색 트리에서 찾는 값이 있는지 확인하고 탐색결과를 result에 추가
  for (int search_val : search_lst) 
  {
    result.push_back(bst.search(search_val));
  }

  return result;
}

//아래 코드는 테스트 코드 입니다.
#include <iterator>
#include <iostream>
void print(vector<bool> vec)
{
    copy(vec.begin(), vec.end(), std::ostream_iterator<bool>(cout, " "));
    cout << endl;
}

int main()
{
    // bool을 출력할 때 true는 1 false는 0 입니다.
    print(solution({5, 3, 8, 4, 2, 1, 7, 10}, {1, 2, 5, 6})); //출력값 : 1 1 1 0
    print(solution({1, 3, 5, 7, 9}, {2, 4, 6, 8, 10})); //출력값 : 0 0 0 0 0    
    return 0;
}

 

d. 문제 후기

  • 시간복잡도 O(N) : 트리에 배열을 넣는 과정에서 최악의 경우 한쪽으로 치우친 트리의 케이스가 나올 수 있기 때문에 보통은 logN과 가깝겠지만 최악의 상황에서는 N이 나온다.
  • AVL트리나, 레드블랙트리를 구현하는 방법을 알아볼 필요가 있다.

 

   3) 예상 대진표(링크)

더보기
더보기

a. 문제 설명

링크 참조

 

 

b. 의사 코드

  1. 문제는 길지만 비교적 간단하게 풀 수 있다. 대진표가 트리의 구조와 동일하기 때문에, 트리의 구조를 생각하며 문제를 풀어보자.
  2. 주어진 a와 b노드를 부모를 타고 쭉쭉 올라가는 형태로 구해보자.

c. 문제 풀이

#include<iostream>
#include <bits/stdc++.h>

using namespace std;

int solution(int n, int a, int b)
{
    int answer = 0;
    
    while(a!=b)
    {
        a = (a + 1) / 2;
        b = (b + 1) / 2;
        answer++;
    }
    
    return answer;
}

 

d. 문제 후기

  • 시간복잡도 O(logN) : 트리로 이루어진 간선들을 탈 때마다 logN 만큼 시간을 절약한다.

 

   4) 다단계 칫솔 판매(링크)

더보기
더보기

a. 문제 설명

링크 참조

 

 

b. 의사 코드

  1. 우선 enroll과 referal은 해시맵으로 묶어서 이진트리 노드의 특성 중 노드의 부모는 하나밖에 없다는 것을 이용할 수 있을것 같다는 생각을 하여 묶었다.
  2. 또한, enroll과 int자료형을 통해 얼마나 이익금을 받는지 해시맵을 통해 묶어주기로 한다.
  3. seller의 부모를 끝없이 찾아야 하기 때문에 for문을 통해 seller를 선택하고, seller의 부모는 만들어둔 해시맵으로 묶어준다. while문을 이용하여 부모가 "-"가 나올때 까지 이익금의 10%를 나눠주는 형태로 반복문을 진행한다.
  4. 마지막으로 완성된 이익금의 해시맵을 배열에 넣어준다.

c. 문제 풀이

#include <bits/stdc++.h>

using namespace std;

vector<int> solution(vector<string> enroll, vector<string> referral, vector<string> seller, vector<int> amount) 
{
    vector<int> answer;
    
    unordered_map<string, string> umap_parent;
    for(int i = 0; i < enroll.size(); i++) umap_parent[enroll[i]] = referral[i];
    
    unordered_map<string, int> umap_money;
    for(const auto& e : enroll) umap_money[e] = 0;
    
    for(int i = 0; i < seller.size(); i++)
    {
        int money = amount[i] * 100;
        string str = seller[i];
        
        while(money > 0 && str != "-")
        {
            int vat = money / 10;
            umap_money[str] += money - vat;
            
            if(umap_parent.find(str) != umap_parent.end())
            {
                str = umap_parent[str];
            }
            else
            {
                break;
            }
            
            money = vat;
        }
    }
    
    for(const auto& e : enroll) answer.push_back(umap_money[e]);
    
    return answer;
}

 

d. 문제 후기

  • 시간복잡도 O(N^2+2N) : 우선 부모자식관계의 노드를 나타내는 해시맵을 만들고, 각 이름별 얼마만큼의 돈을 벌었는지의 해시맵도 만들어준 다음, 판매자와 판매자의 부모들이 이익금을 얼마나 받는지 계산해준다.

 

 

 

 

 

'GroupStudy > [C++]코딩 테스트 합격자 되기' 카테고리의 다른 글

[코딩 테스트 합격자 되기] 6주차 - 그래프  (0) 2024.08.12
[코딩 테스트 합격자 되기] 5주차 - 집합  (0) 2024.08.06
[코딩 테스트 합격자 되기] 3주차 - 해시  (0) 2024.07.25
[코딩 테스트 합격자 되기] 2주차 - 스택/큐  (0) 2024.07.13
[코딩 테스트 합격자 되기] C++ - 알고리즘  (0) 2024.07.11

+ Recent posts

티스토리툴바