알고리즘 썸네일형 리스트형 그래프(Graph)의 정의와 표현 그래프(Graph)의 정의와 표현 알고리즘에 대해 공부할 때 가장 장벽이 높다고 생각하는 부분이 바로 그래프이다.이번 글에서는 기나긴 그래프 알고리즘에 들어가기에 앞서,간단하게 그래프가 무엇인지, 어디에 사용하는지, 어떻게 사용하는지에 대해 알아보도록 하자. 그래프(Graph)란?그래프는 실제 세계의 현상이나 사물을 정점(Vertex)와 간선(Edge)으로 표현을 하기 위해 사용한다.실제 예를 들어보도록 하자. 위의 그림은 일상 생활에서 돈관계를 그래프 구조로 표현을 한 것이다. 민희는 철수에게 5000원을 갚아야 하고,철수는 영희에게 6000원,영희는 민수에게 100원,민수는 영희에게 500원 을 갚아야 하는 관계이다.이렇게 실제 세계의 현상, 즉 여기에서는 사물들 간의 관계를 그래프로 표현 할 수 있.. 더보기 이진탐색(Binary Search)와 Parametric Search 이진탐색(Binary Search)와 Parametric Search 1. 이진탐색1.1 기본 아이디어우리가 원하는 값을 찾고 싶을 때에는 정말 간단하게 생각하면, 모든 값들을 하나씩 보면서 맞는지 아닌지 확인는 방법이 직관적인 방법이라고 할 수 있다. 하지만 이렇게 찾는 것은 가장 마지막에 원하는 값이 있을 경우, 모든 값 들을 한번 씩 살펴보아야 하기 때문에, O(N)으로 볼 수 있다. 그렇다면 좀더 효율적인 방법은 없을까? 에서 시작한 것이 바로 이진탐색(Binary search)이다. 이진탐색(Binary search)의 경우는 결과적으로 보면 O(logN) 만에 원하는 값을 찾을 수 있는데, 그 이유는 정렬이 되있다는 가정이 있기 때문이다. 아래의 그림을 보면서, 왜 그러한지 직관적으로 이해를 .. 더보기 퀵소트(quick sort) 알고리즘 퀵소트(quick sort) 알고리즘 정렬 알고리즘 중 평균적으로 O(NlogN)으로 알려져 있는 Quick sort에 대해 알아보자. 1. 기본 아이디어 기본적으로 O(N^2)으로 정렬하는 알고리즘(Ex : 버블정렬)은 바꾸는 기준이 순회를 하면서 바뀌어 지면서, 일반적으로 for문의 중첩으로 O(N^2)의 복잡도를 가지게 된다. 하지만 퀵소트 알고리즘은 직관적으로 보았을 때, 비교를 반씩 줄여나가면서 해보자! 라는 생각으로 접근을 하면 이해하기 좋을 것 같다. 즉 재귀를 이용한 분할정복 알고리즘이다. 기본적인 아이디어는 상당히 쉽다. 특정한 기준을 Pivot 이라고 부르고 이 pivot을 기준으로 pivot보다 작으면 왼쪽으로, pivot보다 크면 오른쪽으로 이동한다. 기본적인 아이디어를 바탕으로 제.. 더보기 이전 1 다음
