퀵정렬은 분할정복(Divide-Conquer)기법을 이용하여 데이터를 정렬하는 정렬 알고리즘이다.분할정복이란 해결해야 할 부분을 분할하여 문제를 해결하는 방법이다. 퀵정렬은 기준이 되는 pivot을 설정하여 pivot을 기준으로 작은 값은 왼쪽으로 큰 값은 오른쪽으로 이동하여 원소를 정렬한다.pivot의 왼쪽에는 pivot보다 작은 값이 와야하고 pivot의 오른쪽에는 pivot보다 큰 값이 와야 한다. 그래서 Left와 Right를 통해 반대쪽으로 날려보낼 값을 찾을 것이다.또한 Left와 Right가 만나는 지점은 Pivot과 swap이 되는 자리이고 교체된 자리가 기존 pivot값의 올바른 위치가 된다. pivot을 설정하는 방법은 유일하지 않지만 여기선 가운데 위치를 pivot으로 잡았다. 초기상..

이진탐색트리는 이름에서 알 수 있듯이 자식노드를 최대 2개까지만 가지는 이진트리의 특성을 가지고 있으며 다음과 같은 조건을 만족한다. 1. 어떤 노드 V를 기준으로 왼쪽 서브트리의 모든 키값은 V보다 작아야 한다.2. 어떤 노드 V를 기준으로 오른쪽 서브트리의 모든 키값은 V보다 커야 한다.3. 각 노드의 키값은 유일해야 한다. 아래 트리는 이진탐색트리의 모든 조건을 만족한다. 이진탐색트리를 중위순회로 방문하면 오름차순으로 정렬된 값을 얻을 수 있다.1, 2, 4, 6, 8, 9 탐색이진탐색트리는 그 이름에 '탐색'이 있듯 탐색이 효율적이다. 위의 이진탐색트리에서 8을 탐색해보자우선 루트노드 6을 8과 비교했을 때 8은 6의 오른쪽 서브트리에 존재할 것이기 때문에 왼쪽 서브트리는 탐색할 필요가 없다.다음..

힙 정렬은 max-heap 또는 min-heap 자료구조를 이용하여 데이터를 효율적으로 정렬하는 정렬 알고리즘이다. 힙 정렬을 하기 전에 힙의 개념에 대해 간단히 살펴보자 힙(Heap)1. 힙은 완전이진트리 구조를 갖는다.2. 힙은 max-heap, min-heap 둘 중 하나의 특성을 가져야 한다. 완전이진트리를 배열로 구현 시 인덱스를 통해 부모 자식 노드에 바로 접근할 수 있다는 장점이 있다. 여기서 인덱스 0은 사용하지 않는다고 가정한다.자신의 인덱스 i를 기준으로 왼쪽 자식노드의 인덱스는 i * 2, 오른쪽 자식노드의 인덱스는 (i*2)+1을 통해 바로 접근할 수 있다. 또한 자신의 부모노드는 i/2로 바로 접근할 수 있다. 위의 트리는 완전이진트리의 조건을 만족하지만 max-heap이나 min..

선택정렬(Selection-sort)선택정렬은 오름차순, 내림차순 정렬에 따라 가장 작은 값, 가장 큰 값을 선택한 뒤 맨 앞의 위치부터 차례대로 비교하여 정렬하는 방식이다.정렬되지 않은 수 전체를 차례대로 비교하여 가장 작은 값을 찾고 이 값과 가장 첫번째 위치를 교환한다. 이러면 가장 첫번째 위치는 정렬이 된 것이다.그리고 정렬되지 않은 부분에서 다시 가장 작은 값을 찾고 정렬되지 않은 부분의 첫번째 위치와 비교하여 교환한다.이런 과정을 거쳐 정렬되지 않은 모든 부분을 정렬될 때까지 반복하는 것이다. 7, 3, 9, 4, 5, 1를 선택정렬로 오름차순 정렬해보자우선 전체 중 가장 작은 값인 1을 찾는다. 1을 가장 첫번째에 있는 7(인덱스 0)과 비교하여 더 작다면 위치를 바꿔준다.1, 3, 9, 4..

우선순위 큐는 key, value로 이루어진 pair를 저장하는 비선형 자료구조이다.여기서 key는 데이터의 priority를 뜻한다. 스택은 가장 최근에 들어온 데이터, 큐는 가장 먼저 들어온 데이터가 삭제되지만우선순위 큐는 삽입된 순서와 상관없이 우선순위가 높은 데이터가 먼저 삭제된다.따라서 우선순위 큐에는 정렬이 필요하다. 우선순위 큐를 구현하는 방법은 배열, 링크드리스트, 힙을 이용하여 구현한다. 배열배열을 이용하여 구현시 삽입되는 위치를 찾아야 하기 때문에 기존에 저장된 데이터와 우선순위를 비교해주어야 하는 문제점이 생기고 최악의 경우에 기존에 있는 모든 데이터와 비교해야 할 수도 있다.또한 삽입, 삭제 시 기존의 데이터를 밀고 당기는 연산을 계속해야 하는 추가적인 문제가 생긴다. 링크드리스트링..

컨테이너의 여러 종류 중 데이터를 선형적으로 저장하는 시퀀스 컨테이너 벡터, 리스트, 덱에 대해 살펴보자 벡터(Vector)배열과 마찬가지로 연속적인 메모리 공간을 사용한다. 따라서 iterator뿐만 아니라 인덱스로 접근이 가능하기 인덱스를 통한 랜덤 액세스가 빠르다. 또한 배열과 다르게 동적으로 확장이나 축소가 가능하기 때문에 배열에 비해 가변적인 특성을 가지고 있다. 벡터는 뒤에서 데이터를 삽입/삭제 할 때만 효율적이다. push_back(), pop_back() 함수를 사용하며 맨 뒤에서 삽입하거나 삭제하면 그 이후 더 이상 할 일이 없기 때문이다. 그러나 맨 앞이나 중간에서 삽입/삭제가 이루어지면 기존 원소들의 이동이 필요하기 때문에 비효율적이다. 그래서 push_front(), pop_fron..

선형 자료구조인 스택과 큐의 개념 및 특징을 이해하고 배열과 링크드리스트로 구현 시 어떤 장단점이 있는지 알아보자여기서 선형구조란 데이터가 순차적으로 나열되어 있는 구조를 뜻한다. 스택(Stack)스택은 데이터의 삽입 삭제가 한 쪽에서 이루어지는 후입선출(Last In First Out) 자료구조이다.따라서 가장 최근에 들어온 데이터의 위치를 뜻하는 Top을 유지해야 한다.Push(), Pop()으로 삽입 삭제가 이루어진다. 배열과 링크드리스트로 구현할 수 있다.배열로 구현시 스택의 크기가 정해지기 때문에 스택 용량을 초과하는 삽입연산이 이루어질 수 없어서 비효율적이다.이러한 문제는 링크드리스트로 해결할 수 있다. 데이터가 삽입될 때마다 tail에 연결시켜주고 tail을 업데이트 해서 Top을 뜻하게 하..