꼰대 개발자~

[문제] 1, 4, 8, 9, 16, 25, 27, 32, 36, 49, 64...와 같은 어떤수의 거듭제곱으로 만들어진 수들이 정렬되어 있을때 n번째 거듭제곱수를 구하시오

답변 예시

완전 거듭제곱수는 m^k으로 이루어진 수이다. 

1 = 1^k
4 = 2^2
8 = 2^3
9 = 3^2
16= 4^2
25 = 5^2
27 = 3^3
...

이문제는 특별한 규칙이 없으므로 모든수를 구하고 순서를 정하자.

long long nth_perfect_power(int n){
    if(n == 1) return 1;
    
    auto limit = 1e10;
    
    set<long long> powers;
    for(long long m = 2; m * m < limit; m++){
        long long power = m * m;
        while(power < limit){
            powers.insert(power);
            power *= m;
        }
    }
        
    auto it = powers.begin();
    std::advance(it, n-2);
    return *it;
}

이 소스는 퍼포먼스에 문제가 있습니다.

set은 고성능으로 sorting된 형태로 저장하지만 위와 같은 소스에서는 set으로 인하여 탐색과 삽입을 수십만번 반복함으로써 성능상의 문제가 발생합니다.하여 저장시에는 저장만하고 마지막에 한번 sorting하는 방식으로 바꿔봅니다.

long long nth_perfect_power2(int n){
    if(n == 1) return 1;
    
    auto limit = 1e10;
    
    vector<long long> powers;
    for(long long m = 2; m * m < limit; m++){
        long long power = m * m;
        while(power < limit){
            powers.push_back(power);
            power *= m;
        }
    }
    
    std::sort(powers.begin(), powers.end());
    return powers[n-2];
}

[문제] n개의 박스가 있고 각각 1,2,3,4,...n개의 사과가 들어 있다. 이때 k개의 박스를 골라서 n명에서 공평하게 나눠줄있는 k개의 박스 목록을 출력하세요.

답변 예시

이문제 지난 포스트에 있는 C++ 미로찾기(graph traversal) 을 참조하면 조금더 쉽다.

미로찾기와 같이 2차원 그래프가 아니고 단방향 1차원이므로 tree 탐색의 문제다.

우선 중복없는 4개의 상자를 중복없는 조합으로 골라보자

void find_boxes(int n, int start, vector<int> & selected){
    cout << join_str(selected) << endl;

    for(int i=start;i<n;i++){
        selected.push_back(i+1);
        find_boxes(n, i+1, selected);
        selected.pop_back();
    }
}

void select_boxes(int n){
    vector<int> selected;
    find_boxes(n,0,selected);
}

void apple_box(){
    select_boxes(4);
}

// result
{}
{1}
{1,2}
{1,2,3}
{1,2,3,4}
{1,2,4}
{1,3}
{1,3,4}
{1,4}
{2}
{2,3}
{2,3,4}
{2,4}
{3}
{3,4}
{4}
{2}
{2,3}
{3}

오른쪽으로 상자하나씩 열어보고 마지막상자를 열어봤으면 이전 상자로 돌아가서 다음상자를 열어본다. 이름 트리로 그려보다 다음과 같다.

<>--------------|-------|---|
1-------|---|   2---|   3   4
2---|   3   4   3   4   4
3   4   4       4
4

결국은 깊이가 k이고 apple의 총합이 나머지가 남지 않으면 된다.

최종소스는 

bool find_boxes(int n, int k, int start, int sum, vector<int> & selected){
    if(selected.size() == k){
        if(sum % n == 0){
            return true;
        }
        return false;
    }

    for(int i=start;i<n;i++){
        selected.push_back(i+1);
        if(find_boxes(n, k, i+1, sum + (i+1), selected))
            return true;
        selected.pop_back();
    }
    return false;
}

void select_boxes(int n, int k){
    vector<int> selected;
    find_boxes(n, k, 0, 0, selected);
    cout << "result = " << join_str(selected) << endl;
}

int main(int argc, char * argv[]){
    select_boxes(4, 2);
    return 0;
}

[문제] 1부터 숫자가 연속된 문자열(12345678910111213...)이 있을때 n번째 숫자는 뭘까?

답변 예시

1. 단순무식한 효율무시 알고리즘

아주 단순히 생각해 보면 연속된 문제열을 만드는것은 쉽고 문자열을 만든후 n번 문자를 찾는 알고리즘을 구현해 보겠다.

int num_of_pos_1(int n){
    string str;
    for(auto i=1;i<=n;i++){
        str += std::to_string(i);
        if(str.length() > n){
            break;
        }
    }
    return str[n-1] - '0';
}

n이 늘어 나면 늘어 날수록 memory와 cpu비용이 함께 증가하는 아주 안좋은 알고리즘 되겠다.

int to string역시 O(n)이므로 사실상의 시간 복잡도는 O(n^n)이다.

그러나

이걸 아키텍처 적으로 플어본다면 문자열 str은 상수와가 가능하고 상수화하고 n번째 문자를 찾는다면 결국은 O(1)의 완벽한 알고리즘이된다. 상황과 시스템에 따라서 이런 알고리즘도 상당한 퍼포먼스를 발휘할수도 있다. 만약 str을 생성하는 문제가 복잡하고 수식으로 계산하기 힘든경우에는 웜업시간에 str을 생성하고 매 요청때마다 결과를 도출하는것도 사실상 더 많이 쓰이는 방법되겠다.

그래도 알고리즘만 연구하시는 분들은 최적의 공간/시간 복잡도를 추구하므로 최적의 공간/시간 복잡도를 가지는 알고리즘을 연구해보자!!

2. 수치해석적 알고리즘

- 일단 문제를 해결하기 위해서 규칙을 찾아내야한다.

- 문자열을 만드는 숫자를 "k"라고 하고 요구하는 위치값을 "n"이라하자.

- k의 자릿수를 digit이라하자

- 각 digit별 자리수 count(digit) = 9 * 10 ^ (digit-1) 이다.

위의 정의에 의해서 n의 변위 N을 구해보면 아래와 같다

k(digit, k범위) = N(digit, n의 범위)

k(1, {1...9}) = N(1, {1, 2, 3...9})
k(2, {10..99}) = N(2, {10,11,12,13,...,188,189})
k(3, {100...999}) = N(3, {190,191,192,...,2887, 2888, 2889})

digit 구하기

위의 분석에 의거하여 digit은 N(digit)안에 있다이다.

시작 N(digit) <= n <= 종료 N(digit)

이 규칙에 의거하여 digit값을 구해보자

int digit(int n){
    int digit = 1;
    int count = 9;
    int end = 9;
    while(n > end){
        digit++;
        count *= 10;
        end += count * digit;
    }
    return digit;
}

각 digit별 count(digit)는 9 * 10 ^ (digit-1)이라는점에 착안하여 구지 end라는 변수가 필요할까 고민해 본다.

int digit2(int n){
    int digit = 1;
    int count = 9;
    while(n > digit * count){
        n -= digit * count;
        digit++;
        count *= 10;
    }
    return digit;
}

k 구하기

k의 digit별 시작값 Ks(digit) = 10 ^ (digit-1) 이다.

시작값을 구했는데 변화량은 어떻게 구할까?

약간 정규화 해보자. 각 구간별로 시작값으로 n값을 빼면 모두 0부터 시작한다.

n: (1, 2, 3...9) - 1 = N(0, 1, 2,...,8) 
n: (10, 11, 12, 13,...,188,189) - 10 = N(0, 1 ,2, 3,...,178, 179)
n: (190, 191, 192,...,2887, 2888, 2889) - 190 = N(0, 1 ,2,...,2697, 2698, 2699)

결국은 n - Ks(digit)이 변화량이다. 이를 digit으로 나누면 k의 변화량이 된다.

일단 Ns(digit) = Ns(1) + ... + Ns(digit)을 구해보자

int nstart(int digit){
    int ns = 1;
    int count = 9;
    for(int i=0;i<digit-1;i++){
        ns += count * (i + 1);
        count *= 10;
    }
    return ns;
}

이를 이용해서 k값을 구하면

int cal_k(int n){
    int digit = digit2(n);
    return (int)pow(10, digit-1) + (int)(n - nstart(digit))/digit;
}

결국 위와 같이 필요한 변수값들을 구해봤는데 각각의 알고리즘은 digit으로 묶여 있기 때문에 결국은 하나로 합쳐진다.

int cal_k2(int n){
    int digit = 1;
    int count = 9;
    int ks = 1;
    while(n > digit * count){
        n -= digit * count;
        digit++;
        count *= 10;    // 9 * 10 ^ (digit - 1)
        ks *= 10;       // 10 ^ (digit - 1)
    }
    
    // n이 결국은 ns로 부터의 변화량값임 ( 0부터 시작하도록 -1을 해준다 )
    return ks + (n - 1)/digit;
}

n번째 숫자구하기 (결론)

결국 위와 같이 필요한 변수값들을 구해봤는데 각각의 알고리즘을 구성해 봤는데 이를 하나로 합쳐보겠다.

int num_of_pos_2(int n){
    int digit = 1;
    int count = 9;
    int ks = 1;
    while(n > digit * count){
        n -= digit * count;
        digit++;
        count *= 10;    // 9 * 10 ^ (digit - 1)
        ks *= 10;       // 10 ^ (digit - 1)
    }
    
    // n이 결국은 ns로 부터의 변화량값임 ( 0부터 시작하도록 -1을 해준다 )
    int k = ks + (n - 1)/digit;
    return std::to_string(k)[(n-1)%digit] - '0';
}

요즘 꼰대 개발자들은 "하라는데로 해"와 "나만이 할 수 있어", "니가 하는것 보다는 내가 빨라", "내가 하는것이 낮지", "주니어들은 쓸데가 없어", "요즘 쓸만한 개발자들이 없어"라는 말속에서 팀원들의 역량 향상을 통한 팀의 역량 향상 나아가 회사의 팀의 역량 강화로인한 비즈니스의 성공에는 관심이 없는듯하다.

컨텍스트 공유와 기술적 업무지시 보다는 "내가 하고 말지"라는 자세가 많아지는듯하다. 사실상 요즘은 업무지시나 업무지시 불이행에 대한 쪼족한 방법도 없는것도 사실이긴 하다. 꼰대 개발자 입장에서는 컨텍스트 독점을 통한 생명력 확장은 짧게 나마 업계에서 살아남는 하나의 전략인것 같기도 하다.

과거에는 경력과 리더쉽은 비례하던 시기가 있었다. 상명하복의 문화와 단정된 공유속에서 경험은 무엇보다도 우선시 되었으며 컨텍스트 독점은 긴 호봉상승과 경제적 안정감을 주던 시기가 있었다. 문제는 아직도 이 꼰대 문화와 관습에서 벗어나지 못한 꼰대들이 많이 있다는것이 문제다.

요즘은 상명하복의 시대도 아니며 수 많은 오픈소스들과 블로그들은 오히려 꼰대들보다 더 많은 정보와 지식을 공유해주고 있다 또한 비즈니스는 시시각각 변하고 순식간에 흥망성쇠하고 있다. 이 상황에서 컨텍스트 독점 또한 직장내 안정감을 줄 수 없는 상황이 되었다. 또한 요즘은 정확히 "중간"지점의 "업무지시", "코칭", "업무평가"등이 아니면 생계를 위협 할 만큼 큰 문제를 만들어 내기도 한다.

이러한 문제들은 현재의 "리더쉽 부족"의 문제를 야기시켰고 "꼰대 개발자"들을 찾는 계기가 되었지만 "꼰대 개발자"들은 현대의 리더쉽에 대해 준비가 되어 있지 않다. 그나마 살아남는 꼰대들은 팀원들에게는 허드렛일 시키고 자기가 밤을세워서 혼자 다 처리하는 행태를 보이고 있다. 이때문에 작금의 스타트업들은 시니어 보충에도 불구하고 캐파부족에 시달리고 있다.

우리 꼰대 개발자들이 살아 남는 방법은 "부족한 리더쉽"에 도전하는길 뿐이다.

이를 위해 아래의 행동지침에 대해 제안해 볼까한다.

• 모든 문제의 해결책은 시니어인 내가 중심이 되어야한다는 생각을 버려라
  • 위에도 얘기 했지만 요즘은 인터넷과 유튜브, 인강등을 통한 충분한 공유가 이루워 지고 있다. 나 한사람의 검색보다는 팀원 전체의 지식 검색이 더 효육적이며 아직은 고정되지 않는 주니어 / 중니어들의 아이디어가 빛날때가 더 많다는것을 인정해라
  • 끝까지 문제 해결에 대해 독려하고 지지해라. 업무와 기술에 대해 이해시키려는 노력은 부족해서는 안된다.
  • 문제에 대해 경험을 공유하고 방향성을 스스로 찾도록 해라. 그들이 부족한것은 경험뿐이다. 부족한것을 채워주는것이 리더의 역할이다.
  • 자신이 틀린것을 부끄러워하지 마라 - 자신이 틀린것을 리더쉽이 도전받는다고 생각하는 꼰대들이 많은듯하다. 다시한번 얘기하지만 지금은 MZ들이 검색과 지식 수용이 당신들 보다 100배는 빠르다. 
• 컨텍스트를 수시로 공유하고 코칭해라
  • 팀내 일어나고 있는 모든것들은 팀원들과 공유하는것을 게을리 하지 마라 - 팀웍의 최대 걸림돌인 컨텍스트 독점의 문제를 막을 수있다.
  • 각 팀원들이 하고 있는 일에 대해 철저히 공유받고 파악하는 일은 선택이 아니라 필수다 - 매일매일 대화를 해도 서로의 생각은 계속해서 달라지고 얼라인이 틀어지게 된다. 얼라인을 계속해서 맞추고 방향성을 잡아나가는것이 리더쉽의 기초다.
  • 팀원들의 컨텍스트 파악은 그들의 경험부족을 매꿔줄 수 있는 기회를 제공한다. 
  • 일주일 단위의 스프린트회의로는 부족하다 매일 매일해라.
  • 주기적으로 1:1 대화를 해라. 
• 가지고 있는 모든것을 전수해라
  • "이건 나만이 가진 기술인데"라는 생각이 당신을 꼰대로 만드는 지름길이다.
  • 비워야 새로운것을 배울 수 있다. 새로운것을 배우고 새로운 트렌트를 따라잡는 노력을 게을리 하지마라.
  • 나만의 기술이라도 나누면 더욱 발전한다. 나누고 공유하고 토론해라.
• 마음을 나누는것은 가족과 친구와 해라
  • 리더쉽은 "공감" 보다는 "일관성"에서 나온다.
  • 편애는 팀웍에 심각한 상처를 입힌다.
  • 마음을 나누더라도 업무에 있어서 "일관성"은 어떻게든 지켜라 - 그래서 친해지만 일관성을 잃을 수 있다. 

다음시간에는 "팔로워쉽"에 대해 얘기해 볼까한다.

아주 깔끔하게 옷갈아 입히는 AI Model입니다. 이제 쇼핑몰에서도 자기 자신의 이미지에 옷을 입혀보고 구입하는 시대가 오겠습니다.

https://huggingface.co/spaces/levihsu/OOTDiffusion

Hugging Face에 상당히 좋은 품질고 성능의 AI Model이 있어서 소개합니다.

https://huggingface.co/ByteDance/SDXL-Lightning

demo : https://huggingface.co/spaces/ByteDance/SDXL-Lightning

demo site에서 text만으로 image를 생성하는 경험을 해보세요.

123454321, 46864와 같이 뒤집어도 같은 것을 palindrome이라 합니다. 이런 palindrome을 판별하기 위한 최적의 알고리즘에 대해 고찰해 보겠습니다.

간단히 바로 생각나는 알고리즘은

1. 숫자를 문자열로 바꾼다.
2. 문자열을 뒤집는다.
3. 두 문자열을 비교한다.

bool is_palindrome(const string & str){
    auto copy = str;
    std::reverse(copy.begin(), copy.end());
    return copy == str;
}

bool is_palindrome_str(int data){
    return is_palindrome(std::to_string(data));
}

int main(int argc, const char * argv[]) {
    vector<int> data = { 987654, 1234321, 456789, 102979201 };
    for(int i=0;i<data.size();i++){
        cout << data[i];
        if(is_palindrome_str(data[i])){
            cout << " is palindrome";
        } else {
            cout << " is NOT palindrome";
        }
        cout << endl;
    }
}

OUTPUT:
987654 is NOT palindrome
1234321 is palindrome
456789 is NOT palindrome
102979201 is palindrome

PEFORMANCE (1,000 times for 1234321) :  113 milliseconds

이 코드의 문제점은 무거운 memory allocation과 swap이 일어난다는것이고 1만번만 반복해도 1초라는 어마어마한 퍼포먼스를 사용하는 아주 안좋은 알고리즘 되겠다.

memory access를 최대한 줄이고 시간복잡도도 1/2로 줄여보자

알고리즘

1. 왼쪽부터 1씩 증가하는 i번째 문자와 오른쪽 부터 1씩 감소하는 j번째 문자와 비교한다.
2. 만약 다르다면 false를 리턴한다.
3. i >= j 같다면 true을 리턴한다.

bool is_palindrome(const string & str){
    for(size_t i=0,j=str.length()-1; i < j; i++, j--){
        if(str[i] != str[j])
            return false;
    }
    return true;
}

OUTPUT:
987654 is NOT palindrome
1234321 is palindrome
456789 is NOT palindrome
102979201 is palindrome

PEFORMANCE (1,000 times for 1234321) :  81 milliseconds

memory allocation과 swap을 제거하여 상당부분 퍼포먼스를 개선하였다. Search도 딱 N/2만 한다.

그래도 string전환으로인한 memory access문제의 개선은 불가하다.

input이 숫자라는 단서에 착안하여 memory access자체를 제거해 보자

알고리즘

1. reverse 변수를 0으로 초기화
2. reverse 변수에 10을 곱해준다. ( 왼쪽으로 이동 )
3. reverse 변수 입력값을 10으로 나눈 나머지를 더해준다. (마지막 숫자)
4. 입력값을 10으로 나눠서 저장한다. ( 마지막 숫자 제거 )
5. 입력값이 0이면 중단하고 아니라면 2번을 반복한다.

int reverse(int data){
    int reverse = 0;
    while(data > 0){
        reverse *= 10;
        reverse += data % 10;
        data /= 10;
    }
    return reverse;
}

bool is_palindrome(int data){
    return reverse(data) == data;
}

OUTPUT:
987654 is NOT palindrome
1234321 is palindrome
456789 is NOT palindrome
102979201 is palindrome

PEFORMANCE (1,000 times for 1234321) :  16 milliseconds

1번 예제에 비하여 1/10로 실행시간이 줄었다. 이유는 compiler는 계속된 연산이기 때문에 memory 접근을 최소화하고 register단에서 연산을 마무리하기 때문에 상당히 빠르다.

OSI 7 Layer Model은 70-80년대 ISO 표준 국제 기구에서 OSI Model (Open Systems Interconnection Reference Model)이라는 정식 명칙으로 만들어진 고~~~대의 통신 모델입니다. 수십년이 지난 지금도 표준모델로써의 역할을 활발히 하고 있지요.

그런데 왜? 이 고대의 표준모델을 가지고 왔느냐?

• 추상화의 이해
  • 요즘 추상화를 통해서 의존도를 줄이는 개발방법론들 아키텍쳐들( DDD, Clean Architecture등) 이 쏟아져 나오고 있죠. 이 추상화 기법들이 OSI의 기본 개념들로부터 이해하면 좀더 쉬운 이해가 될수있습니다.
  • OSI는 인프라부터 응용영역까지 어떻게 추상화하여 단순화해 나아가고 하위 계측에 대한 의존도를 줄이는지는 아주 적절히 표현하고 있습니다.
  • DDD와 Clean Architecture의 기본개념도 의존도의 방향에 대해 강하게 어필하는것 처럼 OSI도 의존도에 대한 계측과 방향이 중요합니다.
  • 지난 수십년간의 tcp, upd, http등의 구현물들을 보면 추상화에 대한 수많은 기법들을 손쉽게 배울 수 있습니다.
• 통신 패러다임의 이해
  • 요즘 MSA의 등장으로 HTTP가 통신의 기본처럼 되었지만 사실은 HTTP의 하위 layer가 존재하고 http는 이 하위 레이어들의 구현으로 이루어 진다는걸 알면 보안, 압축, 퍼포먼스등에 좀더 빠르게 대응이 가능합니다.
  • TLS( Transport Layer Security, 이전글 참조 SSL(Secure Sockets Layer) vs TLS(Transport Layer Security))라는 개념을 접했을떄 우리는 TLS가 Transport Layer에 위치해 있구나 TCP, UDP등에 적용되는 기술이구나 Session과 Application 기능은 구현되어 있지 않겠구나 .... 바로 추축 할 수 있습니다. 
  • 수많은 하드웨어 규격 ( RS232, RJ45, BLE, E1/CAS 등)은 Data Link Layer Protocol을 만족하면 되고 Application 측면에서 하드웨어들을 사용하면 (BLE, RS232 등)을 사용할때는 Applicaiton Layer, 최소 Network Layer, Transport Layer만 이해하면 가능하고... OSI를 통하여 상호 커뮤니케이션이 가능합니다.

위의 그림은 정말 OSI 7 Layer를 잘 표현해 준 그림인 듯합니다. 

각각의 layer는 하위 layer로 구현되고 다른 layer는 관심사가 아닙니다. 표준 protocol만 잘 지키면 여타 다른 layer의 의존도를 회기적으로 끈어 낼수있지요. 

개발자 답게 코드로 이해 합시다.

FTP를 예를 들어보자.

FTP의 기능을 2가지로 정의해 보자.

* 파일전송

* 파일수신

FTP는 단순히 파일을 전송하고 수신하는 일을 하고 이를 구현하기 위하여 TCP또는 UDP layer를 사용하며 TCP, UDP의 구현방식에는 관심이 없다.

fn ftp::send(file_path){
	let data = read_file();
    
    let handle = tcp::connect(address);
	let data = read_file();
    tcp::send(data);
    tcp::close(handle)
}

위의 코드에서 FTP는 "tcp::"함수들의 구현/변경에는 관심이 없다. 위의 코드만으로 구현이 끝난상황이다. 

여기서 tcp::send() 를 구현해 보자. 

fn tcp::send(data : array){
    loop{
    	let packet = slice_packet(data);
        ip:send_packet(packet)
    }
}

여기서도 TCP 프로토콜은 ip:send_packet()함수의 구현/변경에는 또한 관심이 없다.

!!! 어??? 그럼 tcp:send를 테스트하기 위해서는 ftp::send()가 구현되기를 기다려야하나? 어라? HTTP에서도 쓴다네?

아~~ tcp를 많은 상위 layer에서 어떻게 쓰이는지 모르고 "상위 layer의 구현 또한 관심이 없으므로 unit test을 잘 만들어서 품질을 보장하자"가 TDD의 기본 개념이지 않을까 싶다.

상위 layer가 없으므로 unit test를 만들어 나가면서 구현을 해 나아가는것이다.

[#test]
fn test_send_zero_sized(){
}

[#test]
fn test_send_packet_sized(){
}

[#test]
fn test_send_long_sized(){
}

급하게 마무리한 감이 있는데 .. ㅠ.ㅠ 점차 채워가겠습니다. ^^