신입 개발자 기술면접 : C++ 05 (손코딩: Heapify, 최대힙, 이진탐색)

🗣️ 신입 인터뷰/C++

신입 개발자 기술면접 : C++ 05 (손코딩: Heapify, 최대힙, 이진탐색)

쫀냠 2023. 12. 25. 21:15

안녕하세요, 쫀냐미입니다.
손코딩은 처음이라서요 ...
틀린 내용이 있다면 댓글로 알려주시면 감사하겠습니다 (_ _ )

🗣️ Heapify 코드를 작성해보세요

#include <iostream>
using namespace std;

void swap(int& a, int& b) {
    int temp = a;
    a = b;
    b = temp;
}

int num = 9;
int heap[9] = {7, 6, 5, 8, 3, 5, 9, 1, 6};

int main() {
    for (int i = 1; i < num; i++) {
        int c = i;
        do {
            int root = (c - 1) / 2;
            if (heap[root] < heap[c]) {
                swap(heap[root], heap[c]);
            }
            c = root;
        } while (c != 0);
    }
    for (int i = num - 1; i >= 0; i--) {
        swap(heap[0], heap[i]);
        int root = 0;
        int c = 1;
        do {
            c = 2 * root + 1;
            if (c < i - 1 && heap[c] < heap[c + 1]) {
                c++;
            }
            if (c < i && heap[root] < heap[c]) {
                swap(heap[root], heap[c]);
            }
            root = c;
        } while (c < i);
    }
    for (int i = 0; i < num; i++) {
        cout << heap[i] << " ";
    }
    return 0;
}

🗣️ 최대 힙 구현을 코드로 작성해보세요

#include <iostream>
using namespace std;
#include <vector>
#include <queue>

template<typename T>
class PriorityQueue
{
public:
	// ⏰ O(logN)
	void push(const T& data)
	{
		heap.push_back(data);

		// 👑 COUP' 👑
		int now = static_cast<int>(heap.size()) - 1;
		// 루트 노드까지
		while (now > 0)
		{
			// 부모 노드와 비교해서 heap[now]가 더 작으면 COUP 패배, 빠져나온다
			int next = (now - 1) / 2;
			if(heap[now] < heap[next])
				break;
			// 부모 노드와 비교했을 때, heap[now] 가 더 크면 COUP 진행시켜, 데이터 교체!
			::swap(heap[now], heap[next]);
			now = next; // 타고타고 올라가도록 한다
		}
	}
	// ⏰ O(logN)
	void pop()
	{
		// 👑 REVERSE COUP' 👑
		// 최대값(루트) 을 먼저 제거한다, 마지막 노드를 루트로 옮긴다
		// 역도장깨기를 할 때는 그냥 도장깨기보다 조금 더 까다로운 이유가,
			// 자식이 왼쪽, 오른쪽 둘 다 봐야 해서
			// 두 자식 중 더 큰 아이와 바꿔줘야 한다는 점을 만들어줘야 한다.
		heap[0] = heap.back();
		heap.pop_back()
		int now = 0;
		while true()
		{
			int left = 2 * now + 1;
			int right = 2 * now + 2;

			// 리프에 도달한 경우, 빠져나온다. 더 이상 갈 구석이 없기 때문이다.
			if (left >= (int)heap.size())
				break;

			// (1) next 가 변화가 없건 == 자식이 다 작다			
			int next = now; 
			// (2) next 가 left 가 되건 == 왼쪽 자식이 나보다 크다
			if (heap[next] < heap[left]) next = left; 
			// (3) next 가 right 가 되건 == 오른쪽 자식이 나보다 크다
			if (right < heap.size() && heap[next] < heap[right])
				next = right; 

			// (1) left, right 둘 다 now 값보다 작으면 종료
			if (next == now)
				break;
			// (2),(3) 그게 아니면 역쿠데타 ㄱㄱ
			::swap (heap[now], heap[next]);
			now = next;
		}
	}
	// ⏰ O(1)
	T& top()
	{
		return heap[0];
	}
	// ⏰ O(1)
	bool empty()
	{
		return heap.empty();
	}
	
private:
	vector<T> heap;
};

int main()
{
	vector<int> v;
	PriorityQueue<int> pq;
}

🗣️ 이진 탐색 코드를 작성해보세요

vector<int> numbers;

void BinarySearch(int N) // N 은 우리가 찾을 번호
{
	int left = 0;
    int right = numbers.size() - 1;
    
    while (left <= right) // 이 조건 잊지 말기!
    {
    	cout << "탐색 범위 : " << left << "~" << right << endl;
        
        int mid = (left + right) / 2;
        
        if (N < numbers[mid])
        {
        	right = mid - 1;
        }
        else if  (N > numbers[mid])
        {
        	left = mid + 1;
        }
        else // 값이 같다는 것이니, 찾았다는 의미!
        {
        	cout << "찾았다!" << endl;
			break;
		}
    }
}

int main()
{
	numbers = {1, 8, 15, 23, 32, 44, 56, 63, 81, 91};
    BinarySearch(81);
}

🗣️ 이진 탐색 트리 코드를 작성해보세요

// BinarySearchTree.h

#pragma once

struct Node
{
	Node* parent = nullptr;
    Node* left = nullptr; // 왼쪽 자식
    Node* right = nullptr; // 오른쪽 자식
    int key = 0; // 데이터
};

class BinarySearchTree
{
public:
	
  Node* Search(Node* node, int key); 
  void Insert(int key); // 노드 생성 후 위치를 골라줘서 넣어주는 행위
  
  // 삭제 기능을 위한 헬퍼 함수들
  Node* Min(Node* node); // 어떠한 트리 기준으로 가장 작은 값이 어디?
  Node* Max(Node* node); // 어떠한 트리 기준으로 가장 큰 값이 어디?
  Node* Next(Node* node); // 그 다음으로 큰 ?
  void Replace(Node* u, Node* v); // 삭제할 때 재설정
  void Delete(int key);
  void Delete(Node* node);
  
private:
	Node* _root = nullptr;
}

// BinarySearchTree.cpp

#include "BinarySearchTree.h"

void BinarySearchTree::Insert(int key)
{
	Node* newNode = new Node();
    newNode->key= key;
    
    if(_root == nullptr) // 만약 내가 첫 번째 노드라면
    {
    	_root = newNode;
        return;
    }
    
    // 추가할 위치를 찾기
    Node* node = _root;
    Node* parent = nullptr;
    
    while (node)
    {
    	parent = node;
        if (key < node->key)
        	node = node->left;
        else
        	node = node->right;
    }
    
    newNode->parent = parent;
    
    if (key < parent->key)
    	parent->left = newNode;
    else
    	parent->right = newNode;
        
}

Node* BinarySearchTree::Search(Node* node, int key)
{
	if (node == nullptr || key == node->key)
  		return node;
  
  	if (key < node->key)
  		return Search(node->left, key); // 재귀
  	else 
  		return Search(node->right, key);
}

/* 트리의 최솟값 */
Node* BinarySearchTree::Min(Node* node)
{
  if (node == nullptr)
  	return;
  
  while (node->left)
  	node = node->left;
  
  return node;
}

/* 트리의 최댓값 */
Node* BinarySearchTree::Max(Node* node)
{
	if (node == nullptr)
  		return;
  
  	while (node->right)
  		node = node->right;
  
 	return node;
}

/* ⭐️ GOOGLE: 어떠한 노드를 기준으로 "그 다음으로 큰 데이터"는 어느 노드에 있는지? */
Node* BinarySearchTree::Next(Node* node) 
{
	// 1번째 경우: 한 칸 오른쪽으로 가고 거기서 제일 작은 값을 추출
	if (node->right)
  		return Min(node->right);
        
  	// 2번째 경우: 조상 중 나를 왼쪽 자식으로 들고 있는 조상을 만날 때까지 올라간다
  	Node* parent = node->parent;
  	while (parent && node == parent->left)
  	{
  		node = parent;
  		parent = parent->parent;
  	}
  	return parent;
}

/* 재배치*/
void BinarySearchTree::Replace(Node* u, Node* v)
{
	if (u->parent == nullptr)
		_root = v;
  	else if (u == u->parent->left)
  		u->parent->left = v;
  	else
  		u->parent->right = v;
  
  	if (v)
  		v->parent = u->parent;
 
  	delete u;
}

/* 키 삭제 */
void BinarySearchTree::Delete(int key)
{
	Node* deleteNode = Search(_root, key);
  	Delete(deleteNode);
}

/* 노드 삭제 */
void BinarySearchTree::Delete(Node* node)
{
	if (node == nullptr)
  		return;
    
    // 삭제할 노드의 자식이 왼쪽에 없고 오른쪽에 있는 경우
  	if (node->left == nullptr)
  	{
		Replace(node, node->right); 
  	}
    
    // 삭제할 노드의 자식이 왼쪽에 있고 오른쪽에 없는 경우
  	else if (node->right == nullptr)
  	{
		Replace(node, node->left);
  	}
    
    // 삭제할 노드의 자식이 양쪽의 2개인 경우
  	else
  	{
  		Node* next = Next(node); // 그 다음 큰 녀석
  		node->key = next->key; // 키만 살짝 복사
  		Delete(next); // 원래 그 녀석 삭제
  	} 
}