YJ_Scribbles

ㅇ 다익스트라(Dijkstra)의 최단 경로 알고리즘 이용 - 각 점을 시작점으로 정하여 다익스트라 알고리즘 수행 - 시간복잡도 : n x O(n²) = O(n³) (단, n은 점의 수) ★ 플로이드 와샬 알고리즘 -> 모든 쌍의 최단경로(All Pairs Shortest Paths)문제 -> 여러지점에서 각각의 최단 경로를 구하는 문제 - Warshall은 그래프에서 모든 쌍의 경로 존재 여부를 찾아내는 동적 계획 알고리즘을 제안 - Floyd는 이를 변형하여 모든 쌍 최단 경로를 찾는 알고리즘을 고안 -> 모든 쌍 최단 경로를 찾는 동적 계획 알고리즘 : 플로이드-워샬 알고리즘 (간단히 플로이드 알고리즘) - 플로이드 알고리즘의 시간복잡도 : O(n³) (다익스트라 알고리즘을 n번 사용할 때의 시간복..

★ 동적 계획(Dynamic Programming) 알고리즘 - 최적화 문제를 해결하는 알고리즘 ☆ 동적 계획 알고리즘의 문제 해결 방법 1) 입력 크기가 작은 부분 문제들을 모두 해결 2) 작은 부분 문제들의 해를 이용하여 보다 큰 크기의 부분문제들 해결 3) 최종적으로 원래 주어진 입력의 문제 해결 ☆ 예시1) 피보니치 수열 ㅇ 개선된 피보나치 수열(동적 계획 알고리즘) ☆ 예시2) 타일링 문제1 1) 규칙성을 찾아 점화식 만들기 2) 길이 n의 사각형을 채우는 방법(경우의 수)를 따져봄 ☆ 예시3) 타일링 문제2 - 규칙성을 찾아서 점화식을 만든다 ☆ 예시4) 타일링 문제(3xN) -> 규칙성을 찾아서 점화식을 만들어 해결한다 ★ 구현하기 -> C# 콘솔 앱으로 구현 -> 자세한 설명은 주석으로 처..

☆ 기본 압축의 개념(주어진 파일의 크기를 줄이는 방법) - 파일의 각 문자가 8 bit 아스키 (ASCII) 코드로 저장되면, 그 파일의 bit 수는 8x(파일의 문자 수) -> 파일의 각 문자는 일반적으로 고정된 크기의 코드로 표현하는 것 - 고정된 크기의 코드로 구성된 파일을 저장하거나 전송 -> 파일의 크기를 줄이고, 필요시 원래의 파일로 변환할 수 있으면, 메모리 공간을 효율적으로 사용할 수 있고, 파일 전송 시간을 단축 ★ 허프만 압축 - 빈번히 나타나는 문자에는 짧은 이진 코드를 할당하고, 드물게 나타나는 문자에는 긴 이진 코드를 할당 - 출현 빈도수 (문자가 파일에 나타나는 횟수)에 기반을 둔 이진트리를 만들어서, 각 문자에 이진 코드를 할당 -> 이러한 이진 코드를 '허프만 코드'라고 한..

★ 그리디 알고리즘 - 최적화 문제를 해결하는 알고리즘 - 욕심쟁이 방법, 탐욕적 방법, 탐욕 알고리즘 등으로 불림 ☆ 종류 1. 동전 거스름돈 문제 2. 최소 신장 트리 3. Dijkstra(다익스트라) 최단 경로 4. 부분 배낭 문제 5. 집합 커버 문제 6. 작업 스케줄링 문제 ★ 배낭 문제 - 최대의 가치를 갖도록 배낭에 넣을 물건들은 정하는 문제 (-> n개의 물건이 있고, 각 물건은 무게와 가치를 가지고 있으며, 배낭이 한정된 무게의 물건들을 담을 수 있을 경우) ☆ 부분 배낭 (Fractional Knapsack) 문제 - 물건을 부분적으로 담는 것을 허용 - 그리디 알고리즘으로 해결 ☆ 0-1 배낭 문제 (0/1 배낭 문제) - 부분 배낭 문제의 원형으로 물건을 통째로 배낭에 넣어야 함 -..

★ 최단 경로(Shortest Path) 문제 - 주어진 가중치 그래프에서 어느 한 출발점에서 또 다른 도착점까지의 최단 경로를 찾는 문제 ☆ 최단 경로를 찾는 가장 대표적인 알고리즘 - 다익스트라(Dijkstra) 최단 경로 알고리즘 ☆ 다익스트라 알고리즘 - 주어진 출발점에서 시작 - 출발점으로부터 최단 거리가 확정되니 않는 점들 중에서 출발점으로부터 가장 가까운 점을 추가하고, 그 점의 최단 거리를 확정 ★ Dijkstra(다익스트라) 알고리즘 ShortestPath(G, s) 입력: 가중치 그래프 G=(V,E), |V|=n , |E|=m 출력: 출발점 s로부터 (n-1)개의 점까지 각각 최단 거리를 저장한 배열 D 1. 배열D를 ∞로 초기화시킨다. 단, D[s]=0으로 초기화한다. // 배열 D[..