IT LAB

1. Floyd-Warshall모든 정점 쌍 간의 최단 경로를 찾는 알고리즘 입니다. ✅ 음수 가중치가 허용됨❌ 음의 사이클에는 사용 불가 2. 동작 원리모든 정점을 경유지로 설정✅ 최단 경로가 경유지를 거쳐 더 짧아질 수 있는지 확인➡️ 각 정점 쌍 간의 최단 거리를 반복적으로 갱신합니다. (Dynamic Programming) 초기화모든 정점 쌍에 대해, 직접 연결된 경로의 거리 초기화✅ 자기 자신으로 가는 경로 = 0✅ 연결되지 않은 경로 = infinit 경유지 검사i->j 로 가는 최단 경로가 경유지를 통해 더 짧아질 수 있는지 검사✅ 정점 k를 경유지로 설정 3. 구현더보기int[][] dist = new int[n][n];for (int i = 0; i Time Complexity: O(V..

1. Activity Selection Problem (활동 선택 문제)한 사람이 참여할 수 있는 최대 활동 수를 구하는 문제입니다.한 사람이 동시에 두 가지 활동을 참여할 수 없습니다. 해결 방법가장 먼저 끝나는 활동부터 선택합니다. 탐욕적 선택 속성현재 선택이 다음 선택의 기준에 영향을 미치지 않습니다.선택할 수 있는 가능 시간을 최대화하여, 남은 활동들을 선택할 수 있는 여지를 최대화합니다. 최적 부분 구조먼저 끝나는 활동을 선택하고, 남은 시간에 대해서도 동일한 방식을 적용할 수 있습니다.