0x.알고리즘
-
0x09.정렬 알고리즘(3):퀵 정렬0x.알고리즘 2017. 6. 16. 13:35
4.퀵 정렬(Quick Sort) 위 정렬 방법은 리스트에서 기준점이 되는 데이터를 선정한 후에, 기준보다 작은 데이터들을 왼쪽으로, 큰 데이터들을 오른쪽으로 정렬해나가는 방식으로 기준점을 기준으로 정렬이 완료가 되면 기준점의 좌우로 다시 분할하여 정렬을 하는 방식이다. 위와 같은 리스트가 있다고 가정해보자. 위의 리스트에서는 arry[4]의 데이터 값은 5가 기준(pivot)점이 된다. 파란색으로 표시된 부분을 시작으로 맨 왼쪽부분은 5보다 큰 값을 가진 값이 나올때까지 한 칸씩 오른쪽으로, 맨 오른쪽부분은 작은 값이 나올때까지 한 칸씩 왼쪽으로 이동하며 값을 비교한다. 여전히 기준값을 기준으로 조건에 맞지 않기에 계속해서 이동하며 값을 비교한다. 자 array[2]의 값은 6으로 기준값보다 크고, a..
-
0x08.정렬 알고리즘(2):쉘 정렬0x.알고리즘 2017. 6. 15. 12:22
3. 쉘 정렬(Shell Sort) Shell이라는 사람이 삽입 정렬의 장점을 활용하여 개발한 알고리즘인데 만약 배열이 어느정도 정렬이 되어있다면 효율이 좋다. 이 방식은 배열의 데이터들을 몇 개의 그룹으로 나눈 다음, 각 그룹의 같은 위치의 데이터들을 비교하여 삽입정렬하고 그룹의 크기를 줄여나가는 방식을 사용한다. 위 그림은 크기가 8인 배열의 전체적인 쉘 정렬 순서를 나타낸 것이다. 색이 같은 부분들은 같은 그룹을 뜻하고, 회색으로 표시된 칸들은 비교대상이 된다. 즉 그림의 맨 첫 배열에서는 1,5,8,3이라는 값을 가진 배열칸들이 같은 그룹을 형성하고 6,2,0,7을 뜻하는 나머지 배열칸들이 다른 그룹을 형성해 그룹의 개수가 총 2개가 된다. 두 그룹의 같은 위치에 있는 1과 6데이터를 가진 배열의..
-
0x07.정렬 알고리즘:선택, 삽입 정렬0x.알고리즘 2017. 6. 5. 21:01
정렬 알고리즘 정렬 알고리즘은 실생활에서 아주 많이 사용된다. 내부 정렬, 외부 정렬, 비교 정렬, 분배 정렬등 아주 많은 종류가 있지만 아주 간단한 것부터 시작해보자. 가장 간단한 정렬방법은 오름차순과 내림차순일 것이다. 20, 28, 3, 41, 26, 6 위와 같은 순서를 아래와 같이 정렬하는 것을 오름차순 정렬이라고 하고, 그 반대를 내림차순 정렬이라고 한다.(은근 헷갈림;;) 3, 6, 20, 26, 28, 41 아주 간단한 알고리즘이기에 아주 간단하게 구현할 수 있다. void sort(){ int i, j; for(i=1; i
-
0x06.탐색 알고리즘(4):해쉬법0x.알고리즘 2017. 3. 18. 13:29
4. 해시법 이 방식은 기존의 탐색 알고리즘들과 전혀 다르게 설계되는데, 가장 빠른 속도의 알고리즘이라고 불리기도 한다. 앞서 포스팅한 알고리즘들은 키 값의 지속적인 비교를 통해 탐색 범위를 좁히는 방식이다. 비교라는 것을 잘 생각해보면 범위를 정확히 반으로 줄일 때 가장 효율이 좋다. 하지만 범위를 모호하게 비교해버리면 생각했던 것보다 많은 시간이 소요될 수 있다는 단점이 있다. 해시법은 그 전 방식들과 다르게 직설적이다. 키 값을 1에서 10까지 한정했다고 가정해보자. 가장 빠른 탐색 방법은 1부터 10을 첨자로 하는 배열을 만들어 바로 그 값을 참조하는 것이다. 물론 한정된 범위내에서만 사용이 가능하지만, 조금만 손을 봐주면 충분히 활용할 수 있다. 해시법은 키 값을 파라미터로 사용하는데, 어떤 함..
-
0x05.탐색 알고리즘(3):이진 탐색트리0x.알고리즘 2017. 3. 4. 17:31
3. 이진 탐색트리 이진트리는 다음의 성질중 하나를 반드시 만족한다.ⓐ 자식을 갖지 않음ⓑ 왼쪽 자식 하나만 가짐ⓒ 오른쪽 자식 하나만 가짐ⓓ 왼쪽과 오른쪽 자식 모두를 가짐 이진 탐색 트리의 개념은 왼쪽과 오른쪽으로 나뉜다. 왼쪽에 있는 자식과 그 자식의 자식들이 가지고 있는 데이터들은 정점의 데이터(그림의 15)보다 값이 작고, 오른쪽에 있는 자식과 그 자식의 자식들이 가지고 있는 값들은 정점보다 크다. 말로 표현하려면 여러운데, 왼쪽의 그림으로 보면 조금 쉬울 수 있다.루트의 왼쪽 자식의 값은 루트 값인 15보다 작은 12이며, 오른쪽은 더 큰 값인 19이다. 또한 12(왼쪽 서브트리)의 자손들의 값은 9, 13, 14로 루트 값인 15보다 작다. 정점(루트)의 입장에서보면 왼쪽 서브트리의 값들은 ..
-
0x04.탐색 알고리즘(2):이진 탐색0x.알고리즘 2017. 2. 25. 13:12
2. 이진 탐색 선형탐색과 마찬가지로 이진탐색에서도 배열에 레코드를 삽입하는 방법을 사용하지만, 요소 값의 크기 순으로 삽입한다는 점이 다르다. 다시 말해, 배열의 데이터가 크기순으로 정렬된다.(아래의 배열은 데이터 값이 작은 것부터 순차대로 정렬되도록 하였다) 위 배열에서는 low에서 high까지의 요소들이 탐색 대상이 되는데, low와 high라는 변수로 범위를 지정함으로써 탐색 범위를 제한할 수 있다. 젤 먼저 low와 high사이에 위치한 정중앙 데이터값인 mid와 찾으려는 데이터의 값을 비교한다. 찾는 값이 mid보다 작다면 mid 이후의 요소들은 탐색하지 않아도 되고, 반대로 mid보다 값이 크다면 mid 이전 요소들은 탐색할 필요가 없기 때문이다. 이진탐색에서는 다음의 두 알고리즘이 사용된다..
-
0x03.탐색 알고리즘:선형 탐색0x.알고리즘 2017. 2. 21. 10:20
탐색 알고리즘 레코드(record)는 임의의 객체에 대한 정보를 나타내는 다수의 필드(field)로 구성되어 있는데, 여러 개의 레코드를 명확하게 구별할 때 사용되는 키(key) 필드도 이에 포함된다.(레코드의 구조체로는 파일(file)과 테이블(table)이 있다.) 탐색이란 어떤 키 K를 가진 레코드가 파일 상에 있는지 조사하는 절차로, 탐색을 요청할 경우에 기입하게 되는 것이 키이고, 탐색 후의 출력 결과가 레코드의 위치가 된다. 컴파일러의 경우 식별자 이름이 키가 되고, 식별자에 붙어있는 여러가지의 정보를 포함한 것이 레코드가 된다. 탐색을 하기 위해서는 키에 대한 조건을 지정해야 하는데, 다음과 같이 세부적으로 나눌 수 있다.(파일상에 존재하는 모든 레코드가 갖는 키가 각자 다르다는 전제가 필요..
-
0x02.알고리즘(3):스택&큐&트리0x.알고리즘 2017. 2. 20. 14:09
3.스택(stack) 스택은 메모리관련 개념으로 많이 접할 수 있다. 스택의 어원은 건초더미로 알려져 있는데, 농부들이 건초들을 한 곳에 모을 때 차곡차곡 쌓이는 모습과, 그것들을 사용하기 위해 위에서부터 조금씩 덜어가는 모습을 본따 지었다고 한다. 속된 말로, 빨리 들어온 놈보다 늦게 들어온 놈이 먼저 선택된다는 뜻이다. 이 성질을 유식한 말로 LIFO(Last-In-First-Out)이라고 하기도 한다. 스택은 연산 시 중간 결과를 잠시 기록할 때 주로 사용되는데, 다음은 스택이 산술식을 계산하는 과정이다. 아래에서 사용된 방식은 역 폴란드(Polish Postfix) 표기방식인데, 이는 연산자들이 자신의 피연산자들의 직후에 위치하도록 하는 방법으로, 데이터가 숫자이면 스택에 추가하고, 연산자이면 스..