📖 Computer Science/알고리즘3 [CS Study] 알고리즘 (3) - 최단 거리 알고리즘 시작하기 전에세 번째 챕터는 최단 거리 알고리즘입니다.최단 거리 알고리즘은 그래프에서 정점 간 최단 거리를 구하기 위한 알고리즘입니다.'다익스트라 알고리즘'과 '벨만-포드 알고리즘'의 작동 원리를 이해해보겠습니다.공부하는 데 많은 도움을 받은 '기술면접대비 CS전공 핵심요약집' 저자분께 감사드립니다.다익스트라 알고리즘이란?다익스트라 알고리즘(Dijkstra algorithm)은 간선의 가중치가 음수가 아닌 경우에만 적용할 수 있다.수행 과정을 단계별로 살펴보면 다음과 같다:S를 시작 정점으로 설정하고, 초기에 모든 정점에 도달하는 비용을 무한대(INF)로 설정한다.정점 S와 연결된 정점 A, B, C, D까지의 비용을 갱신한다.방문하지 않은 정점 중 비용이 가장 적게 드는 정점 D를 방문한다. 정점 D와.. 2025. 5. 10. [CS Study] 알고리즘 (2) - 최소 신장 트리 시작하기 전에두 번째 챕터는 최소 신장 트리입니다.신장 트리란, 그래프의 모든 정점을 포함하는 트리를 의미합니다. 그 중에서 최소 신장 트리(MST, Minimum Spanning Tree)는 가중치가 있는 그래프에서 간선의 가중치 총합이 가장 작은 신장 트리를 의미합니다.최소 신장 트리를 생성하는 '프림 알고리즘'과 '크루스칼 알고리즘'의 작동 원리를 이해해봅시다.공부하는 데 많은 도움을 받은 '기술면접대비 CS전공 핵심요약집' 저자분께 감사드립니다.프림 알고리즘이란?프림 알고리즘(Prim algorithm)은 그리디 알고리즘으로, 임의의 정점을 시작점으로 트리를 확장하면서 최소 신장 트리를 생성하는 방식이다. 현재 트리에 포함된 정점과 연결된 간선 중 가중치가 가장 작은 간선으로 연결된 정점을 선택하.. 2025. 5. 10. [CS Study] 알고리즘 (1) - 정렬 알고리즘 시작하기 전에첫 번째 챕터는 정렬 알고리즘입니다. 여러 가지 정렬 알고리즘들을 알아봅시다.공부하는 데 많은 도움을 받은 '기술면접대비 CS전공 핵심요약집' 저자분께 감사드립니다.사진들의 출처는 아래와 같습니다:https://gmlwjd9405.github.io/버블 정렬이란?버블 정렬(Bubble Sort)은 양옆에 위치한 두 값을 비교하면서 크기 순으로 정렬한다.버블 정렬하면 배열의 뒤에서부터 정렬된다. 배열의 n번째 요소를 정렬하는 데 n-1번 필요하므로 배열의 모든 요소를 정리하려면 (n-1)+(n-2)+...+2+1 = n(n-1)/2 만큼 연산을 수행해야 한다. 따라서 O(n^2)의 시간 복잡도를 가진다.선택 정렬이란?선택 정렬(Selection Sort)은 배열을 순회하면서 배열의 앞에서부터 .. 2025. 5. 10. 이전 1 다음
