728x90 IT 개인학습45 신장 트리, 크루스칼, 위상 정렬 알고리즘 신장 트리 " 하나의 그래프가 있을 때 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프 " - 모든 노드가 포함되어 서로 연결되면서 사이클이 존재하지 않는다는 조건은 트리의 성립 조건이기도 하다. - 그래프 알고리즘 문제로 자주 출제되는 문제 유형이다. 크루스칼 알고리즘, Greedy " 다양한 문제 상황에서 가능한 한 최소한의 비용으로 신장 트리를 찾아야 할 때가 있다. " 예시) N개의 도시가 존재하는 상황에서 두 도시 사이에 도로를 놓아 전체 도시가 서로 연결될 수 있게 도로를 설치하는 경우 2개의 도시 A, B를 선택했을 때, 도시 A에서 도시 B로 이동하는 경로가 반드시 존재하도록 도로를 설치하고자 한다. 모든 도시를 "연결"할 때, 최소한의 비용으로 연결하려면 어떤 알고리즘을 이용해.. 2022. 9. 20. 그래프 이론, 서로소 집합 " 여러 개의 도시가 연결되어 있다 " - 노드와 간선으로 이루어진 자료구조, 정점(Vertex)간의 관계를 표현하는 조직도 - 그래프 알고리즘을 의심해보자 - 그래프 자료구조 중에서 Tree 자료구조는 다양한 알고리즘에 사용됨 Tree 자료구조???- - 부모에서 자식으로 내려오는 계층적인 모델에 속한다. - Tree 자료구조는 노드가 N개일 때, 항상 간선의 개수가 N -1개 이다. * 크루스칼 알고리즘 Kruskal - Greedy 알고리즘 (참조) https://cord-ai.tistory.com/154 Greedy(탐욕) ' 현재 상황에서 지금 당장 좋은 것만 고르는 방법 ' ' 사전에 외우고 있지 않아도 풀 수 있을 가능성이 높은 문제 유형 ' - 최단 경로를 빠르게 찾아야 하는 문제는 플로이.. 2022. 9. 8. 이미지 및 영상 압축 방식 " 사진(이미지) = (가로 * 세로)를 가득 메우고 있는 점 Pixel들이 모여있는 것 " 사진의 한 점 한 점마다 어떤 색에 해당되는지를 색깔에 대응되는 숫자로 기록해두면 사진을 볼 때는 역으로 그 숫자들을 읽어 대응되는 색들을 한 점 한 점 화면에 표현해주는 것 RGB Color Space 원본 사진 파일은 사진을 이루는 각 점들의 정보를 RGB 각각 나누어 저장한다. R 0 - 255 (각각 256단계 1Byte = 8bits로 표현) G 0 - 255 B 0 - 255 한 점마다 24bits, 즉 3Byte가 필요한 것 예) 6936 * 9248(64,144,128 Pixel)크기의 사진이 있다면 원본 사진의 용량을 계산한다면 * 3Byte = 약 184MB 하지만 이미지 저장시 파일 크기를 보.. 2022. 9. 4. 플로이드 워셜 Floyd-Warshall 알고리즘 " 모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 경우 " - 다익스트라 알고리즘과 비교하면 구현 과정에서 어렵진 않음 - 다만, 핵심 아이디어를 이해하는 것이 중요 그래프의 정보를 2차원 행렬(배열)을 이용하여 3중 루프를 반복하여 구성된 최단 경로 알고리즘 다익스트라(Greedy) VS 플로이드 워셜(Dynaminc) https://cord-ai.tistory.com/165 최단경로 Shortest Path " 가장 짧은 경로를 찾는 알고리즘이다 " - "길 찾기" 문제라고도 불린다. - 그래프를 이용해 표현(= 각 지점은 그래프에서 " 노드 ", 지점간 연결된 도로는 그래프에서 "간선") - 최단 경로를 모두 cord-ai.tistory.com - 단계마다 최단 거리를 가지는 노.. 2022. 9. 2. 힙 Heap 자료구조 " 우선순위 Priority Queue를 구현하기 위하여 사용하는 자료구조 - Tree 자료구조 " Tree 자료구조??? - 부모에서 자식으로 내려오는 계층적인 모델에 속한다. - DFS/BFS 스택과 큐의 원리를 알아보았다. https://cord-ai.tistory.com/158 DFS / BFS , Graph Structure "Stack, Queue, Recursive Func는 DFS / BFS에서 가장 중요한 개념" https://cord-ai.tistory.com/156 Stack, Queue, Recursive Function " 그래프를 탐색하기 위한 대표적인 두 가지 알고리즘 " 탐색(Search)이란.. cord-ai.tistory.com "스택"은 가장 나중에 삽입된 데이터가 가장.. 2022. 8. 31. 최단경로 Shortest Path " 가장 짧은 경로를 찾는 알고리즘이다 " - "길 찾기" 문제라고도 불린다. - 그래프를 이용해 표현(= 각 지점은 그래프에서 " 노드 ", 지점간 연결된 도로는 그래프에서 "간선") - 최단 경로를 모두 출력하는 문제보다는 단순히 최단 거리를 출력하도록 요구하는 문제가 많이 출제 1. 한 지점에서 다른 특정 지점까지 최단 경로를 구해야 하는 경우 - 다익스트라 2. 모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 경우 - 플로이드 워셜 https://cord-ai.tistory.com/167 플로이드 워셜 Floyd-Warshall 알고리즘 " 모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 경우 " - 다익스트라 알고리즘과 비교하면 구현 과정에서 어렵진 않음 - .. 2022. 8. 31. Python 함수 주석 def function(a, b, c): """ # 주석 test 함수입니다. Args: a (str): a value b int: b value c (str): c value Retruns: None """ pass 2022. 8. 29. 다이나믹 프로그래밍(Dynamic Programming) " 중복되는 연산을 줄이자 " " 메모리 공간을 약간 더 사용하면 연산 속도를 비약적으로 증가시킬 수 있는 방법 " " 완전 탐색 알고리즘으로 접근했을 때 시간이 매우 오래 걸리면 다이나믹 프로그래밍을 적용할 수 있는지 해결하고자 하는 부분 문제들의 중복 여부를 확인해보자 " - (해결하기 어려운 문제) = 깊게 다루는 분야로는 계산 복잡도 이론이 있다. => P-NP??? 공부 추천 - 3차원 리스트를 이용해야하는 복잡한 난이도 문제 = 9장 "최단 경로" 컴퓨터를 활용해도 해결하기 어려운 문제란 무엇인가??? - 최적의 해를 구하기에 시간이 매우 많이 필요하거나 - 메모리 공간이 매우 많이 필요한 문제 등 컴퓨터는 연산 속도에 한계가 있고 메모리 공간을 사용할 수 있는 데이터의 개수도 한정적이라는 점.. 2022. 8. 28. 이전 1 2 3 4 5 6 다음
