선택정렬(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을 뜻하게 하..