푸념! 요즘은 과거 "성문법", "맨투맨"식 영어 교육시대를 살아가는 느낌입니다. 영어를 배우는건지 영어를 가르치기 위한 용어를 배우기 위해 공부를 하는지 알 수 없는 시대! 용어 보다는 실제로 경험해온 개발방법에 최근 정리된 방법론들을 해석해 봅니다. 

 

CQS ( Command Query Segregation )

CQRS를 이해하기 전에 고대 개발자들도 익숙하고 잘 사용하고 있는 CQS에 대해서 이해해보자.

CQS는 Command (변경) 와 Query ( 조회 )를 분리하자는 개념입니다. 

 

뭐 간단한 것부터 설명하면... 여러분이 아주 오랫동안 사용했던... DTO, VO들로 부터 찾을수있습니다.

class DataDTO{
	public int data;
}

위와 같은 메모리지 저장소(?^^)를 정의했다 합시다.

 

지금은 DTO저렇게 정의했다가는 뒷통수 맞겠지만 2Tier 시절에는 많이들 사용했지요.

이 DTO에서 data는 미지의 정제되지 않은 데이터입니다. 극단적으로 type이라도 변경되거나 하면 심각한 리페토링 이슈를 만들어 냅니다. 

 

그래서 간단히 read와 write를 분리하는 pattern을 만들어 냅니다. 

class DataDTO{
    private int data;
    
    public void setData(int value){
    	this.data = value;
    }
    
    public void getData(){
    	return this.data;
    }
}

data의 변경은 public method을 통하여서만 변경됨을 강제됨으로 더이상 data는 미지의 데이터가 아닙니다. 정제된 데이터라고 믿을수있겟지요. 여기서 조금더 확장해 봅시다.

 

class DataDTO{
    private int data;
    
    public void setData(int value){
    	this.data = value;
    }
    
    public void setData(String value){
    	this.data = Integer.parseInt(value);
    }
    
    public void getData(){
    	return this.data;
    }
}

data 변경함수가 추가되었지만... getData() 즉 query (read)부분은 영향받지 않습니다.

 

좀더 확장하면 query 용 dto와 update용 dto를 분리하면 역시 query / update의 변경으로 부터 query logic, update logic을 보호 할수있습니다. 

 

더 얘기하고 싶지만 글이 길어 질것 같으므로 각설하고... 

 

CQRS ( Command Query Reponsibility Segregation )

CQRS는 CQS에서 입/출을 강제 함으로써 변경에 대한 시스템 영향도를 줄이고자 했는데 개발해 보니 기-승-전-DB로 DB가 모든 성능저하의 주범이 되어 버립니다. 이에 아예 DB ( Store / Model / ... ) 도 분리해서 구현하면 어떻게느냐 하는것이 CQRS되겠다.

 

입력(command) -> 입력모델

출력(query) -> 출력모델

입력모델 -> [Aggregator] -> 출력모델

 

단순히 생각해봐도 Async 개념이 들어가 버렸다. 바로 "안될꺼 같은데 수많은 문제가 발생할것 같은데?"라는 생각을 하게될것이다. 

흥미와 빠른 이해를 위해서 실시간성이 들어간 CQRS를 구현한 예를 들어 보고자 한다.

 

다음과 같은 table이 존재한다.

 

[자산]

USER ID AMOUNT
1 1000
2 2000

Application은 위의 테이블을 사용하여 물품을 사고 팔때마다 amount를 조정하여 저장한다.

 

전통적 CRUD 방식으로 프로그램을 작성하면

COMMAND READ
void update(int userId, int change){
    # select amount from [자산] for update where user id = userId
   
    int changedAmount = amount + change;
   
    if(chnageAmount < 0){
        throw "잔액이 부족합니다."
    }

    #update 자산 set amount = chnageAmount
    #commit
}
int selectAmount(int userId){
    #select amount from [자산] where user_id = userId
}

simple합니다. 회원수가 1천, 5천, 1만, 100만 이렇게 늘어나고 1초당 100만건의 거래를 하는 사용자가 등장합니다.

 

update할때마다 lock을 걸기 때문에 조회에도 문제가 생깁니다.

 

하지만 문제 없습니다. 우리는 이미 CQS 패턴으로 시스템을 구성해 놓았기 때문에 "이벤트소싱"개념을 이용해서 물리적인 model을 분리하겠습니다.

 

COMMAND를 위한 테이블 하나를 추가하겠습니다.

 

[자산변동]

SEQ USER ID CHANGE
1 1 100
2 1 -50
3 1 -20

회원의 자산의 변동사항을 기록하는 테이블 입니다.

 

프로그램을 수정합니다.

COMMAND READ
void update(int userId, int change){
    # insert into [자산변동] values () 
}
int selectAmount(int userId){
    # select [자산].amount + SUM([자산변동].change)
        where user_id = userId
}

조회에 부담이 전가되었지만 더이상 LOCK은 없습니다.

 

어? [자산변동]이 무한정 늘어나면? READ에 문제가 생기겠는데? 단연합니다.

그래서 [자산변동] 테이블을 조금 더 변경합니다.

SEQ USER ID CHANGE MERGED
1 1 100 N
2 1 -50 N
3 1 -20 N

MERGED는 자산변동사항이 [자산]테이블에 반영되었음을 얘기합니다.

또 프로그램을 수정합니다. (이벤트 소싱 프로그램도 하나 추가합니다)

 

COMMAND READ Sourcing / Syncing
void update(int userId, int change){
    # insert into [자산변동] values () 
}
int selectAmount(int userId){
    # select [자산].amount + SUM([자산변동].change)
        where user_id = userId
            and merged = 'N'
}
int sync(int userId){
    # udpate
              set [자산].amount += SUM([자산변경].amount)
              set [자산변경].merged = 'Y'
          where user_id = userId
}

 

더이상의 read의 부담도 없고 lock의 부담도 획기적으로 줄었습니다.

 

[오늘의 한줄평!] 초기 구현부터 design pattern / architecture / framework 를 잘 정립하고 가자 나중에 변경과 장애 / 성능 이슈를 얼마나 빨리 해결하여 적시에 비지니스를 완성시키는 척도가 된다!!!

 

[덧붙여서] 사실 이 변경은 최초에 시스템이 CQS를 따르지 않았다면 변경자체가 불가능한 부분이다.

문자열 "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) {}
};

 

map과 방문지 맵을 활용한 이동가능 여부 판단함수

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

 

main 함수

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;
}
[석기시대이야기] RSA (Rivest, Shamir, Adleman)가 처음 뜨기시작했을 때를 기억합니다. 대칭키 위주의 암호화가 주류를 이루는 시대에서 비대칭키 기반의 암호화(PKC) 알고리즘은 보안 업계와 개발 패러다임을 완전히 바꿔버릴만큼 발빠른 움직임이 있었고 개발과 인프라 구성에 지대한 영향을 미치고 큰 변화가 되었으며 "전자서명"이라는 개념은 인터넷뱅킹 시대를 열었으며 종국에는 "블록체인"이라는 괴물을 만들어 냈다. 솔직히 나는 RSA가 가져올 이 크나큰 변화를 전혀 인지하지 못했고 그 스트림에 편승하지 못했다.

결론! 획기적인 기초개념(알고리즘)은 크나큰 나비효과를 가져온다. 개발자라면 SRE적인 성과위주의 응용력도 좋지만 기초개념들을 익혀나가는 것을 게을리 하지 말자

PKC USAGE

간단히 PKC를 통하여 구현되는 중요기술은 암호화 전자서명이다. 

 

Encription (암호화)

대칭키의 최대 문제점은 키의 교환상의 보안헛점입니다. 어떻게든 키가 이동하게되면 탈취 가능성이 존재합니다 그러나 PKC의 입장에서는 상대에게 public key만 공유하고 public key로 암호화하여 전달되도록하면 공유된적 없는 private key를 가지고 있는 오직 나만이 암호문을 해독할수있게 되므로 간편하고 안정적인 통신이 구현된다.

 

Digital Signing (전자서명)

Encription의 반대로 보면 "전자서명"이 구현된다. RSA암호화의 반대로 생각해보면 private key로 암호화된 데이터는 public key로 복호화가 가능합니다. 이말은 public key를 가지고 있으면 전송받은 데이터가 private key를 가진자가 암호화 했다는걸 보증할수있게 되고 이를 "전자서명"이라고 합니다.

 

PKC ( Public Key Cryptography )

PKC는 공개키 기반 암호화 체계를 일컷습니다. 대표적으로 시작을 알린 RSA가있고 PKC의 꽃을 피운 ECC(Elliptic Curve Cryptography)가 있다

 

PKI ( Public Key Infrastructure )

결국은 이름에서 알수있듯이 PKI는 Public Key를 이용한 상호인증 체계정도로 볼수있습니다.

 

여기서!!!! 그냥 머릿속에 떠오릅니다. 전자서명의 헛점이 있네...

public key는 어떻게든 공유되어야 하고 누출되면?

  • 누출된 public key로 암호화하여 전송하면 수신측에서는 정상 팻킷으로 인식하게된다.
  • 극단적으로 public key를 전문에 같이보내는경우 별도의 public key와 private key를 생성하여 private key로 서명후 전송할경우 정상 서명으로 인식하게된다.

여전히 public key 공유에 대한 위험이 존재하고 이를 알고리즘으로 해결하지는 못하고 전송과 인증체계를 만들었는데 

이름하여 PKI

 

앞으로의 설명을 위한 예시를 "무역"의 예를 들어 보겠습니다.

  • 한국의 A라는 업체가 발전기하나를 일본의 B라는 업체에 수출하려고 합니다.
  • A는 아직 대금을 받지 못하였지만 B는 A업체를 신뢰하지 못하므로 대금을 송금하지 못합니다.
  • B는 신뢰할수있는 일본은행 메가뱅크에 대금을 입금하고 거래가 완료되면 송금을 부탁하는 입금증서를 발급받습니다. 이 입금증성에는 메가뱅크의 서명이 포함되어 있습니다.
  • 메가뱅크를 신뢰하는 B는 이 입금증서를 A에게 보내줍니다.
  • 그런데 A는 메가뱅크를 알지도 못하고 신뢰하지 못합니다.
  • 이에 메가뱅크는 미국의 퍼스트리퍼블릭은행에게 신뢰관계를 맺었다는 인증서를 B에게 발급해줍니다.
  • A는 메가뱅크에 입금했다는 입금증과 메가뱅크의 서명, A도 신뢰하는 퍼스트리퍼블릭의 서명이 포함된 메가뱅크 인증서를 받습니다.
  • 마침내 A는 B에게 물건을 보내줍니다.
  • 그리고 A는 메가뱅크로 부터 대금을 지불 받습니다.

 

이 예를 PKI에 적용해 보겠습니다.

  • Client는 Server로 데이터를 전송하려고 합니다.
  • Server가 private key + public key를 하나 생성하여 보내줍니다.
  • Client 전송과정에  public key가 변조되지 않았다고 확신하지 못하고 데이터를 전송하지 못합니다.
  • Server는 신뢰할수있는 기관 (CA, Certificate Authority) "A"에 public key를 제출하고 서명을 곁들인 인증서를 받습니다.
  • Server는 Client에게 이 인증서를 전송합니다.
  • Server는 Client에게 "A" CA에게 public key의 진위를 확인하라하지만 Client "A" CA를 신뢰하지 못합니다.
  • 이에 Server는 Client도 신뢰하는 "B" CA에게 인증을 받고 서명을 받습니다이를 기존 인증서에 포함하여 전송합니다.
  • Client는 "B"를 신뢰하므로 "A"도 신뢰하게 되고 public key를 신뢰하게 됩니다.
  • Client Data를 public key로 암호화 하여 전송합니다.

이와 같은 일련의 과정을 PKI라는 인증체계 입니다.

 

그런데!!!

이런 일런의 과정을 각 CA들이 각자의 방식대로 하게되면 시스템은 복잡하고 어려워 질껍니다.

이에 대한 국제 표준 규격을 만들어 놓은것이 X.509 Protocol 되겠다.

 

인증서 발급

  • 기본적으로 최상위 CA를 RootCA라고 하고 기본적으로 설치 또는 내장을 통하여 신뢰하기로 합니다.
  • 중간 CA는 RootCA로 부터 인증서를 발급받고 신뢰관계를 형성합니다.
  • 업체들은 중간 CA로부터 인증서를 발급받고 신뢰관계를 형성합니다.
  • 이를 "Chain Of Trust"라고 부르고 인증및 발급의 Clustering이 가능하게 합니다.
  • 결국은 내가 RootCA만 신뢰관계가 형성되면 다른 파생된 수많은 인증서들에 대해 신뢰관계를 형성할수있게 됩니다.

보안 연결 ( HandShaking )

  • Client는 지원하는 암호화방식, 난수 등을 서버로 전송합니다.
  • Server는 인증서 + 선택한 암호화 방식 + 난수를 Client로 전송합니다.
  • Client는 전송된 인증서를 Server가 아닌 CA를 통하여 검증합니다, 즉 Chain Of Trust에 있는지 검증합니다.
  • Client 주고받은 랜덤데이터를 활용하여 PMS(PreMaster Secret)을 생성합니다.
  • 이를 인증서의 public key로 암호화하여 전송합니다.
  • Server와 CLient는 서버난수 + 클라이언트난수 + PMS를 이용하여 대칭키를 생성합니다.
  • 서로간에 생성된 대칭키로 통신합니다.
  • 신뢰할수있는 보안연결이 생성되었습니다.

 

X.509 protocol

X.509는 PKI를 구현하기 위한 표준규격이 정의되어 있다. 자세한내용은 전자서명 인증서 표준규격 을 참조하자.

 

SSL ( Secure Socket Layer )

PKI를 이용하여 신뢰할수있는 키교환을 하고 이 키를 기반으로 신뢰할수있는 암호화 통신에 대한 프로토콜이다.  

그 구현체들은.. 너무나도 많고.. 왠만한 개발자들은 https, ssh등을 통하여 이미 쓰고 있는 기술이라고 볼수있다

 

이 모든것들 "https://www.openssl.org/"에 구현되어 있다. 그냥 가져다 쓰자!!!!

 

Forward Proxy와 Reverse Proxy에 대한 설명들을 찾아보면 너무 Devops 측면에서의 설명들이 많다 우리는 개발자 답게 코드로 이해해 보고자 한다.

 

Forward Proxy

말그대로 요청을 Forward해주는 형태의 Proxy이다. 인프라 구조는 아래와 같다고 하자.

 

[Client, IP: 10.1.1.1 ] <-> [Porxy, IP: 10.2.1.1 ] <-> [Server, IP: 10.3.1.1 ]

 

Client가 Proxy를 통하여 Server로 부터 image.png를 받아오기 위한 HTTP 요청은 아래와 같다.

GET http://10.3.1.1/resource/image.png
Host: 10.2.1.1
... 생략

실제로는 10.3.1.1에 대해 요청이지만 Host: 10.2.1.1을 통해서 가져오라는 의미로 작동한다.

Proxy Server는 요청을 수신하고 10.3.1.1로 접속하여 image.png을 받아와서 10.1.1.1로 응답한다.

 

이때 Server가 받는 요청은 아래와 같다.

GET http://10.3.1.1/resource/image.png
Host: 10.3.1.1
... 생략

위의 요청 예제를 보면 자연스럽게 forward proxy의 특성이 나오게 된다.

  • Proxy는 자신의 IP로 해당서버에 요청을 보내므로 Server는 Client의 정체를 알수없게 된다.
  • Proxy는 요청 Server와 대상 Resource를 명확히 알수있으므로 캐싱과 접근제한같은 방화벽 형태를 구성할수있다. 
  • Client 중심적이다 - 원천적으로는 Proxy는 Client의 요청을 중계하는 역할만한다.

Reverse Proxy

일반적으로 중요한 데이터를 가지는 DB, WAS Server등을 추상화하고 감추기 위한 Proxy서버를 지칭한다.

 

여기서도 인프라 구조는 같으나 Proxy만 Reverse로 바꿔보자

 

[Client, IP: 10.1.1.1 ] <-> [Porxy, IP: 10.2.1.1 ] <-> [Server, IP: 10.3.1.1 ]

 

Client가 Proxy를 통하여 Server로 부터 image.png를 받아오기 위한 HTTP 요청은 아래와 같다.

GET http://10.2.1.1/resource/image.png
Host: 10.2.1.1
... 생략

Client입장에서는 단순히 Proxy Server로 요청을 한다.

 

이때 서버가 받는 요청은 Forward Proxy와 같다.

GET http://10.3.1.1/resource/image.png
Host: 10.3.1.1
... 생략

위의 요청을 보면 자연스럽게 Reverse Proxy의 특성이 슬슬기어나온다.

  • Client는 실제 Server의 IP(정보)를 알수없다.
  • Proxy가 대상 Server를 결정하므로 LoadBalancing에 유리하다.
  • 요청 자체를 control하므로 요청을 변경하거나 TLS Termination같은 암호화처리에 컨트롤하기 쉽다.

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

+ Recent posts