3.5. 프로그래밍 개념 및 도구/알고리즘 이론10 [Algorithm] 시간복잡도 목차시간복잡도(time complexity)시간복잡도분석을 하는이유?시간복잡도의 표현방법 시간복잡도(time complexity)컴퓨터 프로그램의 입력값과 연산 수행 시간의 상관관계를 나타내는 척도 시간복잡도분석을 하는이유? 실제 시간으로 알고리즘의 효율성을 비교하게 될경우 CPU와 같은 실제로 연산하는 컴퓨터의 성능은 다 다르고 사용하는 언어에 따른 차이가 있기 때문에 직접적으로 비교가 불가능하다.따라서 알고리즘의 시간을 비교하기 위해서 컴퓨터성능,프로그래밍 언어등등의 차이를 제외하고 객관적인 측정법이 필요하였다.일반적으로 알고리즘의 실행시간은 입력의 크기가 커질경우 증가하였고, 단위연산(basic operation)의 수행 횟수에 비례한다.따라서 단위 연산이 수행되는 횟수와 입력의 크기로 알고리즘.. 2024. 6. 16. [Algorithm] Greedy Code 모음 Greedy 설명 Greedy이란? 최소신장 트리(MST), Kruskal & Prim algorithm 다익스트라 알고리즘(Dijkstra Algorithm) Scheduling 허프만 코드 Greedy Algorithm Code github 예시 거스름돈 Greedy_EX1 거스름돈 (5만원) https://www.mycompiler.io/view/3lrVEJzCfQE Greedy_EX2 거스름돈 (7만원) https://www.mycompiler.io/view/2LVSeGMO4sR MST Greedy_Kruskal https://www.mycompiler.io/view/GXUlcogH3fs Greedy_Prim https://www.mycompiler.io/view/GjxBn54jgD9 다익스트라(.. 2024. 4. 8. [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. [Algorithm] Greedy Algorithm 목차 1. Greedy Algorithm? 2. 대표적인 Greedy 3. 코드모음 _링크_ Greedy Algorithm이란? Greedy Algorithm(이하 Greedy) 말 그대로 탐욕스럽게 현재 '가장 좋아 보이는' 답(최선의 선택)을 선택하는 알고리즘 Greedy는 DP(동적프로그래밍)을 간단한 문제 해결에도 지나치게 많은 일을 하는 문제점을 해결하고자 고안되었다. 최선의 선택은 선택할 당시에 가장 좋은 것을 선택하는 것을 의미합니다 간단하게 예시를 들면 눈앞에 12만원과 18만원이 있다면 18만원을 선택하는 것과 동일합니다. 뒤에 뭐가 있든 최선을 선택하는 것은 좋은 결과물을 보장해줄까요? 한번 예시를 들어보죠 거스름돈 예시입니다. 기존 화폐단위에서 10만원을 큰 화폐부터 거슬러 줘서 적은.. 2024. 4. 7. 3 다이나믹 프로그래밍(Dynamic Programming : DP/동적계획) 보호되어 있는 글 입니다. 2024. 4. 7. 2 정복분할(divide and conquer) 보호되어 있는 글 입니다. 2024. 3. 30. 1 Algorithm 보호되어 있는 글 입니다. 2024. 3. 30. 이전 1 다음 728x90
