반응형 알고리즘/이론6 그래프(Graph)의 정의와 표현 그래프(Graph)의 정의와 표현 알고리즘에 대해 공부할 때 가장 장벽이 높다고 생각하는 부분이 바로 그래프이다.이번 글에서는 기나긴 그래프 알고리즘에 들어가기에 앞서,간단하게 그래프가 무엇인지, 어디에 사용하는지, 어떻게 사용하는지에 대해 알아보도록 하자. 그래프(Graph)란?그래프는 실제 세계의 현상이나 사물을 정점(Vertex)와 간선(Edge)으로 표현을 하기 위해 사용한다.실제 예를 들어보도록 하자. 위의 그림은 일상 생활에서 돈관계를 그래프 구조로 표현을 한 것이다. 민희는 철수에게 5000원을 갚아야 하고,철수는 영희에게 6000원,영희는 민수에게 100원,민수는 영희에게 500원 을 갚아야 하는 관계이다.이렇게 실제 세계의 현상, 즉 여기에서는 사물들 간의 관계를 그래프로 표현 할 수 있.. 2016. 9. 19. max-heap, min-heap - 이진트리의 활용 heap - 이진트리의 활용 실제로 상당히 유용하게 쓰이는 heap에 대해서 알아보도록 하자. heap이란 이진트리를 활용한 상당히 재밌는 구조이다. 주로 max-heap, min-heap으로 가장 큰값 또는 가장 작은 값을 빠르게 찾기 위해서 사용이된다.min, max 뿐만 아니라 원하는 조건대로 compare을 하면 가장 원하는 값을 빠른시간에 뽑아낼 수 있다. 아직 설명하기 전이지만 , sort를 한 후에 골라내는게 더 빠르지 않냐 라는 생각을 할 수 도있다.이 heap의 장점이라면, 삽입, 삭제를 했을 때 추가적인 sort가 필요없다는 것이다.이 정도로 서론을 끝내고 직접 적으로 heap에 대해서 알아보자. 1. heap?heap이란 최대값 또는 최소값을 빠르게 찾기위해서 고안된 트리모양의 자료구.. 2016. 9. 14. 이진트리(Binary Tree) - 트리(Tree)의 기초 이진트리(Binary tree) - 트리(Tree)의 기초 알고리즘과 자료구조를 공부를 하다 보면 후반부에서 스슬 어려워 지기 시작하는 부분이 바로 Tree이다. 트리의 종류도 이진트리, AVL트리, 레드블랙트리, 세그먼트 트리 등등 여러가지 트리의 종류가 있다. 이번 글에서는 트리의 기초 중 가장 간단하고 실제 많이 사용하는 이진트리에서 대해 알아보자. 본격적으로 이진트리에 대해서 살펴보기에 앞서, 간단하게 트리의 관련 용어부터 정리하고 시작하겠다. 0. 트리 용어 정리 그림에 중요한 용어들을 대충 정리를 해 보았다. 하나씩 설명을 하자면, 트리의 요소 하나 하나를 나타내는 동그라미를 노드(node)라고 한다. 트리는 이 노드들 끼리 부모와 자식의 관계를 형성을 하게 된다.그 중 부모노드의 부모노드의 .. 2016. 9. 13. 이진탐색(Binary Search)와 Parametric Search 이진탐색(Binary Search)와 Parametric Search 1. 이진탐색1.1 기본 아이디어우리가 원하는 값을 찾고 싶을 때에는 정말 간단하게 생각하면, 모든 값들을 하나씩 보면서 맞는지 아닌지 확인는 방법이 직관적인 방법이라고 할 수 있다. 하지만 이렇게 찾는 것은 가장 마지막에 원하는 값이 있을 경우, 모든 값 들을 한번 씩 살펴보아야 하기 때문에, O(N)으로 볼 수 있다. 그렇다면 좀더 효율적인 방법은 없을까? 에서 시작한 것이 바로 이진탐색(Binary search)이다. 이진탐색(Binary search)의 경우는 결과적으로 보면 O(logN) 만에 원하는 값을 찾을 수 있는데, 그 이유는 정렬이 되있다는 가정이 있기 때문이다. 아래의 그림을 보면서, 왜 그러한지 직관적으로 이해를 .. 2016. 9. 13. 퀵소트(quick sort) 알고리즘 퀵소트(quick sort) 알고리즘 정렬 알고리즘 중 평균적으로 O(NlogN)으로 알려져 있는 Quick sort에 대해 알아보자. 1. 기본 아이디어 기본적으로 O(N^2)으로 정렬하는 알고리즘(Ex : 버블정렬)은 바꾸는 기준이 순회를 하면서 바뀌어 지면서, 일반적으로 for문의 중첩으로 O(N^2)의 복잡도를 가지게 된다. 하지만 퀵소트 알고리즘은 직관적으로 보았을 때, 비교를 반씩 줄여나가면서 해보자! 라는 생각으로 접근을 하면 이해하기 좋을 것 같다. 즉 재귀를 이용한 분할정복 알고리즘이다. 기본적인 아이디어는 상당히 쉽다. 특정한 기준을 Pivot 이라고 부르고 이 pivot을 기준으로 pivot보다 작으면 왼쪽으로, pivot보다 크면 오른쪽으로 이동한다. 기본적인 아이디어를 바탕으로 제.. 2016. 9. 8. 네트워크플로우(Network flow) - 포드 풀커슨(Ford-Fulkerson) 알고리즘 네트워크 플로우란(Network flow)?그래프의 경로의 길이가 아닌, ‘용량’의 관점에서 바라보는 시점.Ex) 인터넷으로 영화를 다운받고 있는데 파일 원격지에서 얼마나 빨리 받을 수 있는지를 알고 싶다. 각 컴퓨터의 네트워크 장비는 대역폭의 제한이 있다. 따라서 가장 짧은 거리로 오는 것보다. 대역폭이 큰 쪽으로 오는 것이 더 유리하다. 위의 그림의 예에서 가중치는 비용이 아니라, 대역폭, 즉 유량이다.A->B->E 의 경로에서는 최대 1의 데이터를 보낼 수 있는 반면에, A->C->D->E의 경로는 한 정점을 더 지나가게 되지만 한번에 100의 데이터를 보낼 수 있다.용어 - Source – 네트워크의 시작(A), Sink – 네트워크의 도착지(E)- 정점 a에서 b로가는 용량 – c(a,b)- a.. 2016. 7. 28. 이전 1 다음 반응형
