본문 바로가기

분류 전체보기

 (126)
삽입 정렬(Insertion sort) ▶삽입 정렬 (Insertion sort)앞에서부터 정렬될 하나의 데이터를 왼쪽으로 비교하며 swap해서 제 자리를 찾아가도록 정렬시키는 방법이다. 정렬될 데이터가 처음부터 제 위치에 있다면 바로 다음 데이터를 확인하게 되므로, 배열에 데이터가 대부분 정렬되어 있는 경우라면 삽입 정렬이 유리하다. 하지만 데이터가 정렬되어 있어야 하고 삽입/삭제가 빈번한 경우 처음부터 set/map에 데이터를 저장하여 사용하는 게 더 효율적이다. int arr[7] = {5,2,7,4,3,6,1}; 이런 배열이 선언되어있고, 이 배열의 원소들을 정렬한다고 해보자. 이해를 돕기 위해 표를 그려보았다. N개의 원소를 순서대로 확인하면서 바로 앞에 자신보다 큰 원소가 있다면 자리를 바꾸는데, 자신의 앞에 자신과 같거나 작은 원..
합병 정렬 (Merge sort) ▶합병 정렬 (Merge sort)분할 정복 기법으로 데이터를 정렬하는 방법이다. 가장 많이 쓰이는 정렬 기법이며, 크기 N의 데이터를 정렬해야하는 경우 N만큼의 공간이 더 필요하다. 데이터를 딱 한 번만 훑어서 정렬하기 위해서, 배열 arr의 데이터를 정렬하여 배열 tmp에 저장한 뒤 정렬되어있는 tmp의 데이터를 다시 arr에 반영하는 방법을 쓰기 때문이다. 1. 정렬할 N개의 데이터에 대해 범위를 계속해서 반으로 나눈다. (나뉘어진 범위의 데이터들을 덩어리 라고 표현하겠다.) 2. 덩어리의 크기가 1일 때부터 덩어리를 정렬하면서 합친다. 3. 그러면 크기 2의 정렬된 덩어리 하나가 만들어지게 되고, 그 덩어리는 또 다른 데이터 덩어리와 정렬하면서 합친다. 4. 그렇게 합쳐진 덩어리의 크기가 N이 될..
퀵 정렬(Quick sort) ▶퀵 정렬분할 정복 기법(Divide and conquer)으로 데이터를 정렬하는 방법이다. 1. pivot 값을 정하고 그 값보다 작거나 같은 데이터는 왼쪽으로, 큰 데이터는 오른쪽으로 이동시킨다. (정복) 2. 더이상 이동시킬 데이터가 없다면 pivot 위치 기준으로 왼쪽/오른쪽으로 분할하여 재귀적으로 수행한다. (분할)재귀호출될 함수는 매개변수로 left, right를 가지고, left는 정복해야할 범위의 시작지점, right는 끝 지점을 의미한다. 인자 값으로 left와 pivot-1을 넘겨 [left, pivot-1] 범위에 대해 퀵 정렬을 재귀적으로 수행하고 인자 값으로 pivot+1과 right를 넘겨 [pivot+1, right] 범위에 대해 퀵 정렬을 재귀적으로 수행한다. 탈출 조건인 l..
프림(Prim)과 크루스칼(Kruskal) 알고리즘 ▶신장 트리 (Spanning Tree) 그래프의 모든 정점을 연결한 Tree를 말한다. 하나의 그래프에서 신장 트리는 여러 형태가 나올 수 있다. ▶최소 신장 트리 (MST : Minimum Spanning Tree) 다음과 같은 조건을 만족하는 신장 트리를 말한다.1. 간선의 가중치 합이 최소이다.2. 사이클이 존재하지 않는다.3. 모든 정점이 연결되어야 한다. (N개의 정점은 N-1개의 간선으로 연결됨)하나의 그래프에서 MST도 역시 여러 형태가 나올 수 있다. MST를 구하는 대표적인 알고리즘으로 프림 알고리즘과 크루스칼 알고리즘이 있다. ▶프림 알고리즘 (Prim algorithm) 시작 정점을 기준으로 가중치가 가장 작은 간선과 연결된 정점을 선택하며 트리를 확장시켜나가는 방법이다.트리 집합에..
계수 정렬(Counting sort) ▶계수 정렬(Counting sort)정렬할 데이터의 개수를 카운트하여 정렬하는 방법이다.O(N+k)의 시간이 걸리며, k는 정렬할 데이터의 최대 값을 의미한다.양의 정수이면서 k값이 작은 경우 활용하기 좋은 정렬 방법이다. 정렬할 데이터가 6,4,3,1,6,5,1,4,5라면 크기 7의 배열이 필요하다.정렬할 데이터를 처음부터 끝까지 보면서 해당 숫자의 개수를 구하고, 그 값을 누적 합으로 바꾸어 정렬에 활용한다. 좀 더 자세히 살펴보자.정렬해야 할 데이터가 6,4,3,1,6,5,1,4,5인 경우 배열에는 아래와 같이 저장된다. [해당 숫자의 개수][0] [1] [2] [3] [4] [5] [6] 0 2 0 1 2 2 2 이 값을 누적 합으로 바꾼다. [숫자 개수의 누적 합][0][1][2][3][4][..
기수 정렬(Radix sort) ▶기수 정렬 (Radix sort)자리 수가 존재하는 데이터들의 경우 적용 가능한 방법이다. (안정 정렬이 보장됨)e.g) OO자리 양의 정수, 문자열 가장 큰 자리수 혹은 작은 자리 수부터 선입 선출 방식의 자료구조에 분류해서 저장한 뒤, 해당 자리의 숫자가 작은 것부터 데이터를 꺼내 정렬하는 과정을 더 이상 크거나 작은 자리 수가 존재하지 않을 때까지 반복하여 정렬을 완료한다. 정렬에 O(dN)의 시간이 걸리며, d는 정렬해야 할 데이터의 최대 자리 수를 말한다. 빠른 속도로 정렬이 가능하나, 데이터를 분류해서 저장하는 데 필요한 공간이 더 필요하다는 단점이 있다. 같은 데이터 값이더라도 그 순서가 뒤바뀌지 않는 안정 정렬이다.
상호배제와 동기화 ▶상호배제병행 프로세스에서 프로세스 하나가 공유 자원을 사용할 때 다른 프로세스들이 동일한 일을 할 수 없도록 하는 방법이다.소프트웨어로 해결 : 데커의 알고리즘소프트웨어 제공(프로그래밍 언어와 운영체제 수준에서 제공) : 세마포, 모니터하드웨어로 해결 : TestAndSet ▶동기화공유 자원을 동시에 사용하지 못하게 실행을 제어하는 방법을 말한다.동기화는 순차적으로 재사용 가능한 자원을 공유하려고 상호작용하는 프로세스 사이에서 나타난다.동기화로 상호배제를 보장할 수는 있지만, 이 과정에서 교착 상태와 기아 상태가 발생할 수 있다. 임계 자원(critical resource) : 두 프로세스가 동시에 사용할 수 없는 공유 자원임계 영역(critical section) : 임계 자원에 접근하고 실행하는 프..
힙(Heap) ▶힙(Heap)우선순위가 가장 높은 키에 접근이 빈번한 경우 사용되는 자료구조이다. 힙은 반드시 아래의 두 가지 속성을 만족해야 한다. 1. 완전 이진트리(Complete binary tree) 형태이다. (노드들이 왼쪽부터 빠짐없이 채워져 있어야 함, 가득 차지 않아도 됨) 2. 각 노드의 값은 자신의 자식 노드들의 값보다 크거나 같다. (OR 작거나 같다.) ▶Heapifyheap 자료구조의 속성이 깨졌을 때 이를 만족시키기 위해 수행하는 연산. 위에서 아래로 혹은 아래에서 위로 수행할 수 있다. (삽입시 수행) O(logN)의 시간이 걸린다. 아래에서 위로 수행하는 경우 해당 노드의 키가 부모 노드보다 크거나 같은지(OR 작거나 같은지)를 확인하여 결과가 true인 경우 키 값을 swap하고, 위에..

티스토리툴바