lambda and functional programming;

함수형 프로그래밍의 이론적 근간은 람다대수다.

• 람다 칼큘러스는 계산 모델을 표현 하는 하나의 방법론이다.

• 튜링은 튜링머신과 튜링머신이 수행하는 절차적인 명령어들의 집합으로 계산이 무엇인지 정의 했다. 즉, 계산의 주체(튜링머신)를 explicit하게 정의 했다.

• 처치는 계산을 특정 법칙들로 심볼들을 단계별로 변화 시켜 나가는 행위로 정의 했다. 이 관점에서 계산은 수행하는 행위의 주체는 implicit하게 정의 된다.

• 하지만 두 방법 다 계산 문제 관점에서는 동일한 해를 제공할 수 있게 된다. 두 계산 모델은 동치다(Church-Turing Thesis).

• 람다 칼큘러스에서 f(x)=2x는 f=λx.2x로 표현 된다. f라는 심볼에 대응 되는 함수의 identity를 직접적으로 표현할 수 있게 되고, 그게 λx.2x가 된다.

• f가 람다 대수로 표현 가능하다면, 그 함수는 계산가능성을 가지게 된다.

• 람다 대수로 표현 가능하다면, 해당 함수는 turing computable하다. 역도 성립 된다.

• 따라서, 러프하게는 기존의 명령형 프로그래밍으로 표현된 프로그램들 또한 함수형으로 표현 가능하다. 같은 계산의 다른 표현법이다.

함수형 프로그래밍은 declarative 하다.

• 람다 칼큘러스는 튜링머신 같은 계산의 주체를 명시적으로 표현하지 않았다. 즉, 계산가능한 함수가 무엇인지 정의 하기 위해 고안 된 형식체계다.

• 따라서, 함수형 프로그래밍 또한 함수로 정의 되는 계산이 무엇이냐에 대한 것이지 수행 주체가 실행 해야 할 절차(명령)에 대한 기술을 하지 않는다.

• 단순히 계산computation이 무엇인지 그 함수적 표현 자체에만 집중하면 된다.

함수형 프로그래밍은 stateless하다.

• 튜링 머신은 stateful하다. 튜링머신에게 명령을 내리는 방법론에 기반한 프로그래밍 언어는 UTM 위에서 동작하는 튜링머신을 표현해야 하기 때문에 stateful하다.

• 반면, 함수형 프로그래밍은 stateless (해야만?) 하다. 왜냐하면, 함수형 프로그래밍의 근간이 되는 람다 칼큘러스 자체가 계산의 주체를 implicit하게 표현 했기 때문.

• 함수형 프로그래밍의 순수함수 개념도 이 람다 칼큘러스에서 정의된 계산 가능한 함수의 맥락 위에 존재 한다.

• 따라서 함수형 프로그래밍은 계산 주체의 상태에 대한 표현을 근본적으로 배제하게 된다.

OOP 또한 imperative한 프로그래밍이다.

• 절차적 + 함수와 관련 데이터를 묶어 놓음 + 묶어 놓은 객체들의 통신으로 프로그램을 구성

• 즉, 뿌리는 절차적 프로그래밍에 두고, 그걸 발전 시켜 함수를 메소드로 바꿔 클래스들의 집합으로 일종의 설계도를 만들고, 그 설계도를 RAM 위에 인스턴스 형식으로 올려 놓는 방법으로 프로그램을 만드는 방법론이기 때문.

to reactive programming;

이제 이상적인 서버를 가정해보자. 그리고 이 서버가 순수 함수들의 집합라고 가정해보자. 각 함수들은 상태를 가지지 않는다. 인풋에 대한 아웃풋만 출력하게 된다. 상태값을 가지지 않으므로 동시성 문제로부터 자유로울 수 있다.

멀티스레드 환경에서 stateful한 메모리 자원에 어떻게 프로그래밍 해야할지, race condition에 대해 고민할 필요 없이 여러 스트림을 열어 놓고 비동기적으로 처리하면 된다.

여기에 REST 아키텍쳐를 따라가면 서버 단에 상태는 존재하지 않게 된다. 데이터베이스나 외부 api에서 끌어 온 데이터를 함수적으로 처리해주는 프로그램이 될 뿐.

동시성 문제는 튜링머신을 근간으로 한 프로그래밍 언어의 성질로부터 비롯된다. 그렇다면 아예 근본부터 다른 방법론을 채택하면 어떨까? 람다 칼큘러스를 기반으로 한 함수형 프로그래밍으로 프로그램을 표현 한다면? 처음부터 racing condition문제를 최소화 할 수 있지 않을까?

다음에는 currying도 정리해보고, reative programming도 정리해보자..

REFERENCE

[1] https://helloworld.kurly.com/blog/lambda-calculus-1/ [2] https://studyingeugene.github.io/functional-programming/introduction-to-lambda-calculus/

주로 멀티 스레드를 배울 때 자주 나오는 용어. 멀티 스레딩은 프로그램의 동시성을 구현하는 방법이다.

동시성이란 두 개 이상의 단위 작업을 동시에 처리하는 것을 의미한다. 그런데 이 동시에 처리한다는 말이 좀 애매모호해서 오해가 발생한다.

두 작업이 동시에 처리된다? 그렇다면 두 프로세서에서 두 작업을 각각 처리하는 건가? 정답은 아니다.

여러 프로세서에서 여러 작업을 처리하는 건 병렬성이 성립하는지 여부이고, 동시성은 작업이 아닌 cpu를 주체로 놓고 봐야 한다.

행간을 읽자면 cpu 하나당 동시에 n개 이상의 여러 작업을 처리하는 방식이 동시성이라고 볼 수 있다.

동시성 개념을 이해해보자

목적 관점에서 보자. 동시성은 크게 두 가지 목적을 가진다.

1. cpu 사용률 optimization
2. 유저 관점에서 responsiveness

1. cpu 사용률 optimization

P1,P2 두 프로세스가 현재 돌고 있고, CPU 코어는 하나라고 가정해보자.

P1이 디스크 r/w IO 작업 시스템 콜을 보내게 되면, P1은 자동으로 wait queue로 빠지게 된다. 이 때 OS는 어떤 선택을 해야 할까? IO 작업을 blocking으로 두면 P2는 CPU에서 처리 가능함에도 불구하고, CPU를 점유할 수 없게 된다. 이 때 OS에서 센스 있게 P2로 컨텍스트 스위칭을 해주면, P1이 IO 작업 결과를 대기하는 동안 CPU는 P2를 처리할 수 있게 된다. 따라서, CPU 사용률이 올라 간다.

이 관점에서 동시성은 정해진 타임라인 위에서 P1과 P2를 효율적으로 배분하여 CPU 사용률을 높이기 위해 프로세서가 동시에 여러 작업을 바꿔가며 진행하는 것을 뜻한다.

2.responsiveness

p1...,pn까지 n개의 프로세스가 있고 CPU 코어는 하나라고 가정해보자.

이제 p1에서 pn까지 순차적으로 처리된다고 가정해보자. 그러면 p1이 끝나야 p2 작업이 수행 될 수 있고, pn은 앞의 모든 프로세스가 수행될 때까지 대기해야 한다. 자, 이제 pn이 키보드 타입 결과를 받아 velog 블로그 글을 업데이트 해주는 프로세스라고 하자. 그런데 모든 프로세스가 순차적(sequential)하게 처리된다면, 내가 지금 타이핑 하고 있는 문자가 굉장한 딜레이를 가지고 반영이 될 것이다.

이런 문제를 해결하기 위해 OS는 time-division multiplexing, 즉 특정 주기를 가지고 각 프로세스들을 interweaving해서 처리하게 된다. 최초 가정이었던 프로세서가 하나인 모델을 생각해보면, 이 프로세서가 p1...pn까지 OS 스케쥴러 알고리즘에 따라 왔다 갔다 하면서 동시에 여러 프로세스를 바꿔가며 처리 하게 된다.

이 스케쥴러 알고리즘에 우선순위를 둬서, 내가 velog에 타이핑 하고 있는 프로세스에 우선권이 부여된다면, 다른 백그라운드 프로세스가 돌고 있더라도 타이핑 하는 순간 OS가 타이핑을 반영하는 프로세스를 우선적으로 처리 해서, 사용자에 대한 프로그램의 반응성이 좋아지게 된다. 물론, 이 사용성은 컨텍스트 스위칭 비용을 댓가로 지불 하게 된다(thrashing) .

두 예시 다 cpu 하나가 동시에 여러 프로세스를 왔다 갔다 하면서 처리한다는 공통점을 가지고 있다. 즉, 동시성은 cpu와 프로세스 사이에서 1:n 관계가 있어 이걸 어떻게 전환하며 처리하는지, CS 관점에서 작업 단위의 교차실행 대한 것이고, 병렬성은 여러 프로세스(혹은 스레드, 혹은 더 넓은 범위의 작업들)가 같은 타임 t0에 동시에 처리 되는지, 물리적 의미에서 동시실행 여부에 대한 것이다.

동시성 문제

이건 어떻게 보면 교차실행에 필연적으로 따라오게 되는 문제라고 볼 수 있다.

스레드 t1,t2가 있다고 가정하자.

여기서 두 가지 염두해 둬야 할 게 있다.

1. OS가 스레드를 스케쥴링 한다.
2. 스레드 t1,t2는 공유하는 자원이 있다.

OS의 스케쥴링으로 인해 t1,t2의 코드는 여러 경우의 수로 interweaving 된다. 그리고 각 경우의 수 마다 t1의 실행코드와 t2의 실행코드가 막 뒤섞이게 되는데, 이 때 공유자원에 접근하는 코드들의 순서가 섞이게 되면 당연히 접근 순서에 따라 결과가 바뀌게 된다.

물리적인 RAM의 주소 정보는 운영체제가 관리하고, virtual memory의 주소 정보는 프로세스가 관리한다. 그렇다면 우리가 컴파일한 exe 파일에 명시되어 있는 주소 정보는 virtual memory의 주소 정보이다.

이 virtual memory 주소정보는 컴파일 시점에 확정 되며, OS가 이 확정된 virtual memory 주소를 실제 물리 주소 메모리로 매핑 해주게 된다.

그래프 탐색 dfs/bfs 

복기

outDfs에서 else return문을 넣어주지 않았다. 
해당 return문이 없으면 visited 처리가 되지 않아 계속 무한 탐색하게 된다. 

#include <bits/stdc++.h>
using namespace std; 
typedef pair<int,int> pp; 

int cnt=0;
int m,n,rnd=0; 
int prevEdgesCnt; 
int a[104][104];
int visited[104][104]; 
int dx[4] = {0,0,-1,1};
int dy[4] = {1,-1,0,0}; 
vector<pp> currMeltedCheese; 

bool outOfBound(int y, int x){
    return (y < 0 || x < 0 || x >= m || y >= n); 
} 

//outDfs
void outDfs(int y, int x){
    if( a[y][x] == 0 ) visited[y][x] = 1;//outair
    else return; //else return이 없으면 해당 노드 visited 처리가 안 돼서 무한 방문문

    for(int i=0; i<4; i++){
        int ny = y + dy[i]; 
        int nx = x + dx[i];
        if( outOfBound(ny,nx) || visited[ny][nx] ) continue; 
        outDfs(ny,nx); 
    }
}

//// isMeltable
bool isMeltable(int y, int x){
    int ny,nx; 
    for(int i=0; i<4; i++){
        ny = y + dy[i]; 
        nx = x + dx[i]; 
        if( outOfBound( ny,nx ) ) continue; 
        if( visited[ny][nx] ) return true; 
    }
    return false; 
}

void melt(){
    for(int i=1; i<n; i++){
        for(int j=1; j<m; j++){//현재 방문 중인 노드가 1이고 외부 공기와 인접해 있는 경우
            if(a[i][j] == 1){ //치즈인 경우 녹는 치즈인지 확인
                if( isMeltable(i,j) ){ //melt
                    a[i][j] = 0; 
                    currMeltedCheese.push_back( {i,j} ); 
                }
            }
        }
    }
}

void input(){
    cin >> n >> m; 
    for(int i=0; i<n; i++)
    for(int j=0; j<m; j++)
        cin >> a[i][j]; 
}

// 초기화 
void init(){
    fill(&visited[0][0], &visited[0][0] + 104 * 104, 0);
    currMeltedCheese.clear(); 
}

void solve(){
    input();
    while(true) {
        init();
        outDfs(0,0);// dfs 
        melt(); 

        // when all melted     
        if( currMeltedCheese.size() == 0 ){
            cout << rnd << "\n"; 
            cout << prevEdgesCnt; 
            break; 
        }

        rnd++;
        prevEdgesCnt = currMeltedCheese.size(); 
    }
}

int main() {
    solve();
    return 0;
}

그리디

*복기 : *

최초 풀이 당시 order by day, price로 정렬 후 각 day 마다 최대값을 뽑아냄. 하지만 day가 같더라도, 최대 price를 가지는 값들을 골라야 했음(반례 생각 x).

*fail ver : *

#include <bits/stdc++.h>
using namespace std; 
typedef pair<int,int> pp; 
typedef map<int,int> m;
void l(){ cout << " ------- " << endl;}

int n; 
vector<pp> v; 

//customSsort : order by date , price
bool cSort(const pp &a, const pp &b){
    if(a.second != b.second){//sort by day 
        return a.second < b.second; 
    }
    //sort by money
    return a.first > b.first; 
}

//input 
void i(){
    cin >> n; 
    int d,p; 
    for(int i=0; i<n; i++){
        cin >> d;
        cin >> p; 
        v.push_back({d,p});
    }
}

//solution 
void s(){
    int money=0, date=0;
    sort(v.begin(), v.end(), cSort ); 
    for(pp dp : v){
        if(date < dp.second){ 
            money += dp.first; 
            date = dp.second;//현재 날짜짜
        }
    }
    cout << money;
}

void sol(){
    i();s(); 
}

int main() {
    sol(); 
    return 0;
}

*success ver : *

priority queue를 사용해서 풀 수 있다.

1. 각 day마다, 각 대학의 pay를 pq(오름차순)에 넣어준다.
2. 해당 day보다 pq의 크기가 커지는 경우(하루 당 방문 횟수가 한 번인데 가능한 방문 횟수보다 커지는 경우)
3. pop해서 최소값을 내보낸다.

아래의 pq를 사용했다.

priority_queue<int, vector<int> ,greater<int>> pq 

1. int 값을 담고
2. underlying 자료구조는 vector이며
3. 오름차순으로 (greater)로

pq를 생성한다.

#include <bits/stdc++.h>
using namespace std; 
typedef pair<int,int> pp; 
typedef map<int,int> m;
priority_queue<int, vector<int>,greater<int>> pq; 
void l(){ cout << "------- " << endl;}
int n; vector<pp> v; 

// day 정렬 
bool cSort(const pp &a, const pp &b){
    if(a.second != b.second){//sort by day 
        return a.first < b.first; 
    }
    return a.second > b.second; //sort by money 
}

//input 
void i(){
    cin >> n; 
    int d,p; 
    for(int i=0; i<n; i++){
        cin >> p;
        cin >> d; 
        v.push_back({d,p});
    }
    sort( v.begin(), v.end() ); 
}

//solution 
void s(){
    int money=0;
    for(pp dp : v){
        pq.push(dp.second);//price 
        if(pq.size() > dp.first) pq.pop();// pop 
    }
    while(!pq.empty()){
        money += pq.top(); pq.pop();         
    }
    cout << money;
}

void sol(){
    i();s(); 
}

int main() {
    sol(); 
    return 0;
}

쉬운 문제 같았는데 오래 걸렸다. 샷건 마렵다. 중간에 또 cSort 때문에 문제가 있었는데, 이 부분 다시 확인 해봐야 겠다.

왜 ADT가 필요할까

구현체가 되는 자료구조의 인터페이스 역할을 한다. 아래 네 가지의 이점이 따라온다.

1. 모듈화 / 추상화
2. 다형성 / 유연성 확보
3. 표준화

구현체가 되는 자료구조는 개발자가 직접 구현하든, 아니면 미리 구현 되어 있는 라이브러리를 사용하든 어떤 언어를 사용하더라도 ADT의 스펙사항을 만족해야 한다.

따라서 개발자는 ADT만 알아도 자료구조의 세부구현과 관계 없이 데이터가 어떤 식으로 구축될지 개략적인 데이터 설계를 할 수 있게 된다.

ADT는 자료형의 수학적 모델링이다. 데이터가 어떻게 표현되는지에 대한 세부 사항, 즉 알고리즘과 알고리즘을 표현하는 프로그래밍 언어를 추상화하여, 데이터에 어떤 연산(operation)들을 적용할 수 있는지에 대해 정의를 해 놓은 것이다.

DS는 ADT에 정의된 operation들을 알고리즘과 특정 프로그래밍 언어를 사용해 정의한 것이다.

구조에 따라 아래와 같은 분류가 가능하다.

선형Linear :

1. stack :
   • LIFO
   • push : 스택에 원소를 집어 넣는다.
   • pop : 스택에서 원소를 꺼낸다.
   • peek : stack pointer가 가리키는 값을 확인한다.
   • isEmpty : 스택이 비어 있나 확인한다.
2. queue :
   • FIFO
   • enqueue : 큐에 항목을 추가
   • dequeue : 큐에서 항목 제거 후 반환
   • isEmpty : 큐가 비어있는지 확인
3. list :
   • 순서가 강제 된다. (extrinsic)
   • 중복이 허용된다.

비선형Non-Linear :

1. graph
2. tree
   • binary tree
     • heap

위의 자료형들은 전부 세부 구현이 누락 되어 있지만, 어떻게 동작하는지에 대한 특성과 operation들이 정의 되어 있다.

스프링 진영에서 제공해주는 인증/인가 프레임워크

인증/인가(Auth)

1. 인증Authentication : 자원에 접근하는 사용자의 신원 확인. 즉, 거수자냐 아니면 가라치는지 확인하러 온 소대장이냐 암구어(호?) 등을 사용해서 신원을 확인.

2. 인가Authhorization : 자원에 접근하는 사용자의 권한이 있는지 여부. 즉, 내부인 인 건 확인 됐는데 이 탄약고(자원)에 출입 가능한 사람이냐 아니냐. 인증이 선결 돼야 하는 개념.

현실세계에서도 인증, 인가 개념은 존재한다. 같은 개념인데 그걸 디지털 리소스에 대해 적용한 것 뿐이다.

Spring security 아키텍처

아키텍처 구조는 위와 같다. 인증/인가를 구현한 프레임워크이기 때문에 스프링 진영에서 만들어 놓은 구조를 따라 비워 놓은 걸 쏙쏙 집어 넣어주면 인증/인가 기능을 구현을 할 수 있게 된다.

스프링 진영에서 어떤 식으로 인증/인가를 구현했는지 개념을 훑어보자. 들어가기에 앞서, 객체지향의 프리즘으로 위의 구조를 바라보자.

위의 화살표들은 각 과정마다 객체들이 주고 받는 메세지라고 이해하면 될 것 같다. 각 메세지들은 순서를 가지고, 해당 순서를 거쳐서 인증/인가가 이뤄지게 된다.

따라서 위의 아키텍쳐 구조를 이해하기 위해서는

1. 구성요소(객체)
2. 구성요소들이 주고 받는 메세지

크게 두개로 또개서 생각해볼 수 있다. 1번 2번 다 알아보긴 힘드니까, 1번 객체 단위로만 큰 덩어리로 쪼개서 해석해보자.

AuthenticationFilter

HttpRequest 객체를 인터셉트해서 auth 관련 필터링을 하는 객체. Delegation Pattern을 이용해서 톰캣 서블릿 컨테이너 안에 있는 필터 체인에서, 스프링 IoC 안에 있는 FilterChainProxy로 auth 관련 필터링을 위임한다. 어차피 스프링이나 톰캣이나 하나의 JVM 위에서 같이 굴러가고 있어서 위임이 가능하다.

위의 아키텍처 구성을 보자. 크게 아래 두 개의 대구조로 쪼개진다.

1. Http 관련 요청을 처리하는 Web/Was 서버에 해당하는 Tomcat
2. 자바 어플리케이션 프레임워크 Spring Container

서버 아키텍처 구조고, 밖에서 클라이언트의 Http(s) 요청이 날아왔다고 가정하자. 클라이언트에서 요청이 날아오면 해당 요청의 java object 표현인 HttpRequest 객체가 생성 되고, 그리고 해당 Http(s) 관련 요청을 처리하는 Tomcat의 Servlet Container에서 FilterChain을 타게 된다.

위 그림을 보자면 그 Tomcat 쪽 FitlerChain을 타는 와중에, Spring Security Framework에서 auth 관련 처리를 위해, Servlet Filter 안 DelegatingFilterProxy 인터페이스의 FilterChainProxy를 구현해서, HttpRequest 객체를 납치(?)한 뒤, 스프링 진영에서 구현한 기술로 Auth 관련 체크를 하게 된다.

public class AuthenticationFilter extends UsernamePasswordAuthenticationFilter {

    ////.. some code //// 
    @Override
    public Authentication attemptAuthentication(HttpServletRequest request, HttpServletResponse response)
            throws AuthenticationException {
        String username = obtainUsername(request);
        String password = obtainPassword(request);

        if (username == null) {
            username = "";
        }
        if (password == null) {
            password = "";
        }

        UsernamePasswordAuthenticationToken authRequest = new UsernamePasswordAuthenticationToken(username, password);

        // Authenticate the user
        return authenticationManager.authenticate(authRequest);
    }

    @Override
    protected void successfulAuthentication(HttpServletRequest request, HttpServletResponse response,
                                            FilterChain chain, Authentication authResult) throws IOException, ServletException {
        // If authentication is successful, proceed with the filter chain
        chain.doFilter(request, response);
    }
}

위 클래스는 스프링 시큐리티 프레임워크의 pre-built UsernamePasswordAuthenticationFilter 클래스를 extends 하고 있다.

inheritance heirchy 타고 올라가보면 Filter 인터페이스를 구현하고 있는데, 패키지 명을 보면 jakarta.servlet의 Filter. 즉 서블릿 필터의 인터페이스다.

그런데 위와 같은 클래스들을 한 땀 한 땀 하나씩 설정해주는 건 귀찮기 때문에, 스프링 시큐리티에서는 config 설정 파일로 빼서 filter chain을 한꺼번에 설정해주는 방법을 제공해준다.

@Configuration
@EnableWebSecurity
public class SecurityConfig extends WebSecurityConfigurerAdapter {
    //// some code... ////
    @Override
    protected void configure(HttpSecurity http) throws Exception {
        http
            .authorizeRequests()
                .antMatchers("/public/**").permitAll()
                .antMatchers("/admin/**").hasRole("ADMIN")
                .anyRequest().authenticated()
                .and()
            .formLogin()
                .loginPage("/login")
                .permitAll()
                .and()
            .logout()
                .permitAll();
    }
    //// some code... ////
}

위와 같이 설정해주면 되고, HttpSecurity 클래스를 받아서 필터링 해주는데, 그럼 Servlet Container에서 Servlet Filter 타고 있는HttpRequest는 어디에 있는 거지 해서 찾아보니까, 파라메터로 받겠지 해서,

HttpSecurity를 열어 보니, RequestMatcher 클래스를 Has-a 관계로 가지고 있고, RequestMatcher를 열어 보면,

public interface RequestMatcher {
    //// some code... ////
    boolean matches(HttpServletRequest request);
    //// some code... ////
}

위와 같이 HttpServletRequest를 파라메터로 받는 걸 확인할 수 있다.

SecutriyContextHolder

• SecurityContext : 현재 실행 스레드의 보안 관련 정보와 그 메타적 맥락에 대한 정보를 담고 있다.
  • Authentication : 인증 객체. 그냥 말 그대로 인증 관련 정보를 가진다.
    • Principal : Autheticated된 User 엔티티의 정보를 담고 있다. User Entity의 Identity를 표현하는 객체
      • Credentials : Principal 객체의 인증에 관련된 정보
    • Authorities : Principal 객체의 인가에 관련된 정보

그냥 스프링 시큐리티 프레임워크에서 인증 관련 정보를 관리하기 위해 자바 오브젝트로 auth 관련 정보들을 위와 같이 표현 했다고 이해하면 될 것 같다.

REFERENCE

[1] https://mangkyu.tistory.com/76 [2] https://docs.spring.io/spring-security/reference/index.html [3] https://docs.spring.io/spring-security/site/docs/current/api/org/springframework/security/config/annotation/web/builders/HttpSecurity.html

Wikipedia:

Geometry (from Ancient Greek γεωμετρία (geōmetría) 'land measurement'; from γῆ (gê) 'earth, land', and μέτρον (métron) 'a measure')[1] is a branch of mathematics concerned with properties of space such as the distance, shape, size, and relative position of figures.

그리스 어원을 보면 land measurement. 즉, 땅을 측량하며 사람들이 만들어 낸 수학 분과라고 할 수 있다. 땅은 리얼월드, 물리적으로 존재하는 공간적 개념이고, 기하학은 해당 공간에 대한 측량(measurement)를 수행하며 인간들이 인지적으로 처리하기 쉬운 수의 개념으로 공간을 표현한 것이라고 생각하면 될 것 같다.

즉, 최초 탄생 배경부터 현실 세계의 공간이라는 개념과 분리할 수 없는 수학 분과인 것이고(어쩌면 수학의 모태일지도), geometirc한 표현은 결국 공간감각의 추상화 관점에서 접근할 수는 있어도, 공간감각과 분리해서 이해할 수 없을 것 같다.

다만 기하학은 시간의 흐름에 따라 형태,크기,거리,상대 위치 등의 개념을 넘어 대칭성, 변형, 곡률 등의 더욱 추상적인 개념을 통해 수학적 오브젝트를 공간적으로 이해할 수 있는 도구로 진화해 왔다.

수는 양을 원자적 단위로 파악할 수 있는 하위 개념인 것이고(실수는 공간으로 생각되지만), 양은 우리를 둘러 싸고 있는 리얼 월드의 근본 성질로서, 개념의 내포에 해당하는 징표들에 매핑한 후 언어적으로 다룰 수 있는 numeral로 labeling 한 뒤, 우리 머리 속에서 정의(의미론적으로)하게 된다.

그리고 그런 labeling 된 징표들을 조합하여 수학적 오브젝트를 언어적으로 구성할 수 있다. 이 때 주로 사용하는 언어는 1차 논리의 언어가 되고( 논리모델 설정 작업), 외부와 단절된 주관적 공간에서의 symbol manipulation으로 넘어가게 된다(힐베르트님!!). 물론 의미론적인 고정작업이 적확 했는지에 대한 회의는 남아 있을 것이다(우리는 객관의 본질을 믿어야 한다).

다시 말해, geometry에서 파악하고자 하는 리얼 월드의 요소는 공간이 된다. 하지만 그런 리얼 월드의 공간을 넘어, 우리 머릿 속에 존재하는 추상적인 수학적 오브젝트 또한 기하학적 분석의 대상이 될 수 있다.

선형성의 equation 표현은 아래와 같다.

$Ax+B=y$

1. equation이니까 y와 x의 동치 관계를 표현한 수식이고
2. x는 domain set, y는 range set으로
3. 각 집합은 각 집합의 interest가 되는 대상들을 포함하고
4. 둘의 관계가 x에 unary operator가 적용 되지 않은 형태로 표현된 것

그렇다면 x에 unary operator가 포함되지 않았다는 건 어떤 의미일까? y와 x의 관계가 상수 A와 B만으로 완전하게 표현됨을 뜻한다. 즉, 두 집합의 관계를 알고 싶으면 상수 A와 B의 정보만 보면 된다는 것.

상수 A,B는 물리학에서는 계수와 같은 정보가 되고, 계수는 보통 unit을 변환하는 변환계수 등의 의미를 가지게 된다.

덧붙여 unary operator가 들어가면 이 unary operator에 대한 풀이를 어떻게 해야 하는지에 대한 부가적인 정보가 더 필요하다. 즉, 해를 찾기 더 어려워진다.

단순히 생각해보면 뭔가 해야될 게 늘어나면 어려워지고, 없앨 수록 쉬워진다. 방정식도 마찬가지. operator에 해당하는 심볼을 날릴 수록 쉬워진다. 안 해도 되니까.

여튼 선형방정식은 Y=AX+B 꼴로 표현 가능한데, X나 Y는 데이터 셋에 해당하는 집합이 될 수 있고, 데이터는 현실에 대한 어떤 정보를 표현할 수 있기 때문에, 어떤 두 현실의 정보 간의 관계를 A와 B라는 상수만 바라보면서 정성적으로, 그리고 정량적으로 이해할 수 있게 된다.

물론 자연계의 현상을 선형적으로 완벽하게 스냅샷처럼 찍어내는 것은 불가능에 가깝다. 하지만 일단 해는 구할 수 있다는 점, 그래서 근사치를 구하는 모델이자 방법론으로써 선대는 훌륭한 가치를 지닌다.

많은 경우에서 비선형 구조를 가진 시스템은 일단 선형적 구조를 가진 선대 형태로 구조를 바꿔 근사해를 구할 수 있게 된다.

행렬과 선형변환

행렬은 linear transformation과 동치이다.

선형대수학의 기본정리는 아래와 같다.

1. scalar multiplication, vector addition 등의 연산이 잘 정의된 두 벡터공간이 있고
2. 그 두 벡터공간 사이에 각 집합 내의 대수적 구조가 보존되는 mapping(one-to-one이 아니어도 됨)이 존재하여 그 mapping을 T라고 했을 때
3. mapping T와 동치인 mxn 행렬이 존재한다.

위의 해석대로 선형대수의 행렬을 해석해보면 아래와 같이 이해해볼 수 있다.

1. 두 벡터공간 사이의 관계를
2. 상수만으로 표현하는데
3. 그 상수가 행렬이 된다.

그래서 왜 행렬으로 표현할까? 사실 별 이유는 없다. 아니, 제일 중요한 이유가 있다. 계산이 쉽기 때문이다. 행렬에 따라 붙는 게 행렬의 연산인데, 선형변환 T로만 표현한다고 생각해보자. 그냥 함수만 있고 어떻게 계산하는지에 대한 연산(알고리즘)에 대한 내용이 없다.

여기에 연산에 대한 내용을 추가한 게 행렬인 것. 두 집합 사이에 선형적인 연결 T가 있다는 건 알겠는데, 그걸 쉽게 풀리는 형태로 만들기 위해 나온 게 행렬이고, 그 둘이 똑같다는 걸 수학적으로 증명한 것이 선형대수학의 기본정리이다.

선형대수학의 기본정리 덕분에 우리는 선형변환의 문제를 기계적인 행렬 계산 문제로 바꿔서 풀 수 있는 것이다.

선형변환 T -> 선형대수학의 기본정리 -> 행렬

그래서 행렬로 표현하면 뭐다? 풀리는 형태로 문제를 바꿨고 계산이 쉽다..

벡터공간의 선형성 vs 위에서 대충 끄적인 선형의 개념

자, 이제 위에서 알아본 선형의 개념에 대한 일반적인 스케치와 벡터 공간의 선형 변환에서 말하는 선형성을 비교해보자. 벡터공간에 대한 정의는 링크로 갈음하겠다. 위에 스케치에서 적어 놓은 건 일반적으로 선형 하면 $R^2$ 위에서 직선을 떠올리기 때문에 거기서 부터 출발하려고 선형에 대한 개념을 나름대로 적어 놓았다.

이제 공간에 대한 여러 성질을 구체화 해서 벡터공간을 만들었다고 생각해보자. 또로롱. 벡터 공간이 만들어졌다. 이제 $R^2$ 위에서 우리가 일반적으로 생각하는 선형 함수와 벡터 공간 위에서의 선형변환을 비교해보자.

선형변환의 linearity에 대한 정의를 보면, 선대를 미리 학습한 사람들에게 익숙한 superposition에 대한 내용이 나온다.

$t(ax+by) = at(x)+bt(y)$

위의 꼴로 표현이 가능한데, x는 vector space에 속한 임의의 벡터가 된다. 그리고 선형대수학의 기본정리에 의해 y는 A라는 linear transformation과 동치인 계산이 쉬운 행렬로 갈아 끼울 수 있다.

$A(ax+by) = aA(x)+bA(y)$ where A is a matrix

이제 우리가 익히 아는 $R^2$ 실수 집합 위에서의 선형 함수와 벡터공간 위에서의 선형성을 비교해보자. 아래 수식은 $R^2$ 실수 집합 위에서의 선형 함수를 위의 벡터공간에서의 linearity의 정의와 비교한 수식이다[2].

$f(x)=ax+b$ $f(u+v)=a(u+v)+b=au+av+b=f(u)+f(v)−b≠f(u)+f(v)$

두 정의가 일치하지 않는 이유는 ax+b에서의 상수 b 때문이고, 벡터 공간에서의 선형변환은 상수 b를 허용 안 하는 제약이 추가적으로 들어가게 된다. 왜 일까? 이유는 아래와 같다.

선형변환은 벡터공간의 대수적 구조를 보존하는 변환이다.

변환을 적용하는 domain 벡터 스페이스 V에서는 $u+v=w$라는 연산이 성립한다. 여기서 부터 출발해보자.

1. $u+v=w$
2. $t(u)=u'+b$ (실수의 선형 함수와 비슷한 꼴이라면)
3. $t(u)+t(v)= u'+v'+ 2b$
4. $u'+v'+ 2b \ne u'+v'$

도착지 codomain 벡터 스페이스 W에서 대수적 구조가 보존이 안 된다. 그래서 공간을 translation 하는 상수를 없애버린 것. 이제 잠시 대수적 구조가 보존 되는 아름다운 선형변환을 감상해보자.

선대의 세부적인 내용들은 많이 까먹었는데 업데이트 해봐야지..

REFERENCE

[1] https://namu.wiki/w/%EC%84%A0%ED%98%95%EB%8C%80%EC%88%98%ED%95%99%EC%9D%98%20%EA%B8%B0%EB%B3%B8%EC%A0%95%EB%A6%AC

[2] https://math.stackexchange.com/questions/1912970/intutive-difference-between-linear-map-transformation-vs-linear-function

standalone은 어떤 어플리케이션이 독립적으로 실행될 수 있는 단위일 때 standalone이라고 표현한다. 쉽게 말하면 이렇게 표현할 수 있을 것 같다.

딸깍 한 번으로 모든 게 끝나는 상태로 패키징된 어플리케이션

복기

1. 스택을 쓸 생각을 하지 못 했다.
2. 마구잡이로 구현해서 메모리 초과 발생

*문제유형 : 자료구조(스택) *

자료 구조 : 스택 
문자열

처음 접근한 방법은 아래와 같다. 단순구현 방식으로 풀었는데, 메모리 초과가 발생.

1. 최초풀이 : split을 이용한 단순 구현

#include <bits/stdc++.h> 
#include <sstream> 
using namespace std; 

// 1. 문자열이 폭발 문자열을 포함하고 있는 경우에, 모든 폭발 문자열이 폭발하게 된다. 
// 2. 남은 문자열을 순서대로 이어 붙여 새로운 문자열을 만든다.
// 3. 새로 생긴 문자열에 폭발 문자열이 포함되어 있을 수도 있다.
// 4. 폭발은 폭발 문자열이 문자열에 없을 때까지 계속된다.
// 5. 상근이는 모든 폭발이 끝난 후에 어떤 문자열이 남는지 구해보려고 한다. 남아있는 문자가 없는 경우가 있다. 이때는 "FRULA"를 출력한다.
// restriction : 폭발 문자열은 같은 문자를 두 개 이상 포함하지 않는다.
string str;
string bomb;

void input() {
    ios_base :: sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    str.reseriossve(1000004);//미리 할당  
    cin >> str >> bomb;
}

string removeBomb(string str, string bomb) {
    string res = "";
    long long pos = 0;
    string token = "";
    while ((pos = str.find(bomb)) != string::npos) {
        token = str.substr(0, pos);
        res += token; 
        str.erase(0, pos + bomb.length());
    }
    res += str; 
    return res;
}

string explosion(string str, string bomb) {
    if (str.length() == 0) return "FRULA";
    else if(str.find(bomb) == string::npos ) return str; // exit condition
    else return explosion(removeBomb(str, bomb), bomb);// 폭발 문자열이 있는 경우
}

void solve() {
    input();
    cout << explosion(str, bomb);
}

int main() {
    solve();
    return 0;
}

알고리즘 분류를 열어보니 자료구조, 스택이 나와 있다. 스택을 써야 한다는 힌트를 얻고, 어디에 스택을 써야 할까 생각해보니, 입력 받은 그 시점에 deque 혹은 stack에 넣고 폭발 문자열 수 만큼 뒤로 확인하면 시간 복잡도를 더 줄일 수 있다.

위의 알고리즘의 경우에는 find를 하기 위해 순차적으로 문자열을 탐색해야 한다.

2. 두 번째 풀이 : deque(or 스택)을 이용한 구현

// Online C++ compiler to run C++ program online
#include <bits/stdc++.h>
using namespace std; 

string str, bomb; 
deque<char> q;  

void input(){
    ios_base :: sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    str.reserve(1000004);//미리 할당  
    cin >> str >> bomb;
}

bool isBomb(string bomb, int bomblen, int pos){
    for(int i=0; i<=bomblen; i++){
        if( q[i] != bomb[ bomblen - i ]) return false;     
    }
    return true; 
}

void deleteBomb(int bomblen) {
    for (int i = 0; i <= bomblen; i++) {
        q.pop_front();
    }
}


void printQueue(){
    reverse(q.begin(), q.end());  
    while(!q.empty()){
        cout << q.front(); 
        q.pop_front();
    }
}

////  queue를 이용한 풀이 
void solve(){
    int bomblen = bomb.length() - 1; 
    //1. string 전체 순회 
    for(int i=0; i<str.length(); i++){//O(N*B)
        q.push_front(str[i]); 
        //2. 마지막 입력값이 bomb의 마지막 값과 같은지 체크 
        if(q.front() == bomb[bomblen]){
            //3. bomb의 마지막 값과 같다면 해당 위치부터 뒤로 bomb의 값과 전부 같은지 체크 
            if( isBomb(bomb, bomblen, i) ) deleteBomb( bomblen ); //같을 경우 bomb에 해당하는 문자열 제거 
        }
    }
    if(q.empty()) cout << "FRULA";
    else printQueue(); 
}    


int main() {
    input(); 
    solve();
    return 0;
}

데이터베이스는 여러 사용자가 같은 레코드에 접근해서 데이터를 rw하게 된다. 즉, 멀티 유저가 동일한 자원에 동시에 접근하므로 동시성 문제가 필연적으로 발생할 수 밖에 없다. 특히 db 특성상 트랜잭션에 있어 데이터의 무결성이 보장 되는 것이 중요한데, 동시성 문제가 제대로 핸들링 되지 않을 경우 아래와 같은 문제들이 발생할 수 있다.

전제 : A 트랜잭션과 B 트랜잭션이 동일한 레코드 r에 접근한다고 가정하자.

*Dirty Reads : * $t_1$ : A 트랜잭션에서 레코드 r을 읽어와서 작업 $t_2$ : B 트랜잭션에서 레코드 r을 update -> r' $t_3$ : A 트랜잭션에서 다시 레코드 r'을 읽어와서 작업 $t_4$ : B 트랜잭션에서 다시 레코드 r'를 rollback ->r

위의 시나리오에서 A 트랜잭션 관점에서 봤을 때 $t_1$ 시점에서 읽은 레코드은 $t_3$ 시점에서 읽은 레코드 r'과 불일치 하게 된다. 즉, 레코드 r의 무결성이 깨졌다. A 입장에서는 clean한 값이 아닌 변경된 값(dirty)을 읽었으므로 dirty read가 성립된다.

또한, B 트랜잭션은 실패하여 r'에서 r로 database 상태를 롤백 하는 것이 무결성이 깨지지 않는 조건인데, 트랜잭션 A 입장에서는 이미 값을 읽어버렸으므로 무결성은 이미 깨진 상태라고 할 수 있다. 그리고 해당 더러운 데이터가 커밋 된다면 데이터 오염이 발생하게 된다.

$r(t_1) \ne r(t_3)$

*Non-Repeatable Reads : * $t_1$ : A 트랜잭션에서 레코드 r을 읽어와서 작업 $t_2$ : B 트랜잭션에서 레코드 r을 update -> r' $t_3$ : A 트랜잭션에서 다시 레코드 r'을 읽어와서 작업

하 트랜잭션 안에서 같은 데이터를 조회 했는데 값이 달라지는 현상. 위의 시나리오에서는 $r(t_1) \ne(t_3)$. Dirty read와 다른 점은 롤백 밖에 없어 보인다.

*Phantom Reads : * $t_1$ : A 트랜잭션에서 레코드 r을 읽어와서 작업 $t_2$ : B 트랜잭션에서 r 조회 조건과 같은 레코드 insert -> q $t_3$ : A 트랜잭션에서 다시 레코드 r,q를 읽어와서 작업

트랜잭션 A 관점에서는 $t_3$ 시점에서 없었던 레코드 q가 새로 생겨서 팬텀 리드가 된다.

결국 ACID의 I가 문제

위의 동시성 문제는 결국 트랜잭션들 사이의 isolation 레벨을 어떻게 관리하느냐의 문제가 된다. 여러 트랜잭션이 같은 레코드에 동시적으로 접근하는 걸 허용해서 성능을 향상 시킬지, 아니면 무조건적인 ACID를 보장 하여 데이터의 무결성을 지킬 것인지, 두 요건을 저울질 해서 개발자 각자의 판단으로 트랜잭션의 Isolation level을 아래와 같이 설정할 수 있다.

1. Read Uncommitted : 커밋 되지 않은 트랜잭션 사이의 read를 허용한다. 각 트랜잭션 프로세스 마다 마구잡이로 읽을 수 있으니까 온갖 문제가 생길 수 있다.

2. Read Committed : 커밋된 데이터만 조회 가능하다.Phantom Read와 Non-Repeatable Read가 발생 가능하다.

3. Repeatable Read : UndoLog로 MVCC(Multi-Version-Concurrency Control)을 한다. Non-repeatable read는 막아주지만, phanton read는 발생할 수 있다.

4. Serializable Read : 가장 엄격한 격리 수준으로 트랜잭션의 순차적 처리를 보장한다. SELECT 작업시 S-Lock을 걸어 삽입/수정/삭제 트랜잭션을 막아 버린다. 동시처리 성능을 희생하여 데이터의 무결성을 지키는 설정.

[1] https://mangkyu.tistory.com/288 [2] https://amazelimi.tistory.com/entry/DB-Dirty-Read-Non-Repeatable-Read-Phantom-Read-%EC%98%88%EC%8B%9C-%EB%B0%8F-Snapshot-Isolation-Level-LIM [3] https://steady-coding.tistory.com/562

• 배열
• 링크드리스트
• 트리
• 그래프
• 테이블 등

(그림이 좀 괴랄하긴 한데, mermaid가 처음이라 익숙해지면 다시 그려야 될 것 같다..)

여튼 위의 패턴을 분석해보면 아래와 같이 요약할 수 있다.

1. Array는 Aggregator 인터페이스를 구현한다.
2. ArrayIterator는 Iterator 인터페이스를 구현한다.
3. Item은 Array 클래스의 부분으로 생명주기를 함께한다.
4. ArrayIterator는 Array를 소유한다.

mermaid에서는 create을 표현하는 기능을 제공해주지 않지만, [1]의 유튜브 영상 내 클래스도에서는 Aggregator가 ArrayIterator를 create 해주는 표현이 있다.

그리고 해당 기호는 아래 함수로 구현된다.

    public class Array Impelements Aggregator{
        private Item[] items;//Array 클래스는 item을 HAS-A관계로 소유한다. 

        ////... some codes ...//// 

        @Override
        public Iterator iterator(){//Aggregator는 Iterator를 create한다
            return new ArrayIterator(this); 
        }
    }

Array 클래스는 Iterator 인터페이스를 구현한 ArrayIterator를 생성해서 리턴 해주는 메소드를 가지고 있다.

REFERNCE

[1] https://www.youtube.com/watch?v=T3sXKtlr0Ow&list=PLe6NQuuFBu7FhPfxkjDd2cWnTy2y_w_jZ

아래 그림을 보자.

당연히 서버-클라이언트 구조로 되어 있다.

1. Client가 bash를 통해 docker build/pull/run 등의 커맨드를 주면, 도커 데몬이 해당 커맨드를 실행해서 원격 registry 도커 허브에 있는 이미지 파일을 다운로드 받는다.
2. 이미지 파일은 2차 저장소에 저장 되고
3. docker create 명령어로 도커 컨테이너를 생성한 뒤
4. docker start 명령어로 도커 컨테이너를 프로세스로 만들어 실행할 수 있다.

도커 이미지

도커 이미지는 특정 시점에서 어플리케이션과 어플리케이션의 종속성, 그리고 실행환경 전반을 snapshot으로 찍어 놓은 read only 묶음 파일이라고 보면 될 것 같다.

• 어플리케이션을 패키징/전송 하기 위한 단위
• 소스 코드, 라이브러리, 종속성, 도구 및 응용 프로그램을 실행하는데 필요한 기타 파일을 묶은 snapshot
• read only

이미지는 여러 레이어로 구성될 수 있으며, 각 레이어들은 고유한 uuid 값을 가진다.

도커 컨테이너

도커 이미지로 부터 만들어진 실행 가능한 런타임 환경으로, portable(이식가능) 단위가 된다. 컴퓨팅 환경의 표준화를 구현 했다고 하는데, 이건 low 단에 어떤 환경이 있더라도 어플리케이션이 구동 되게 하려는 java의 WORA 철학과도 어느 정도 맞물리는 부분이 있는 것 같다. 어떻게 보면 java 또한 hw에 종속적이지 않은 개발을 하기 위해 jvm을 만들었으니까.

그리고 컨테이너를 생성하면 도커 이미지 파일 위에 rw 레이어인 컨테이너 레이어가 생기며 프로세스로 구동 된다고 한다.

bandit16 link https://overthewire.org/wargames/bandit/bandit17.html

command to solve this level

이 레벨을 풀기 위해 알아야 하는 커맨드들은 아래와 같다.

1. ssh :

• ssh 접속 커맨드
• ssh [id]@[url] -p[port]

2. telnet :

• text-based communication protocol
• telnet [hostname] [port]

3. nc(Netcat) :

• networking utility for reading from and writing to network connections using TCP or UDP
• port scanning, file transfers, and creating network connections
• nc -vz [hostname] [port]

4. openssl :

• A robust open-source toolkit for implementing SSL/TLS protocols.
• connects to a remote SSL/TLS server

5. s_client :

• A specific OpenSSL tool that connects to a remote SSL/TLS server and prints information about the SSL connection

6. nmap :

• open-source network scanning tool for discovering hosts and services on a computer network
• security auditing, and finding open ports
• nmap -p 1-1000 hostname (to scan ports 1 through 1000)

*문제 : *

The credentials for the next level can be retrieved by submitting the password of the current level to a port on localhost in the range 31000 to 32000. First find out which of these ports have a server listening on them. Then find out which of those speak SSL and which don’t. There is only 1 server that will give the next credentials, the others will simply send back to you whatever you send to it.

1. a port on localhost in the range 31000 to 32000
2. listening port which of those speak SSL

*문제 풀이 : *

1. listening 포트를 찾는다.

    nmap -p 31000-32000 localhost

2. SSL로 로그인 가능한 포트를 찾는다.

    nmap --script ssl-enum-ciphers -p 31000-32000 hostname

nmap은 네트워크 스캐닝 툴 중 하나로, 강력한 기능들이 스크립트 되어 있다고 한다. 호스트 찾아내기, 호스트의 운영체제, 어떤 포트를 어떤 프로세스가 사용하고 있는지(오....), 스텔스 스캔, 방화벽 사용감지 등을 할 수 있다고 한다.

nmap을 사용하면 명시한 호스트의 포트 레인지를 스캔하게 된다. 그리고 해당 포트들 중 어떤 SSL cipher를 사용하는지 보여준다.

31518번 포트와 31790번 포트 ssl 통신으로 열려 있는 걸 확인할 수 있다. 이제 접속해보자.

31790포트로 접속해보면 다음 스테이지 패스워드를 돌려준다.

REFERENCE

[1] https://m.blog.naver.com/alice_k106/221468341565 [2] https://namu.wiki/w/nmap

이전에 tesseract를 사용해서 OCR로 텍스트를 추출 해야 하는 작업 도중, 윈도우 로컬 환경에서는 잘 돌아가던 로직이 centOS에서는 전혀 동작하지 않는 상황이 발생한 적이 있었다.

운영과 로컬 OS 실행환경이 달라서 생긴 문제였는데, 이게 웹 어플리케이션 내부 로직 문제면 그 로직만 보면 되지만 환경 불일치로 인한 문제가 발생하면 버그나 이슈가 발생한 포인트가 어디인지 감을 잡기 힘들다.

해당 이슈의 경우에도 tesseract OCR 오픈소스 라이브러리를 자바에서 사용할 수 있게 한 JNA wrapper tess4j에서, 내부적으로 윈도우용 .dll 파일만 보유 하고 있어, 리눅스 OS에서 바라 봐야 할 다이나믹 링킹 라이브러리를 찾지 못 해 발생한 이슈였는데, OS 레벨까지 내려가서 문제를 찾아야 했을 때는 정말 심해에 빠진 듯한 막막함을 느꼈던 기억이 난다.

그렇다면 누군가는 이런 이슈에 대한 해답을 내놓지 않았을까? 내가 겪은 문제는 이전에 다른 누군가가 겪었을 확률이 높고, 그 해답 또한 이미 존재할 확률이 높으니까. 이런 의존성 문제와, 런타임 환경 불일치에 의해 발생하는 이슈를 누군가가 어떠한 형태의 솔루션으로 제공하지 않았을까?

뭔가 직관적으로 추상화 레벨을 끼워 넣으면 될 것 같은 생각이 든다. 대부분의 개별적인 문제들은 그 문제들을 추상화 하여, 위에 추상화 레벨 위에서 문제를 해결하는 방법으로 해결 되는 경우가 많은 것 같다.

그리고 역시 컨테이너 기술이 그 해답이었다. 바다 위에 떠 있는 고래(도커)가 저 심해 같은 의존성 및 런타임 환경 문제를 해결해 주는 수호신 같은 느낌이랄까..

1. Containerization ??

컨테이너 기술의 정의는 아래와 같다.

a technology that enables the packaging and running of an application and its dependencies in a standalone, isolated environment known as a container.

1. 가볍고, 이식가능하고, scalable한 방법으로 어플리케이션과 의존성을 패키징 하여
2. 독립적인 standalone 형태로 배포, 실행하기 위한 기술

즉, 어플리케이션이 환경에 독립적으로 배포 되고 실행할 수 있게 도와주는 기술이다.

컨테이너 엔진:

• 컨테이너들을 올려 놓고 실행
• 커널 위에서 동작
• linux의 cgroup 명령어로 독립된 실행환경을 확보

컨테이너 이미지:

• read only
• 어플리케이션과 어플리케이션이 동작하기 위한 의존성을 패키징한 것.
• 어플리케이션 + 의존성(라이브러리, .dll, .so 등등) + 환경 관련 정보.
• 어플리케이션의 스냅샷을 찍어 놓은 file
• 2차 저장소에 저장

컨테이너 :

• r/w
• a process(ram)
• 컨테이너 엔진 위에 올라가 실행 되고 있는 어플리케이션
• 컨테이너 이미지의 실행 상태

2. Docker ??

도커는 위의 컨테이너 기술을 구현한 오픈소스 프로젝트로 리눅스 서버 위에서 돌아가는 어플리케이션들의 독립적인 standalone 실행환경을 제공 해준다.

• 각각의 컨테이너들은 독립된 하드웨어 자원을 할당 받게 된다.
• 호스트 시스템의 운영 체제 커널을 공유하여 리소스의 효율적인 활용이 가능하다.

가상화와 비교해보자.

가상화(하이퍼바이저) :

1. 하이퍼바이저
2. 게스트 OS
3. 바이너리/라이브러리/어플리케이션

도커 :

1. OS
2. Container Engine
3. Container(바이너리/라이브러리/어플리케이션)

차이점 :

가상화의 경우, 어플리케이션 레이어에서 infra layer로 가기 위해 각 어플리케이션 마다 OS가 필요하다. 반면, 컨테이너는 모든 어플리케이션 마다 하나의 OS(kernel)을 통해 인프라에 접근하게 된다.

위의 예시를 보자.

가상화 용량 = OS 3개 + 하이퍼바이저 1개
컨테이너 용량 = OS 1개 + 컨테이너 엔진

이렇게 구성이 되는데, OS는 상당히 무거운 소프트웨어 이고, 우분투 기준 약 1.8gb의 용량을 차지하게 된다. 위의 예시에서는 3개의 어플리케이션을 돌리기 위해 총 5.4gb의 OS를 위한 용량이 필요하게 된다.

반면 도커 바이너리는 40mb~200mb 공간을 차지하며, OS 또한 커널을 공유하기 때문에 속도가 빠르다. 반면, 하이퍼바이저는 하나의 추상화 레이어 위에서 OS가 동작하기 때문에 속도 또한 느려지게 된다.

어플리케이션이 n개 이상으로 확장될 경우까지 생각해보면, 도커 쪽이 압도적으로 확장성(scalable)한 걸 직관적으로 알 수 있다. 가상화 쪽은 어플리케이션과 OS가 하나의 세트로 설치 돼야 하고, 도커 컨테이너는 정말 standalone 컨테이너 하나만 띡 올리면 되기 때문👍

REFERENCE

[1] https://www.youtube.com/watch?v=m454YTyPWSk&list=PLApuRlvrZKogb78kKq1wRvrjg1VMwYrvi&index=9 [2] https://www.youtube.com/watch?v=pR-cGS6IGvI [3] https://www.youtube.com/watch?v=eKj13PsoMNE [4] https://suyeon96.tistory.com/52

복기

1. 다른 방법으로 풀어 보려고 했는데 점점 이상해졌다.
2. 비트마스킹 기준, 정수 5가 정수 11보다 사전 정렬 시 더 뒤에 와야 한다. 이걸 못 깨달았다.

*문제유형 : 조합 찾기 *

조합 전략 : bitmasking 

*비트셋 프린트 : *

void printBitSet(vector<pp> resultSetVector, int N){
    for(pp resultPair : resultSetVector ){
        for (int i = 0; i < N; i++){
            if (resultPair.first & (1 << i)){
                cout << i + 1 << " ";
            }
        }
    }
}

위의 방법으로 비트를 받아서 프린트 하면 사전 정렬이 힘들어진다. custum sorting으로 정렬해서 풀어보려고 했는데 너무 복잡하고 재귀까지 써서 하다 보니까 타임아웃 나서 주어진 해답으로 풀게 됐음.

//// 최소 bit를 리턴 
int getMinBit(int a){
    return a & (-a);
}

//// custom compare function : 최소 bit를 정수로 표현 해도 대소관계는 유지된다. 재귀버전 x
bool compare(pp a, pp b) {
    return getMinBit(a.first) < getMinBit(b.first);
}

*최종 해답: *

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pp;
int N, mp, mf, ms, mv, res=INT_MAX;
map<int, vector<vector<int>>> resultSetVector;
struct food{
    int v[5];
};

vector<food> input(){
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    cin >> N >> mp >> mf >> ms >> mv;
    vector<food> fList(N);
    for (int i = 0; i < N; i++){
        for (int j = 0; j < 5; j++){
            cin >> fList[i].v[j];
        }
    }
    return fList;
}

void solve(){
    vector<food> fList = input();
    for (int i = 0; i < (1 << fList.size()); i++){
        vector<int> v; 
        int sum[5] = {0};
        for (int j = 0; j < fList.size(); j++){
            if (i & (1 << j)){
                v.push_back(j+1); 
                for (int k = 0; k < 5; k++){
                    sum[k] += fList[j].v[k];
                }
            }
        }
        //// 1. 최소 영양소 조건 
        if (sum[0] >= mp && sum[1] >= mf && sum[2] >= ms && sum[3] >= mv){   
            //2.2. 새로운 값으로 채워 줌. 
            //// 2. 최소 비용 
            if(res >= sum[4]){
                res = sum[4];
                resultSetVector[res].push_back(v); 
            }              
        }
    }

    if (res == INT_MAX) cout << -1 << '\n';
    else{
        sort(resultSetVector[res].begin(), resultSetVector[res].end());  
        cout << res << "\n";
        for(int a : resultSetVector[res][0]){
            cout << a << " ";
        } 
    }
}

int main(){
    solve();
}

아래와 같은 redis와 스프링 세션 연동 작업을 하다가 연결이 안 되는 문제가 발생 했다.

1. build.gralde

    //redis
    implementation 'org.springframework.boot:spring-boot-starter-data-redis'
    implementation 'org.springframework.boot:spring-session-data-redis'

2. redis / spring session 연동 테스트를 위한 컨트롤러

@RestController
public class AuthController {
    // Create Jackson ObjectMapper

    String HOME_VIEW_COUNT = "HOME_VIEW_COUNT";

    @GetMapping("/")
    public String hello(Principal principal, HttpSession session) throws JsonProcessingException {
        incrementCount(session , HOME_VIEW_COUNT);
        return "hello this is session ";// + principal.getName();
    }

    @GetMapping("/count")
    public String count(HttpSession session){
        return "HOME_VIEW_COUNT : " + session.getAttribute(HOME_VIEW_COUNT);
    }

    private void incrementCount(HttpSession session, String attr){
        var homeViewCount = session.getAttribute(attr) == null ? 0 : (Integer) session.getAttribute(attr);
        session.setAttribute(attr, homeViewCount += 1);
    }

}

3.application.properties

#### Spring Session
#### spring.session.jdbc.initialize-schema = none
spring.session.store-type=redis

#### Redis
spring.redis.host=localhost
spring.redis.port=6379

이슈발생

[2]의 Spring 공식문서 9.2.1 Connecting to Redis 항목에서는 application.properties에 커넥션 정보만 추가해주면 자동으로 연결 된다고 한다. 하지만 정작 날아오는 세션 값을 보니 톰캣의 jsessionid가 리턴 됐다.

해결

spring session과 연동이 안 돼서 톰캣의 jsessionid가 리턴 된 것 같은데 대체 왜 spring session이 연동이 안 됐을까.

1. 테스트 코드로 Redis connection을 먼저 확인

     @Test
    @DisplayName("redis connection 테스트")
    public void redisConnectionTest(){
        ////redis connection infor
        String redisHost = "localhost";
        int redisPort = 6379;
        String redisPassword = null;

        RedisClient redisClient = null;
        StatefulRedisConnection<String, String> connection = null;

        //// connect
        redisClient = RedisClient.create("redis://" + redisHost + ":" + redisPort);
        connection = redisClient.connect();

        //// 패스워드 체크
        //if (redisPassword != null && !redisPassword.isEmpty()) {
        //  connection.sync().auth(redisPassword);
        //}

        //// 테스트 go go
        String serverInfo = connection.sync().info();

        String testKey = "test_key";
        String testValue = "test_value";

        connection.sync().set(testKey, testValue);
        String retrievedValue = connection.sync().get(testKey);

        //// assert
        assert connection.isOpen() : "Connection to Redis failed";

        //// Close the connection when done
        if (connection != null) connection.close();
        if (redisClient != null) redisClient.shutdown();

    }

테스트는 통과 했고,

로컬에 기동 된 레디스에 값도 잘 들어간다. 즉, redis에 직접 연결은 된다. spring session에서 접근이 안 되는 것 같은데 테스트 해보자.

2. Spring Session 연동 테스트

test를 위한 컨트롤러 추가

  @Controller
  @EnableRedisHttpSession
  public class TestSessionController {
      @GetMapping("/setTestSessionAttribute")
      @ResponseBody
      public String setSessionAttribute(HttpSession session) {
          session.setAttribute("test_key", "test_value");
          return "Session attribute set";
      }
  }

spring session test 케이스

@SpringBootTest
@AutoConfigureMockMvc
public class RedisSpringSessionConnection {
    @Autowired
    private MockMvc mockMvc;

    @Test
    public void testSetAndGetSessionAttribute() throws Exception {
        // Set session attribute
        ResultActions setResult = mockMvc.perform(get("/setTestSessionAttribute"));

        setResult.andExpect(status().isOk())
                .andExpect(content().string("Session attribute set"));
    }
}

[2]의 9.2.1 Connecting to Redis에서는 application.properties에 커넥션 정보만 추가해주면 자동으로 연결 된다고 하는데, 위 테스트가 계속 깨져서 확인해보니 RedisConnectionFactory를 찾을 수 없다는 에러가 뜬다.

그래서 아래 RedisConfig를 추가해줬다.

redis config 파일

@Configuration
@EnableRedisHttpSession
public class RedisConfig {
    @Bean
    public RedisConnectionFactory redisConnectionFactory() {
        return new LettuceConnectionFactory();
    }
}

이제 spring-session 값이 redis에 들어가는 걸 확인 할 수 있다. 마지막으로 클라이언트로 날아오는 쿠키값을 확인해보면,

JSessionid에서 spring session의 디폴트값인 session으로 바뀌어 있고,

외부 저장소 레디스에 세션이 저장 되어 서버를 재기동 해도 view_count가 그대로 나온다.

REFERENCE

[1] https://docs.spring.io/spring-session/reference/guides/boot-redis.html [2] https://docs.spring.io/spring-boot/docs/3.2.0/reference/htmlsingle/#data.nosql.redis.connecting

bandit15 link https://overthewire.org/wargames/bandit/bandit16.html

command to solve this level

이 레벨을 풀기 위해 알아야 하는 커맨드들은 아래와 같다.

1. ssh :

• ssh 접속 커맨드
• ssh [id]@[url] -p[port]

2. telnet :

• text-based communication protocol
• telnet [hostname] [port]

3. nc(Netcat) :

• networking utility for reading from and writing to network connections using TCP or UDP
• port scanning, file transfers, and creating network connections
• nc -vz [hostname] [port]

4. openssl :

• A robust open-source toolkit for implementing SSL/TLS protocols.
• connects to a remote SSL/TLS server

5. s_client :

• A specific OpenSSL tool that connects to a remote SSL/TLS server and prints information about the SSL connection

6. nmap :

• open-source network scanning tool for discovering hosts and services on a computer network
• security auditing, and finding open ports
• nmap -p 1-1000 hostname (to scan ports 1 through 1000)

*문제 : *

The password for the next level can be retrieved by submitting the password of the current level to port 30001 on localhost using SSL encryption.

*문제 풀이 : *

opeenssl s_client [옵션] [호스트:포트]

openssl s_client -connect localhost:30001

위의 커맨드를 입력하면 아래와 같은 SSL/TLS 커넥션이 이뤄진다.

1. SSL/TLS Handshake:

Can't use SSL_get_servername
depth=0 CN = localhost
verify error:num=18:self-signed certificate
verify return:1
depth=0 CN = localhost
verify error:num=10:certificate has expired
notAfter=Jan 25 20:43:52 2024 GMT
verify return:1
depth=0 CN = localhost
notAfter=Jan 25 20:43:52 2024 GMT
verify return:1

2. Certificate:

-----BEGIN CERTIFICATE-----
MIIDCzCCAfOgAwIBAgIEXPQtNDANBgkqhkiG9w0BAQUFADAUMRIwEAYDVQQDDAls
b2NhbGhvc3QwHhcNMjQwMTI1MjA0MjUyWhcNMjQwMTI1MjA0MzUyWjAUMRIwEAYD
...
-----END CERTIFICATE-----

인증서를 받는다.

*3. SSL/TLS Session Information: *

SSL handshake has read 1339 bytes and written 373 bytes
Verification error: certificate has expired

몇 바이트를 읽고 썼는지 확인

이후 현재 단계 비밀번호를 입력 하면 다음 단계로 넘어갈 수 있다.

REFERENCE

[1] https://overthewire.org/wargames/bandit/bandit16.html [2] https://www.cloudflare.com/ko-kr/learning/ssl/what-happens-in-a-tls-handshake/ [3] https://m.blog.naver.com/alice_k106/221468341565

복기

1. x,y를 바꿔 썼다.
2. outOfBound를 먼저 체크해야 오버플로우가 발생하지 않는다.

*문제유형 : brute force search *

탐색 전략 : brute force
탐색 방법 : bfs 

// Online C++ compiler to run C++ program online
#include <bits/stdc++.h>
using namespace std; 
// 입력의 첫째 줄에는 공백으로 구분된 두 정수 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1000 이다. R은 미로 행의 개수, C는 열의 개수이다.
typedef pair<int,int> pp; 
int R,C;
int visited[1004][1004]; 
char cmap[1004][1004]; 
int fmap[1004][1004]; 
int dx[4] = {0,0,1,-1}; 
int dy[4] = {-1,1,0,0};
//pp start; 
queue<pp> q; 
queue<pp> fq; 

bool outOfBound(int y, int x){
    return (y < 0 || x < 0 || y >= R || x >= C );
}

bool isExit(int y, int x){//탈출구 
    return (y == 0 || x == 0 || y == R - 1 || x == C -1); 
}

bool isWall(int y, int x){
    return cmap[y][x] == '#'; 
}

void input(){
    // 초기화 
    fill(&fmap[0][0],&fmap[0][0] + 1004 * 1004 , INT_MAX ); 
    cin >>R>>C;
    for(int i=0;i<R;i++)
    for(int j=0;j<C;j++){
        cin >> cmap[i][j];
        if(cmap[i][j] == 'F'){//fire then 
            fmap[i][j] = 1; 
            fq.push({i,j}); 
        }
        if(cmap[i][j] == 'J'){//출발 지점 
            q.push({i,j});
            visited[i][j] = 1;
        }
    } 
}

//bfs 
int solution(){
    int y,x; 
    int ny,nx; 
    //bfs fire
    while(!fq.empty()){
        tie(y,x) = fq.front(); 
        fq.pop(); 
        for(int i=0; i<4; i++){
            ny = y + dy[i]; 
            nx = x + dx[i]; 
            if( fmap[ny][nx] != INT_MAX ) continue; //visited  
            if(outOfBound(ny,nx)||isWall(ny,nx)) continue; 
            fq.push({ny,nx}); 
            fmap[ny][nx] = fmap[y][x] + 1; 
        } 
    }
    //bfs person 
    while(!q.empty()){
        tie(y,x) = q.front(); 
        q.pop(); 
        if(isExit(y,x)){
            return visited[y][x]; 
        }
        for(int i=0; i<4; i++){
            ny = y + dy[i]; 
            nx = x + dx[i];
            if(outOfBound(ny,nx) || visited[ny][nx] || isWall(ny,nx)) continue; 
            if(fmap[ny][nx] <= visited[y][x] + 1) continue; //이미 불이 있는 지역 
            q.push({ny,nx});
            visited[ny][nx] = visited[y][x] + 1;
        }
    }
    return -1; 
}

//solve
void solve(){
    input(); 
    int result = solution();
    if(result == -1) cout << "IMPOSSIBLE"; 
    else cout << result; 
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    solve(); 
}