본문 바로가기

□ 이론

 (26)
합병 정렬 (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는 정렬해야 할 데이터의 최대 자리 수를 말한다. 빠른 속도로 정렬이 가능하나, 데이터를 분류해서 저장하는 데 필요한 공간이 더 필요하다는 단점이 있다. 같은 데이터 값이더라도 그 순서가 뒤바뀌지 않는 안정 정렬이다.
힙(Heap) ▶힙(Heap)우선순위가 가장 높은 키에 접근이 빈번한 경우 사용되는 자료구조이다. 힙은 반드시 아래의 두 가지 속성을 만족해야 한다. 1. 완전 이진트리(Complete binary tree) 형태이다. (노드들이 왼쪽부터 빠짐없이 채워져 있어야 함, 가득 차지 않아도 됨) 2. 각 노드의 값은 자신의 자식 노드들의 값보다 크거나 같다. (OR 작거나 같다.) ▶Heapifyheap 자료구조의 속성이 깨졌을 때 이를 만족시키기 위해 수행하는 연산. 위에서 아래로 혹은 아래에서 위로 수행할 수 있다. (삽입시 수행) O(logN)의 시간이 걸린다. 아래에서 위로 수행하는 경우 해당 노드의 키가 부모 노드보다 크거나 같은지(OR 작거나 같은지)를 확인하여 결과가 true인 경우 키 값을 swap하고, 위에..
연결 리스트와 배열 (Linked list) ▶연결 리스트종류는 단일/이중/원형 연결 리스트가 있다. 데이터를 가진 노드를 포인터로 연결해 놓은 자료구조이다.연결리스트는 데이터의 추가/삭제가 O(1)의 시간에 가능하다는 장점이 있지만 (다음 노드의 주소만 변경해주면 됨)배열과는 달리 특정 위치의 데이터 찾기가 최악의 경우 O(N)의 시간이 걸린다는 단점이 있다.(가장 앞이나 뒤에 있는 노드부터 포인터를 하나씩 이동해가며 데이터를 찾아야함) ▶배열번호(인덱스)와 번호에 대응하는 데이터들로 이루어진 자료구조로, 같은 종류의 데이터들을 순차적으로 저장한 것을 말한다.특정 위치의 데이터에 접근하는 것이 O(1)의 시간에 가능하다는 장점이 있지만 (인덱스로 데이터에 바로 접근)데이터 추가/삭제가 최악의 경우 O(N)의 시간이 걸린다는 단점이 있다.(데이터를..
데이터베이스란? ▶데이터베이스의 정의 어느 한 조직에서 업무 처리를 위해 다수의 사용자들이 공용으로 사용하는 통합/저장된 운영 데이터의 집합을 말한다. 쉽게 말하면, 데이터의 중복을 최소화하고 여러 사용자들이 공유할 수 있도록 저장되어 조직을 운영하는데 사용되는 데이터의 집합이라고 할 수 있다. ▶데이터베이스의 특징 실시간으로 데이터가 검색/삽입/갱신/삭제될 수 있으며, 여러 사용자가 동시에 접근하여 이용할 수 있고, 데이터 중복을 최소화하여 관리한다. 또한, 데이터 검색 시 요구받은 데이터 내용으로 검색하게 된다는 특징이 있다. 1. 계속적인 변화 2. 동시 공유3. 실시간 접근성4. 내용에 의한 참조5. 데이터 중복의 최소화 ▶데이터베이스의 구성 요소- 개체(Entity) : 실세계에 존재하는 (서로 구별되는)유형 ..

티스토리툴바