꼰대 개발자~

[문제] 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';
}

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단에서 연산을 마무리하기 때문에 상당히 빠르다.

세계인의 타임킬링게임 "지뢰찾기"게임에서 특정 블럭을 눌렀을때 막혀있지 않은 최대 면접을 구하여 OPEN해줄때 사용할 수 있는 면적구하기 알고리즘 입니다. Graph, DFS에 관련해서는 미로찾기(graph traversal)을 먼저 읽고 오면 도움이 됩니다.

이전 포스트에서 언급한바와 같이 Graph - DFS ( Depth First Search ) 알고리즘은 완전 탐색 즉 모든 노드를 방문할 수 있는 알고리즘입니다. 이 알고리즘은 조금 응용해서 방문할 수 있는 모든 노드를 방문하면 결국은 방문수가 해당 node group의 넓이가 됩니다.

 문제

아래와 같은 지도가 존재할때 빈칸으로 이루어진 영역중 최대 크기 영역의 크기를 구해봅시다.

사전 정의

다음의 설명들에 사용된 코드들은 아래와 공통 코드들은 미로찾기(graph traversal)의 공통코드들을 재활용합니다.

최대 넓이 구하기

일단 DFS함수를 하나 만들고 각 노드별로 넓이를 구합니다 ( 방문노드의 합 ), 이때 방문한 노드는 넓이를 구하지 않습니다.

int dfs_area(vector<vector<int>> & map, vector<vector<int>> & visited, int x, int y){
    int theWays = 1;
    
    visited[y][x] = 1;
    
    if(moveable(map, visited, x-1, y))
        theWays += dfs_area(map, visited, x-1, y); // left
    if(moveable(map, visited, x+1, y))
        theWays += dfs_area(map, visited, x+1, y); // right
    if(moveable(map, visited, x, y-1))
        theWays += dfs_area(map, visited, x, y-1); // up
    if(moveable(map, visited, x, y+1))
        theWays += dfs_area(map, visited, x, y+1); // down
    
    return theWays;
}

int main(int argc, const char * argv[]) {
    
    vector<vector<int>> map = {
        {0, 0, 0, 1, 1, 0, 0},
        {0, 0, 0, 1, 1, 0, 0},
        {0, 1, 1, 1, 1, 1, 1},
        {1, 0, 0, 1, 0, 0, 0},
        {1, 0, 0, 1, 0, 0, 0},
    };
    
    print_map("MAP", map);
    cout << endl;
    
    vector<vector<int>> visited(map.size(), vector<int>(map[0].size()));
    
    int max_area = 0;
    // 모든 노드의 최대 넓이를 구합니다.
    for(int y=0;y<map.size();y++){
        for(int x=0;x<map[0].size();x++){
            if(map[y][x] == 1) continue;
            if(visited[y][x] == 1) continue;
            
            auto area = dfs_area(map, visited, x, y);
            if(max_area < area) max_area = area;
        }
    }
    
    cout << "Max Area Size : " << max_area << endl << endl;
    
    print_map("VISTED", visited);
    
    return 0;
}

출력값은

결과	방문지

지도상에 방문할수있는 모든 노드를 방문하였고 최대 크기 area도 찾아 냈습니다.

지뢰찾기

이 프로그램을 지뢰찾기에 응용해 봅시다.

사용자가 (1, 1) 좌표 를 클릭했다 하면 main program만 조금 수정합니다.

int main(int argc, const char * argv[]) {
    
    vector<vector<int>> map = {
        {0, 0, 0, 1, 1, 0, 0},
        {0, 0, 0, 1, 1, 0, 0},
        {0, 1, 1, 1, 1, 1, 1},
        {1, 0, 0, 1, 0, 0, 0},
        {1, 0, 0, 1, 0, 0, 0},
    };
    
    print_map("MAP", map);
    cout << endl;
    
    vector<vector<int>> visited(map.size(), vector<int>(map[0].size()));
    
    int x = 1, y = 1;
    auto area = dfs_area(map, visited, x, y);
    cout << "Area Size from (" << x << "," << y << ") is " << area << endl << endl;
    
    print_map("VISTED", visited);
    
    return 0;
}

결과	방문지

(1,1) 좌표를 클릭했을때 속해 있는 area의 넓이를 구했고 방문지 노드도 모두 구했다.

이제!!! 지뢰게임을 만들어 보시라...

아래에 full source를 올려둡니다. 여러가지 테스트 해봅시다.

//
//  main.cpp
//  area
//
//  Created by Jack Kim on 2023/06/09.
//

#include <iostream>
#include <vector>
using namespace std;

class location{
public:
    int x;
    int y;
    shared_ptr<location> prev;
public:
    location(int x, int y, shared_ptr<location> prev)
    : x(x), y(y), prev(prev) {}
};

bool moveable(vector<vector<int>> & map, vector<vector<int>> & visited, int x, int y){
    if(x < 0 || x > map[0].size()-1) return false;
    if(y < 0 || y > map.size()-1) return false;
    if(map[y][x] != 0) return false;
    if(visited[y][x] != 0) return false;
    
    return true;
}

void print_map(const string & title, vector<vector<int>> & map){
    int width = (int)map[0].size();
    int height = (int)map.size();
        
    cout << "[" << title << "]" << endl;
    for(int x=0;x<width*2+1;x++)cout << "─"; cout << endl;
    for(int y=0;y<height;y++){
        cout << "│";
        for(int x=0;x<width;x++){
            string ch = " ";
            switch(map[y][x]) {
                case 1: ch  = "▒"; break;
                case 0: ch  = " "; break;
                case 9: ch  = "+"; break;
            }
                        
            cout << ch ;
            if(x != width-1)
                cout << " ";
        }
        cout << "│" << endl;
    }
    for(int x=0;x<width*2+1;x++)cout << "─"; cout << endl;
}

int dfs_area(vector<vector<int>> & map, vector<vector<int>> & visited, int x, int y){
    int theWays = 1;
    
    visited[y][x] = 1;
    
    if(moveable(map, visited, x-1, y))
        theWays += dfs_area(map, visited, x-1, y); // left
    if(moveable(map, visited, x+1, y))
        theWays += dfs_area(map, visited, x+1, y); // right
    if(moveable(map, visited, x, y-1))
        theWays += dfs_area(map, visited, x, y-1); // up
    if(moveable(map, visited, x, y+1))
        theWays += dfs_area(map, visited, x, y+1); // down
    
    return theWays;
}

int main(int argc, const char * argv[]) {
    
    vector<vector<int>> map = {
        {0, 0, 0, 1, 1, 0, 0},
        {0, 0, 0, 1, 1, 0, 0},
        {0, 1, 1, 1, 1, 1, 1},
        {1, 0, 0, 1, 0, 0, 0},
        {1, 0, 0, 1, 0, 0, 0},
    };
    
    print_map("MAP", map);
    cout << endl;
        
    // 최대 넓이 영역 크기 구하기
    {
        vector<vector<int>> visited(map.size(), vector<int>(map[0].size()));
        
        int max_area = 0;
        // 모든 노드의 최대 넓이를 구합니다.
        for(int y=0;y<map.size();y++){
            for(int x=0;x<map[0].size();x++){
                if(map[y][x] == 1) continue;
                if(visited[y][x] == 1) continue;
                
                auto area = dfs_area(map, visited, x, y);
                if(max_area < area) max_area = area;
            }
        }
        
        cout << "Max Area Size : " << max_area << endl << endl;
        
        print_map("VISTED", visited);
    }
    
    // 특정지점에서 넓이 구하기 (1,1)
    {
        vector<vector<int>> visited(map.size(), vector<int>(map[0].size()));

        int x = 1, y = 1;
        auto area = dfs_area(map, visited, x, y);
        cout << "Area Size from (" << x << "," << y << ") is " << area << endl << endl;

        print_map("VISTED", visited);
    }

    
    return 0;
}

문자열 리스트가 아래와 같이 존재 할때 

["a", "x", "n", "na", "b", "ba"]

"banana"로 조합되는 조합의 합은? ( 중복 사용 허용 )

#include <iostream>
#include <vector>
#include <string>
using namespace std;

const string target = "banana";

int combination(vector<string> & data, const string & comb, vector<string> & results){
    int found = 0;
    for(auto itr=data.begin();itr!=data.end();itr++){
        vector<string> new_results(results);

        string new_comb = comb + *itr;
        if(new_comb.size() > target.size())
            continue;;
        
        auto p = target.find(new_comb);
        if(p != 0) continue;
        
        new_results.push_back(*itr);
        
        if(new_comb.size() == target.size()){
            cout << "FOUND (" << new_comb << ") : ";
            for(auto i=new_results.begin(); i!=new_results.end();i++){
                cout << *i;
                if(i+1 != new_results.end()){
                    cout << " - ";
                }
            }
            cout << endl;
            
            found++;
            continue;
        }
        
        found += combination(data, new_comb, new_results);
    }
    return found;
}

int main(int argc, const char * argv[]) {
    vector<string> data = {
        "a", "x", "n", "na", "b", "ba"
    };
    
    vector<string> results;
    
    int result_count = combination(data, "", results);
    cout << "result_count : " << result_count << endl;
    
    return 0
}

결과

FOUND (banana) : b - a - n - a - n - a
FOUND (banana) : b - a - n - a - na
FOUND (banana) : b - a - na - n - a
FOUND (banana) : b - a - na - na
FOUND (banana) : ba - n - a - n - a
FOUND (banana) : ba - n - a - na
FOUND (banana) : ba - na - n - a
FOUND (banana) : ba - na - na

result_count : 8

Recursive는 상당히 많은 알고리즘 문제나 면접문제에 나오는 알고리즘 이지만 사실 거시적 소프트웨어 구현측면에서는 잘 사용하지 않는 기법이다. 이유는 

• 사용되는 메모리 스택의 크기를 가늠하기 어렵고 
• 스택 오버플로을 컨트롤하기 어렵다.
• 모니터링 또한 어렵다.

위의 내용을 이해하기 위해 recursive가 무언가에 대해 얘기하자면... 유명한 N!을 구하는 프로그램을 짜보자

N! = N * (N-1) * (N-2) * ... * 2 * 1

이걸 조금 바꿔보면 

N! = N * (N-1)! 

이지용?

이를 코드로 구현하면 ...

int factorial(int n){
    if(n == 1) return 1;
    return n * factorial(n-1)
}

N!를 구하는 문제가 간단한 4줄로 구현되었다. 

이코드에 stack의 S도 나오지 않았지만 실제는 stack이 사용되었다.

compiler는 function call시 현재의 argument를 stack에 저장하고 새로운 function으로 진입한다.

함수가 리턴되면 저장된 argument를 pop하여 현재의 local 변수들도 대체하고 연산을 수행한다.

결국은 n==1이 될때까지 stack에 저장하고 순차적으로 n!를 계산한다.

여기서 문제는 stack은 compiler에 의해 관리된다는 점이고 heap영역과 공유되기 때문에 깊이가 깊어지면 stack overflow과 발생하고 panic에 빠지는데 control할수있는 방법이 없다. 실행되는 시점에 남은 stack영역을 check하기도 쉽지 않으며 ... abort또한 어렵다.

배보다 배꼽이 더 큰 상황???

사실 N!의 경우 for문으로 간단히 계산할수있지만 recursive와 stack에 대한 내용이므로 어렵게 stack을 이용한 방법으로 바꿔 보겠다.

void push(int n);
int pop(); // returns -1 if stack is empty

int factorial(int n){
    while(n > 1){
    	push(n--);
    }
    
    int n;
    int result = 1;
    while((n=pop()) > 0){
    	result *= n;
    }
    
    return result;
}

n==1이 될때까지 stack에 넣은후 반대순서로 pop하여 곱하는 간단하고 비효율적(?!!)인 코드입니다.

recursive와의 차이점은 stack이 user level에 관리되고 overflow시 user level에서 관리가 가능하다는 점이 다름니다.

실제로 실무에서는 user level에 관리되는 형태로 많이 쓰입니다.

개념만 이해합시다. 실무에서는 응용력!! 이니까.!!!

PS : 실제로 N!를 구현한다면 단순히 for loop를 사용할 껍니다.

int factorial(int n){
    int result = 1;
    for(int i = 2; i <= n; i++){
    	result = result*i;
    }
    return result;
}