이동식 저장소

Graph 그래프란 하나 이상의 정점이 0개 이상의 간선으로 이어진 것을 말한다. 간선은 양방향일 수도, 단방향일 수도 있다. 간선이 단방향이라면 간선을 통해 한쪽 방향으로만 이동할 수 있으며, 반대로는 이동할 수 없다. 간선에는 가중치가 있을 수도 있다. 일반적으로 가중치란 간선을 지나가는 비용 또는 정점 간의 거리를 의미한다. 그래프와 관련된 알고리즘으로는 최단 거리 알고리즘과 SCC 등이 있다. Tree 생각해 보니 Heap보다 Tree를 먼저 정리해야 했는데... 뭐 어쩔 수 없지. 사이클이 없는 그래프를 Tree라고 부른다. 사이클이란 정점에서 출발하여 서로 다른 간선을 지나 자기 자신으로 돌아오는 경로이다. 트리의 맨 위에 있는 노드를 루트 노드라고 한다. 반대로 맨 밑에 있는 노드를 리프 노..

Array 배열은 같은 타입의 자료 여러 개를 일직선으로 저장하는 자료구조이다. 메모리 공간에도 연속적으로 저장되는 특성 때문에 대량의 비트 연산을 쉽게 수행할 수 있다. 모든 자료가 연속적으로 저장되므로, 첫 번째 원소의 주소만 알면 상수 시간에 모든 원소에 접근할 수 있다. 그러나 (맨 뒤에 삽입하는 경우를 제외하면) 삽입과 삭제 연산을 처리하는 데 선형 시간이 걸린다. 삽입 또는 삭제하는 위치 뒤에 있는 요소들을 뒤로 밀거나(삽입) 앞으로 당겨와야(삭제) 하기 때문이다. 배열이 꽉 찼다면 메모리를 추가로 할당받아야 한다. 운이 나쁘다면 아예 다른 위치로 값을 옮겨야 할 수도 있다. LinkedList 값을 연속해서 저장하지 않고, 다음 값의 주소만을 가리키는 방식으로 저장한다. 메모리 상에 연속해서..

$N$개의 수를 오름차순으로 정렬하는 알고리즘에 대해 알아보자. 내림차순이나 커스텀 정렬은 비교하는 기준만 바꾸면 된다. 버블 정렬 버블 정렬은 인접한 두 수를 비교하며 정렬하는 알고리즘이다. 다음을 반복한다. 첫 원소부터 시작하여 인접한 두 개의 원소를 비교한다. 앞의 원소가 뒤의 원소보다 크다면 두 원소의 위치를 바꾼다. 같은 방법으로 총 $N-1$번의 비교를 수행한다. 이렇게 하면 가장 큰 수를 맨 뒤로 보낼 수 있다. 모든 수가 정렬될 때까지 1~3번을 반복한다. 위의 시행을 한 번 시행할 때마다 수를 하나씩 정렬할 수 있다. 구체적으로 $i$번째 시행에서 $i$번째로 큰 수가 정렬된다. 따라서 위의 시행을 최대 $N$번 반복하면 배열을 정렬할 수 있다. 이름이 버블 정렬인 이유는 정렬되는 과정이..