'Computer Science'에 해당되는 글 12건

  1. 2011.05.26 insertion sort - Java
  2. 2011.05.17 binary search - Java
  3. 2011.05.16 binary search - c
  4. 2011.05.12 반전 알고리즘
  5. 2011.05.11 도형 내부 채우기
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. 17. 20:50

binary search - Java

java로 이진탐색을 구현했는데 익숙해서인지 금방 끝났다. 새로운 패키지 만들기 귀찮아서 JUnit 으로 메소드를 생성했다.

@Test

public void main()
{
int n = 10;
int x[] = scaffolding(n);
int k = 70;
int result = binarySearch(x, n, k);
System.out.println(result);
}

public int[] scaffolding(int n)
{
int x[] = new int[n];
for(int i = 0; i < n; ++i)
x[i] = i * 10;
return x;
}

public int binarySearch(int[] x, int n, int k)
{
int l = 0; int u = n - 1; int m;
while(true) {
m = (l + u) / 2;
if(l > u)
return -1;
if(x[m] == k)
return m;
else if (x[m] > k)
u = m - 1;
else if (x[m] < k)
l = m + 1;
}
}


저작자표시

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

insertion sort - c  (0) 2011.05.28
insertion sort - Java  (0) 2011.05.26
binary search - c  (0) 2011.05.16
반전 알고리즘  (0) 2011.05.12
도형 내부 채우기  (0) 2011.05.11
Posted by 준피
Computer Science/Algorithm2011. 5. 16. 21:24

binary search - c

c로 이진탐색을 구현해봤다. 오랜만에 쓴 포인터 덕에 고생좀 했다.

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

int binarysearch(int *x, int k, int n);
int* scaffolding(int n);

int main(){
    int n; int k; int *x;
    
    printf("\n배열 크기 : ");
    scanf("%d", &n);
    x = scaffolding(n);

    printf("\n찾고싶은 수 : ");
    scanf("%d", &k);

    int result = binarysearch(x, k, n);
    printf("\nresult : %d\n\n", result);
    
    return 0;
}

int* scaffolding(int n) {
    int *x; int i;

    x = (int *)malloc(n * sizeof(int));
    for(i = 0; i < n; ++i)
        x[i] = i * 10;
    
    return x;
}

int binarysearch(int *x, int k, int n) {
    int l = 0; int u = n-1; int m;

    while(1) {
        m = (l+u) / 2;

        if(l > u)
            return -1;

        if(x[m] == k) 
            return m;
        else if(x[m] > k)
            u = m-1;
        else if(x[m] < k)
            l = m+1;
    }
}

 


저작자표시

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

insertion sort - c  (0) 2011.05.28
insertion sort - Java  (0) 2011.05.26
binary search - Java  (0) 2011.05.17
반전 알고리즘  (0) 2011.05.12
도형 내부 채우기  (0) 2011.05.11
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 준피
Computer Science/Algorithm2011. 5. 11. 19:18

도형 내부 채우기

1로 연결된 도형 내부를 1로 채우기

예제>
입력
00000000000000000000
00111111111111111110
00100000000000000010
00111110000000000010
00000010000000000100
00001100000000000010
00001000000000000010
00001111111111111100
00000000000000000000

출력
00000000000000000000
00111111111111111110
00111111111111111110
00111111111111111110
00000011111111111100
00001111111111111110
00001111111111111110
00001111111111111100
00000000000000000000
 

메인 메소드

List<String> sample = makeSample();
int x = 10; int y = 3;    -> 시작지점은 임의로 만들었다.
char[][] maps = sampleToMaps(sample);
 
mark(x, y, maps);

칸을 채우는 메소드로 재귀호출함

private void mark(int x, int y, char[][] maps)
{
maps[y][x] = '1';
if(x-1 > 0 && '0' == maps[y][x-1]) {
mark(x-1, y, maps);
}
if(x+1 < maps[y].length && '0' == maps[y][x+1]) {
mark(x+1, y, maps);
}
if(y-1 > 0 && '0' == maps[y-1][x]) {
mark(x, y-1, maps);
}
if(y+1 < maps.length && '0' == maps[y+1][x]) {
mark(x, y+1, maps);
}
}


문제를 만드는 메소드
처음부터 2x2 char로 map만들기 불편하기 때문에 만들었다.

private List<String> makeSample()
{
List<String> result = new ArrayList<String>();
result.add("00000000000000000000");
result.add("00111111111111111110");
result.add("00100000000000000010");
result.add("00111110000000000010");
result.add("00000010000000000100");
result.add("00001100000000000010");
result.add("00001000000000000010");
result.add("00001111111111111100");
result.add("00000000000000000000");

return result;
}

문제를 해결할 자료구조에 옮기는 메소드

private char[][] sampleToMaps(List<String> sample)
{
char[][] result = new char[sample.size()][20];
for(int i = 0; i < result.length; ++i){
sample.get(i).getChars(0, sample.get(i).length(), result[i], 0);
}
return result;
}

저작자표시

'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.12
Posted by 준피

티스토리툴바