본문 바로가기

Algorithm

 (30)
[Algorithm] 모든 쌍 최단 경로 | Floyd-Warshall Algorithm 이전에 포스팅했던 모든 쌍 최단 경로, 다익스트라 알고리즘을 이용하는 법과 또다른 알고리즘 방식인 Floyd-Warshall 알고리즘에 대해 기록해보고자 한다! 이전의 다익스트라 알고리즘,, 각 점을 시작점으로 정하여 다익스트라의 최단 경로 알고리즘을 수행 시간복잡도는 배열을 사용하면 (n-1) x O(n^2) = O(n^3) Floyd-Warshall 알고리즘 (플로이드-워샬)? 💡접근법 두 정점을 잇는 최소 비용 경로는 경유지를 거치거나 거치지 않는 경로 중 하나에 속한다. 만약 경유지를 거친다면 그것을 이루는 부분 경로 역시 최소 비용 경로여야 한다. 💡동적 계획 알고리즘으로 접근하기 위해, 먼저 부분 문제들을 찾는다. 그래프에 점이 3개 있는 경우, 직접 가는 경로와, 점 하나를 거쳐 경유하는 경..
[Algorithm] 동적 계획 알고리즘 동적 계획 알고리즘에 대해 공부하기 전에,, 이전에 포스팅했던 분할정복 방법! 다시 살펴보기 💡분할정복 방법? 하향식 top-down 접근법 상위 레벨의 복잡한 문제를 재귀적으로 작은 문제들로 나누고, 이들의 해를 결합해서 문제를 해결하는 방법 분할된 부분 문제들은 서로 독립적 퀵정렬, 합병 정렬, 이진 탐색 ➰피보나치 수열을 분할 정복으로? 같은 계산이 반복됨 -> 비효율적! 💡동적 계획 알고리즘? 그리디 알고리즘과 같이 최적화 문제를 해결하는 알고리즘 작은 문제에 대한 결과를 테이블에 저장해 놓고, 이를 이용하여 입력의 크기가 보다 큰 문제의 해를 점진적으로 만들어가는 방법 최댓값/최솟값을 구하는 최적화 문제에 적용 부분 문제들 사이에 의존적 관계가 존재한다. 이러한 관계는 문제 또는 입력에 따라 다..
[Algorithm] 허프만 압축 💡허프만 압축 아이디어 파일에 빈번히 나타나는 문자 -> 짧은 이진코드 할당 드물게 나타나는 문자 -> 긴 이진코드 할당 💡접두부 특성 (prefixx property) 허프만 압축방법으로 변환시킨 문자 코드들 사이에 존재 각문자에 할당된 이진 코드는 어떤 다른 문자에 할당된 이진코드의 접두부가 되지 않는다를 의미 접두부 특성의 장점은 코드와 코드 사이를 구분할 특별한 코드가 필요 없다는 것! 💡그래서, 허프만 압축은 뭘까? 입력파일에 대해 각문자의 출현 빈도수에 기반을 둔 이진트리를 만들어서, 각 문자에 이진코드를 할당 이러한 이진코드를 허프만 코드라고 한다. 💡의사코드 입력 : 입력 파일의 n개의 문자에 대한 각각의 빈도 수 출력 : 허프만 트리 1. 각 문자당 노드를 만들고, 그 문자의 빈도수를 노..
[Algorithm] 작업 스케줄링 💡작업스케줄링 수행해야할 다수의 Job을 주어진 목적에따라 어떻게 수행할지를 결정하는 문제 주어진 목적에따라 작업스케줄링을 다양하게 정의할 수 있다. 이러한 문제들은 대부분 NP-hard문제이나, 일부 목적에 대해서 또는 문제를 단순화 시킬 경우 polynomial time에 해결할 수 있다. 💡작업스케줄링 문제 작업의 수행시간이 중복되지 않도록 모든 작업을 가장 적은 수의 기계에 배정하는 문제이다. n개의 각작업은 시작시간과 종료시간이 있다. 주어진 문제요소 작업의 수 각 작업의 시작과 종료시간 : 이는 정해져 있으므로 작업의 길이도 주어진 것이 된다. 시각시간, 종료시간, 작업의 길이에 대해 그리디 알고리즘을 생각해 볼 수 있는데 빠른 시작시간 작업 우선 배정 빠른 종료시간 작업 우선 배정 짧은 작업..
[Algorithm] 집합 커버 문제 (Set Covering Problem) 💡집합커버문제 (Set Covering Problem) n개의 원소를 가진 집합 U U의 부분집합들을 원소로하는 집합 F F의 원소들인 집합들 중에서 어떤 집합들을 선택하여 합집합하면 U와 같게 되는가? 여기서, F에서 선택하는 집합들의 수를 최소화하는 문제이다. ❓최적해를 어떻게 찾아야할까? 가장 단순한 방법 : F에 있는 집합들의 모든 조합을 1개씩 합집합하여 U가 되는지 확인하고, U가 되는 조합의 집합 수가 최소인 것을 찾는 것 Brute Force Algorithm : n개의 원소가 있으면 (2^n -1)개를 다 검사 필요 n이 커지면 최적해를 찾는 것은 실질적으로 불가능 실제로 집합커버문제는 NP-hard 문제로 polynomial time optimal algorithm을 설계하기 매우 어렵..

티스토리툴바