Computer Science/알고리즘30 [알고리즘] ep7++) 다익스트라 확장 알고리즘 다익스트라 확장 알고리즘은 기본 다익스트라 알고리즘을 수정하여 단일 출발점에서 목표 지점까지의 최단 경로뿐만 아니라 최단 경로의 수까지 계산할 수 있도록 한다. 이 문제에서 요구하는 것은 다익스트라 알고리즘을 사용하여 각 정점까지의 최단 거리를 계산하고, 동시에 각 정점에 도달하는 최단 경로의 수를 세는 기능을 추가한 것이다. 위 샘플그래프 G에 대해 아래 정점쌍 4개를 s(ource) 및 t(arget) 인자쌍으로 각각 사용하여 수행하라(즉, 프로그램을 4회 수행함). 각 수행 결과는 아래 예시처럼 인쇄할 것 [출력예시]source target 최단거리 최단경로 수C A 1 1 C F .. 2024. 8. 2. [알고리즘] ep7+) 다익스트라와 벨만-포드 알고리즘 구현 주의: 그래프 알고리즘 구현 시, 그래프의 인접 정보(즉, 부착 간선리스트 또는 인접행렬) 없이도 수행 가능한 문제라고 판단되면 간선리스트 구조로 그래프를 간편하게 구현할 것을 우선적으로 고려하라. 그렇지 않고, 인접 정보가 있어야 수행한다고 판단되면 인접리스트 구조 또는 인접행렬 구조 중에 해당 문제 해결에 효율성 면에서 유리하다고 판단되는 것을 선택하여 구현하라. 문제1) 무방향 양의 가중그래프 -> 다익스트라 알고리즘무방향 양의 가중그래프(undirected weighted graph) G와 출발정점이 주어지면, 출발정점에서 다른 모든 정점으로 가는 최단거리를 구하는 프로그램을 작성하라. 입력 그래프의 성질:◦ n(1 ≤ n ≤ 100)개의 정점과 m(1 ≤ m ≤ 1,000)개의 간선으로 구성.. 2024. 7. 27. [알고리즘] ep7) 최단경로 ㅁ최단경로 문제(shortest path problem): 가중그래프 두 개의 정점 u와 v가 주어졌을 때, u와 v 사이의 무게의 합이 최소인 경로를 구하는 문제최단경로길이: 간선들의 무게 합 응용: 인터넷 패킷 라우팅, 항공편 예약, 자동차 네비게이션 [최단경로 속성 2가지]속성1)최단경로의 부분경로(subpath) 역시 최단경로이다 속성2)출발정점으로부터 다른 모든 정점에 이르는 최단경로들의 트리가 존재한다 - 단일점 최단경로(single-source shortest path) - 최단경로는 무방향뿐만 아니라 방향그래프에서도 정의가 가능하다- 그래프에 음의 무게를 가진 싸이클이 있거나, 무방향그래프에 음의 무게를 가진 간선이 있으면 부정한다- 최단경로트리(shortest path tree)는 루트.. 2024. 7. 26. [알고리즘] ep6+) Prim-Jarnik과 Kruskal 알고리즘 구현 주의: 그래프 알고리즘 구현 시, 그래프의 인접 정보(즉, 부착 간선리스트 또는 인접행렬) 없이도 수행 가능한 문제라고 판단되면 간선리스트 구조로 그래프를 간편하게 구현할 것을 우선적으로 고려하라. 그렇지 않고, 인접 정보가 있어야 수행한다고 판단되면 인접리스트 구조 또는 인접행렬 구조 중에 해당 문제 해결에 효율성 면에서 유리하다고 판단되는 것을 선택하여 구현하라. 문제1) Prim-Jarnik 알고리즘 구현입력으로 주어지는 그래프를 Prim-Jarnik 알고리즘을 이용하여 최소신장트리(Minimum Spanning Tree, MST)를 생성하는 프로그램을 작성하고, 최소신장트리의 생성 과정과 총무게를 결과로 출력하시오. 입력 그래프의 성질: n (1 ≤ n ≤ 100) 개의 정점과 m (1 ≤ m .. 2024. 7. 26. [알고리즘] ep6) 최소신장트리(MST) ㅁ가중그래프(weighted graph): 각 간선이 무게(weight)라 부르는 수치값을 가지는 그래프 무게의 예: 거리, 비용, 시간 등 이 철도 그래프에서는 간선의 무게가 여행거리를 표현한다 신장 부그래프: 그래프 G의 모든 정점들을 포함하는 부그래프신장트리(spanning tree): 모든 정점이 다 이어져 있으면서, 싸이클이 없는 무방향 그래프 (자유 트리인 신장 부그래프)ㅇ최소신장트리(MST, Minimum Spanning Tree): 가중그래프의 총 간선 무게가 최소인 신장트리응용: 통신망, 교통망 [MST 속성 2가지] - MST 알고리즘 정확성 검증에 이용1. 싸이클 속성T를 가중그래프 G의 MST라 하자e를 T에 존재하지 않는 G의 간선으로, C를 T에 추가하여 형성된 싸이클로 가정그.. 2024. 7. 25. 휴리스틱(heuristic) 알고리즘 ㅇ휴리스틱(heuristic): 문제 해결, 학습, 또는 발견을 위한 경험적 기법 또는 방법론 최적의 해결책을 보장하지는 않지만, 실용적으로 충분히 좋은 해결책을 빠르게 찾는 데 유용하다 [활용 분야] 컴퓨터 과학: 알고리즘 설계에서, 특히 탐색 알고리즘에서 휴리스틱을 사용하여 탐색 공간을 줄이고 효율성을 높인다의사결정: 불확실한 상황에서 결정을 내릴 때, 휴리스틱은 빠른 결정을 돕는 도구로 사용된다심리학: 인지 심리학에서 사람들의 문제 해결과 의사결정 과정을 설명하기 위해 휴리스틱 개념을 사용한다 예를 들어, 가용성 휴리스틱(availability heuristic)은 사람들이 머릿속에 쉽게 떠오르는 정보를 바탕으로 결정을 내리는 경향을 설명합니다 ㅇ휴리스틱 알고리즘: 불충분한 시간이나 정보로 인하.. 2024. 7. 25. [알고리즘] ep5-3++) 분할통치법 vs DP 문제) 여행의 최소비용을 구하는 알고리즘을 작성하라.airtelDC(분할통치 버전)와 airtelDP(동적프로그래밍 버전)를 구현하고 실행시간을 비교 프로그램 요구사항: 1) 각 해결버전의 정방향, 역방향 버전 가운데 자유롭게 하나를 선택하여 구현하라. 2) 출력예시: 최종적으로 다음과 같이 인쇄되어야 한다. ※ 참고1) 아래는 MAX = 30인 경우의 인쇄결과임.2) X.XXXXXXXX는 cputime in milliseconds. 주의:반드시 아래 가이드라인의 main 함수 내용과 동일하게 실행하고 출력을 구하라.n = 6로 한 테스트실행 결과가 수작업실행 결과와 일치하는지 확인한 후 n = MAX로 한 본실행을 시도할 것.경로가 아닌 최소비용만을 요구하는 문제이므로, 만약 최소비용 경로가 두 .. 2024. 7. 24. [알고리즘] ep5-3+) 위상순서 찾기 문제) 주어진 방향그래프 G에 대해 다음과 같이 수행하는 프로그램을 작성하라.1. G가 방향 비싸이클 그래프(directed acyclic graph: DAG)면 위상순서(topological order)를 구해 인쇄.2. G에 방향 싸이클(directed cycle)이 존재하면 위상순서를 구할 수 없으므로 0을 인쇄. 힌트:이 문제의 경우 그래프를 인접리스트 구조로 표현하는 것이 시간 성능 면에서 유리하며 배열로 구현하는 편이 코딩에 용이하다.위상 정렬 알고리즘에는 두 가지 버전이 있다. 첫째 깊이우선탐색(DFS)을 응용하는 버전, 둘째 각 정점의 진입차수(in-degree)를 이용하는 버전이다. 본 문제 해결을 위해 두 번째 버전을 사용하라. 이 버전은 그래프 G가 DAG면 위상순서를 구하고 그렇지 .. 2024. 7. 24. [알고리즘] ep5-3) 방향그래프 ㅁ방향그래프(directed graph): 모든 간선이 방향간선인 그래프 응용: 일방통행 도로, 항공노선, 작업 스케줄링 방향 DFS 알고리즘에서, 네 종류의 간선이 발생한다1. 트리간선(tree edges): 새로운 정점 방문 시 사용되는 간선2. 후향간선(back edges): 현재 정점에서 이미 방문한 정점으로 돌아가는 간선3. 전향간선(forward edges): 조상의 정점에서 자손의 정점으로 향하는 간선4. 교차간선(cross edges): 같은 레벨 또는 다른 서브트리의 정점으로 향하는 간선 방향그래프 G의 두 정점 u와 v에 대해 만약 u에서 v로의 방향경로가 존재한다면, "u는 v에 도달한다(reach)" 또는 "v는 u로부터 도달 가능(reachable)하다"라고 말한다 방향그래프 G.. 2024. 7. 23. 이전 1 2 3 4 다음
