728x90 메모장171 그래프 이론, 서로소 집합 " 여러 개의 도시가 연결되어 있다 " - 노드와 간선으로 이루어진 자료구조, 정점(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. 이진 탐색 Binary Search " 범위를 반씩 좁혀가는 탐색 " 순차 탐색 Sequential Search - 리스트 내에서 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 매우 빠르게 탐색하는 이진 탐색 알고리즘 - 예시) Greedy '거스름돈' 문제에서 가장 큰 화폐 단위부터 확인(탐색)해서 각 단위에 대하여 처리한 것 - 리스트 내에 데이터가 아무리 많아도 시간만 충분하다면 항상 원하는 원소(데이터)를 찾을 수 있다는 장점 - 데이터의 개수가 N개일 때 최대 N번의 비교 연산이 필요하므로 최악의 경우 시간복잡도 O(N) - 리스트에 특정 값의 원소가 있는지 체크할 때 순차 탐색으로 원소를 확인하고, 리스트 자료형에서 특정한 값을 가지는 원소의 개수를 세는 count() 메서드를 이용할 때에도 내부에서는 순차 탐색이 수행됨.. 2022. 8. 24. 이전 1 2 3 4 5 6 ··· 22 다음
