자료구조/알고리즘 공부, 알고리즘의 중요성

대학교 2학년 때 공부했던 자료구조와 알고리즘을 다시 한 번 공부해볼까 합니다.

알고리즘과 자료구조는 소프트웨어/하드웨어 엔지니어를 가리지 않고 모두 필요한 기본 소양입니다.

 

1. 함수와 함수끼리 주고 받는 데이터에 대해 이해하고 -> 모듈과 모듈 사이에 주고받는 데이터에 대해 이해하고
2. 함수에서 데이터를 어떻게 처리할지 정의한다 -> 모듈에서 데이터를 어떻게 처리할지 정의한다

 이러한 공통점으로 인해 입사시 보는 알고리즘 테스트는 python/java/c++/c를 가리지 않습니다.

 물론 편의성으로 인해 python이 선호되지만 python 역시 여러가지 표현(언어)중 하나입니다.

 이러한 점은 verilog hdl 또한 다르지 않습니다.

 

 따라서 더욱 효율적인 시스템을 설계하기 위해 다시 자료구조와 알고리즘 공부를 해볼까 합니다.

 

 첫 번째로 알고리즘의 중요성을 이해하기 위해 유클리디안 호제법을 예시로 들어서 표현해보겠습니다.

https://wh00300.tistory.com/108

최소공배수 / 유클리디안 호제법

 유클리디안 호제법은 최소공배수를 찾는 방법으로 이전 포스팅에서는 모듈러를 사용해서 구현했습니다.

 

 유클리디안 호제법을 구현하는 방법은 모듈러 외에 다양하게 있습니다. 

 뺄셈을 이용하거나, 모듈러 연산을 사용하거나 재귀함수를 사용해서도 구현할 수 있습니다.

 이번에는 이 세가지 방법에 대해 구현하고 연산 시간을 테스트해보겠습니다.

 

1. 뺄셈을 이용한 유클리디안 호제법

int gcd_minus (int u, int v) {

    int t;

    while (u) {

        if (u < v) {

            t = u; u = v; v = t;

        }

        u = u - v;

    }

    return v;

}

 

2. 모듈러를 사용한 유클리디안 호제법

int gcd_moduler (int u, int v) {

    int t;

    while (v) {

            t % u; u = v; v = t;

    }

    return u;

}

 

3. 재귀함수를 사용한 유클리디안 호제법

int gcd_recursion (int u, int v) {

    if (v == 0)

        return u;

    else 

        return gcd_recursion(v, u % v);

}

 

이렇게 세 개의 함수를 테스트해보겠습니다.

각 함수는 10,000,000회씩 수행하며, time.h의 clock을 이용해 몇 clock이 소모되었는지 체크합니다.

 

1. 12와 9의 최소공배수 찾기

12와 9의 최소 공배수 찾기

 여기서는 Moduler < Minus < Recursion순으로 시간이 적게 소모되었습니다.

 하지만 Minus와 Recursion의 경우 큰 차이를 보이지 않네요.

2. 280과 30의 최소공배수 찾기

280과 30의 최소 공배수 찾기

 이번에는 Moduler < Recursion < Minus순으로 시간에 적게 소모되었습니다.

 Minus에서는 Moduler의 약 2.8배의 시간이 소모되었고, Recursion에 비해서는 약 1.8배정도 소모되었습니다.

 

3. 2980과 20의 최소공배수 찾기

2980과 20의 최소 공배수 찾기

 마지막은 Moduler < Recursion < Minus 순입니다.

 그리고 차이는 Minus가 Moduler와 Recursion의 약 70배와 40배가 소요되었습니다.

 

 1번과 2번에서는 세 가지 함수의 차이가 크게 나타나지 않았습니다.

 물론 2.8배와 1.8배 역시 적은 숫자은 아니지만 3번과 같은 상황과 비교하면 무척 작은 숫자입니다.

 

 만약 minus를 사용한 경우 3번과 같은 상황을 예측하지 못 했다면 그대로 사용했을 수도 있습니다.

 하지만 3번과 같은 상황에서 많은 시간이 소요될 것입니다.

 

 간단한 테스트를 마무리 하겠습니다.

 앞으로 더 공부해서 좋은 시스템 구조를 생각하게 되었으면 좋겠습니다.