본문 바로가기

전체 글53

[알고리즘 공부] 플로이드 워셜 0. 개요요즘 막학기가 종강하고 조금 해이해진 것 같다...이제 진짜 백수 신분이기 때문에 더 힘내서 공부해보려고 한다!! 1. 알고리즘 개념플로이드 워셜 알고리즘은 모든 정점 간의 최단 거리를 구할 때 사용되는 알고리즘으로,다이나믹 프로그래밍(DP) 기법 중 하나이다.정점 A에서 정점 B로 이동할 때, 정점 K를 거쳐가는 것이 더 유리한가? 를 계산하는 알고리즘으로 볼 수 있다. 이 역시 이전 시간에 정리해보았던 벨만 포트 알고리즘과 유사하게음수 가중치가 있는 그래프에서도 사용될 수 있지만,음수 사이클이 있을 경우 사용될 수 없다.또한 이 역시 모든 경우의 수를 모두 탐색하기에 정점 수가 적은 경우에 사용될 수 있다. 2. 알고리즘 구현플로이드 워셜 알고리즘은 위에서 말했던 것처럼k 번째 정점을 거쳐갔.. 2025. 12. 20.
[알고리즘 공부] 벨만포드 알고리즘 0. 개요지금 진행하고 있는 코테 스터디인 알고리즘의 왕에서정말 처음보는 알고리즘이 많이 올라와 호기심에 공부하게 되었다. 1. 알고리즘 개념벨만-포드(Bellman-Ford) 알고리즘은 가중치가 있는 그래프에서한 정점에서 다른 모든 정점까지의 최단 거리를 구하는 알고리즘이다. 유사한 다익스트라 알고리즘과의 차이는, 바로 음수 가중치가 있더라도 동작한다는 점이다.또한 벨만-포드 알고리즘은 음수 사이클 존재 여부도 판별할 수 있다는 점이 또 다른 차이점이다. 하지만 다익스트라 알고리즘보다 성능이 낮기 때문에 정점 수가 비교적 작은 그래프에서 사용될 수 있다. 2. 알고리즘 구조우선 가장 핵심적인 아이디어는 최단 경로는 최대 정점수 보다 하나 적은 수의 간선만을 포함하기 때문에,모든 간선을 정점 수 -1 번.. 2025. 12. 17.
[알고리즘 공부] 분할 정복 0. 개요분할 정복은 아마도 알고리즘 중 가장 기초적인 계념일 것이다.대표적인 탐색 알고리즘 중 하나인 이진 탐색도 분할 정복 알고리즘 중 하나이기 때문이다.이번에는 다양한 분할 정복 알고리즘에 대해 알아보고 정리해보려고 한다. 1. 알고리즘 개념분할 정복(Divide and Conquer)은 말 그대로 문제를 분할하고분할된 작은 문제들을 해결한 뒤 결과를 합치는 것이다. 대표적인 알고리즘으로는 병합 정렬, 퀵 정렬, 이진 탐색이 있다. 1) 병합 정렬병합 정렬은 대표적인 분할 정복 접근의 정렬 알고리즘이다. 1) 배열을 반으로 계속 나누고2) 나뉜 배열을 각각 정렬한 뒤3) 정렬된 배열을 병합하면서 전체를 정렬하는 알고리즘이다. #include #include using namespace std;voi.. 2025. 12. 2.
[알고리즘 공부] 머지 소트 트리 0. 개요예전에 도전했다가 못 풀었던 문제 중 시도해 볼만한 문제가 있는지 찾아봤다.그 문제는 바로 백준의 K 번째 수였다.주어진 배열에서 s번째에서 e번째 숫자까지 정렬하고, 그중 k 번째 수를 찾는 문제였다.지금이었으면 세그먼트 트리를 사용해서... 아마... 풀지.. 않았을까..?그래서 이번에는 세그먼트 트리를 이용한 자료구조 중 하나인 머지 소트 트리에 대해 공부해보았다. 1. 알고리즘 개념머지 소트 트리는 세그먼트 트리의 각 노드에 해당 구간의 원소들을 정렬한 배열을 저장한 자료구조이다.따라서 정렬된 구간을 이용한 문제들을 빠르게 처리할 수 있다.이때는 보통 O(long^2 N)안에 처리된다. 2. 알고리즘 구조 기본적으로 세그먼트 트리 형태로 생겼으며,각 노드는 노드의 속성에 따라 다른 값이 .. 2025. 11. 29.

티스토리툴바