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

이번 포스팅에서는 이산수학의 한 개념으로써 조합에서 중복을 확인하는 방법이다. 알고리즘에서는 완전탐색의 경우에서 시간복잡도를 줄이는 기법으로 많이 활용된다.  예시문제: 세 사람의 심리적 거리,

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

https://kau-algorithm.tistory.com/27 간단한 알고리즘 - 정수론 이 글은 학회 회원 랑이집사님의 허락을 받아 에브리타임 게시글을 그대로 가져왔습니다. 코딩테스트에서 나오는 비주류 유형이 몇가지 있는데, 그중 하나인 정수론에 대해 적어보려고 합니다. kau-algorithm.tistory.com 심화 정수론!!! 기본 안내서 pdf 및 블로그 정리 모음 https://rkm0959.tistory.com/category/PS/PS%20%EC%A0%95%EC%88%98%EB%A1%A0%20%EA%B0%80%EC%9D%B4%EB%93%9C 'PS/PS 정수론 가이드' 카테고리의 글 목록 rkm0959.tistory.com 증명을 정리해놓은 심화 과정들!! https://site.th..

이번 포스팅에서는 스택의 정의와 성질, 구현 방법, 활용에 대해서 정리합니다. 스택은 큐, 데큐와 서로 비슷한 부분이 많기 때문에 함께 공부하는 것을 적극 추천합니다.또한 스택은 비교적 여러 알고리즘에서 활용합니다. 따라서 어렵더라도 제대로 이해하고 넘어가야 합니다. 1. 스택의 의미와 특징스택이란?마지막으로 들어온 원소가 제일 먼저 나가는 자료구조더 이해하기 쉽게 풀어보면 한쪽 입구만 뚫린 터널이라고 생각할 수 있다. 이 구조는 데이터들이 한쪽으로만 들어갔다가 나오며 무언가 쌓는 모양을 생각할 수 있다. 이러한 형태 때문에 "쌓다"라는 의미에서 스택(stack)으로 불린다. 스택의 특징LIFO(Last In First Out)의 구조를 가진다.원소의 추가/제거/확인이 모두 O(1)이다.최상단의 원소에만..

이번 포스팅에서는 선형 자료구조인 큐에 대해서 알아보겠습니다. 큐는 스택, 데큐와 비슷한 점이 아주 많기 때문에 이들과 같이 비교하면서 보는게 좋습니다. 1. 큐 FIFO의 규칙을 가지는 자료구조입니다. 선입선출이라고도 합니다. 마치 놀이공원 대기줄을 연상시키죠. 2. 구현 배열을 이용해 구현할 수 있지만 head와 tail이 계속해서 밀리는 문제때문에 연결리스트를 이용한 원형 큐로 구현하는 것이 효율적입니다. 하지만 C++의 STL에는 이미 선형 큐가 구현되어 있습니다. STL의 queue를 쓰는 것을 적극 추천합니다. 다음은 큐 구현을 연습하기에 좋은 기본적인 문제들입니다. [백준 10845] 큐 [백준 18258] 큐2 [백준 2164] 카드2 3. 활용 큐는 주로 한 방향으로 처리되는 데이터들을 ..