꼰대 개발자~

과거에 서해대고 계측관리에 사용했던 framework ( 물리엔진 )입니다. 사용하기 쉽고 수 많은 예제와 거의 모든 기능을 담고 있습니다. 요즘은 Unreal이 대세지만 수십년을 꾸준히 관리되어온 프로젝트인만큼 초심자에게는 좋은 자료가 될듯합니다.

https://irrlicht.sourceforge.io/

실제 응용 프록젝트는 여기를 참조하세요

 https://dooli98.tistory.com/m/3

문자열 "aaabcabcab" sub string 중 가장 긴 중복 문자열 찾기

void max_length_duplicated_test(){
    const string target = "aaabcabcab";
    
    string max_str = "";
    for(auto i=0; i<target.size();i++){
        for(auto j=1; j<=target.size()-i;j++){
            string sub = target.substr(i, j);
            
            auto p = target.find(sub, i+1);
            if(p != string::npos){
                //cout << "FOUND : " << sub << endl;
                if(max_str.size() < sub.size())
                    max_str = sub;
            }
        }
    }
    
    cout << "max str : " << max_str << endl;
    
}

결과

max str : abcab

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

["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

요즘 코딩테스트가 대중화되면서 graph traversal 에 대한 문제가 많이 나오는것 같다. 좀 완벽히 이해 하고자 해본다.

graph와 tree traversal에 대한 간단한 내용은 [Algorithm] Graph & Tree 읽어보면 좋을듯하고 이글에서는 graph traversal에 대해 구체적으로 구현하고 응용해 보겠다.

문제

아래와 같은 미로가 존재하고 'S'에서 시작하여 'E'로 이동합니다.  "▒"은 벽으로 이동 할 수 없습니다.

사전 정의

다음의 설명들에 사용된 코드들은 아래와 공통 코드를 사용합니다. 

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;
}

int main(int argc, const char * argv[]) {
    vector<vector<int>> map = {
        {0, 1, 0, 0, 0, 0, 0},
        {0, 1, 0, 1, 0, 1, 0},
        {0, 0, 0, 0, 0, 1, 0},
        {1, 1, 1, 1, 0, 1, 0},
        {1, 1, 1, 1, 0, 0, 0},
    };
    
    print_map("MAP", map);
    cout << endl;

    {
        cout << "<BFS BY QUEUE>" << endl << endl;
        vector<vector<int>> visited(map.size(), vector<int>(map[0].size()));
        queue<shared_ptr<struct location>> q; bfs(map, visited, q);
    }
    cout << endl;
    {
        cout << "<DFS BY STACK> " << endl;
        stack<shared_ptr<struct location>> s;
        vector<vector<int>> visited(map.size(), vector<int>(map[0].size()));
        dfs(map, visited, s);
    }
    cout << endl;
    {
        cout << "<DFS BY RECURSIVE>" << endl;
        vector<vector<int>> visited(map.size(), vector<int>(map[0].size()));
        dfs_recursive(map, visited, shared_ptr<location>(new location(0, 0, nullptr)));
    }
    cout << endl;
    {
        cout << "<DFS ALL BY RECURSIVE>" << endl;
        vector<vector<int>> visited(map.size(), vector<int>(map[0].size()));
        vector<vector<int>> record(map.size(), vector<int>(map[0].size()));
        auto count = dfs_recursive_all(map, visited, record, shared_ptr<location>(new location(0, 0, nullptr)));
        cout << "total path : " << count << endl << endl;
        
        print_visited("[VISITED]", map, record);
    }
    cout << endl;

    return 0;
}

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;
            }
            
            if(x == 0 && y == 0) ch = "S";
            else if(x == width-1 && y == height-1) ch = "E";
            
            cout << ch ;
            if(x != width-1)
                cout << " ";
        }
        cout << "│" << endl;
    }
    for(int x=0;x<width*2+1;x++)cout << "─"; cout << endl;
}

void print_visited(const string & title, vector<vector<int>> & map, vector<vector<int>> & visited){
    vector<vector<int>> visited_map = map;
    for(auto y=0;y<map.size();y++){
        for(auto x=0;x<map[0].size();x++){
            if(visited[y][x] == 1)
                visited_map[y][x] = 9;
        }
    }
    print_map(title, visited_map);
    cout << endl;
}

void print_result(vector<vector<int>> & map, vector<vector<int>> & visited, shared_ptr<location> & p, bool show_visited = true){
    vector<vector<int>> found_path = map;
        
    auto temp = p;
    while(temp != nullptr){
        found_path[temp->y][temp->x] = 9;
        temp = temp->prev;
    }
    print_map("PATH", found_path);
    
    
    if(show_visited) print_visited("VISITED", map, visited);
}

DFS (Depth First Search)

DFS는 진행할수있는 노드부터 먼저 search하는 알고리즘입니다. 전문적으로하면 하위노드를 먼저 search 해 나간다는것이고 하위노드를 더이상 search 할수없을때 진행방향과 반대로 돌아와야 합니다. 그래서 stack을 사용합니다.

일단 코드를 한번 봅시다.

void dfs(vector<vector<int>> & map, vector<vector<int>> & visited, stack<shared_ptr<location>> & s){
    int width = (int)map[0].size();
    int height = (int)map.size();
    
    s.push(shared_ptr<location>(new location(0, 0, nullptr)));
    while(!s.empty()){
        auto p = s.top(); s.pop();
        
        int x = p->x, y = p->y;
        
        visited[y][x] = 1;
        
        if(x == width - 1 && y == height - 1){
            print_result(map, visited, p);
            return;
        }
        
        if(moveable(map, visited, x-1, y)) s.push(shared_ptr<location>(new location(x-1, y, p))); // left
        if(moveable(map, visited, x+1, y)) s.push(shared_ptr<location>(new location(x+1, y, p))); // right
        if(moveable(map, visited, x, y-1)) s.push(shared_ptr<location>(new location(x, y-1, p))); // up
        if(moveable(map, visited, x, y+1)) s.push(shared_ptr<location>(new location(x, y+1, p))); // down
        
    }
}

스택을 사용해서 깊이우선 탐색을 해보았습니다. 그런데 출력값이 이상합니다.

탐색결과	방문지

짧은 길을 놔두고 빙빙 돌아갔습니다.

"DFS는 계속 앞으로 파 나아가기 때문에 최적의 길을 찾아주지는 않는다"라는 걸 알 수 있습니다.

좀더 간단한 실험을 위해서 재귀적으로 바꿔보겠습니다. (stack을 사용하면 recursive로 바꿀 수 있다. Stack과 Recursive을 참조하세요.) 

void dfs_recursive(vector<vector<int>> & map, vector<vector<int>> & visited, shared_ptr<location> p){
    int width = (int)map[0].size();
    int height = (int)map.size();
    
    int x = p->x, y = p->y;
    
    visited[y][x] = 1;
    
    if(x == width - 1 && y == height - 1){
        print_result(map, visited, p);
        return;
    }
    
    
    if(moveable(map, visited, x-1, y))
        dfs_recursive(map, visited, shared_ptr<location>(new location(x-1, y, p))); // left
    if(moveable(map, visited, x+1, y))
        dfs_recursive(map, visited, shared_ptr<location>(new location(x+1, y, p))); // right
    if(moveable(map, visited, x, y-1))
        dfs_recursive(map, visited, shared_ptr<location>(new location(x, y-1, p))); // up
    if(moveable(map, visited, x, y+1))
        dfs_recursive(map, visited, shared_ptr<location>(new location(x, y+1, p))); // down
}

엇 근데 결과값이 다름니다.

탐색결과	방문지

stack형은 갈수있는 모든 경로에 대해 stack에 push하고 찾고 recursive는 stack에 현재를 push하고 바로 하위노드를 찾기 때문에 결과가 다를뿐 최적의 경로를 찾지 못하는것은 같네요.

결국은 DFS는 기본적으로 모든 node를 방문하지만 유일한 최적의 경로를 찾아주지는 못하는구나... 

DFS로 하나의 경로를 찾는건 의미 없구나... 그럼 DFS는 완전 탐색이지 그럼 모든 경로의 수를 구할수 있겠구나. 

stack에서 pop할때 현재 위치의 visited flag를 지우면 더이상 진행경로가 없을때 백트렉킹하여서 다른 경로를 계속 찾아서 모든 경로를 방문한다는걸 이용해서 S->E로 가는 모든 경로를 찾아 봅시다.

int dfs_recursive_all(vector<vector<int>> & map, vector<vector<int>> & visited, vector<vector<int>> & record, shared_ptr<location> p){
    int width = (int)map[0].size();
    int height = (int)map.size();
    
    int x = p->x, y = p->y;
    
    visited[y][x] = 1;
    record[y][x] = 1;
    
    int theWays = 0;
    if(x == width - 1 && y == height - 1){
        print_result(map, visited, p, false);
        theWays += 1;
    }
    
    if(moveable(map, visited, x-1, y))
        theWays += dfs_recursive_all(map, visited, record, shared_ptr<location>(new location(x-1, y, p))); // left
    if(moveable(map, visited, x+1, y))
        theWays += dfs_recursive_all(map, visited, record, shared_ptr<location>(new location(x+1, y, p))); // right
    if(moveable(map, visited, x, y-1))
        theWays += dfs_recursive_all(map, visited, record, shared_ptr<location>(new location(x, y-1, p))); // up
    if(moveable(map, visited, x, y+1))
        theWays += dfs_recursive_all(map, visited, record, shared_ptr<location>(new location(x, y+1, p))); // down


    visited[y][x] = 0;
    
    return theWays;
}

탐색결과	방문지
total path : 4

S->E로 가는 모든 경로를 찾았고 가능한 모든 노드를 방문했습니다.

BFS (Breadth First Search)

DFS는 모든 경로를 찾아주지만 유일한 최적의 경로를 찾지는 못합니다. BFS은 갈수있는 모든 경우들을 적어두고 순차적으로 한번씩 방문하는경우로 Queue를 사용합니다. 항상 처음에 최단경로를 찾아줍니다.

void bfs(vector<vector<int>> & map, vector<vector<int>> & visited, queue<shared_ptr<struct location>> & q){
    int width = (int)map[0].size();
    int height = (int)map.size();
    
    q.push(shared_ptr<location>(new location(0, 0, nullptr)));
    while(!q.empty()){
        auto p = q.front(); q.pop();
        
        int x = p->x, y = p->y;
        
        visited[y][x] = 1;

        if(x == width - 1 && y == height - 1){
            print_result(map, visited, p);
            return;
        }
        
        if(moveable(map, visited, x, y-1)) q.push(shared_ptr<location>(new location(x, y-1, p))); // up
        if(moveable(map, visited, x, y+1)) q.push(shared_ptr<location>(new location(x, y+1, p))); // down
        if(moveable(map, visited, x-1, y)) q.push(shared_ptr<location>(new location(x-1, y, p))); // left
        if(moveable(map, visited, x+1, y)) q.push(shared_ptr<location>(new location(x+1, y, p))); // right
    }
}

위의 코드를 실행해보면 left-right-up-down의 순서에 상관없이 최단거리를 찾아 줍니다.

탐색결과	방문지

최단 경로만큼 다른 노드를 방문했지만 유일한 최단 경로를 찾았습니다.

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

//
//  main.cpp
//  path_finder
//
//  Created by Jack Kim on 2023/06/01.
//

#include <iostream>
#include <vector>
#include <iomanip>
#include <queue>
#include <string>
#include <ostream>
#include <stack>
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) {}
};

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;
            }
            
            if(x == 0 && y == 0) ch = "S";
            else if(x == width-1 && y == height-1) ch = "E";
            
            cout << ch ;
            if(x != width-1)
                cout << " ";
        }
        cout << "│" << endl;
    }
    for(int x=0;x<width*2+1;x++)cout << "─"; cout << endl;
}

void print_visited(const string & title, vector<vector<int>> & map, vector<vector<int>> & visited){
    vector<vector<int>> visited_map = map;
    for(auto y=0;y<map.size();y++){
        for(auto x=0;x<map[0].size();x++){
            if(visited[y][x] == 1)
                visited_map[y][x] = 9;
        }
    }
    print_map(title, visited_map);
    cout << endl;
}

void print_result(vector<vector<int>> & map, vector<vector<int>> & visited, shared_ptr<location> & p, bool show_visited = true){
    vector<vector<int>> found_path = map;
        
    auto temp = p;
    while(temp != nullptr){
        found_path[temp->y][temp->x] = 9;
        temp = temp->prev;
    }
    print_map("PATH", found_path);
    
    
    if(show_visited) print_visited("VISITED", map, visited);
}

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 bfs(vector<vector<int>> & map, vector<vector<int>> & visited, queue<shared_ptr<struct location>> & q){
    int width = (int)map[0].size();
    int height = (int)map.size();
    
    q.push(shared_ptr<location>(new location(0, 0, nullptr)));
    while(!q.empty()){
        auto p = q.front(); q.pop();
        
        int x = p->x, y = p->y;
        
        visited[y][x] = 1;

        if(x == width - 1 && y == height - 1){
            print_result(map, visited, p);
            return;
        }
        
        if(moveable(map, visited, x, y-1)) q.push(shared_ptr<location>(new location(x, y-1, p))); // up
        if(moveable(map, visited, x, y+1)) q.push(shared_ptr<location>(new location(x, y+1, p))); // down
        if(moveable(map, visited, x-1, y)) q.push(shared_ptr<location>(new location(x-1, y, p))); // left
        if(moveable(map, visited, x+1, y)) q.push(shared_ptr<location>(new location(x+1, y, p))); // right
    }
}

void dfs(vector<vector<int>> & map, vector<vector<int>> & visited, stack<shared_ptr<location>> & s){
    int width = (int)map[0].size();
    int height = (int)map.size();
    
    s.push(shared_ptr<location>(new location(0, 0, nullptr)));
    while(!s.empty()){
        auto p = s.top(); s.pop();
        
        int x = p->x, y = p->y;
        
        visited[y][x] = 1;
        
        if(x == width - 1 && y == height - 1){
            print_result(map, visited, p);
            return;
        }
        
        if(moveable(map, visited, x-1, y)) s.push(shared_ptr<location>(new location(x-1, y, p))); // left
        if(moveable(map, visited, x+1, y)) s.push(shared_ptr<location>(new location(x+1, y, p))); // right
        if(moveable(map, visited, x, y-1)) s.push(shared_ptr<location>(new location(x, y-1, p))); // up
        if(moveable(map, visited, x, y+1)) s.push(shared_ptr<location>(new location(x, y+1, p))); // down
        
    }
}

void dfs_recursive(vector<vector<int>> & map, vector<vector<int>> & visited, shared_ptr<location> p){
    int width = (int)map[0].size();
    int height = (int)map.size();
    
    int x = p->x, y = p->y;
    
    visited[y][x] = 1;
    
    if(x == width - 1 && y == height - 1){
        print_result(map, visited, p);
        return;
    }
    
    
    if(moveable(map, visited, x-1, y))
        dfs_recursive(map, visited, shared_ptr<location>(new location(x-1, y, p))); // left
    if(moveable(map, visited, x+1, y))
        dfs_recursive(map, visited, shared_ptr<location>(new location(x+1, y, p))); // right
    if(moveable(map, visited, x, y-1))
        dfs_recursive(map, visited, shared_ptr<location>(new location(x, y-1, p))); // up
    if(moveable(map, visited, x, y+1))
        dfs_recursive(map, visited, shared_ptr<location>(new location(x, y+1, p))); // down
}

int dfs_recursive_all(vector<vector<int>> & map, vector<vector<int>> & visited, vector<vector<int>> & record, shared_ptr<location> p){
    int width = (int)map[0].size();
    int height = (int)map.size();
    
    int x = p->x, y = p->y;
    
    visited[y][x] = 1;
    record[y][x] = 1;
    
    int theWays = 0;
    if(x == width - 1 && y == height - 1){
        print_result(map, visited, p, false);
        theWays += 1;
    }
    
    if(moveable(map, visited, x-1, y))
        theWays += dfs_recursive_all(map, visited, record, shared_ptr<location>(new location(x-1, y, p))); // left
    if(moveable(map, visited, x+1, y))
        theWays += dfs_recursive_all(map, visited, record, shared_ptr<location>(new location(x+1, y, p))); // right
    if(moveable(map, visited, x, y-1))
        theWays += dfs_recursive_all(map, visited, record, shared_ptr<location>(new location(x, y-1, p))); // up
    if(moveable(map, visited, x, y+1))
        theWays += dfs_recursive_all(map, visited, record, shared_ptr<location>(new location(x, y+1, p))); // down


    visited[y][x] = 0;
    
    return theWays;
}


int main(int argc, const char * argv[]) {
    vector<vector<int>> map = {
        {0, 1, 0, 0, 0, 0, 0},
        {0, 1, 0, 1, 0, 1, 0},
        {0, 0, 0, 0, 0, 1, 0},
        {1, 1, 1, 1, 0, 1, 0},
        {1, 1, 1, 1, 0, 0, 0},
    };
    
    print_map("MAP", map);
    cout << endl;

    {
        cout << "<BFS BY QUEUE>" << endl << endl;
        vector<vector<int>> visited(map.size(), vector<int>(map[0].size()));
        queue<shared_ptr<struct location>> q; bfs(map, visited, q);
    }
    cout << endl;
    {
        cout << "<DFS BY STACK> " << endl;
        stack<shared_ptr<struct location>> s;
        vector<vector<int>> visited(map.size(), vector<int>(map[0].size()));
        dfs(map, visited, s);
    }
    cout << endl;
    {
        cout << "<DFS BY RECURSIVE>" << endl;
        vector<vector<int>> visited(map.size(), vector<int>(map[0].size()));
        dfs_recursive(map, visited, shared_ptr<location>(new location(0, 0, nullptr)));
    }
    cout << endl;
    {
        cout << "<DFS ALL BY RECURSIVE>" << endl;
        vector<vector<int>> visited(map.size(), vector<int>(map[0].size()));
        vector<vector<int>> record(map.size(), vector<int>(map[0].size()));
        auto count = dfs_recursive_all(map, visited, record, shared_ptr<location>(new location(0, 0, nullptr)));
        cout << "total path : " << count << endl << endl;
        
        print_visited("[VISITED]", map, record);
    }
    cout << endl;

    return 0;
}

Tree와 Graph에 대해 알아보고 실무에서는 거의 쓰이지 않는 알고리즘 문제들을 풀어보고자 한다.

사실 개념만 이해하고 기 구현된 라이브러리들을 사용하면 된다. ( 있는걸 알아야 찾아서 쓰지 )

Tree

• What is this?
  • 방향을 가지는 비순환 구조 
  • Node와 Edge로 구성
• Searching
  • Preorder
    • 왼쪽 자식노드부터 오른쪽 자식 노드까지 탐색
    • recursive하게 간단 구현
  • Inorder
    • 맨 왼쪽이 노드부터 탐색 시작
    • 탐색이 끝나면 루트를 거처 오른쪽 노드로 이동
    • 탐색 계속
  • postorder
    • 맨 왼쪽 노드부터 탐색시작
    • 탐색이 끝나면 루트를 거치지 않고 노드로 이동
    • 모든 하위노드 탐색이 끝나면 루트 탐색
• Binary Searching Tree
  • 각 노드가 유일키를 가질때
  • 루트노드의 왼쪽 서브 트리는 루트보다 작은값으로 이루어짐
  • 루트노드의 오른쪽 서브 트리는 투트보다 큰 값으로 이루어짐
  • 시간복잡도는 O(N)으로 빠른 서치가 가능
  • Building과 Searching이 동시에 이루어져 빠름
  • 규형잡힌 구조가 아닐때는 비효율적

Graph

• What is this?
  • Vertical (node)와 Edge로 구성
  • 순환 구조
  • 방향없음
• Searching
  • DFS ( 깊이 우선 탐색 )
    • 하위 노드들을 먼저 탐색하는 구조
    • 하위 노드들을 추상화하여 recursive가 가능한 구조
    • stack (recursive)를 이용하여 구현이 간단!
  • BFS ( 넓이 우선 탐색 )
    • 인접한 노드들을 먼저 탐색하는 구조
    • 미지의 하위탐색 노드들일 존재하므로 queue를 이용하여 기록 및 탐색 
    • 완전탐색

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;
}

2006년에 SI회사에 있을때 썻던글을 수정없이 올렸습니다. 참고하세요.

퍼포먼스의 최고의 화두는 누가 머라고 해도 DISK IO다. 컴퓨팅시스템에서 상대적으로 가장느린놈이 이놈이다. SSD와 같은 메모리 디스크가 있지 않느냐라고 얘기하는 사람이 있다면 지금당장 뒤로가기 버튼을 누루는것이 정신건장에 유익하겠다.

다스크에 즉 영구저장장치의 제1의 요구사항은 영구성이다. 전원이 끊어져도 저장한데이타는 유지되어야 한다. 그래서 항상 운영체계(KERNEL) 또는 시스템 개발자는 디스크에 정확히 쓰여졌는지 확인해야한다 또한 디스크 같이 대용량 데이타를 필요에 따라 쉽고 빠르게 잡근하기위에 파일이나 디렉토리와 같은 개념(INODE)으로 인덱싱하는데 이 인덱스와 데이타가 불일치하게되면 디스크의 기본기능을 못하는 쓰레기가 된다. 그래서 물리적인 속도뿐만 아니라 무결성 측면에서도 많은 코스트를 감수할수밖에는 없는것이다.

아이폰과 갤럭시를 비교해보자 하드웨어사양은 아이폰이 딸리는데도 불구하고 아이폰이 더 빠르다고 느껴지지 않는가? 여러가지 이유가 있겠지만 가장 근원적인 이유는 배터리 탈착이다. 디스크 얘기하다가 왠 배터리? 위에서 얘기했지만 디스크는 어떤한 상황이 와도 데이타가 보존 되어야한다. 그런데 포터블 기기라는 특수한 상황이기 때문에 사용자가 데이타 저장시 디스크에 저장된것이 확인되어야한다. 사용자가 언제 배터리를 빼버릴지 떨어뜨릴지 알수가 없기 때문이다.

그런데 배터리를 단단히 고정하고 사용자가 배터리를 임의데로 뺄수없게 한다면? 모든 즉시성에서 벗어날수있게 되는것이다 시스템이 바쁠때 메모리에 저장해 뒀다가 한가할때 디스크에 쓸수있게 되는것이다. 얼마나 퍼포먼스가 개선되겠냐 하겠지만 아주아주 큰 퍼포먼스 차이를 느낄수있는것이 이방법이다(아주 큰 캐쉬를 사용할수있는것또한 이방법이다)

그럼 원론으로 돌아와서 그래서 어쩌라는것이냐?

결론부터 말하면 디스크 IO를 줄이라는것이다. 위에 얘기한것처럼 디스크는 해당데이타 즉 파일의 위치를 칮는데 많은 코스트를 소요한다. 그러므로 많은데이타를 모아서 한번에 쓰고 읽는 작업을 해야한다는것이다.

예를들어 어떤 스트림으로 부터 부정기적 데이타가 유입된다하면 그때 그때마다 디스크에 저장하는것이 코드상으로 간결하고 편리할것이다. 하지만 최악은 경우 스트림에서 1바이트씩 1기가의 데이타가 들어온다면 시스템은 사망할것이 자명하다.

그럼 몇가지 포인트를 잡아 보겠다.

0. 섹터

   : H/W와 성능은 일체다. H/W의 특성을 모르는 상황에서 성능개선은 뜬구름 잡는 얘기다. 섹터는 디스크에 한번에 써넣고 읽는 데이타 단위다. 즉 섹터보다 작은 데이타도 한 섹터만큼의 영역을 가지며 섹터보다 큰 데이타는 여러개의 섹터를 소유한다. 그리고 이 섹타들의 정보를 보관하는것이 I-NODE다. 일반적으로 HDD는 512KB, Flash Memory는 4096KB를 섹터로 가진다.

1. USER LEVEL (사용자 레벨)

   : FILE I/O중 USER LEVEL 사용상 편리한 메타데이타와 기능들을 포함한다. 물론 USER LEVEL 함수들은 KERNEL LEVEL 함수들을 호출한다. 간단히 파일입출력이 필요하다면 간단히 아래와 같이 처리할수 있다.

위의 함수들은 USER LEVEL이다. I-NODE Sync라든가 캐쉬처리라든가하는 문제를 Default또는 지정된 방식으로 자체 처리한다. 개발자들은 신경쓸것이 별로 없다. 이말은 돌려서 다시 말하면 성능개선할 부분도 많이 않다는 것을 의미한다. 하지만 여기에도 성능개선 방법은 존재한다.

각각의 버퍼를 만들어서 조각난 데이타 입출력을 섹터크기만큼 모아서 한꺼번에 써넣는것이다. 물론 함정은 존재한다. 버퍼에만 데이타가 존재할때 비정상 종료를 했을때 데이타가 날라갈수 있는 최악의 경우이다. 시스템이 비정상 종료시 파일 데이타 또한 의미가 없거나 비정상종료에 대응할수 있는 H/W 시스템일 갖추어진 시스템에서 사용할수 있겠다.

2. KERNEL LEVEL (시스템 레벨)

   : DISK I/O는 언제나 KERNEL을 거친다. 최고의 성능을 내고자한다면 언제나 KERNEL LEVEL의 함수들을 사용하여 최적의 모듈/함수를 구축하는것이 하나의 방법일 것이다.

--> 작성중입니다.

2006년에 SI회사에 있을때 썻던글을 수정없이 올렸습니다. 참고하세요.

요즘 세상에는 하드웨어가 발전되고 최적의 알고리즘들이 모듈화 되어있어서 퍼포먼스 튜닝에 대한 수요가 많이 없다. 또한 퍼포먼스 튜닝은 하드웨어, 운영체계, 컴파일러,프로토콜등의 구조를 모르고서는 구현할 수 없는것이 바로 그것이기 때문에 사실 시도 자체도 않하는 경우가 많다. 그렇지만 최고의 개발자를 꿈꾼다면 퍼포먼스와 메모리 최적화에 대한 개발습관을 들이고 끊임없이 시스템 구조에 대한 연구없이는 선주자들이 주는 콩고물이나 주워먹는 개발자가 될수밖에는 없다

필자의 예를들면 1990년대에는 PDA라고하는 지금의 스마트폰에서 폰기능만 뺀 기기들이 있었다 지금의 기기들하고는 비교도 않될정도의 낮은 사양이었고 지원되는 개발툴 주변기기들도 형편없었다. 그래서 하드웨어를 알아야 했고 운영체제 특성을 알아야했다. 안드로이드가 등장한 시기까지 나를 찿는 업체들은 줄을 섰다. 안드로이드부터 시작한 개발자들은 안드로이드 프래임웍이 재공하는 수천가지 기능들이 당연한거라고 생각하겠지만 사실 수년동안 모바일 또는 포터블 기기를 개발한 사람들이 아주쉽게 시간이 많이 드는 기능들을 프래임웍속에 숨겨놓았기 때문에 지금 안드로이 개발자들이 자바 개발자들과 같은 대우를 받고 있는것이다.

필자 얘기하고 싶은것은 PDA시절을 얘기하는것이다. 사실 퍼포먼스와 메모리 최적화를 고려하지않으면 왠만한 시스템은 탑제될수없었다. 그래서 나에대한 유니크는 컷다

혹자는 말할것이다 안드로이드와 아이폰이 대세고 그걸하면 되는거 아니냐고 PDA시절에는 WINDOWS CE가 대세였다. 지금 그 개발자들 설곳이 없다(애플의 OBJECTIVE C에 대해서도 할말은 많지만 퍼포먼스 튜닝에서 다룰 부분은 아니고)

혹자는 하드웨어가 발전했는데 자꾸 옛날얘기를 하느냐고 할수도 있을듯하다. 하드웨어가 발전할수록 데이타도 늘어나고 있다는것이다. 구글의 무인자동차? 인고지능? 이거다 데이타와의 싸움이다.

1클럭의 시간 요즘 하드웨어에서는 시간으로 환산도 않되지만 간은 작업을 수백만번 한다면 유의미한 시간이 될것이다. 앞으로하는 강좌를 잘 인지하여 개발시 습관을 들이기 바란다