전체 글

[ 알고리즘 ] 스택, 큐

스택 ( Stack ) vs 큐 ( Queue ) 스택과 큐는 자료 구조의 형태이며, 서로 상반되는 형태를 가진 자료 구조이다. 둘이 어떤 차이가 있는지 한번 살펴보도록 하자 스택 ( Stack ) 스택이란 쌓는다는 것을 의미한다. 예를 들어 책을 박스에 쌓어서 창고에 보관하려고 했는데 내가 보려고 뒀던 책을 상자에 실수로 넣었으면 넣은 순서의 반대로 하나 하나 꺼내서 책을 찾아야 할 것이다. 상자에 차곡 차곡 쌓인 책을 꺼낼때 밑에서 부터 꺼낼수 없듯이 마지막에 넣은 자료가 가장 먼저 꺼내지는 특징을 가진 구조이다. 이러한 스택의 구조는 후입선출 ( LIFO ) 구조라고 한다. 상자에 책을 쌓는, 스택에 값을 삽입하는 연산을 Push, 상자에서 책을 꺼내는, 스택에 값을 삭제하는 연산을 Pop 이라 한..

[ 알고리즘 ] 그래프, 트리

그래프 트리 방향성 방향, 무방향 방향 사이클 순환, 비순환, 자기순환(self-loop) 비순환 루트노트 루트 없음 한개의 루트 노드 부모- 자식 부모-자식 개념 없음 1:N 의 부모-자식 관계 모델 네트워크 모델 계층 모델 간선 수 자유 N-1개 그래프 그래프란 노드 ( Node ) 와 간선 ( Edge ) 를 하나로 모아둔 자료 구조로, 연결되어 있는 객체들간의 관계를 나타내는 자료 구조이다. 그래프는 다음과 같은 특징을 갖는다. 그래프는 노드 ( 정점 Vertex 라고도 함), 간선 ( Edge ) 로 이루어져 있으며 간선이 화살표인 경우에는 방향성을 띄게 된다 이를 유향 그래프라고 하고, 화살표가 없는 경우는 무향 그래프라고 한다. 간선에 특정한 수치를 가질 수 있는데 이를 가중치 ( Weigh..

[ 알고리즘 ] 이진 탐색 ( Binary Search )

이진 탐색 ( Binary Search ) 업 앤 다운이라는 게임이 있다. 이 게임의 룰은 사회자가 1~100 사이의 숫자를 정한 뒤 그 숫자를 돌아가면서 맞추는 게임으로 부른 숫자가 사회자가 부른 숫자보다 낮으면 Up, 부른 숫자가 사회자가 부르는 숫자보다 높은 숫자면 Down 이라고 해서 그 숫자를 맞추는 게임이다. 이 게임에서 가장 빠른 방법은 당연히 운빨로 한번에 맞추는거겠지만, 평균에 수렴하게 되면 가장 빠르게 답을 찾을 수 있는 방법은 절반값을 계속 불러서 답을 찾아가는 방식이다. 이런식으로 값을 찾아가는 방식이 바로 이진 탐색 방식이다. 이 방식을 사용하면 100에서 값을 찾는데 걸리는 최악의 경우 logn ( 이진 로그) 으로 6.64 정도, 아무리 최악의 상황에도 7번 안에 답을 찾을 수..