[정렬알고리즘] - 5. 퀵정렬(Quick Sort)

Study/Algorithm 2008. 12. 15. 22:46

퀵정렬은 이름만 듣기에는 정렬 알고리즘중에서 가장 빠를것 같다는 오해를 불러 일으킬 수 있다. 하지만 퀵정렬은 정렬알고리즘 가운데 가장 빠른 알고리즘은 아니다. 하지만 실용적인 속도는 보장한다. 그리고 전형적인 재귀 알고리즘이지만 비재귀로도 가능하기에 꽤나 괜찮은 알고리즘 중에 하나다.

특징적인 것은 Pivot을 두고 왼쪽은 Pivot보다 작은 데이타 오른쪽은 Pivot보다 큰 데이타 이런식으로 정렬 해나가는 알고리즘이다. 이것을 재귀적으로 수행해 나가며 최후에 분할된 데이터의 사이즈가 1이 될경우 종료된다.

퀵정렬의 구현은 아래와 같다. 참고 도서에는 피벗을 우측에 데이터로 해서 구현해 뒀는데 난 반대로 좌측에 두고 구현해 보았다.


<성능 테스트>
 데이터 갯수  수행시간
 10000  2
 20000  4


난수라서 다행히 스택 오버 플로우는 발생하지 않았다. 하지만 역순이라면 스택오버 플로우가 발생하게 된다. 이를 방지하기위해 비재귀로 바꿔줄 필요가 있다.
이는 추후에 추가를
Posted by hazeyun
,

[정렬알고리즘] - 4. 쉘 정렬(Shell Sort)

Study/Algorithm 2008. 12. 11. 21:29

쉘정렬은 삽입정렬의 취약점을 보완하고자 나온 정렬 알고리즘인데 변위를 하나 두어서 변위 간격의 요소들을 뽑아서 삽입정렬 변위를 줄이고 다시 삽입정렬.. 이렇게 해나가다 변위가 1이 되면 삽입정렬을 하고 종료한다.
이렇게 변위를 두기 때문에 삽입정렬에 루프가 두개나 더 추가된다.
하지만 여러가지 자료에는 삽입정렬보다 뛰어난 성능 이라고 설명되어있다. 그리고 돌려봤더니 왠걸 삽입정렬 보다 한참 느렸다.
.
.
한참 헤매다가 혹시나 해서 Release 버전으로 돌렸더니..
헉 삽입정렬 보다 빠르다는 사실..! 나를 당혹케 했다 ㅋ

아래는 구현이다.


<성능 테스트>
 데이터 갯수  수행 시간
 10000  492
 20000  1844

p.s. 위의 테스트는 Debug모드로 수행했기에 삽입정렬보다 느리게 측정되었다. Release모드시 0이다.
나중에 날잡아 Release로 모드 테스트 해봐야겠다.
Posted by hazeyun
,

[정렬알고리즘] - 3. 거품 정렬(Bubble Sort)

Study/Algorithm 2008. 12. 10. 11:24

커품 정렬은 배열의 인접요소를 비교하여 교환하는 방법의 알고리즘인데 이것이 마치 거품이 보글보글하는 모양이라고 해서 거품 정렬이라 한다.
공부하기로 거품정렬이 정렬알고리즘 중에서 가장 느리고 형편없는 알고리즘이다. 얼마나 느리고 형편없는지 아래 테스트 결과를 다른알고리즘과 비교해 보면 알 수 있을 것이다.

아래는 버블정렬의 구현이다.


<성능 테스트>
 데이터 갯수  수행 시간
 10000  383
 20000  1498
Posted by hazeyun
,

[정령알고리즘] - 2. 삽입정렬(Insertion Sort)

Study/Algorithm 2008. 12. 7. 23:56

삽입정렬 알고리즘은 선택정렬과 함께 가장 많이 사용되고 간단한 방법의 정렬법이다. 선택정렬이 많은 비교와 적은 교환을 수행한다면 삽입정렬은 그와 반대되게 많은 교환과 적은 비교로 수행된다.

삽입정렬은 주어진 데이터의 2번째 부터 선택하여 그 앞쪽의 데이터와 대,소를 비교하여 작다면 앞쪽의 데이터를 뒤로 보내고 삽입할 공간을 마련해두고 삽입하게 된다.

구현은 아래와 같다.


<성능 테스트>
 데이터 갯수  수행시간
 10000  125
 20000  474

Posted by hazeyun
,

[정렬알고리즘] - 1. 선택정렬(Selection Sort)

Study/Algorithm 2008. 12. 7. 00:48

선택정렬 알고리즘은 정렬알고리즘 가운데 가장 쉬운 방법으로 사람들이 일반적으로 흩어진 카드를 맞추거나 할 때 일상생활에 사용하는 방법을 알고리즘으로 그대로 옮긴 것이다.

정렬되지 않은 데이터중에 가장 작은것을 찾아 앞에두고 그나머지 것들 중에 다시 가장 작은것을 찾아 그다음에 두고 이런식으로 반복하다 보면 정렬이 완료되어 있다.

그것을 알고리즘으로 구현하면 아래와 같다.



<성능 테스트>
간단하게 timeGetTime()함수를 사용하였고, 데이터는 난수 생성 하였다.
Release모드가 아닌 Debug모드로 테스트.
 난수 갯수  시간
 10000  156
 20000  625


Posted by hazeyun
,

CRC-32

Study/Algorithm 2008. 11. 23. 23:52


CRC란 무엇일까?
위키백과를 찾아 보게 되면..

순환 중복 검사(巡環重復檢査), CRC(cyclic redundancy check)는 네트워크 등을 통하여 데이터를 전송할 때 전송된 데이터에 오류가 있는지를 확인하기 위한 체크값을 결정하는 방식을 말한다.

데이터를 전송하기 전에 주어진 데이터의 값에 따라 CRC 값을 계산하여 데이터에 붙여 전송하고, 데이터 전송이 끝난 후 받은 데이터의 값으로 다시 CRC 값을 계산하게 된다. 이어서 두 값을 비교하고, 이 두 값이 다르면 데이터 전송 과정에서 잡음 등에 의해 오류가 덧붙여 전송된 것 임을 알 수 있다.

CRC는 이진법 기반의 하드웨어에서 구현하기 쉽고, 데이터 전송 과정에서 발생하는 흔한 오류들을 검출하는 데 탁월하다. 하지만 CRC의 구조 때문에 의도적으로 주어진 CRC 값을 갖는 다른 데이터를 만들기가 쉽고, 따라서 데이터의 무결성을 검사하는 데는 사용될 수 없다. 이런 용도로는 MD5 등의 함수들이 사용된다.

정도로 설명 되있다.

CRC-32 에 사용되는 값은 0x04c11db7 이다.

구현해 보고 싶다. 빡세게 공부해서 함 해봐야겠군..ㅡ_ㅡ+

Posted by hazeyun
,

[Algorithm] - 동적 계획을 이용한 TSP구현!

Study/Algorithm 2008. 6. 12. 00:47

동적계획으로 구현을 위해서는 동적계획 부터 알고 넘어가야겠다. 동적 계획이란...
알고리즘 구현방법 중의 하나로 문제를 해결함에 있어서 기존에 계산된 결과가 있다면 그것을 사용하여 수행 시간을 단축 시키는 방법이다.
그럼 이 동적계획법을 사용하여 TSP를 구현함에 있어서의 기존에 구해진 재귀관계식 부터 살펴보자..맨땅에 헤딩 할 순 없으니깐;;;;;;ㅋ

사용자 삽입 이미지

위의 식에서 D[V1][V-{V1}] 이라는 배열이 바로 동적계획에 사용될 최소 여행 경로의 거리를 저장할 배열이다. 그리고 W[i][j]배열이 정점 i에서 j로 가는 간선의 가중치를 담을 배열이다.
위의 식을 일반화 해서 i<>1 이고 Vi가 A에 속하지 않을때라 하면 아래와 같이 된다라고 하는....

사용자 삽입 이미지

위 수식을 얻는 과정은 알고리즘 책을 봐야겠다...;
.
.
그럼 위의 주어진 재귀식을 통해 프로그램으로 승화 시켜보자~! ㅡ_ㅡ+

일단 필요한 배열들... 동적계획을 위해 계산된 결과를 저장할 이차원 배열 D[][]와 간선들의 가중치를 저장할 배열 W[][]가 있어야겠다. 그럼 여기서 문제되는게 A로 표기된 'V-{vi}' 요녀석을 어떻게 표현 할껀지가 이번 동적계획의 핵심이 되겠다.
검색을 좀 해보게되면 배열(?) 또는 리스트로 담는다는 분들도 있고, bit로 해서 표현한다는 분들도 있는데.. 난  bit로 하기로 결정!
bit로 하게 되었을때 간단히 보면 v1,v2,v3,v4가 있을 때 v1,v2가 포함되어 있다면 0011로 표시될수 있다. 흠 이렇게 하면 이해가 잘 되지 않지만 아래를 보면
 


V4

V3

V2

V1

십진수

모든 정점이 포함되지 않음

0

0

0

0

0

정점 V1이 포함

0

0

0

1

1

정점 V2가 포함

0

0

1

0

2

이렇게 표로 나타내보면 이해가 쉬울 것이다. 하지만 이방법에도 불필요한 메모리 공간을 사용한다는 문제점이 존재하고 이문제가 TSP를 해결하는데 정점의 수가 제한되게 된다.
이제 본격적으로 코드를 살표보기로 하자!

Posted by hazeyun
,

[Algorithm] -Tsp알고리즘?

Study/Algorithm 2008. 6. 5. 17:05

TSP란 Traveling Salesman Problem으로 외판원 문제로 많이 알려져있다.
wiki백과를 찾아보면
외판원 문제(Traveling salesperson problem) 또는 순회 외판원 문제는 조합 최적화 문제의 일종이다. 줄여서 TSP라고도 쓴다. 이 문제는 NP-난해에 속하며, 흔히 계산 복잡도 이론에서 해를 구하기 어려운 문제의 대표적인 예로 많이 다룬다.
라고 어렵게 적혀있다ㅡ_ㅡ;
간단히 적어보면 그래프로 설명하면 되는데 아래와 같은 그래프가 있을때 각각의 정점을 있는 간선에는 가중치가 주어져 있다. 이 그래프에서 정점 v1에서 모든 정점을 거쳐 v1으로 다시 돌아 오기까지거치 간선들의 가중치가 최소가 되도록 하는 경로를 구하는 문제다. 이렇게 적고보니 별거 아닌거 같기도ㅋ

사용자 삽입 이미지
그럼 이제 이녀석을 동적계획법, 깊이우선탐색법, 최상우선탐색으로 정복해보자!


 

Posted by hazeyun
,

[Algorithm] - 0-1Knapsack Problem & Fractional Knapsack

Study/Algorithm 2008. 5. 15. 23:14

알고리즘 과제로 0-1배낭채우기와 Fractional 배낭채우기를 구현..
일단 두 문제에 대해서 간단히 짚고 넘어 가자면 0-1배낭채우기란 배낭에 넣을 아이템을 쪼갤 수 없다. 반면 Fractional 배낭채우기란 배낭에 넣을 아이템을 쪼갤 수 있다. 이 두가지의 차이를 빼면 이후에 조건은 배낭의 아이템을 넣어 최대의 이익을 얻는 문제다.
0-1배낭채우기는 동적계획법을 이용해서 구현했고, Fractional 배낭채우기는 Greedy알고리즘을 이용해서 구현 했다. 그리고 두 알고리즘의 비교를 위해 각각의 알고리즘의 수행 속도를 결과에 포함 시켰다.
아래 실행화면...

사용자 삽입 이미지
invalid-file

파일불러오기 버튼으로 데이터가 저장된 파일을 불러와서 시작버튼으로 수행하면 된다.
입력 데이터를 만들 때 입력 데이터 형식을 맞춰 줘야되는데 입력 데이터 형식은 첫번째 줄에는 항목의 수, 두번째 줄에는 배낭의 용량, 세번째 줄에는 항목들의 이익, 네번째줄에는 항목들의 무게..
예)
3
15
10 3 20
5 8 10
이런 식으로 맞춰줘야한다.
첨부된 파일에 기본 입력데이타set 3개도 포함시켜 뒀다.
p.s. win32로 만들어서 노가다도 좀들었고, 생각보다 UI가 이쁘지 않게 나왔다. mfc를 보던지 해야지..ㅋ

Posted by hazeyun
,

티스토리툴바