'알고리즘'에 해당되는 글 6건

  1. 2011.06.10 생각하는 프로그래밍
  2. 2011.05.30 quick sort - c
  3. 2011.05.28 insertion sort - c
  4. 2011.05.26 insertion sort - Java
  5. 2011.05.12 반전 알고리즘
즐길거리/책2011. 6. 10. 21:33

생각하는 프로그래밍


정말 대단한 책이다. 단순히 검색 알고리즘이 이렇고, 정렬 알고리즘이 이렇다 라는 설명따윈 하지 않는다.

이 책을 읽고 나서 얻은 가장 큰 교훈은 바로 "알고리즘이란 문제해결 능력"이라는 사실이다. 주변의 컴공 학부생들은 알고리즘하면 정렬과 탐색을 가장 많이 떠올리며 질색하곤 한다. 하지만 이 책에서는 한번도 정렬과 탐색을 강조한 적이 없다. 다만 문제 해결을 하는 과정에서 자연스레 녹아들곤 한다. 그로 인해 이 책에서는 여러 조건이 걸려있는 문제에서 효과적인 방법으로 해결하는 여러가지 방법을 보여준다. 이 책을 읽으면서 기초체력을 튼튼히 했다는 뿌듯함이 가장 컸다. 이건 마치 스파링에 임하기 전에 다양한 기본 기술을 체득하고 링위에 오르는 것과 똑같다고 본다.  

이 책을 읽기 전과 후의 가장 큰 차이점은 밑천을 좀 얻었다는 사실이다. 다양한 문제를 해결하는 방법을 보여줌으로써 좋은 알고리즘에 대한 감을 높여주었다. 역시나 최적화란 항상 로우레벨을 빼놓을 수 없다는 사실을 깨달았다. 그래서 다시 c언어 공부를 하고 있다. 메모리를 접근하는 감이 더 필요하다고 생각한다. 책을 읽다가 종종 학부시간에 재밌게 들었던 컴퓨터 구조를 다시금 떠올리며 설레인다.
저작자표시

'즐길거리 > 책' 카테고리의 다른 글

교양 노트  (0) 2011.07.05
MongoDB 완벽가이드  (0) 2011.06.29
미식견문록  (0) 2011.05.11
파라다이스  (0) 2011.04.07
손에 잡히는 정규 표현식  (0) 2011.04.01
Posted by 준피
Computer Science/Algorithm2011. 5. 30. 14:52

quick sort - c

퀵소트를 c로 구현해봤다. 퀵소트는 처음부터 재귀호출을 이용해서 구현했다.

#include <stdio.h>

#include <malloc.h>

#include <stdlib.h>

#include <time.h>


void print_array(int *x, int n);

int* scaffolding(int n);

void quicksort(int *x, int n);

void swap(int *, int *);


int main() {

int *x, n, i;


printf("배열 크기 : ");

scanf("%d", &n);

x = scaffolding(n);

print_array(x, n);


quicksort(x, n);

print_array(x, n);


return 0;

}


void quicksort(int *x, int n) {

if(n <= 1)

return;


int i, m = 0;


for(i = 1; i < n ; ++i) {

if(x[0] > x[i]) {

swap(&x[++m], &x[i]);

}

}

swap(&x[m], &x[0]);

quicksort(x, m);

quicksort(x+m+1, n-m-1);

}


void swap(int *a, int *b) {

int temp = *a;

*a = *b;

*b = temp;

}


void print_array(int *x, int n) {

int i;

for(i = 0; i < n; ++i)

printf("%d ", x[i]);

printf("\n");

}


int* scaffolding(int n) {

srand((unsigned) time(NULL));

int *x, i;


x = (int *)malloc(n * sizeof(int));

for(i = 0; i < n; ++i)

x[i] = rand() % n;


return x;

}


밑의 함수는 정렬하는 부분만 다른 알고리즘으로 풀어봤다.

void quicksort(int *x, int n) {

if(n <= 1)

return;


int l = 0, u = n;

while(1) {

do {++l;} while(x[0] > x[l] && l < n);

do {--u;} while(x[0] <= x[u] && u > 0);

if(u < l)

break;

swap(&x[l], &x[u]);

}

swap(&x[0], &x[u]);

quicksort(x, u);

quicksort(x+u+1, n-u-1);

}




저작자표시

'Computer Science > Algorithm' 카테고리의 다른 글

Quick Select - Find k-th item in an unsorted array.  (0) 2014.06.29
quick sort - Java  (0) 2011.05.30
insertion sort - c  (0) 2011.05.28
insertion sort - Java  (0) 2011.05.26
binary search - Java  (0) 2011.05.17
Posted by 준피
Computer Science/Algorithm2011. 5. 28. 21:09

insertion sort - c

삽입정렬을 c로 구현해봤다. 이진탐색을 구현하면서 포인터에 익숙해진터라 좀 더 수월하게 작업했다.

#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>
#include <time.h>

int* scaffolding(int);
void print_array(int *, int);
void insertionsort(int *, int);

int main() {
int *x, n, i;
printf("배열 크기 : ");
scanf("%d", &n);
x = scaffolding(n);
printf("입력 : ");
print_array(x, n);

insertionsort(x, n);
printf("결과 : ");
print_array(x, n);

return 0;
}

void insertionsort(int *x, int n) {
int i, j;
for(i = 1; i < n; ++i){
for(j = i; j > 0 && x[j-1] > x[j]; --j){
int temp = x[j-1];
x[j-1] = x[j];
x[j] = temp;
}
}
}

void print_array(int *x, int n) {
int i;
for(i = 0; i < n; ++i)
printf("%d ", x[i]);
printf("\n");
}

int* scaffolding(int n) {
srand((unsigned) time(NULL));
int *x, i;

x = (int *)malloc(n * sizeof(int));
for(i = 0; i < n; ++i)
x[i] = rand() % n;

return x;
}


위의 삽입정렬에서 배열의 값을 swap 해주는 부분만 알고리즘을 바꿔봤다.
메모리에 쓰는 작업을 덜하기 때문에 좀 더 효율적이다.

void insertionsort(int *x, int n) {
int i, j, temp;
for(i = 1; i < n; ++i){
temp = x[i];
for(j = i; j > 0 && x[j-1] > temp; --j)
x[j] = x[j-1];
x[j] = temp;
}
}





저작자표시

'Computer Science > Algorithm' 카테고리의 다른 글

quick sort - Java  (0) 2011.05.30
quick sort - c  (0) 2011.05.30
insertion sort - Java  (0) 2011.05.26
binary search - Java  (0) 2011.05.17
binary search - c  (0) 2011.05.16
Posted by 준피
Computer Science/Algorithm2011. 5. 26. 23:03

insertion sort - Java

삽입 정렬을 자바로 작성해봤다.

@Test
public void insertionSort() 
{
int[] x = new int[10];
for (int i = 0; i < x.length; i++)
x[i] = (int) (Math.random() * x.length);
for(int i = 1; i < x.length; ++i){
for(int j = i; j > 0; --j){
if(x[j] < x[j-1]){
int temp = x[j-1];
x[j-1] = x[j];
x[j] = temp;
}
}
}
}


이번 삽입 정렬은 swap을 하지 않는 방식으로 해봤다.

@Test
public void insertionSort2() 
{
int[] x = new int[10];
for (int i = 0; i < x.length; i++)
x[i] = (int) (Math.random() * x.length);
int i, j, temp;
for(i = 1; i < x.length; ++i){
temp = x[i];
for(j = i; j > 0 && x[j-1] > temp; --j)
x[j] = x[j-1];
x[j] = temp;
}
}



저작자표시

'Computer Science > Algorithm' 카테고리의 다른 글

quick sort - c  (0) 2011.05.30
insertion sort - c  (0) 2011.05.28
binary search - Java  (0) 2011.05.17
binary search - c  (0) 2011.05.16
반전 알고리즘  (0) 2011.05.12
Posted by 준피
Computer Science/Algorithm2011. 5. 12. 22:16

반전 알고리즘

문제 : n개의 원소를 가지는 벡터 x를 i만큼 왼쪽으로 회전시키기
        즉, ab => ba

예제> n = 8, i = 3 인 경우에 a = 1 2 3, b = 4 5 6 7 8 가 된다.
 
입력 : 1 2 3   4 5 6 7 8
출력 : 4 5 6 7 8   1 2 3 

======================================< 풀     이 >==========================================


private static final int N = 1000000; -> 샘플 길이
private static final int SHIFT = 1000; -> 왼쪽으로 shift 하는 횟수


reverse 알고리즘
- swap 횟수 : N번
- 수행시간 : 약 10밀리세컨드

int[] result = getSample(N);

reverse(0, SHIFT-1, result);
reverse(SHIFT, N-1, result);
reverse(0, N-1, result);

배열을 거꾸로 뒤집는다.

private void reverse(int i, int j, int[] input){
while(i < j) {
int temp = input[j];
input[j] = input[i];
input[i] = temp;
i++;
j--;
}
} 

juggling action 알고리즘 
- swap 횟수 : N번
- 수행 시간 : 약 50 밀리세컨드

int[] result = getSample(N);
for(int i = 0; i < getGCD(N, SHIFT); ++i) {
int t = result[i];
int k = getGCD(N,SHIFT) + i;

for(int j = i; j < result.length; j += getGCD(N, SHIFT)){
if(k < result.length){
result[j] = result[k];
k += getGCD(N, SHIFT);
}else{
result[j] = t;
}
}
}

최대공약수(Greatest Common Divisor)를 찾는다.

private static int getGCD(int a, int b){
while(0 != b){
int temp = a % b;
a = b;
b = temp;
}
return Math.abs(a);
}

shift 알고리즘
- swap 횟수 : (N-1)*SHIFT
- 수행 시간 : 약 3500밀리세컨드

int[] result = getSample(N);

for(int i = 0; i < SHIFT; ++i){
for(int j = 1; j < result.length; ++j){
int t = result[j];
result[j] = result[j-1];
result[j-1] = t;
}
} 

INPUT을 생성한다.

private int[] getSample(int length) {
int[] result = new int[length];
for (int i = 0; i < result.length; i++) {
result[i] = i;
}
return result;
}

실험>

조건 1> N = 1000000(백만), SHIFT = 1000
 - reverse : 10ms
 - juggling action : 52ms
 - shift : 3640ms

조건 2> N = 1000000(백만), SHIFT = 10
 - reverse : 10ms
 - juggling action : 47ms
 - shift : 43ms

조건 3> N = 1000000(백만), SHIFT = 5
 - reverse : 10ms
 - juggling action : 45ms
 - shift : 24ms

조건 4> N = 1000000(백만), SHIFT = 1
 - reverse : 10ms
 - juggling action : 45ms
 - shift : 10ms

 
결과>

reverse 알고리즘은 꾸준한 성능을 보여준다. 
jugging action 알고리즘은 꾸준한 성능을 보여주지만 조건에 따라 shift알고리즘보다 성능이 낮기도 한다.
세가지 알고리즘 모두 제한된 메모리를 갖고 있다는 전제조건에서 구상했다.

만일, i만큼의 벡터를 임시변수에 옮긴 후, n-i개의 원소를 i만큼 왼쪽으로 옮긴다음에 x의 뒤쪽에 임시변수를 
복사해야 한다면 i만큼의 메모리를 필요로 하게 된다. 

 
reverse알고리즘 동작 원리>

a` = a의 reverse, b` = b의 reverse

(ab)` = b`a`  <= 이 법칙은 중고등학교 수학시간에 배웠다.

a b => a` b` => (a` b`)` = ba

 

참고자료 : 생각하는 프로그래밍 칼럼2 
저작자표시

'Computer Science > Algorithm' 카테고리의 다른 글

insertion sort - c  (0) 2011.05.28
insertion sort - Java  (0) 2011.05.26
binary search - Java  (0) 2011.05.17
binary search - c  (0) 2011.05.16
도형 내부 채우기  (0) 2011.05.11
Posted by 준피

티스토리툴바