이번 포스팅에서는 최소 신장 트리(MST) 알고리즘을 알아보겠습니다. 최소 신장 트리는 난이도가 높은 알고리즘에 속합니다. 따라서 그래프 이론, 트리의 개념, 서로소 집합(Union-Find), 정렬, 우선순위 큐에 대한 이해가 선행되어야 합니다. 따라서 기본적인 알고리즘을 먼저 이해한 후에 공부하는 것을 권장합니다.최소 신장 트리 알고리즘은 크게 크루스칼 알고리즘과 프림 알고리즘이 있습니다. 이 글에서는 크루스칼(Kruskal's algorithm), 프림 알고리즘을 소개하고 활용에 대해서 알아보겠습니다. 1. 최소 신장 트리란?V개의 정점과 E개의 간선이 양방향 그래프 형태로 연결되어 있다고 가정해봅시다. 또한 이 그래프는 연결그래프입니다. (연결그래프란 소외된 정점이 없다는 것을 의미합니다. 즉, ..

별거 없다. 그냥 구현을 요구하는 문제이다. 하지만 구현 과정에서 프로그래밍에 대한 여러 가지 기본 지식을 요구하는 만큼 난이도가 있는 유형이다. 특히 구현하고 나서 디버깅하는 과정에서 많은 시간이 걸린다. 특히 배열 out of bound, 오버플로우 등을 잡는데 정신이 나갈 수 있다. 따라서 평소에 꾸준히 알고리즘을 하며 구현능력을 기르며 미리 대비해 놓아야 하는 유형이다. 예제는 삼성 기출문제가 유명하다. 연구소 문제 등이 대표적이다.

이번 포스팅에서는 유니온 파인드 알고리즘에 대해서 알아보겠습니다. 유니온 파인드를 알기 위해 간단한 트리의 개념을 알아야 합니다. 트리가 처음이라면 먼저 간단하게라도 트리의 개념과 트리 순회를 알아보고 오는 것을 추천드립니다.유니온 파인드 알고리즘은 기본 구현보다 최적화 방법과 문제 적용이 더 중요합니다. 최적화 원리까지 이해하고 문제 적용하는 것을 강력 권장합니다. 1. 유니온 파인드란?다음과 같이 여러 노드간의 연결 관계가 주어졌다고 해봅시다.임의의 두 노드가 주어졌을 때 유니온 파인드 알고리즘을 이용하면 두 노드가 같은 집합에 속하는지 확인할 수 있습니다. 예를 들어 1과 2는 같은 집합, 3과 5도 같은 집합, 4와 6은 다른집합입니다. 유니온 파인드를 이용하면 이러한 연산을 O(1)에 바로 알 ..

1. 가중치가 1인 무방향 그래프인 경우: BFS로 풀면 최초 방문 위치가 최단 경로가 보장된다.2. 가중치가 있는 방향이 있는 그래프인 경우: 데이크 스트라 알고리즘3. 플로리드 알고리즘(음수 간선도 가능)4. 벨만 포드 알고리즘

이번 포스팅에서는 비트마스킹에 대해 다루겠습니다. 비트마스킹을 이해하려면 비트에 대한 기본적인 이해가 필요합니다. 따라서 비트연산, 이진수의 표현과 변환 방법, 부분집합에 대해 이해가 선행되어야 합니다. 일반적으로 C++의 헤더에는 비트마스킹의 여러 기능을 지원합니다. 하지만 비트연산을 통해 직접 구현할 줄 알아야 합니다. 따라서 이번 포스팅에서는 직접 구현하고 원리를 알아보는 것을 위주로 다룹니다. 1. 개념 비트마스킹이란? 컴퓨터로 처리하는 모든 정보는 0과 1의 이진수로 이루어져 있습니다. 비트마스킹은 이진수의 비트 표현을 이용하여 자료구조(주로 집합)를 표현하는 기법입니다. 0은 해당 비트에 원소가 없음을, 1은 해당 비트에 원소가 있음을 나타냅니다. 예를 들어 10진수 14를 이진수로 변환하고 ..