개발공부/알고리즘 이론6 MST 알고리즘(크루스칼, 프림) 최소비용 신장트리 (Minimum Spanning Tree, MST)MST의 특징신장트리: 그래프의 모든 정점을 포함하며, 사이클이 없는 트리입니다.최소 비용: 간선 가중치의 합이 최소가 되는 트리입니다.유일성: 모든 간선의 가중치가 서로 다르면 MST는 유일합니다. 즉 여러 경로가 나올 수 없다는 것이다.MST 알고리즘MST를 구하는 알고리즘은 다음과 같은 두 가지 주요 방법이 있다.1. 크루스칼 알고리즘 (Kruskal’s Algorithm)방법: 간단하게 생각하면 sort하고 sort순서대로 간선연결하고 cycle이 발생하는지 검증만 하면 끝이다.그래프의 모든 간선을 가중치 기준으로 오름차순 정렬합니다.최소 가중치의 간선부터 하나씩 추가합니다.사이클이 발생하지 않는 경우에만 간선을 추가합니다.모든 .. 2024. 12. 7. Graph-다익스트라 알고리즘(Dijkstra Algorithm) 다익스트라 알고리즘이란?먼저 백번 글로 읽는 것 보다 움짤을 보자 1. 다익스트라 알고리즘의 특징그래프 유형: 방향 그래프 또는 무방향 그래프에 적용 가능.가중치 조건: 간선 가중치(Weight)가 음수일 수 없음.출발점 기준: 하나의 시작 정점에서 다른 모든 정점까지의 최단 경로를 계산.2. 알고리즘 동작 방식초기화:출발점 s에서 모든 정점까지의 거리 값을 무한대(∞)로 설정.출발점 s의 거리는 0으로 설정.우선순위 큐(최소 힙)를 사용하여 가장 가까운 정점을 효율적으로 추출.최단 거리 업데이트:현재까지 가장 짧은 경로로 방문하지 않은 정점을 선택.선택된 정점을 기준으로, 인접 정점의 거리 값을 업데이트.만약 새로운 경로가 기존 경로보다 짧다면, 해당 정점의 거리를 갱신.반복:모든 정점이 처리될 때까.. 2024. 12. 7. 그래프란?(Computer Science) bfs, dfs, scc, dag 1. 먼저 그래프란 뭘까?개체들과 개체들의 일대일 관계를 수학적으로 나타내는 표현 방법이다. 2. 그래프의 종류에는 이렇게 크게 세가지 정도가 있다.희소 그래프 (Sparse Graph): 간선의 수가 정점 수에 비해 상대적으로 적은 그래프.완전 그래프 (Complete Graph): 모든 정점이 서로 간선으로 연결된 그래프.밀집 그래프 (Dense Graph): 간선의 수가 정점 수에 비해 상대적으로 많은 그래프.3. 그리고 그래프의 기본 알고리즘은 bfs, dfs가 있는데 이를 응용한 알고리즘이 존재한다.BFS (Breadth-First Search)BFS는 그래프의 모든 정점을 층층이 탐색하는 알고리즘입니다. 큐(Queue)를 사용하여 시작 정점에서 가까운 정점부터 탐색한다.알고리즘 과정시작 정점.. 2024. 12. 6. 시간복잡도 g(n)은 f(n)의 상한이다. 2024. 10. 20. 알고리즘 시간 복잡도, 마스터 정리 일반적으로 반복문 같은 경우에는 보는게 쉽다. 그냥 가장 큰 루프를 보면 되는데, 까다로운 것은 자기호출 함수가 있을 때 까다롭다. 그래서 수학 잘하는 형님들이 공식을 만들었는데 바로 마스터 정리이다. 증명하는 과정도 있는데 난 수학이 잼병이라 잘 모르겠다. 이렇게 좋은게 있다~~ 하고 쓰면 될 것 같다. a: 재귀가 호출 된 수b: 기존의 n보다 얼마나 쪼개는가.c: 재귀가 아닌 것의 반복, 시간복잡도이다. 대표적인 합병 정렬을 예시로 보자.a= 2 -> 재귀가 2번 호출 되므로b=2 -> 재귀가 2로 나누어 지므로 mid =(low+high)/2k= 1 -> merge과정은 시간 복잡도가 n이므로 구체적으로 따지면 n-1번 수행하게 되는데 그냥 편의상 n으로 봐도 무방하다. 그렇다면 T(n) =.. 2024. 10. 7. 분할정복 divide & conquer (알고리즘) +(백준 1780) 알고리즘 문제에서 분할정복 문제를 만나면 어떻게 접근해야 하는지 정리하는 글이다. 이 문제를 찾는 인사이트는 문제를 보고 이 문제를 작은 문제로 쪼갤 수 있을까?를 보는 것이다.그리고 고민거리가 몇가지 있다. 1. 어떻게 나눌 것인가?2. 어디까지 나눌 것인가? degenerate case의 크기?3. 대칭적으로 나눌 것인가? 합병 VS 쾌속 정렬4. combine 단계가 필요한가? ( 대부분 쪼개긴 해야 하는데 합병 단계는 크게 필요 없는 경우가 많다.) 수시적으로 살펴보자 아래의 사진은 분할 정복을 표현하는 식이다. 이를 점화식으로 표현하면 아래와 같다.점화식의 해법은 아래와 같다. 1. 특성 방정식2. 텔레스코핑3. 마스터 정리 1번 2번은 머리 아프니 3번만 알아도 크게 상관 없다고 생각한다.ht.. 2024. 10. 7. 이전 1 다음
