ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • 문제로 풀어보는 알고리즘 0.3 생각해보기 풀이
    개발하면서/Algorithm,DS,PS 2012. 8. 29. 16:25

    요새 심심할때 문제로 풀어보는 알고리즘책을 보고있습니다.

    저같은 초보자한테 참 좋네요 : ) 

     

     

     

    4년전에 알고리즘 트레이닝북으로 개발에 발을 들여놨던 기억이 나네요. 

    정말 계란으로바위치기하듯이.......디버깅만 수천번한것같아요 ㅋㅋㅋㅋㅋㅋㅋㅋ (생각없이 무작정 코딩코딩~!! ㅎㅎ)

     

    무튼 이번에 인사이트북에서 이벤트로  아래 이벤트를 열었습니다.

    책보면서 생각 했던게 있어서 코딩시작.....;;

    http://www.insightbook.co.kr/post/3814

     

    
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    
    int data[] = {1, 2, 3, 4, 5, 6, 7, 8};
    
    void right_rotate(int begin, int end, int k)
    {
        int length = end-begin+1;
        int divide_into = length/2 + 1;
        int *temp = (int*) malloc(sizeof(int)*(divide_into));
    
        int *arr = data + begin;
    
        if (length < k)
            k = k % length;
    
        if ( divide_into <= k ) {
            memcpy(temp, arr, (length-k)*sizeof(int));
            memmove(arr, arr+(length-k), k*sizeof(int));
            memcpy(arr+k, temp, (length-k)*sizeof(int));
        } else if (divide_into > k ) {
            memcpy(temp, arr+(length-k), k*sizeof(int));
            memmove(arr+k, arr, (length-k)*sizeof(int));
            memcpy(arr, temp, k*sizeof(int));
        }
       free(temp);
    }
    int main(int argc, char* argv[])
    {
        int i;
    
        for (i = 0; i < sizeof(data)/sizeof(int); i++)
            printf ("[%d]: %d\t", i, data[i]);
        puts("");
    
        right_rotate(2, 6, 2);
    
        for (i = 0; i < sizeof(data)/sizeof(int); i++)
            printf ("[%d]: %d\t", i, data[i]);
        puts("");
        return 0;
    }
    

     

     

     

    요새 ruby를 시작해서 ruby로 하면 어떻게 될까.....해서 봤더니....엄머....rotate라는 함수가 있네요. 

    아래와 같이 짜봤습니다.
    class Array
            def right_rotate (first, last, k)
                    length = last - first
                    k %= length if k > length
    
                    tmp = self.slice!(first..last)
                    tmp.rotate!(-k)
                    idx = first
                    tmp.each do
                    |item|
                            self.insert(idx, item)
                            idx += 1
                    end
            end
    end
    
    arr = [1, 2, 3, 4, 5, 6, 7, 8]
    
    puts "before:\t"+arr.inspect
    
    arr.right_rotate 2, 6, 1
    puts "after:\t"+ arr.inspect
    

     

     

     

    c는 범위에 반을 나눠서(divide_into) 옮기려고 하는크기에 따라서 다르게했습니다. 

    사용하는 메모리를 조금이나마 아껴보고자;;; 

     

    ruby는 slice로 범위만큼 도려내고, rotate한다음에 다시 insert. 간단합니다. 

    이런 재미있는 이벤트를 기획하신 인사이트북. 감사합니다~!!

    댓글 0

Designed by Tistory.