close
프로필 배경
프로필 로고

S4NGJI

Computer Science/Data Structure & Algorithm · 2023. 6. 28. fullscreen 넓게보기

트리/힙/그래프(2) - 힙&그래프

1. 힙

  • 원소 삽입 삭제에 대한 O(log N)의 시간 복잡도를 만족하기 위해 완전 이진 트리 사용
  • 힙 구현 시 항상 최대원소가 트리의 루트에 위치

1) 힙 연산

(1) 원소 삽입하기

  • 완전 이진 트리를 유지 → 트리의 마지막 레벨, 마지막 노드 오른쪽에 원소 추가
  • 최대 원소가 트리의 루트에 위치하기 위해 새로 삽입한 원소의 크기를 비교하여 swap하는 과정을 거침

(2) 원소 삭제하기

  • 가장 큰 원소만 삭제 가능
  • 루트 노드와 마지막 노드를 교환한 후 마지막 노드를 삭제
  • 최대 원소가 트리의 루트에 위치하기 위해 다시 루트 노드와 자식 노드의 크기를 비교하여 swap

(3) 힙 초기화하기

  • 힙은 불변성을 유지해야함→ 힙 생성 알고리즘으로 업데이트
  • 아래쪽 서브 트리부터 힙 불변 속성을 만족하도록 힙을 업데이트

2) 연습 문제 10: 중앙값 구하기

#include <iostream>
#include <queue>
#include <vector>

struct median
{
	std::priority_queue<int> maxHeap;
	std::priority_queue<int, std::vector<int>, std::greater<int>> minHeap;

	void insert(int data)
	{
		if (maxHeap.size() == 0)
		{
			maxHeap.push(data);
			return;
		}

		if (maxHeap.size() == minHeap.size())
		{
			if (data <= get())
				maxHeap.push(data);
			else
				minHeap.push(data);

			return;
		}

		if (maxHeap.size() < minHeap.size())
		{
			if (data > get())
			{
				maxHeap.push(minHeap.top());
				minHeap.pop();
				minHeap.push(data);
			}
			else
				maxHeap.push(data);

			return;
		}

		if (data < get())
		{
			minHeap.push(maxHeap.top());
			maxHeap.pop();
			maxHeap.push(data);
		}
		else
			minHeap.push(data);
	}

	double get()
	{
		if (maxHeap.size() == minHeap.size())
			return (maxHeap.top() + minHeap.top()) / 2.0;

		if (maxHeap.size() < minHeap.size())
			return minHeap.top();

		return maxHeap.top();
	}
};

int main()
{
	median med;

	med.insert(1);
	std::cout << "1 삽입 후 중앙값: " << med.get() << std::endl;

	med.insert(5);
	std::cout << "5 삽입 후 중앙값: " << med.get() << std::endl;

	med.insert(2);
	std::cout << "2 삽입 후 중앙값: " << med.get() << std::endl;

	med.insert(10);
	std::cout << "10 삽입 후 중앙값: " << med.get() << std::endl;

	med.insert(40);
	std::cout << "40 삽입 후 중앙값: " << med.get() << std::endl;
}

3) 실습 문제 5: 힙을 이용한 데이터 리스트 병합

#include <iostream>
#include <algorithm>
#include <vector>

struct node
{
	int data;
	int listPosition;
	int dataPosition;
};

std::vector<int> merge(const std::vector<std::vector<int>>& input)
{
	auto comparator = [](const node& left, const node& right) {
		if (left.data == right.data)
			return left.listPosition > right.listPosition;
		return left.data > right.data;
	};

	std::vector<node> heap;
	for (int i = 0; i < input.size(); i++)
	{
		heap.push_back({input[i][0], i, 0});
		std::push_heap(heap.begin(), heap.end(), comparator);
	}

	std::vector<int> result;
	while (!heap.empty())
	{
		std::pop_heap(heap.begin(), heap.end(), comparator);
		auto min = heap.back();
		heap.pop_back();

		result.push_back(min.data);
		int nextIndex = min.dataPosition + 1;
		if (nextIndex < input[min.listPosition].size())
		{
			heap.push_back({input[min.listPosition][nextIndex], min.listPosition, nextIndex});
			std::push_heap(heap.begin(), heap.end(), comparator);
		}
	}

	return result;
}

int main()
{
	std::vector<int> v1 = {1, 3, 8, 15, 105};
	std::vector<int> v2 = {2, 3, 10, 11, 16, 20, 25};
	std::vector<int> v3 = {-2, 100, 1000};
	std::vector<int> v4 = {-1, 0, 14, 18};

	auto result = merge({v1, v2, v3, v4});

	for (auto i : result)
		std::cout << i << ' ';
	std::cout << std::endl;

	return 0;
}

2. 그래프

  • 트리에서 표현하지 못하는 원형 또는 순환적 종속성을 표현하는 방법
  • 필요한 노드와 에지가 있는 그래프를 비가중 그래프
  • 에지에 가중치 또는 더 많은 정보를 부여하는 가중 그래프 → 최단 경로 탐색
  • 방향성이 없는 무방향 그래프와 방향성이 있는 방향 그래프

1) 인접 행렬로 그래프 표현하기

  • 노드의 집합이 있고 노드끼리 서로 연결이 가능
  • 노드 N개 → 그래프는 N*N 크기의 이차원 배열
  • 이차원 배열에 저장되는 값은 노드를 잇는 엣지의 가중치

2) 연습 문제 11: 그래프를 구성하고 인접행렬로 표현하기

#include <iostream>
#include <vector>

enum class city : int
{
	MOSCOW,
	LONDON,
	SEOUL,
	SEATTLE,
	DUBAI,
	SYDNEY
};

std::ostream& operator<<(std::ostream& os, const city c)
{
	switch (c)
	{
	case city::LONDON:
		os << "런던";
		return os;
	case city::MOSCOW:
		os << "모스크바";
		return os;
	case city::SEOUL:
		os << "서울";
		return os;
	case city::SEATTLE:
		os << "시애틀";
		return os;
	case city::DUBAI:
		os << "두바이";
		return os;
	case city::SYDNEY:
		os << "시드니";
		return os;
	default:
		return os;
	}
}

struct graph
{
	std::vector<std::vector<int>> data;

	graph(int n)
	{
		data.reserve(n);
		std::vector<int> row(n);
		std::fill(row.begin(), row.end(), -1);

		for (int i = 0; i < n; i++)
		{
			data.push_back(row);
		}
	}

	void addEdge(const city c1, const city c2, int dis)
	{
		std::cout << "에지 추가: " << c1 << "-" << c2 << "=" << dis << std::endl;

		auto n1 = static_cast<int>(c1);
		auto n2 = static_cast<int>(c2);
		data[n1][n2] = dis;
		data[n2][n1] = dis;
	}

	void removeEdge(const city c1, const city c2)
	{
		std::cout << "에지 삭제: " << c1 << "-" << c2 << std::endl;

		auto n1 = static_cast<int>(c1);
		auto n2 = static_cast<int>(c2);
		data[n1][n2] = -1;
		data[n2][n1] = -1;
	}
};

int main()
{
	graph g(6);
	g.addEdge(city::LONDON, city::MOSCOW, 2500);
	g.addEdge(city::LONDON, city::SEOUL, 9000);
	g.addEdge(city::LONDON, city::DUBAI, 5500);
	g.addEdge(city::SEOUL, city::MOSCOW, 6600);
	g.addEdge(city::SEOUL, city::SEATTLE, 8000);
	g.addEdge(city::SEOUL, city::DUBAI, 7000);
	g.addEdge(city::SEOUL, city::SYDNEY, 8000);
	g.addEdge(city::SEATTLE, city::MOSCOW, 8400);
	g.addEdge(city::SEATTLE, city::SYDNEY, 12000);
	g.addEdge(city::DUBAI, city::SYDNEY, 1200);

	g.addEdge(city::SEATTLE, city::LONDON, 8000);
	g.removeEdge(city::SEATTLE, city::LONDON);

	return 0;
}

3) 인접 리스트로 그래프 표현하기

  • 행렬 이용시 문제점 : 노드 개수의 제곱에 비례하는 메모리 사용
  • 직접 연결되어 있는 엣지만 저장하는 방식의 그래프 → 인접 리스트

4) 연습 문제 12: 그래프를 구성하고 인접 리스트로 표현하기

#include <iostream>
#include <vector>
#include <algorithm>

enum class city : int
{
	MOSCOW,
	LONDON,
	SEOUL,
	SEATTLE,
	DUBAI,
	SYDNEY
};

std::ostream& operator<<(std::ostream& os, const city c)
{
	switch (c)
	{
	case city::LONDON:
		os << "런던";
		return os;
	case city::MOSCOW:
		os << "모스크바";
		return os;
	case city::SEOUL:
		os << "서울";
		return os;
	case city::SEATTLE:
		os << "시애틀";
		return os;
	case city::DUBAI:
		os << "두바이";
		return os;
	case city::SYDNEY:
		os << "시드니";
		return os;
	default:
		return os;
	}
}

struct graph
{
	std::vector<std::vector<std::pair<int, int>>> data;

	graph(int n)
	{
		data = std::vector<std::vector<std::pair<int, int>>>(n, std::vector<std::pair<int, int>>());
	}

	void addEdge(const city c1, const city c2, int dis)
	{
		std::cout << "에지 추가: " << c1 << "-" << c2 << "=" << dis << std::endl;

		auto n1 = static_cast<int>(c1);
		auto n2 = static_cast<int>(c2);
		data[n1].push_back({n2, dis});
		data[n2].push_back({n1, dis});
	}

	void removeEdge(const city c1, const city c2)
	{
		std::cout << "에지 삭제: " << c1 << "-" << c2 << std::endl;

		auto n1 = static_cast<int>(c1);
		auto n2 = static_cast<int>(c2);
		std::remove_if(data[n1].begin(), data[n1].end(), [n2](const auto& pair) {
			return pair.first == n2;
			});
		std::remove_if(data[n2].begin(), data[n2].end(), [n1](const auto& pair) {
			return pair.first == n1;
			});
	}
};

int main()
{
	graph g(6);
	g.addEdge(city::LONDON, city::MOSCOW, 2500);
	g.addEdge(city::LONDON, city::SEOUL, 9000);
	g.addEdge(city::LONDON, city::DUBAI, 5500);
	g.addEdge(city::SEOUL, city::MOSCOW, 6600);
	g.addEdge(city::SEOUL, city::SEATTLE, 8000);
	g.addEdge(city::SEOUL, city::DUBAI, 7000);
	g.addEdge(city::SEOUL, city::SYDNEY, 8000);
	g.addEdge(city::SEATTLE, city::MOSCOW, 8400);
	g.addEdge(city::SEATTLE, city::SYDNEY, 12000);
	g.addEdge(city::DUBAI, city::SYDNEY, 1200);

	g.addEdge(city::SEATTLE, city::LONDON, 8000);
	g.removeEdge(city::SEATTLE, city::LONDON);

	return 0;
}

 

출처 : 코딩 테스트를 위한 자료구조와 알고리즘 with C++ (길벗)

'Computer Science > Data Structure & Algorithm' 카테고리의 다른 글

그리디 알고리즘  (0) 2023.07.02
분할 정복  (0) 2023.07.01
해시 테이블과 블룸 필터  (0) 2023.06.29
트리/힙/그래프(1) - 트리  (0) 2023.06.27
리스트 / 스택 /큐  (0) 2023.06.26
Computer Science/Data Structure & Algorithm 관련 글
더 보기

티스토리툴바