본문 바로가기

분류 전체보기

 (79)
그래프(Graph)란? 수학에서, 더 구체적으로 그래프 이론에서, 그래프는 일부 객체들의 쌍들이 서로 연관된 객체의 집합을 이루는 구조라고 얘기한다. 컴퓨터에서의 그래프는 수학에서 객체 간에 짝을 이루는 관계를 자료구조로 모델링한 것이다. 그래프에서는 객체를 정점(Vertext) 또는 노드(Node), 점(포인트/Point) 등으로 표현하는데 보통 정점(Vertex)를 더 많이 사용하고 두개의 객체간 어떤 관계가 있는지를 나타낼 때는 에지(Edge), 간선, 링크(Link) 등으로 표현다. 따라서 객체간의 관계를 이루는 집합을 그래프 G 라고 하면 이는 버텍스 집합 V와 에지의 집합 E의 순서쌍을 G = (V, E)로 나타낼수 있다. ▲ [출처] https://www.geeksforgeeks.org/graph-data-stru..
자료구조(Data Structure)란 SW 프로그램 구현시 우리는 많은 자료들을 사용합니다. 자료들은 크게 2가지 타입으로 나뉘는데 각 언어(language) 에 내장된(built-in) 타입과 사용자가 정의한 타입이 있습니다. 이런 자료들을 선언하면 컴퓨터는 각 자료의 크기에 맞게 메모리를 할당하고 사용자는 자료에 접근 할 때 메모리에 엑세스하여 읽 고/쓰게 (R/W) 하게 됩니다. ▲ [출처] https://www.freecodecamp.org/news/these-are-the-best-free-courses-to-learn-data-structures-and-algorithms-in-depth-4d52f0d6b35a/ 문제는 이런 자료들을 메모리에 저장 할 때 중구난방으로 막 저장하게 되면 자료를 효율적 다루기가 어려워 진다. 실생활을..
그래프(Graph)-너비우선탐색(BFS, Breadth First Search) algorithm 지금까지 그래프란 무엇이고 그래프를 표현하기위한 방법으로 인접행렬과 인접리스트를 알아보았다. 이번에는 그래프의 모든 정점(노드)들을 방문하는 순회(traversal)에 대해서 알아보려고한다. 그래프의 일종인 트리에서도 이미 순회하는 방법을 알아 보았는데 pre-order, in-order, post-order, level-order 가 있었다. 그래프에서는 모든 정점들을 순회하기위한 방법은 여러가지가 있지만 대표적으로 2가지가 있는데 하나는 너비우선탐색(BFS, Breadth First Search)이고 다른 하나는 깊이우선탐색(DFS, Depth First Search)이다. △ [출처] https://neo4j.com/blog/graph-algorithms-neo4j-graph-algorithm-co..
그래프(Graph)-깊이우선탐색(DFS, Depth First Search) 그래프를 순회하기위한 방법중 너비우선탐색(BFS, Breadth First Search) 은 알아봤고 이번에는 깊이우선탐색(DFS, Depth First Search)알고리즘을 살펴보자. 깊이우선탐색(DFS, Depth First Search)은 이진트리의 전위순회(pre order)과 비슷한 개념이고 재귀나 스택(Statck)를 이용하여 알고리즘을 구현할 수 있다. △ [출처] https://www.tutorialspoint.com/data_structures_algorithms/depth_first_traversal.htm 위에서 주어진 예제에서와 같이 DFS 알고리즘은 S에서 A에서 D로 G에서 E에서 B로, F에서 마지막으로 C로 이동한다. DFS를 스택를 이용하여 구현할 수 있다고 하였는데 코드..
최소신장트리(Minimum Spanning Tree)-크러스컬(Kruskal) 알고리즘 최소신장트리를 생성하기위한 알고리즘으로 크러스컬 알고리즘을 설명한다. 만약 최소신장트리가 무엇인지 모른다면 최소신장트리(Minimum Spanning Tree) 를 먼저 학습해야한다. Q. 크러스컬 알고리즘은 무엇인가 ? 크러스컬 알고리즘은 최소신장트리를 생성하기위한 알고리즘 중하나로 핵심은 모든 그래프 G 에 연결된 모든 에지들의 가중치를 오름차순으로 정렬하고 에지 중 가장 작은 것부터 하나씩 이어 나가는 방법이다. 주의 할 점은 이어 붙일 때 그래프에 사이클이 생기지 않도록 해야(신장트리가 되려면 사이클이 없다고 얘기했다.) 한다는것이다. 그림으로 설명하면... STEP (a) 그래프에서 에지의 가중치가 가장 작은 E = (h,g)를 젤 먼저 선택한다. 이어서 가중치가 낮은 순서대로 하나씩 선택해 나..
최소신장트리(Minimum Spanning Tree) 최소신장트리란? 하나씩 분해하면서 살펴보자. Q. 신장트리란 ? 그래프는 각 정점과 정점간 연결된 에지의 집합임. G=(V,G). 그런 그래프중 모든 정점을 포함하고 & 정점간 서로 연결(connected)되어 있고 & 사이클(cycle)이 없는 그래프를 말한다. 트리자료구조가 바로 이 조건에 성립하고 그래서 신장트리라고 함. 그림2 에서 (a)는 무방향 그래프인이고 모든 정점간 연결되어 있으나 사이클(a-b-c, b-c-d등등)이 존재해서 신장트리가 아니다. (b), (c), (d) 는 모든 정점을 포함하고 & 정점이 서로 연결되어 있고 & 사이클이 하나도 없으니 신장트리라고 할 수 있음. 따라서 신장트리는 그래프의 부분그래프(subgraph) 라고 볼 수 있고 모든 신장트리는 정점 V 가 N개 라면 ..
멱집합(Power Set) A의 모든 부분집합을 원소로 하는 집합을 A의 멱집합(power set)이라 하고 P(A) 또는 2A로 나타낸다. 예를들어 S = { 1 , 2, 3, 4 } 일때 부분집합(power set) = {{}, {1}, {2}, {1,2}, {3}, {1,3}, {2,3}, {1,2,3}, {4}, {1,4}, {2,4}, {1,2,4}, {3,4}, {1,3,4}, {2,3,4}, {1,2,3,4}} 이다. 따라서 임의의 유한집합에 대해서 그 크기가 |A| = n 이라고 할때, 부분집합의 개수는 2n 개가 된다. 그럼 컴퓨터에서 임의의 집합의 모든 부분집합을 출력하는 알고리즘은 어떻게 될까? 사실 생각해보면 { a, b, c, d, e, f } 의 모든 부분집합을 나열하려면 a 를 제외한 { b, c, d,..
분할정복(Divide & Conquer) 알고리즘이란? 분할정복 알고리즘(Divide and Conquer Algorithm)이란 해결하고자 하는 문제(Problem)를 통째로 놓고 푸는 것이 아니고 문제를 작은 크기의 동일한 문제들(Problems)로 분할해서 각각의 작은 문제를 순환적으로 해결하는 방법을 말한다. ▲ [출처] https://medium.com/cracking-the-data-science-interview/divide-and-conquer-algorithms-b135681d08fc 분할정복에 대한 유례는 1805년 12월 2일 아우스터리츠 전투에서 프랑스의 황제 나폴레옹이 사용했던 훌륭한 전략에서 따왔다고 한다. 오스트리아-러시아 연합군은 나폴레옹의 군대보다 15,000명 정도 많았다. 연합군은 프랑스군의 우측면에 대규모 공격을 감행했다...

티스토리툴바