Greedy5 [Algorithm] 허프만 코드 허프만 코드는 문자를 데이터로 표현할 때 더 적은 데이터양을 사용하면서 문자를 표현하기 위해 압축하는데 사용하는 방법으로 Greedy Algorithm중 하나입니다. 문자의 빈도수를 이용하여 사용빈도수가 높은 문자는 짧은 비트로 표현, 사용빈도수가 낮은 문자는 긴 비트로 표현합니다. 즉, 가변 길이 코드이다. 예시를 들어 설명하겠습니다. EX) 압축하고자 하는 문자열 : bacbca -> 고정 길이 코드 : a~c. 3개의 문자를 구분하기 위해 2bit 필요하고 총 12bit를 사용한다 -> 가변 길이 코드 : 허프만 코드를 이용해서 나온 값으로 10bit로 줄어든다 그러나 여기서 의문점이 있다. 010을 ac(0/10)인지 ba(01/0)인지 구분이 안간다 즉 이진 코드를 다시 문자열로 변환할 때 어디.. 2024. 4. 8. [Algorithm] Scheduling Scheduling은 Greedy Algorithm의 대표적인 활용 알고리즘이다 해당 알고리즘의 목표를 통해서 Greedy의 설계방법을 알수있다. 1. 스케줄짜기(Scheduling) 기다리는 시간을 최소화하는 것이 목표인 알고리즘이다. 여기서는 시스템 내부 시간 (The time in the system)을 기준으로 측정을 하는데 시스템 내부 시간은 기다리고 수행하는 시간을 합친시간이다. 즉, Scheduling의 목표는 최적의 순서를 찾아 시스템 내부 시간 을 줄이는것이다. 예시를 통해서 간단하게 알아보겠다. 예시 효율적인 과제하기 과제를 효율적으로 하고자한다. 한번 과제를 시작하면 중간에 다른 과제를 할 수 없다고 한다면 어떤 순서로 해야 효율적일까? 과제이름 걸리는시간 취창업 실무 3시간 컴퓨터 .. 2024. 4. 8. [Algorithm] 다익스트라 알고리즘(Dijkstra Algorithm) 다익스트라 알고리즘은 음의 가중치가 없는 그래프의 한 노드에서 각 모든 노드까지의 최단거리를 구하는 알고리즘이며 도로 교통망 같은 곳에서 나타날 수 있는 그래프에서 두 노드 간의 최단경로를 찾는 알고리즘이기도 하다. (무방향/ 방향그래프 둘다 상관없이 사용가능하다) 해당 알고리즘은 DP(다이나믹 프로그래밍)와 Greedy Algorithm(탐욕 알고리즘)을 복합적으로 사용하는 알고리즘이다. 최단거리는 여러개의 최단거리로 나눠져있고 이전까지 구한 최단 거리는 그대로 사용한다 → DP 눈앞에 보이는 최적의 선택을 한다 → Greedy 예시를 들면서 한번 다익스트라로 어떻게 풀어나가는지 확인해보고 마무리 지어보겠습니다. 예시 네비게이션 1번에서 6번을 최단 경로로 찾아가야하는 상황에서 모든 노드까지의 최단거리.. 2024. 4. 8. [Algorithm] 최소 신장 트리(MST), Kruskal & Prim algorithm 신장 트리(Spanning Tree) 그래프 내의 모든 정점을 포함한 최소 연결 부분 그래프이며 Tree이기 때문에 사이클이 존재할 수 없다. 최소비용 신장 트리 (Minimum Spanning Tree : MST) 신장 트리 중 간선의 가중치 합이 최소인 트리이다. 가중치가 존재하는 무방향 Graph에서 Spanning Tree(이하 신장 트리)를 무작위로 만들어 었을 경우 cost는 다양하게 나옵니다. 하지만 그중에서 최소 비용으로 만드는 신장 트리를 Minimum Spanning Tree(이하 최소비용 신장 트리)라고 한다 사진을 보면 Graph에서 Cost(가중치합)을 고려 안한 신장 트리를 제작을 했을 경우 Cost가 13이 나오게 됩니다. 여기서 Cost를 최소한으로 줄여본 신장 트리는 Cos.. 2024. 4. 7. 이전 1 2 다음
