이 문제는 일단, 다른 비슷한 팰린드롬으로부터 dp임을 생각을 하고 풀었다. 그렇다면 top-down으로 해보자 그림과 같이 길이가 1이면 무조건 0이다. 그자체로 팰린드롬이니까 길이가 2이면 숫자가 다르면 무조건 1이다. 하나를 추가해야하니까

그러핟면 3부터는 어떻게 될까 1,2,3이 다르면 두가지 경우가 있다. 맨처음숫자 1을 추가해서 1,2,3,1인경우 맨 끝숫자 3을 추가해서 3,1,2,3인경우 그렇다면 어떤걸 추가해야할까?

만약에 1,2,3이아니라 1,2,2라고 생각해보자, 1,2,2,1은 하나만 추가하면되는데 2를 앞에다 추가하려면 2,2,1,2,2로 2를 2개추가해야한다.

여기서 부터 1,2의 팬린드롬만드는데 필요한 숫자와 2,2를 팬린드롬 만드는데 숫자를 비교하면된다.

1,2의 팬린드롬 만드는데 필요한 숫자가 1이니까 1+1 2,2는 이미 팬린드롬 0이니까 0+1로 정답 1부터3까지는 1이된다.

이식이 min(check(start+1,end),check(start,end-1))이 된다.

만약에 같으면 어떻게 될까? 1,2,3,1이런식으로 말이다. 그러면 2,3의 팬린드로 만드는 숫자를 알면된다. dp[1][4] = check(start+1,end-1)이다.

또한 dp느낌이 나는게 위 그림 삼각형처럼 재귀를 부르더라도 이미 최적의 값을 찾으면 다시 호출하지 않도록 -1이면 호출 아니면 반환 이런식으로 처리했다.

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

int N;
int arr[5001];
int dp[5001][5001];

void init() {
    cin >> N;
    for (int i = 1; i <= N; i++) {
        cin >> arr[i];
    }

    // dp 초기화
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            dp[i][j] = -1;
        }
    }

    // 길이 1
    for (int i = 1; i <= N; i++) dp[i][i] = 0;

    // 길이 2
    for (int i = 1; i < N; i++) {
        dp[i][i + 1] = (arr[i] == arr[i + 1] ? 0 : 1);
    }
}

int check(int start, int end) {
    if (dp[start][end] != -1) return dp[start][end];

    if (arr[start] == arr[end]) {
        dp[start][end] = check(start + 1, end - 1);
    } else {
        dp[start][end] = min(check(start + 1, end), check(start, end - 1)) + 1;
    }

    return dp[start][end];
}

void solve() {
    check(1, N); // 실제 계산은 여기서 다 된다
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    init();
    solve();
    cout << dp[1][N] << "\n";
    return 0;
}

틀린풀이

Flow를 처음부터 생각해보자.

목표지점까지 최소로 도달해야한다. 그래프 형태이다.

딱, 여기서부터 BFS를 사용해야겠다, 라는 생각이 들었다.

두번째, 방문처리를 이미 했으면 다시 방문을 안해야한다고 생각했다. 왜냐하면, queue이기 때문에 이미 방문을 한시점이 최소라고 생각했기 때문이다.

그렇다면, 항상 말부터 이동을 먼저하고 그다음 원숭이가 방문하는 형식으로 진행하면 된다고 생각했다.

왜냐하면 0 0 0 0 0 0 에서 2,3을 한번에 말로 이동을 했다고 치자, 그러면 굳이 1,1 1,2 1,3 그다음 2,3확인시 이미 앞에서 2,3을 한번에 이동시킨게 방문처리가 되어있으므로 4번이나 움직여서 간걸 처리를 안해버리면 된다고 생각했기 때문이다.

그러나 문제는 말부터 항상 이동시킨다고 해서 그게 최선의 결과가 항상 나오는게 아니다. 예를들어, K가 1일때 만약 1,1에서 말부터 움직여서 초록색 1,2로 이동했다고 치자. 끝칸까지 가야하는데 이미 점프를 써버려서 도달을 못한다.

그다음에 원숭이로 이동을 하면, 빨간색으로 1,2,그다음에 3,2에 가야하는데, 이미 말이 방문처리를 해버려서 3,2에 방문을 못한다. 아직 점프를 안해서 3,2에 가서 점프를하면 되는데 말이다.

그래서 핵심은 그럼, 아직 뛰지 않은 놈들은 3,2에 방문이 가능해야한다는것이다. 이말은 다르게, 뛴 횟수에 따라 다르게 3,2 방문처리르 해줘야한다는것이다.

이말은 3차원 배열로 처음에 말부터 뛰면 [3][2][1] = true지만 [3][2][0] = false이기 때문에, 한번도 안뛴 놈들은 여기가 false라서 방문처리를 할 수 있게 해야한다.

정답코드

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

int K = 0;
int W, H = 0;
int map[201][201] = { 0, };
bool visited[201][201][31] = { false, };
int Answer = 100000000;

int m_dx[4] = { 0,0,1,-1 };
int m_dy[4] = { 1,-1,0,0 };
int h_dx[8] = { -2,-1,-2,-1,1,2,1,2 };
int h_dy[8] = { -1,-2,1,2,2,1,-2,-1 };

void init() {
    cin >> K;
    cin >> W >> H;

    for (int i = 0; i < H; i++) {
        for (int j = 0; j < W; j++) {
            int tmp = 0;
            cin >> tmp;
            map[i][j] = tmp;
        }
    }
}

void bfs() {
    queue<pair<pair<int, int>, pair<int, int>>>q;
    q.push({ { 0,0 }, { 0, 0 } });
    visited[0][0][0] = 1;

    while (!q.empty()) {
        int Use = q.front().first.first;
        int cnt = q.front().first.second;
        int x = q.front().second.first;
        int y = q.front().second.second;
        q.pop();
        if (x == H - 1 && y == W - 1 && Answer > cnt) Answer=cnt;

        /*
        * 만약 한번 점프를 쓰고, a,b에 도착을했음. 근데 뒤에서 안쓰고 안쓰고 한번쓰고 a,b에 도착을 하면 굳이 이걸 카운트할 필요가 없잖아
        * 
        */

        //원숭이로 이동
        for (int i = 0; i < 4; i++) {
            int nx = x + m_dx[i];
            int ny = y + m_dy[i];

            //Use를 ++ 시키지 않은채로 map이 0이고 범위안벗어나면 넣기
            if (nx >= 0 && nx < H && ny >= 0 && ny < W && !visited[nx][ny][Use] && map[nx][ny] == 0) {
                visited[nx][ny][Use] = true;
                q.push({{ Use,cnt + 1 }, { nx,ny }});
            }
        }

        //말로이동
        if (Use < K) {
            for (int i = 0; i < 8; i++) {
                int nx = x + h_dx[i];
                int ny = y + h_dy[i];

                if (nx >= 0 && nx < H && ny >= 0 && ny < W && !visited[nx][ny][Use + 1] && map[nx][ny] == 0) {
                    visited[nx][ny][Use + 1] = true;
                    q.push({ { Use+1,cnt + 1 }, { nx,ny } });
                }
            }
        }

    }
}

int main() {

    init();

    bfs();

    if (Answer == 100000000) { cout << "-1"; }
    else {
        cout << Answer;

    }
    return 0;
}

문제 흐름 요약

만약 3번의 주사위를 던지고 말이 2개있다면 그림과 같이 1번 말이 3번 움직이는경우, 2번 움직이고 2번말이 1번움직이는 경우 이런식으로 진행될것이다. 3번 움직인 다음, 2번 움직이고 2번말을 움직여야한다는 점에서 BackTracking인것을 확인했다.

그럼 진짜 backtracking으로 풀어도되나? 주사위를 10번 던지는데 말의 갯수는 4개이다. 그러면 경우의수가 4^10이고 2^20이니까 1048576가지 경우의수가 나온다. 시간내에 충분히 풀 수 있다.

문제 1.

2->4->6 번 이런식으로 노드를 탐색하는 방법은 그전에 유니온 파인드에서도 해봤다. 인덱스 2번의 배열 값에 다음 움직일 4번을 넣으면 된다. 그런데 이렇게 했더니 문제가 있다. 그림과 같은 16번 노드일때, 18번으로 갈지 19번으로 갈지 값에 뭘 넣어야할지 모르기 때문이다.

고로 처음에 어떻게 생각했냐면, 노드를 LinkedList형태로 풀라고했다.

int dice[10];
int Max = 0;
struct Node {
    int num;        // 데이터 변수
    Node* next_black;
    Node* next_blue;     // 다음 노드를 가리킬 포인터

    // 생성자 (선택 사항)
    Node(int value) : num(value), next_blue(nullptr), next_black(nullptr) {}
};

void init() {
    //주사위 받기
    for (int i = 0; i < 10; i++) {
        int tmp = 0;
        cin >> tmp;
        dice[i] = tmp;
    }

    Node* head = new Node(0);
    Node* cur = head;

    //2 ->4 -> 6... ->40까지 연결
    for (int i = 2; i <= 42; i += 2) {
        cur->next_black = new Node(i);
        cur = cur->next_black;
    }

    Node * end = cur;

    Node * twentiyfive = new Node(25);

    //10에서 25까지 가는 노드 연결
    cur = head;
    while (cur->num != 10) {
        cur = cur->next_black;
    }

    //13노드
    for (int i = 13; i <= 19; i += 3){
        cur->next_blue = new Node(i);
        cur = cur->next_blue;
    }
    //19번노드->25번노드 연결
    cur->next_black = twentiyfive;

    //20에서 25번 가는 노드 연결
    cur = head;
    while (cur->num != 20) {
        cur = cur->next_black;
    }

    //22번노드
    for (int i = 22; i <= 24; i += 2) {
        cur->next_blue = new Node(i);
        cur = cur->next_blue;
    }

    //24번과 25번 연결
    cur->next_black = twentiyfive;

    //30번 출발 연결
    cur = head;
    while (cur->num != 30) {
        cur = cur->next_black;
    }

    //28번노드
    for (int i = 28; i >= 26; i--) {
        cur->next_blue = new Node(i);
        cur = cur->next_blue;
    }

    //26번과 25번 연결
    cur->next_black = twentiyfive;


    //마지막으로 25번과 40번 연결
    //40번 노드 찾기
    cur = head;
    while (cur->num != 40) {
        cur = cur->next_black;
    }

    for (int i = 30; i <= 35 ; i+=5) {
        twentiyfive->next_blue = new Node(i);
        twentiyfive = twentiyfive->next_blue;
    }

    //마지막으로 35과 40번 연결,40과 42연결
    twentiyfive->next_blue = cur;
    cur->next_black = end;

}

이렇게 설정해서 만약 출발 노드가 10,20,30이라면 BT할때 color를 blue로 해서 if문을 통해 color가 blue라면 next_blue로 노드를 이동시키는 방식으로 구현하려고 했다.

문제점

1. 구현이 너무 어렵다
2. 만약 현재 위치가 14번이라면, 14에서 16으로 이동하기위해서 시작노드부터 14번 노드까지 이동한 후에, 그다음 14번노드에서 16번으로 이동해야하는 번거로움이 있다.

그래서 문제를 풀지 못했다.

해결법

문제의 핵심은 주사위의 숫자는 1이상이라는것이다. 고로 10,20,30에서 출발한다면 일단 그다음 노드로 최소 한칸은 이동해야 한다는 것이다.

그러면 아까 문제는 16번노드가 두개로 겹치기 때문에 문제가 생겼다. 그러면 겹치지 않게 바꿔주면된다. 출처[블로그]

그러고나서, 5번노드에서 22번노드로 가는경우에는 어차피 1번은 이동을해야하니까 next값을 22로 설정하면된다. 그 다음 이동횟수 만큼 이동하면 된다.

    //10 20 30에서 파랑색 방향
    turn[5] = 22;
    turn[10] = 31;
    turn[15] = 28;

    //어차피 주사위는 한번은 굴림 파랑색에서 출발시 한칸 먼저 움직이기
        if (turn[current_pos] > 0) {
            move--;
            //만약 current_pos가 5라면 next_pos는 22가됌
            next_pos = turn[current_pos];
        }

정답코드

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

int map[34];
int score[34];
int turn[34];
bool check[34];
int position[4];
int dice[10];

int Max = 0;

void init() {
    //다이스 받기
    for (int i = 0; i < 10; i++) {
        int tmp = 0;
        cin >> tmp;
        dice[i] = tmp;
    }
    //바깥쪽 설정 인덱스 0번에 다음에 갈 1번이저장되어있음
    for (int i = 0; i < 21; i++) {
        map[i] = i+1;
    }

    //도착점
    map[21] = 21;

    for (int i = 22; i < 27; i++) {
        map[i] = i + 1;
    }
    map[27] = 20;

    map[28] = 29; map[29] = 30; map[30] = 25;
    map[31] = 32; map[32] = 25;

    //10 20 30에서 파랑색 방향
    turn[5] = 22;
    turn[10] = 31;
    turn[15] = 28;

    //점수판 갱신
    for (int i = 0; i < 21; i++) {
        score[i] = i * 2;
    }
    score[22] = 13; score[23] = 16; score[24] = 19;
    score[25] = 25; score[26] = 30; score[27] = 35;
    score[28] = 28; score[29] = 27; score[30] = 26;
    score[31] = 22; score[32] = 24;
}

void dfs(int cnt, int num) {
    if (cnt == 10) {
        if (num > Max)Max = num;
        return;
    }

    //4개의 말 확인
    for (int i = 0; i < 4; i++) {
        int move = dice[cnt];
        int current_pos = position[i];
        int next_pos = current_pos;
        //어차피 주사위는 한번은 굴림 파랑색에서 출발시 한칸 먼저 움직이기
        if (turn[current_pos] > 0) {
            move--;
            next_pos = turn[current_pos];
        }

        //움직이기
        while (move > 0) {
            move--;
            next_pos = map[next_pos];
        }

        if (next_pos == 21 || !check[next_pos]) {
            //cout << next_pos << " ";
            position[i]=next_pos;
            check[current_pos] = false;
            check[next_pos] = true;

            dfs(cnt + 1, num + score[next_pos]);

            position[i]=current_pos;
            check[current_pos] = true;
            check[next_pos] = false;
        }
    }

}

int main() {
    init();
    dfs(0,0);
    cout << Max;
}

문제 흐름 도식화 하기

이렇게 그래프가 있다고 치자. 처음에 문제를 읽고, 출발 노드에서 목적 노드까지 도착해야하므로 BFS를 통한 풀이를 생각하였다.

BFS

BFS의 시간복잡도를 살펴보자 BFS의 시간복잡도는 O(N+M) 노드수 + 간선수이다. 왜냐하면, 각 노드를 한번씩 방문하여 visited 체크를 해야하는 N번 그리고 각 노드에서 간선의 수가 M개 있으므로 M을 더하면 시간복잡도 내에 풀이가 가능하다.

그러나 문제는 맨처음 1번노드를 넣고 2번 3번노드를 방문처리를 한뒤에 큐에 넣는다. 문제는 1->2->3->4가 정답인데 이미 앞서서 2번과 3번 노드를 방문 처리하였기 떄문에 2번에서 3번으로 가지 못한다. 고로 1->3->4번의 경우만 탐색이 가능하다.

고로 BFS로는 풀이가 불가능하다.

DFS + 백트래킹

DFS는 어떨까 일반적인 DFS도 방문처리를 하기때문에 풀지 못하지만 백트래킹을 통해 풀면 전체 경우의 수를 파악할 수 있다. 예를들어, 1 2 3 4 경우를 파악한뒤 1 3 4 를 확인할 수 있다. 그러나 이건 시간 초과가 발생한다. 만약 노드가 10000개에서 간선의 갯수가 100,000개 이니까 양방향이므로 200,000개이므로 하나의 노드에서 평균 간선이 20개정도로 예측할 수있다.

그러면 전체 경우의 수는 하나의 노드에서 20개의 간선이 있고, 또 이어진 노드에서 간선이 직전노드를 제외하면 19개 또 다음노드가 18개 이렇게 이어지면 2019...로 무조건 시간초과가 나게 된다.

BFS+이분탐색

위의 그림에서 생각해볼게 있다. 1번노드에서 1을 넣으면 BFS탐색 한번으로 가능한가? 가능하다. 2를 넣어도 가능한가? 가능하다 3도 가능하다 4를 넣으면 1번과 3번의 cost가 3이니까 넣지 않고 2번노드는 5니까 넣을것이다. 그러면 3번노드는 방문처리가 안되어있으므로 2번노드에서 3번노드로 이동이가능하다.

그렇다면 무게 1부터 최고 무게인 1,000,000,000까지 for문을 돌면서 최댓값을 찾으면 된다. 그렇게 되면 O(1,000,000,000 * (N+M))이 된다. 당연히 시간초과가 된다.

이럴떄는 1,000,000,000를 이분탐색으로 가능한 무게를 찾아주면 된다. 그렇게 되면 이분탐색에서 log 1,000,000,000이 10정도니까 풀 수 있다.

//이분탐색코드
int start = 1;
    int end = 1000000000;

    while (start <= end) {
        int mid = (start + end) / 2;
        fill(visited, visited + N + 1, false);
        if (bfs(mid)) {
            start = mid + 1;
            if (mid > Answer) Answer = mid;
        }
        else {
            end = mid - 1;
        }
    }

//bfs코드
bool bfs(int weight) {
    queue<int>q;
    q.push(departure);
    visited[departure] = true;
    while (!q.empty()) {
        int n = q.front();
        q.pop();

        for (int i = 0; i < map[n].size(); i++) {
            int next = map[n][i].first;
            int cost = map[n][i].second;

            if (!visited[next] && weight <= cost) {
                q.push(next);
                if (next == arrival) return true;
            }
        }
    }
    return false;
}

전체코드
int N, M;
vector<vector<pair<int,int>>> graph;
bool visited[10001];
int departure, arrival;
int Answer = 0;

void init() {
    cin >> N >> M;
    graph.assign(N+1, {});
    for (int i = 0; i < M; i++) {
        int d, a, cost;
        cin >> d >> a >> cost;
        graph[d].push_back({a, cost});
        graph[a].push_back({d, cost});
    }
    cin >> departure >> arrival;
}

bool bfs(int weight) {
    queue<int> q;
    q.push(departure);
    visited[departure] = true;

    while (!q.empty()) {
        int n = q.front();
        q.pop();

        for (auto &edge : graph[n]) {
            int next = edge.first;
            int cost = edge.second;

            if (!visited[next] && cost >= weight) {
                if (next == arrival) return true;
                visited[next] = true;
                q.push(next);
            }
        }
    }
    return false;
}

void solve() {
    int start = 1, end = 1000000000;

    while (start <= end) {
        int mid = (start + end) / 2;
        fill(visited, visited + N + 1, false);

        if (bfs(mid)) {
            Answer = mid;
            start = mid + 1;
        } else {
            end = mid - 1;
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    init();
    solve();
    cout << Answer;
}

중요!!!!!!!
처음에는 vector<pair<int,int>>map[100001]로 썻는데
이것보다
vector<vector<pair<int,int>>>map;하고 N으로 resize를 하는게 좋다.
map.assign(100001,{});
그리고 사용은 동일하게 배열처럼 쓰면된다.

모델의 기본단위 - 층 add메서드를 통해 층을 쌓고, 각 층끼리 조합을 통해 CNN,RNN구현가능 모델 구축시 1~4과정을 계속 돌리면서 weight와 bias를 찾는과정

1. 데이터 생성 train data(During learning): 학습에 사용되는 데이터 -> 이걸 통해 가중치와 편향을 최적화하기 위해 사용됨. validation data(During learning): 오버피팅을 확인하기 위해 사용되는 데이터 -> 전체데이터를 한번 학습시킨뒤에 과적합 확인을 위해 사용됨 test data(After learning): 학습후 정확도 평가, 입력값에 대한 미래의 값을 예측하기위해 사용됨

2. 모델구축 Sequential(): 인공신경망 자체(그림에서 박스) Flatten: 입력층을 add로 붙임, 다차원 입력데이터를 1차원으로 정렬 Dense: 은닉층을 add()로 붙임, 입력과 출력사이의 있는 모든 노드가 연결되어있음, 첫번째 인자가 출력 노드수, activation - 활성화 함수(linear,sigmold,relu) 3번: 첫번째 계층에 바로 Dense 계층을 쓰는경우 같이 나타냄

3. 모델 컴파일 최적화 알고리즘, 오차함수, 모니터링 지표를 통해서 컴파일 model.compile(optimizer = SGD(learning_rate=0.1),loss='mse',metrics='['accuracy']') 최적화알고리즘 SGD, 학습률 0.1, 오차함수 mse, 매트릭 loss(손실)은 기본이므로 여기서 정확도도 같이 측정하겠다.

4. 모델 학습 손실함수값이 최소가 되게 각 층의 가중치와 편향을 찾음 model.fit(x_train,t_train,epochs=10,batch_size=100,verbose=0,validation_split=0.2) 첫번째 인자: 입력데이터, 두번째 인자: 정답데이터, 세번째 인자: 전체데이터를 총 10번반복, validation_data는 내가 만든 테스트셋, split은 데이터중 20프로를 가져다가 검증데이터로 사용

5. 모델 평가 test데이터를 통해 모델평가 및 임의의 데이터로 예측 model.evaluate(x_test, t_test, epochs=10, batch_size=100) x_test: 테스트 데이터, t_test는 정답데이터 , epochs: 평가를 위해 몇번을 반복할껀지

->return: 테스트 데이터의 정확도 model.predict(x_input_data,batch_size=100) 1번째 인자는 예측하고자하는 데이터, return: numpy

6. 모델 저장 가중치와 편향이 최적화된 모델을 저장 -> 다양한 테스트 데이터에 재학습 필요없음 model.save()

Linear Regression, Loss function

regression(회귀): Training Data를 통해 데이터 특성과 산관관계 파악 - 미지의 데이터가 주어졌을때 결과 예측 결국 왼쪽의 test 데이터를 바탕으로 y=Wx+b 그래프를 찾는것임 W는 가중치 b가 편향 y=Wx+b를 찾았다고 가정 -> x를 뿌려서 y를 찾으면 시험성적 t와의 차이만큼 오차가 생김 t-y 즉 ML은 t-y의 합이 최소가 되서 미래 값을 잘 예측할 수 있는 w랑 b를 찾는것임

즉 손실함수란 y=Wx+b에다가 x값을 넣은 y랑 t와의 차이를 전부 더해서 수식으로 나타내는것인데, 이게 t-y를하면 -, +가 합쳐져서 0일수있으니까 이걸 제곱해서 손실함수를 구함

즉 loss function은 평균오차를 구하는것임

Gradient Decent algorithm

b가 0이라고 가정 W값의 변화에따라 18.7 -> 4.67 -> 0 이런식으로 변화하는것을 알 수 있음 이걸 그래프로 그려보면 이렇게되고, 미분값이 0일때 E(w)값이 최소임을 찾을 수 있다. 즉, 임의의 W를 선택하고 미분값이 작아지는 방향으로 증가,감소시켜나가다가 더이상 작아지지 않는곳을 찾고, 그지점이 E(w)의 최소값임

E(W)의 편미분 값이 양수라면 W값은 왼쪽으로 이동해야함 E(W)의 편미분 값이 음수라면 W값은 오른쪽으로 이동해야함

알파: 학습율 편향인 b도 동일함 프로세스: trainig data가 들어오면 손실함수를 계산 -> 손실함수 값이 최소면 종료 -> 아니라면 손실함수가 최소가 되는 W,b를 편미분 값을 이용해 update

선형회귀

입력 정답 1 2 0 -4 5 4 3 4 ... 이렇게 input과 정답이 들어오면, y = w1x1 + w2x2 + w3x3 + b라는 선형회귀 문제가 된다 우리는 w1,2,3,b를 찾아야한다.

model = Sequential() //모델생성
model.add(Dense(1, input_shape(3,),activation = 'linear')) // 입력이 3개들어와서 3
model.compile(optimizer = SGD(learning_rate= 1e-2),loss = 'mse') // SGD 학습알고리즘, rate가 학습률 loss가 평균제곱오차

Classification(분류) 미지의 입력데이터에 대해서 결과값이 어떤 종류로 분류될 수 있는가를 예측 공부시간 9, fail ... 32, pass 라면, 미지의 공부시간 55가 들어오면 fail인지 pass인지

Logistic Regression

1. 앞에서 했던 Linear Regression으로 최적의 직선을 찾고
2. 그직선으로 위(1), 아래(0)으로 나눈다.

classification에서는 출력값 y가 0또는1을 가져야하는데 train data x가 z=Wx+b를 통과하면 z가 나오고, z를 sigmoid함수를 통해 계산값이 0.5보다 크면 1 작으면 0으로 분류하는 작업이 필요 sigmoid(y축 범위가 0또는1임)

Classification 프로세스

1. 입력과 정답 Trains data를 넣는다.
2. Regression을 통해 Wx+b를 찾는다.
3. Wx+b값을 sigmoid함수에 넣어서 y값을 찾는다.
4. 손실함수를 계산한다. 손실함수 계산방법 p(C=1|x) = y = sigmoid(Wx+b) -> 인풋 x값이 한개일때 출력이 1일 확률이다. p(C=0|x) = 1-p(C=1|x) = 1-y -> 인풋 x값이 한개일때 출력이 0일 ㅗ학률이다.

p(C=t|x) = y^t(1-y)^1-t이다. 그런데 x가 1개가아니라 a개라고 치면, 확률의 곱인 우도함수로 나타낼수있다. 즉 우도함수가 최대가 되도록 W,b를 업데이트 해나가야하는데, 문제는 함수값이 최대값을 알기위해서는 편미분을 해야하는데(앞에서 경사하강법) 곱셈은 그게 힘드니까, log를 취해줌 그러면 덧셈으로 바꾸고, 함수의 부호를 바꿔주면 함수의 최대화 문제를 최소화 문제로 바꿀수있다. 이렇게 만든 E(W,b)가 최소인지 확인하고 만약 아니라면, W,b의 값을 편미분을 통해서 바꿔가면서 업데이트 한다. 5. E(W,b)의 값이 최소라면 종료한다.

실제 예제 keras에서는 노랑색 부분에 sigmoid(Wx+b)를 수행 피마 인디언 부족 당뇨병 발병 여부 예측(data set)

import numpy as np

try:

    loaded_data = np.loadtxt('./diabetes.csv', delimiter=',')

    # training data / test data 분리

    seperation_rate = 0.3  # 분리 비율
    test_data_num = int(len(loaded_data) * seperation_rate)

    np.random.shuffle(loaded_data)

    test_data = loaded_data[ 0:test_data_num ]
    training_data = loaded_data[ test_data_num: ]

    # training_x_data / training_t__data 생성

    //training_data에서 0부터 마지막 전까지가 input data
    training_x_data = training_data[ :, 0:-1]
    //마지막이 정답데이터 발병유무
    training_t_data = training_data[ :, [-1]]

    # test_x_data / test_t__data 생성
    test_x_data = test_data[ :, 0:-1]
    test_t_data = test_data[ :, [-1]]

    print("loaded_data.shape = ", loaded_data.shape)
    print("training_x_data.shape = ", training_x_data.shape)
    print("training_t_data.shape = ", training_t_data.shape)

    print("test_x_data.shape = ", test_x_data.shape)
    print("test_t_data.shape = ", test_t_data.shape)

except Exception as err:

    print(str(err))

model = Sequential()

# 노드 1개인 출력층 생성, input_shape는 x_data.shape[1]이 input 층이 8개인것임 classification이니까 sigmoid사용
model.add(Dense(training_t_data.shape[1], 
                input_shape=(training_x_data.shape[1],),
                activation='sigmoid'))  


# 학습을 위한 optimizer, 손실함수 loss 정의
//학습알고리즘 SGD, 손실함수 로지스틱 classification에서는 정답이 0 또는 1이므로 loss함수를 binary로 지정
model.compile(optimizer=SGD(learning_rate=0.01), 
              loss='binary_crossentropy', 
              metrics=['accuracy'])

model.summary()

//fit메서드로 학습, validation_split: training data로 부터 20%비율로 validation data생성후 overfitting확인
hist = model.fit(training_x_data, training_t_data, epochs=500, validation_split=0.2, verbose=2)

model.evaluate(test_x_data, test_t_data)
//loss와 accuracy를 matplotlib을 통해확인
import matplotlib.pyplot as plt

plt.title('Accuracy')
plt.xlabel('epochs')
plt.ylabel('accuracy')
plt.grid()

plt.plot(hist.history['accuracy'], label='train accuracy')
plt.plot(hist.history['val_accuracy'], label='validation accuracy')

plt.legend(loc='best')

plt.show()

plt.title('Loss')
plt.xlabel('epochs')
plt.ylabel('loss')
plt.grid()

plt.plot(hist.history['loss'], label='train loss')
plt.plot(hist.history['val_loss'], label='validation loss')

plt.legend(loc='best')

plt.show()

epochs이 200번부터는 더이상 증가하지 않는데, 200번 부터는 오버피팅이 발생하는것임.

Deep Learning Basic

인공지능 -> 머신러닝(선형회귀, 로지스틱 회귀) -> 딥러닝 (ANN,CNN,RNN) Logistic 회귀는 중간에 은닉층이 없이 입력층과 출력층이 그대로 연결되어있음. 딥러닝은 은닉층이 존재

기본 코드

//모델 생성은 동일
model = tf.keras.models.Sequential()

//은닉층 추가, 은닉층 노드가 8개이고, 은닉층으로 들어오는 input이 1개인것임.
model.add(tf.keras.layers.Dense(8, input_shape(1,), acivattion = 'sigmoid'))

//은닉층과 출력층을 붙임, 출력노드 1개
model.add(tf.keras.layers.Dense(1,activation='sigmoid'))

//컴파일
model.compile(tf.keras.optimizers.SGD(learning_rate=0.1), loss = 'binary_crossentropy',mettrics=['accuracy'])
//모델 학습
model.fit(x_data,t_data,epochs = 500)

MNIST

입력층: Flatten을 사용해서 28*28크기의 2차원이미지를 784개의 길이를 가지는 1차원 벡터로 변환 은닉층: 은닉층의 갯수와 은닉층에서의 노드개수는 하이퍼 파라미터로 개발자가 튜닝 출력층: * 출력층 노드갯수는 정답의 범주와 같은 10개로 설정함, 학습데이터가 0부터 9 까지 10개이므로 출력층 노드갯수또한 10개로 설정해야함.

데이터 전처리

• 정규화 MinMax공식을 사용, 데이터 범위를 0~1사이의 값으로 변화, '[0,52,255]'->'[0,0.2,1.0]'

• 표준화 평균과 표준편차를 사용하여 특정범위를 벗어난 데이터를 outlier로 간주, data_new = data-Mean/표준편차

• 원핫 인코딩 정답개수와 동일한 크기를 가지는 리스트를 만들고, 정답에 해당하는 리스트의 인덱스값에 1을 넣고 나머지는 0을 넣음 -> 리스트에서 가장 큰 값을 가지는 인덱스를 정답으로 인식

//데이터 전처리: 정규화,원핫 인코딩
# 학습 데이터 / 테스트 데이터 정규화 (Normalization)
# 최솟값 0 최댓값 255
x_train = (x_train - 0.0) / (255.0 - 0.0)

x_test = (x_test - 0.0) / (255.0 - 0.0)


# 정답 데이터 원핫 인코딩 (One-Hot Encoding)
# 원핫인코딩은 to_categorical 메서드를 이용, MNIST의 정답데이터가 0~9까지 10개 중 한개이므로, num_classes=10으로 지정하여 10개의 리스트를 만들어야함
t_train = tf.keras.utils.to_categorical(t_train, num_classes=10)

t_test = tf.keras.utils.to_categorical(t_test, num_classes=10)

//모델생성
model = tf.keras.Sequential()

# input_shape이 28*28크기 2차원 이미지를 784개의 1차원 벡터를 Flatten으로 바꾸기
model.add(tf.keras.Input(shape=(28, 28)))
model.add(tf.keras.layers.Flatten())

#은닉층의 하이퍼 파라미터 100은 알아서 조정
model.add(tf.keras.layers.Dense(100, activation='relu'))

# 정답층의 노드갯수는 입력층의 노드개수와 동일한 10
model.add(tf.keras.layers.Dense(10, activation='softmax'))

# Optimzer을 Adam으로 사용, 손실함수는 원핫 인코딩 방식이므로 반드시 categorical_crossentropy를 사용해야함.
model.compile(optimizer=tf.keras.optimizers.Adam(learning_rate=1e-3),
              loss='categorical_crossentropy',
              metrics=['accuracy'])

#모델학습, traning data로부터 30%비율로 validationi data생성해서 오버피팅 확인
hist = model.fit(x_train, t_train, epochs=30, validation_split=0.3)

#정확도 확인
plt.title('Accuracy')
plt.xlabel('epochs')
plt.ylabel('accuracy')
plt.grid()

plt.plot(hist.history['accuracy'], label='train accuracy')
plt.plot(hist.history['val_accuracy'], label='validation accuracy')

plt.legend(loc='best')

plt.show()

2번째 Fashion MNIST 신발 한장의 사진 28*28이고, 학습데이터가 6만장, 만개의 테스트데이터, 정답이 0부터 9까지 10개로 나눠져있음, 0번 신발 1번 옷,,,,

fashion_mnist.load_data()로 테스트 데이터, 학습데이터를 불러옴

#Fashion Mnist예제에서는 원핫 인코딩은 사용하지 않음
x_train = (x_train - 0.0) / (255.0 - 0.0)

x_test = (x_test - 0.0) / (255.0 - 0.0)

... 앞선 예제와 동일

#compile부분이 loss함수가 원핫 인코딩이 아니므로, sparse_categorical_crossentropy로 설정

model.compile(optimizer=tf.keras.optimizers.Adam(learning_rate=1e-3),
              loss='sparse_categorical_crossentropy',
              metrics=['accuracy'])
.... 앞선 예제와 동일

CNN

컨볼루션 수식에서 f(x)*g(x-t)부분은 f(x)에다가 곱셈 연산을 통해 [1,0,2]라는 원본데이터를 [2,0,4]로 바꾸는것이고, 적분구간은 평균을 구하는것이다.

고로 시간에 따라 움직이는 데이터 g(x)에 의해서 입력 f(x)가 평균적으로 얼만큼 변하는지를 나타내는것임.

NN vs CNN 뉴럴 네트웍에서는 앞선시간했던것 처럼 은닉층이 존재하고 출력층에서 나온 y값을 손실함수의 최솟값인지 확인하는 과정을 거친다.

CNN도 동일하다. 그러나 NN에 해당하는 은닉층이 여러개의 컨볼루션 층과 완전연결층으로 구성되어있음을 확인할 수 있다.

conv: 입력데이터와 가중치들에 해당하는 집합체인 필터와의 컨볼루션 연산을 통해 입력데이터의 특징(feature)를 추출한다. 첫번재 컨볼루션층에 주어지는 입력데이터 A1 * filter_1+b2(첫번째 컨볼루션 층의 편향) -> A1의 특징 추출

두번재 컨볼루션층에 주어지는 입력데이터 A2 * filter_2+b3(두번째 컨볼루션 층의 편향) -> A2의 특징 추출

relu: activate function, 입력으로 주어진 값이 0보다 크면 그대로 내보내고, 0보다 작으면 0을 내보냄

pooling: 입력정보에서 최댓값, 최솟값, 평균값등으로 압축하여 연산량을 줄여준다. 대부분 max pooling이 사용됌.

패딩 컨볼루션 이후 디맨션 축소로인한 입력데이터 주변을 0으로 채우는것.

입력(4,4) 필터 (3,3) 패딩1, 스트라이드 1(필터 한번이동할때 간격) OH = (4 + 21 -3)/1 +1 =4 OW = (4+21-3/1) + 1 = 4 결과 출력데이터 크기 (4,4)

CIFAR 10

CIFAR 10은 aiplane,automobil,bird등 10개의 정답데이터, 하나의 사진당 32323이라는 컬러 데이터로 이루어져있음

#데이터 불러오기
(x_train, y_train),(x_test, y_test) = cifar10.load_data()

# 높이 너비 채널의 형태로 텐서로 변환
x_train=x_train.reshape(-1, 32, 32, 3)
x_test=x_test.reshape(-1, 32, 32, 3)

//255로 나누어 0과 1사이 값으로 정규화, 최댓값이 255이기 때문
x_train = x_train.astype(np.float32) / 255.0
x_test = x_test.astype(np.float32) / 255.0

cnn = Sequential()

#Convolution Layer, 3*3 크기의 필터 32개로 구성
cnn.add(Conv2D(input_shape=(32,32,3), kernel_size=(3,3),
               filters=32, activation='relu'))

#Convolution Layer, 3*3 크기의 필터 64개로 구성
cnn.add(Conv2D(kernel_size=(3,3), filters=64, activation='relu'))

#Maxpooling진행
cnn.add(MaxPool2D(pool_size=(2,2)))
#25%비율로 연결을 끊어 overfitting방지
cnn.add(Dropout(0.25))

#3차원 텐서를 1차원 벡터로 변환
cnn.add(Flatten())

#128개의 노드를 가지는 dense층
cnn.add(Dense(128, activation='relu'))
cnn.add(Dropout(0.5))
#출력층은 0부터 9까지 정답
cnn.add(Dense(10, activation='softmax'))

cnn.compile(loss='sparse_categorical_crossentropy',
            optimizer=tf.keras.optimizers.Adam(), metrics=['accuracy'])

hist = cnn.fit(x_train, y_train, batch_size=128, 
               epochs=30, validation_data=(x_test, y_test))

성능개선 방법

1. 컨볼루션 레이어를 더 중첩시키면 성능이 개선됨
2. 회전, 줌, shift등으로 이미지 데이터 보강
3. 높은 해상도로 바꾸기 3232 -> 469469
4. 배치 정규화 등

Image Data Augmentation 원본이미지에 회전, 반전, 확대등으로 이미지 데이터 개수를 증가시키는것

keras - imageDataGenerator제공

# ImageDataGenerator생성, 30도이내 회전, 가로 30%범위 이동, 40%범위에서 기울임, 좌우반전 가능
gen = ImageDataGenrator(rotation_range = 30, width_shift_range=0.3,shear_range=0.4,horizontal_flip=True)

#load_img호출시 return이 JpegImageFile이므로 CNN학습을위해서 img_to_array로 변형시켜줘야함 정규화로 0부터1사이 값으로
loaded_img = load_img(img_names[i],target_size=(100,100))

#정구화
loaded_img_array = img_to_array(loaded_img/255.0)

image_array_list.append(loaded_img_array)

batch_size = 2
#flow함수에 입력으로 주어지는 데이터는 (원본데이터 전체 갯수, 높이,너비,채널)의 형식인 4차원 텐서로 주어져야함.
# 만약 (100,100,3) 100by100 color 사진이 4개 있다면, (4,100,100,3)으로 주어져야함
#이렇게 전체 개수를 포함한 4차원텐서로 만들기위해서는 np.array등을 사용
#batch_size는 size만큼 무작위로 뽑아서 변형진행
data_gen = gen.flow(np.array(img_array_list), batch_size = batch_siz)

#두개의 이미지가 생성
img = data_gen.next() 

flow_from_directory()예제

data_gen = gen.flow_from_directory(diretory=data_path,batch_size=batch_siz,shuffle=True,target_size(100,100),class_mode='categorical')

flow_from_directory()함수를 이미지 부를때, 하위 디렉토리 이름에 맞춰 자동으로 라벨링을함 test_dir -cat: cat1.jpg,cat2.jpg -deer: derr1.jpg,,,

class모드는 정답을 나타내는 방식이며, binary는 0또는1 categorical은 one-hot encoding형태, sparse는 십진수형태

one-hot encoding 왜 사용하냐, 연속적인 특징이 없는경우에 연속성이 없다는것을 확실히 하기 위해서.

label = data_gen.next()에서 batch_siz만큼 이미지 생성 그러나 mode가 categorical방식이므로 label이 one-hot encoding방식으로 나타나므로 십진수로 표현하기위해서 np.argmax(label)을 해줘야함

결론 Linear Regression은 단일 선형회귀 y = w^Tx+b를 만드는 모델이다. 은닉층이 없거나 1개인 다층퍼셉트론이다. CNN은 입력이미지의 지역적 패턴을 잡아내기위해서 컨볼루션 연산을 사용하고, 마지막에 Linear Regression을 통해서 추출된 고수준 특징을 바탕으로 회귀값,분류를 산출하는것이다. 고로 마지막 Linear층은 그 특징으로 최종결정을 내리는 층이다.

Linear Regression은 사진을 한번 쓱보고 이건 뭐다라는 판단 CNN은 사진을 여러번 컨볼루션하며 선이있네 -> 원이 있네 -> 귀같네 -> 아,고양이네 이런식으로 구체화하는 판단.

이 문제의 핵심은 바로 행과 열을 뒤집는 순서가 상관 없다는 것이다. 여기서 2행 -> 4행 -> 2열을 뒤집나 4행 -> 2행 -> 2열을 뒤집나 2열 -> 4행 -> 2행을 뒤집나 최종 그림은 똑같이 나온다.

그럼 행을 두번 뒤집는 경우도 동일할까? 그렇다. 000 111 -> 101 -> 010 111 => 111 2열뒤집기 111 다시1행 뒤집기 101

그러면 1행을 먼저 두번 뒤집은 상태인 초기상태에서 2열을 뒤집어도 동일한 상태임을 확인 할 수있다.

그러면 이 지식을 가지면 우리는 이것을 알 수 있다.

1,2,3,,,,10행에서 조합을 통해 어떤 행을 뒤집을 지 찾는다. -> 1행 뒤집기 , 1과3행을 뒤집기,, 전부 뒤집기 이런식으로

그다음에 행을 전부 뒤집었다면 열을 비교해서 target과 열이 다르다면 열을 무조건 뒤집는다. 그러고 나서 Target과 동일한지 비교하면된다.

여기서 행이 만약 5개라면 총 경우의 수는 2^5이 된다. 여기서 비트 마스크를 사용할것이다.

5행이 있다면, 비트마스크를 통해 00000, 00001, 00010,,,,11111 을통해 1이면 뒤집는 행으로 판단하면된다.

for(int rowMask =0;rowMask<(1<<n);rowMask++){
        vector<vector<int>>tmp = beginning;
        int flip=0;
        for(int i=0;i<n;i++){
            if(rowMask & (1<<i)){
                rowflip(tmp,i);
                flip++;
            }

        }
}

전형적인 비트마스크 코드다. rowMask가 일단 0인건알겠고 (1<<n)이 뭔지 봐보자 1<<n에서 n이 3이면 1000이 된다. 그러면 십진수로 8이되는것이다. 그러면 rowMask가 0부터 8까지 int가 들어가는것이다. 핵심 1. n은 자리수이다. ____ n이 4이면 4자리

그렇다면 두번째 for문은 무엇일까. rowMask가 만약 1010 이라면 2번째와 4번째 행을 뒤집어야한다. for(int부터 n까지)자리수가들어가게되고 & 연산을 통해 2번째와 4번째가 동일한 i가 2,4일때만 참이된다. 즉 for문은 1인 자리수를 호출하는것이다.

#include <string>
#include <vector>

using namespace std;
int n=0;
int m=0;

void rowflip(vector<vector<int>> & matrix, int row){
    for(int i=0;i<m;i++){
        matrix[row][i] = 1 - matrix[row][i];
    }

}

void colflip(vector<vector<int>> & matrix, int col){
    for(int i=0;i<n;i++){
        matrix[i][col]= 1-matrix[i][col];
    }

}

int solution(vector<vector<int>> beginning, vector<vector<int>> target) {
    int answer = 0;

    n=beginning.size();
    m=beginning[0].size();

    int minFlip=999999;
    for(int rowMask =0;rowMask<(1<<n);rowMask++){
        vector<vector<int>>tmp = beginning;
        int flip=0;
        for(int i=0;i<n;i++){
            if(rowMask & (1<<i)){
                rowflip(tmp,i);
                flip++;
            }

        }

        for(int i=0;i<m;i++){
            if(tmp[0][i] != target[0][i]){
                colflip(tmp,i);
                flip++;
            }

        }

        if(tmp == target && minFlip>flip) minFlip = flip;
    }

    if(minFlip == 999999) {
        answer = -1;
    }else{
        answer = minFlip;
    }

    return answer;
}

1. 핵심적으로 55부터 먼저 가능하면 덮어쓰는 형식으로 가면 안된다, 왜냐하면 44를 놓는것이 답일수도 있기때문
2. 그러면 결국 1을 만났을때 5칸 4칸,3칸,,,이런식으로 전부 확인을 해야한다는점. -> 여기서 재귀를 써야한다는것을 판단.
3. 재귀호출시 항상 0~10까지로 범위를 설정 왜냐하면, 그래야 그다음 1을 찾을 수 있기 때문
4. 만약 if문을 넣고 끝나면 반드시 return을 넣을것 이게 분할정복에 해당하는, 2630문제와 동일한데, return을 안넣으면 무한루프에 빠질수있음 왜냐하면 그림과 같이 2,2을 덮고 0인걸 1로 복구했다 치자 그러면 재귀니까 마지막으로 호출된 0,0으로 가게되고 여기서 이중포문을 탈출하지 못했다면, for문을 돌아 2,2의 1을 덮어쓰러 가야하기 때문이다.
5. 마지막으로 시작점이 좌표로 주어진경우 i=x, x+k(이동할좌표) 이런식으로 쓰면된다.

코드

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <cmath>
#include <queue>
#include <deque>
#include <stack>
using namespace std;

int Answer = 999999;
int map[10][10];
int paper[5] = { 5,5,5,5,5 };

void init() {
    for (int i = 0; i < 10; i++) {
        for (int j = 0; j < 10; j++) {
            cin >> map[i][j];
        }
    }
}

bool one_left() {
    for (int i = 0; i < 10; i++) {
        for (int j = 0; j < 10; j++) {
            if (map[i][j]==1)return false;
        }
    }
    return true;
}

//만약 5,5주어지고 5장짜리면, 5 6 7 8 9 임 -> 10을 넘김녀 안됌, y도 마찬가지
bool check_size(int x, int y , int k) {
    if ((x + k >= 10) || (y + k >= 10)) return false;
    return true;
}

//k숫자만큼 1이 있는지 확인
bool check_paper(int x, int y, int k) {
    //3,3위치에서 k가 4이면 5장이라는거임 5장이면 3,4,5,6,7임 그러면 i는 3이고 i< 3+4+1인 8이어야함
    for (int i = x; i < x + k+1; i++) {
        for (int j = y; j < y + k+1; j++) {
            if (!map[i][j]) return false;
        }
    }
    return true;
}

void fill_paper(int x, int y, int k) {
    //k가 4이면 5장을 채워야한다는거임 x 가 3이면 3,4,5,6,7 이고 x+k가 3+4니까 7이다. 고로 8이 와야하므로 
    for (int i = x; i < x + k+1; i++) {
        for (int j = y; j < y + k+1; j++) {
            map[i][j] = 0;
        }
    }
}


void unfill_paper(int x, int y, int k) {
    //k가 4이면 5장을 채워야한다는거임 x 가 3이면 3,4,5,6,7 이고 x+k가 3+4니까 7이다. 고로 8이 와야하므로 
    for (int i = x; i < x + k + 1; i++) {
        for (int j = y; j < y + k + 1; j++) {
            map[i][j] = 1;
        }
    }
}
void solve(int cnt) {
    if (cnt > Answer) return;
    //색종이를 다 채운경우
    if (one_left()) {
        if (cnt < Answer) {
            Answer = cnt;
            return;
        }
    }

    for (int i = 0; i < 10; i++) {
        for (int j = 0; j < 10; j++) {
            if (map[i][j]==1) {
                for (int k = 4; k >= 0; k--) {
                    if (paper[k] > 0 && check_size(i,j,k) && check_paper(i,j,k)) {
                        paper[k]--;
                        fill_paper(i, j, k);
                        solve(cnt + 1);
                        unfill_paper(i, j, k);
                        paper[k]++;
                    }
                }
                return;
            }
        }
    }
}

int main() {
    init();
    solve(0);
    if (Answer == 999999) { cout << "-1"; }
    else {
        cout << Answer;
    }
}

Prove 프로젝트를 하던 중, 회원 탈퇴시 엔티티를 삭제하는 과정에서 문제를 만났다.

구글링을 했을때 여러가지 삭제 방법이 있었는데, 각각의 방식을 알아보고, 나의 생각을 드러내 보도록 하겠다.

CASCADE

CASCADE란? 어떤 엔티티와 다른 엔티티가 매우 밀접한 관계에 있을때, A라는 엔티티에 특정 작업을 수행했을때, B라는 엔티티에도 동일한 작업을 행하는 것입니다.

예를 들어, 계시판과 댓글은 아주 밀접한 관계에 있습니다. 왜냐하면, 계시판이라는 엔티티가 선행되지 않으면 댓글이라는 엔티티는 존재 의미가 없기 때문입니다.

@Entity
public class Post{
    @Id
    @GeneratedValue
    private Long id;

    @OneToMany(mappedBy = "post", casacade = CascadeType.REMOVE)
    private List<Comment> comments = new ArrayList<>();
    ...
}

@Entity
public class Comment {

    @Id
    @GeneratedValue
    private Long id;

    private String value;

    @ManyToOne
    @JoinColumn(name = "post_id")
    private Post post;
    ...
}

이러한 관계에서 JPA를 사용하여서 postrepository.deleteByID()이런식으로 호출하면, Post도 지우지만, 해당 엔티티와 연관된 Comment엔티티까지 Cascade속성이 전파되어 같이 삭제 된다.

장점으로는, 당연히 굳이 Comment 삭제 로직을 작성하지 않아도 되서 편할것입니다.

그러나, Cascade 옵션은 사용하지 않는 것이 좋은데 이유는 바로

1. 양방향 연관관계 매핑시 충돌가능성 일단 RDB는 방향 자체가 존재하지 않는다. 즉 양방향이라는 개념자체가 없다. 고로 DB와 비슷하게 가려면 양방향 연관관계를 사용하지 않는다. OneToMany를 사용하더라도 실질적으로 One쪽의 DB에 컬럼이 생기지 않는다. 또한 양방향 연관관계를 설정하면 양쪽 모두에 참조 변수를 설정해야하는 불편함이 있다.

2. N+1문제 JPA를 사용해서 삭제를 하면 Post에 Comment가 10개 가 있으면 총 delete쿼리가 11개가 날라가는 심각한 문제가 발생한다. 해당 내용은 여기를 참고하자

3. 의도치 않은 삭제 만약 User <-> Comment <-> Like와 같이 엔티티가 연관관계가 있는데 User를 삭제하면 Comment도 자동 삭제 된다고 가정합시다. 그런데 Like는 Comment를 참조해야합니다. 이처럼 의도치않은 로직으로 삭제가 진행되는 경우가 있습니다.

일단 제일 큰 문제점은 JPA를 사용하면 쿼리를 N+1로 날린다는 점입니다.

OnDelete

그렇다면 양방향 연관관계를 하지 않으면서 N+1개의 쿼리를 날리지 않는 방법은 없을까요? 있습니다. @Ondelete

@Entity
public class Comment {

    @Id
    @GeneratedValue
    private Long id;

    private String value;

    @ManyToOne
    @JoinColumn(name = "post_id")
    @OnDelete(action = OnDeleteAction.CASCADE)
    private Post post;
    ...
}

이렇게 하고 Post의 OneToMany를 삭제한다. 이렇게 실행하면 Hiberate에서 alter문이 발생하게 되는데, on delete cascade가 추가되게 됩니다. 고로 @OnDelete는 JPA가 해주는게 아니라 데이터베이스가 제약조건을 설정하여서 레코드를 연쇄적으로 제거합니다.

고로, DDL에 의해서 스키마 자체에 해당 cascade조건이 추가가 되고, JPA가 아닌 제약조건을 통해서 데이터베이스에서 참조하는 레코드를 연속적으로 제거해줍니다.

당연히 쿼리를 N+1개 날리는게아니라, delete쿼리를 Post 한개만 날리고, 해당 쿼리를 받은 데이터베이스가 스키마의 제약조건을 살펴보고 이와 연관된 Comment도 같이 지워주는 것입니다.

그러나 문제가 있다. 해당 연관된 연쇄작업은 데이터베이스가 하기 때문에, FK를 통해서 Post의 Id에 해당되는 Comment 레코드로 가서 일일히 삭제하기 때문에 FK가 반드시 필요하게 됩니다.

그러나, 실무에서는 FK를 지정하는 경우가 많다고 합니다. 이부분은 저도 실무를 접하지 않아서 정확히 알지 못하지만, FK제약조건으로 Lock이 걸리거나, 스키마 변경이 어려워서 사용하지 않는다고 합니다.

FK제약조건으로 인해 요구사항에 따라 변화할 수 있는 스키마 구조가 어렵고 다른 테이블의 pk를 fk로 지정하여 insert할때 pk가 진짜 있는지 부모테이블에 Lock을 걸고 확인하던가, 아니면 레코드를 삭제할때 해당 pk를 fk로 사용하는 레코드가 있는지 판별해야하는등 이슈가 있을 것입니다.

그래서 아마, JPA를 사용할때

@Entity
public class Comment {

    @Id
    @GeneratedValue
    private Long id;

    private String value;

    @ManyToOne
    @JoinColumn(name = "post_id", foreignKey = @ForeignKey(ConstrainMode.NO_CONSTRAINT))
    private Post post;
    ...
}

이런식으로 포링키를 사용하지 않는다는 조건을 넣는다고 알고 있습니다. 고로, FK를 지정하지 않는다면 @OnDelete방식도 수행하기 어렵습니다.

그래서 어떻게 해야하냐?

지금 현재 저의 프로젝트의 엔티티를 보면 Prove(계시판)

public class Prove {
    @ManyToOne(fetch = FetchType.LAZY)
    private UserEntity user;
    ...
}

좋아요

public class Like {
    @Id
    @GeneratedValue(strategy = GenerationType.IDENTITY)
    private Long id;

    @ManyToOne(fetch = FetchType.LAZY)
    @JoinColumn(name = "user_id")
    private UserEntity user;

    @ManyToOne(fetch = FetchType.LAZY)
    @JoinColumn(name = "prove_id")
    private Prove prove;

}

댓글

public class Comment {
    @Id
    @GeneratedValue(strategy =  GenerationType.IDENTITY)
    private Long id;

    private String comment;

    @ManyToOne(fetch = FetchType.LAZY)
    UserEntity user;

이런식 등등으로 각 엔티티에 User가 있습니다.

그래서 UserService에서 delete메서드를 만들고

public ResponseEntity<?> deleteUser() {
        Long userId = userRepository.findByUsername(getUseranmeWithToken()).getId();

        // 순차적으로 삭제
        commentLikeRepository.deleteByUserId(userId);
        commentRepository.deleteByUserId(userId);
        likeRepository.deleteByUserId(userId);
        proveRepository.deleteByUserId(userId);
        userRepository.deleteUserById(userId);

        return new ResponseEntity<>("유저 삭제 완료",HttpStatus.OK);
    }

그냥 엔티티 별로 별도 쿼리를 날리면서 삭제를 해줍니다.

    @Query("DELETE FROM CommentLike cl WHERE cl.user.id = :userId")
    void deleteByUserId(@Param("userId") Long userId);

Query("DELETE FROM Prove p WHERE p.user.id = :userId")
    void deleteByUserId(@Param("userId") Long userId);

이렇게 되면 총 5개의 쿼리를 별도로 날립니다. JPQL을 사용하여서 쿼리는 N+1문제가 생기지 않습니다.

결론

FK를 걸지 않는다, 양방향 연관관계 매핑을 맺지 않는다, N+1문제를 발생시키지 않는다.

이러한 조건을 만족하기 위해서는 각 엔티티별로 별도로 delete쿼리를 날리는게 최선인것 같습니다. 혹시 다른 의견이나 방법이 있다면 알려주십쇼

해당 문제는 위상정렬 + DP 문제입니다.

위상정렬이란?

사이클이 없는 방향 그래프의 모든 노드를 순서대로 나열하는 것을 의미한다. 세 과목을 모두 수강하기위한 순서는 자료구조 -> 알고리즘 -> 고급알고리즘 (O) 자료구조 -> 고급 알고리즘 -> 알고리즘 (X)

이를 위해서는 진입차수가 0인 노드들을 확인해야한다.

1. 진입차수가 0인 모든 노드를 큐에 넣는다.
2. 큐가 빌때까지 다음의 과정을 반복한다. 큐에서 원소를 꺼내 해당 노드에서 나가는 간선을 그래프에서 제거한다. 새롭게 진입차수가 0이된 노드를 큐에 넣는다.

https://www.youtube.com/watch?v=xeSz3pROPS8

해당 문제를 보면, 위상정렬의 특징을 알 수 있는데, 반드시 직전의 건물들이 모두 지어져야 현재 건물을 지을 수 있다는점에서 확인 할 수 있다.

위상정렬 코드

//노드의 갯수 v, 간선의 갯수 e
int v, e;

//들어오는 차수
int indegree[10001];
vector<int> graph[10001];

//위상정렬함수
void topologySort(){
    vector<int> result;
    queue<int> q;
    for(int i=1;i<=v;i++){
        if(indegree[i]==0) q.push(i);
    }

    while(!q.empty()){
        int now = q.front();
        q.pop();
        result.push_back(now);

        for(int i=0;i<graph[now].size();i++){
            indegree[graph[[now][i]]]-=1;
            if(indegree[graph[now][i]]==0) q.push(graph[now][i]);
        }
    }

    for(int i=0;i<result.size();i++){
        cout<< result[i] << ' ';
    }
}

사이클이 없어야하는 이유가 바로, 사이클이 존재하면 진입차수가 0인 노드가 아에 없기 때문입니다.

틀린코드

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <queue>
#include <cstring>
using namespace std;

int N;
int K;
int Time[1001];
vector<int> graph[1001];
int indegree[1001];
int target;
int Max = 0;

void topologysort() {
   queue<pair<int, int>>q;

   for (int i = 1; i <= N; i++) {
      if (indegree[i] == 0) q.push({ i,Time[i] });
   }

   while (!q.empty()) {
         int now = q.front().first;
         int cost = q.front().second;
         q.pop();

         for (int i = 0; i < graph[now].size(); i++) {
            if (graph[now][i] == target && Max < Time[graph[now][i]] + cost) Max = Time[graph[now][i]] + cost;
            indegree[graph[now][i]] -= 1;
            if (indegree[graph[now][i]] == 0) q.push({ graph[now][i], cost + Time[graph[now][i]] });
         }
   }
}

int main() {
   int T = 0;
   cin >> T;
   for (int i = 0; i < T; i++) {
      cin >> N >> K;
      for (int j = 1; j <= N; j++) {
         cin >> Time[j];
      }
      for (int j = 0; j < K; j++) {
         int a = 0;
         int b = 0;
         cin >> a >> b;
         graph[a].push_back(b);
         indegree[b] += 1;
      }
      cin >> target;
      topologysort();
      cout << Max << "\n";

      //초기화
      Max = 0;
      memset(Time, 0, sizeof(Time));
      memset(indegree, 0, sizeof(indegree));
      for (int i = 0; i < 1001; i++) {
         graph[i].clear();
      }

   }
}

해당 코드의 핵심은 queue에 넣을때 지금까지 거쳐온 건물 짓는 시간을 같이 넣는것이다. 첫번째가 노드 숫자고, 두번째가 해당 건물을 지을때 까지 걸린 시간이다.

if (graph[now][i] == target && Max < Time[graph[now][i]] + cost) Max = Time[graph[now][i]] + cost; 이부분에서 어차피 우리는 target의 max값만 알고 싶은거니까, 이렇게 7번 노드가 타겟이면, 2번노드에서 Max값과 비교 3번노드에서 Max값과 비교하니까 이렇게만 해도 되는줄 알았다.

그런데 문제가 있다. 2번 노드와 3번노드는 진입노드가 아무것도 없으니까 괜찮은데, 2번노드 뒤에 다른 진입노드들이 있다면 항상 최대 값임을 보장하지 않는다는 것이다.

예를 들어보자, 맨처음에 <1,100> <4,1> 이 큐에 들어갈 것이다. 그다음 <1,100>에서는 간선을 --시키고 3번노드와 2번노드가 연결되어있으므로 그냥 넘어간다. <4,1>에서 <3,2>가되고, <2,3>이 된다 왜냐하면 이미 간선을 줄여놨기 때문이다. 고로, 2번까지의 총 시간이 3이 되는것이다 원래는 101인데 말이다.

고로 DP를 사용하여서 Max값을 갱신해가면서 적어줘야한다.

정답코드

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <queue>
#include <cstring>
using namespace std;

int N;
int K;
int Time[1001];
int Dp[1001];
vector<int> graph[1001];
int indegree[1001];
int target;
int Max = 0;

void topologysort() {
    queue<int>q;

    for (int i = 1; i <= N; i++) {
        if (indegree[i] == 0) q.push(i);
        Dp[i] = Time[i];
    }

    while (!q.empty()) {
            int now = q.front();
            q.pop();

            for (int i = 0; i < graph[now].size(); i++) {
                int next = graph[now][i];
                indegree[next] -= 1;
                if (Dp[next] < Time[next] + Dp[now]) Dp[next] = Time[next] + Dp[now];
                if (indegree[next] == 0) q.push(next);
            }
    }
}

int main() {
    int T = 0;
    cin >> T;
    for (int i = 0; i < T; i++) {
        cin >> N >> K;
        for (int j = 1; j <= N; j++) {
            cin >> Time[j];
        }
        for (int j = 0; j < K; j++) {
            int a = 0;
            int b = 0;
            cin >> a >> b;
            graph[a].push_back(b);
            indegree[b] += 1;
        }
        cin >> target;
        topologysort();
        cout << Dp[target] << "\n";

        //초기화
        Max = 0;
        memset(Time, 0, sizeof(Time));
        memset(indegree, 0, sizeof(indegree));
        memset(Dp, 0, sizeof(Dp));
        for (int i = 0; i < 1001; i++) {
            graph[i].clear();
        }

    }
}

https://codenme.tistory.com/32 난이도가 상당한거 같습니다..

처음에 틀린코드

#include <iostream>
#include <vector>
#include <algorithm>
#include<memory.h>
#include <string>

using namespace std;

bool graph[1000001];
vector<int>e;
int current = 0;

string solution(int n, int k, vector<string> cmd) {
    memset(graph, true, sizeof(graph));
    string answer = "";
    current = k;
    for (int i = 0; i < cmd.size(); i++) {
        string commend = cmd[i];
        if (commend.size() > 1) {
            //U,D
            char direction = commend[0];
            int amount = 0;
            string tmp = "";
            for (int x = 2; x < commend.size(); x++) {
                tmp += commend[x];
            }
            amount += stoi(tmp);
            int extra = 0;
            //D인경우
            if (direction == 'D') {
                for (int j = 0; j < e.size(); j++) {
                    if (e[j] <= current + amount && current < e[j]) extra++;
                }
                current += (amount+extra);
            }
            else {
                //U인경우
                for (int j = 0; j < e.size(); j++) {
                    if (e[j] < current && current -amount <= e[j]) extra++;
                }
                current -= (amount+extra);
            }
        }
        else if (commend[0] == 'C') {
            graph[current] = false;
            e.push_back(current);
            //마지막인경우
            if (current == n-1) {
                while (1) {
                    if (!graph[current]) { 
                        current--; 
                        continue;
                    }
                    break;
                }
            }
            else {
                while (1) {
                    if (!graph[current]) {
                        current++;
                        continue;
                    }
                    break;
                }
            }
        }
        else {
            //Z인경우
            graph[e[e.size() - 1]] = true;
            e.erase(e.end()-1);
        }
    }

    for (int i = 0; i < n; i++) {
        if (graph[i]) { answer += "O"; }
        else {
            answer += "X";
        }
    }
    return answer;
}

우선 이 문제를 보고 배열로 풀어야겠다는 생각을 했습니다. U으로 두번을 이동하면 두번 이동할때 false인 인덱스가 있다면 한칸 더 이동하는 방식으로 하였습니다.

C의 경우 vector에다가 넣고, graph를 false로 갱신했습니다. 마지막인 경우: 앞으로 current를 이동하는데 false이면 계속 이동시켰습니다. 마지막이 아닌경우: 뒤로 current를 이동시키는데 false이면 계속 이동시켰습니다.

Z의 경우 그냥 true로 바꾸고 vector에서 지워줬습니다.

그런데 이렇게 하면 시간초과가 발생하는데, 솔직히 시간복잡도를 계산해봐도 왜 그런지는 자세히는 모르겠습니다. 왜냐하면, C와 Z는 O(1)로 해결할수 있고 문제는 U,D인데 중간에 false가 얼마나 있는지 모르니까 계속 움직여야하는건 맞습니다. 근데 노드가 cmd의 X의 합이 1000000 이라했으니까 결국 U,D로 움직이는 연산이 1,000,000번이면 되는데 이게 굳이 시간초과가 뜨는 이유는 모르겠습니다.

해설에서도 이런식으로 밖에 나와있지 않아 잘 이해가 가지 않았습니다.

해결 링크드 리스트를 사용하라 했습니다.

        if(c[0] == 'U'){
            int num = stoi(c.substr(2,8));
            for(int i=0;i<num;i++){
                cur = cur -> prev;
            }

U의 경우 cur을 num만큼 앞으로 땡겨줍니다.

else if(c[0]=='D'){
            int num = stoi(c.substr(2,8));
            for(int i=0;i<num;i++){
                cur = cur -> next;
            }

D의 경우 cur -> next로 뒤로 땡겨줍니다.

else if(c[0]=='C'){
            stk.push(cur);

            //중간 노드삭제
            if(cur -> prev !=NULL){
                cur -> prev -> next = cur -> next;
            }
            if(cur -> next !=NULL){
                cur -> next -> prev = cur -> prev;
            }
            //마지막노드는 cur을 앞으로 나머지는 cur을 한칸 뒤로
            if(cur -> next == NULL) cur = cur -> prev;
            else cur = cur -> next;
        }

C의 경우 그냥 중간에 있는 노드를 삭제한다고 생각해봅시다. cur -> prev -> next = cur -> next와 cur -> next -> prev = cur -> prev를 해줘야합니다. 그런데 맨 앞의 노드는 cur -> prev가 NULL 이므로 NULL -> next를 통해 세그먼트 fault가 발생할 수 있습니다. 맨 뒤의 노드도 마찬가지 입니다. cur -> next 가 NUll 인데 NULL -> prev를 하면 세그먼트 fault가 발생할 수 있습니다.

그래서 두가지의 조건을 적어주고, 이제 cur을 이동시키면 됩니다. cur의 이동조건은 2가지 입니다. 만약 그냥 이동시키면 되면 cur -> next를 통해서 이동시키고 마지막인 경우는 앞으로 한칸 이동시키면 됩니다.

else{
            Node * repair = stk.top();

            if(repair -> next != NULL) repair -> next ->prev = repair;
            if(repair -> prev != NULL) repair -> prev -> next = repair;
            stk.pop();
        }

Z의 경우도 간단합니다. repair -> next -> prev = repair을 해줘야합니다. 그런데 생각해보면 여기도 repair -> next가 없을 수 있습니다. 언제? 마지막 노드일때 repair -> prev도 마찬가지입니다. 맨 앞의 노드의 경우 NULL이 발생합니다. 고로 해당 조건을 적고 pop을 해줍니다.

실제 시험장에서 풀라하면, 아마 segment fault때문에 콘솔에 찍어보지도 못하고 아마 절대 못풀었을 거 같습니다. 이걸 연결리스트로 풀 생각을 하기보다는, 일단 정확성이라도 맞출수 있는 실력을 기르는게 중요한거 같습니다..

이번 문제의 알고리즘은 DP를 사용해서 풀었습니다.

답안이 생각나지 않아, https://yabmoons.tistory.com/158 해당 글을 참고하여 풀었습니다.

처음 로직을 생각한건 x=1,y=1에 왔을때, 이중 포문을 map끝까지 돌면서 1인지 검사하여서 가장 큰 사각형을 찾는 로직을 생각했는데 이는 만약 모든 정사각형이 1로 채워져 있다면 100010001000*1000 이므로 1000000000000 이므로 무조건 시간 초과가 날것이라고 생각했습니다.

딱봐도 뭔가 DP로 풀어야할것 같긴한데, DP는 이전의 결과를 저장해 뒀다가, 다음에 써먹어야하는데 어떤 이전의 결과를 저장해 둘건지 생각이 나질 않았습니다.

우선 해당 사각형에서 끝에 있는 1이 왜 2*2 큰 사각형이 되지 못할까요?

당연히 왼쪽, 위쪽, 왼쪽 대각선의 3가지 블럭이 1이 아니기 때문입니다. 고로 2*2 사각형이 되려면 기준점이 1,1 배열의 원소라면 1,0 0,0 0,1 에 1이 있어야합니다.

그러면 3*3은 어떨까요? 3 곱하기 3 배열에서 마지막 빨간색 원소를 기준으로 3칸짜리 사각형이 되려면, 2칸짜리 사각형이 3개가 있어야합니다.

이러한 점들을 고려하여 2 * 2행렬로 가보면 아까 1로 전부 채워진 행렬에서 마지막 끝점을 기준으로 [i-1][j] [i][j-1] [i-1][j-1]의 배열에서 가장 작은 값을 가져와서 +1을 해줍니다. 만약 여기서 0이 하나라도 있다면 1이므로 마지막 끝 기준점의 원소배열의 값이 2가 아니라 1일것입니다.

해당 로직을 적용하면 3 * 3은 이렇게 됩니다.

그리고 조건을 생각해보면 숫자가 0이면 무조건 어차피 사각형이 안만들어지므로, 건너뛰고 1이면 검사를 하고

map을 map[0][0]부터 쭉 값을 넣고, 왼쪽 윗쪽, 대각만 확인하는거니까 for문을 1,1부터 돌리면 되는거 아닌가? 싶은데 그러면 안되는게

000000000 000000000 100000000 000000000... 이런식이면 1,1부터 검사를 하면 무조건 다 0이라 정답이 0으로 나오고 3,1에 있는 1을 계산을 못하게 된다.

고로, map을 초기화 할때 1,1부터 넣어서 계산을 하도록 해야한다.

#include <iostream>
#include <vector>

using namespace std;

int map[1010][1010];

int main() {
    int n = 0;
    int m = 0;

    cin >> n >> m;

    for (int i = 1; i <= n; i++) {
        string s = "";
        cin >> s;
        for (int j = 0; j <= s.size(); j++) {
            map[i][j+1] = s[j] - '0';
        }

    }

    int answer = 0;

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (map[i][j] == 1) {
                int tmp = 2000;
                if (map[i - 1][j - 1] < tmp) tmp = map[i - 1][j - 1];
                if (map[i][j - 1] < tmp) tmp = map[i][j - 1];
                if (map[i - 1][j] < tmp) tmp = map[i - 1][j];

                map[i][j] = tmp + 1;
                if (tmp + 1 > answer) answer = tmp + 1;
            }
        }
    }

    cout << answer * answer << endl;
    return 0;
}

이번 포스팅은

https://mangkyu.tistory.com/76 해당 블로그의 좋은 Spring Security 글을 읽고, 이해한 내용을 풀어서 쉽게 설명하고, 다른 글들을 참고하여서 Spring Security의 동작원리에 대해서 설명해보겠다.

Spring Security를 공부하면서 느낀점이 참, 다형성을 활용하여서 유지보수는 물론이고, 확장에 참 용이하게 만들었다는 느낌이 들었다.

서론은 이만 줄이고, 시작해보도록 하겠다.

Spring Security란?

Spring Security는 인증과 인가를 담당하는 스프링 하위 프레임 워크이다. 그렇다면 인증과 인가가 무엇인가?

• 인증 유저가 누구인지 확인하는 절차, 로그인하는것

• 인가 유저가 요청하는 request를 실행할 수 있는 권한이 있는 유저인가를 확인하는 것. 로그인을 하더라도, role이 admin이 아니면 admin 작업을 실행할 수 없다.

Spring Security는 인증 절차를 거친후에 인가 절차를 진행한다. 이때 필요한 인증,인가에 대한 정보를 Principal을 아이디, Credential을 비밀번호로 사용한다.

Spring Security는 인증에 대한 부분을 Filter흐름에 따라 처리하고 있다.

그렇다면 Filter는 어떻게 작동하는가? 기본적으로 Filter는 Servlet에서의 필터를 말하며, Request & Response를 처리할때 실행되는 자바 클래스이다.

Request가 Client로부터 Spring Controller에 도달하기전에 한번 Response가 Spring Controller로부터 Client에게 전달되기 전에 한번 이렇게 실행이 된다.

이해를 쉽게 하기 위해서는 로그인 요청을 보냈을때부터, 하나하나 로직을 타가면서 이해를 해보도록하자.

클라이언트가 API 요청을 하면 Client -> Web server(Tomcat) -> Filter Chain -> Dispatcher Servlet -> Controller 이 순서로 동작하게 된다.

여기서 Filter Chain에다가 요청마다 Logging을 하는 Filter를 두었다면, 요청이 들어올때마다, Controller의 로직 성공 유무에 관계없이 요청을 로깅할 수 있을 것이다.

그렇다면 Spring Security Filter Chain은 무엇인가? Spring Security에서는 Filter 인터페이스를 구현하여 보안에 필요한 작업들을 수행하는 필터를 제공한다. 우리가 많이 보았던, UsernamePasswordAuthenticationFilter도 여기에 속한다. 중요한것은, 이것은 Filter라는 것이다. 우리가 커스텀하여서 UsernamePasswordAuthenticationFilter의 구현체를 만들 수 있는데, 예를 들어, null이 불가능하게 한다던지 id가 10자리 이상 넘어가면 거절한다는지, 원하는 개발 환경에 맞춰 커스텀할 수 있게 인터페이스로 만들었다는것이 좋다.

그렇다면, Servlet filter에서 Spring Security의 filter chain으로 어떻게 넘어갈까? DelegatingFilterProxy와 FilterChainProxy이다.

그림과 같이, Client의 요청을 받아 Servlet Filter Chain을 진행하던중 DelegatingFilterProxy객체에 다다르면, Application Context에서 SpringSecurityFilterChain이름으로 생성된 Bean을 찾는다. 그게 바로 FilterChainProxy이다. 해당 빈을 찾으면 SpringSecurityFilterChain으로 요청을 위임한다. 각각의 Filter들에게 순서대로 요청을 체인형식으로 넘기면서 처리한다.

그러면, 그림과 같이 LogoutFilter, UsernamePasswordAuthenticationFilter, Bean으로 등록된 FilterChainProxy등등은 Spring Security 라이브러리를 설치하면 기본적으로 등록이된다.

그럼 SpringSecurity의 아키텍쳐를 봐보자 처음에 약간 헷갈린게, HTTP Request가 들어온다고 치자, 그러면 AuthenticationFilter로 간다고 그림에 보여져 있다.

그래서 아 Filter Chain에서 AuthenticationFilter가 있는건가? 싶었는데 그건또 아니다. 그러면 이게 무슨말이냐면, AuthenticationFilter라는 구체적인 클래스가 존재하는게 아니고, 인증을 처리하는 여러 Filter에 존재하는 예를 들어, 우리가 많이 아는 UsernamePasswordAuthenticationFilter등을 범용적인 용어로 AuthenticationFilter라고 지칭한다.

고로 우리는 여기까지 요청이 들어왔을때 SpringSecurityChain에서 UsernamePasswordAuthenticationFilter까지 들어온 것을 확인할 수 있다.

UsernamePasswordAuthenticationFilter

@Log4j2
public class CustomAuthenticationFilter extends UsernamePasswordAuthenticationFilter {

    public CustomAuthenticationFilter(AuthenticationManager authenticationManager) {
        super.setAuthenticationManager(authenticationManager);
    }

    @Override
    public Authentication attemptAuthentication(HttpServletRequest request, HttpServletResponse response) throws AuthenticationException {
        UsernamePasswordAuthenticationToken authRequest = new UsernamePasswordAuthenticationToken(request.getParameter("userEmail"), request.getParameter("userPw"));
        setDetails(request, authRequest);
        return this.getAuthenticationManager().authenticate(authRequest);
    }

}
출처: https://mangkyu.tistory.com/77 [MangKyu's Diary:티스토리]

UsernamePasswordAuthenticationFilter는 인터페이스다. 왜냐하면 그 이유는 앞에서 설명을 했다. id가 null인지 뭐 개발 환경에 따라서 조건에 맞춰서 개발하는 커스텀 구현체를 만들기 위해서이다.

attemptAuthentication메서드 부분을 봐보자, request에서 id,password를 가져오고 UsernamePasswordAuthenticationToken을 만들고 반환한다.

그러면, UsernamePasswordAuthenticationToken이 뭐냐?

public class UsernamePasswordAuthenticationToken extends AbstractAuthenticationToken {
    // 주로 사용자의 ID에 해당함
    private final Object principal;
    // 주로 사용자의 PW에 해당함
    private Object credentials;

    // 인증 완료 전의 객체 생성
    public UsernamePasswordAuthenticationToken(Object principal, Object credentials) {
        super(null);
        this.principal = principal;
        this.credentials = credentials;
        setAuthenticated(false);
    }

    // 인증 완료 후의 객체 생성
    public UsernamePasswordAuthenticationToken(Object principal, Object credentials,
            Collection<? extends GrantedAuthority> authorities) {
        super(authorities);
        this.principal = principal;
        this.credentials = credentials;
        super.setAuthenticated(true); // must use super, as we override
    }
}


public abstract class AbstractAuthenticationToken implements Authentication, CredentialsContainer {
}
출처: https://mangkyu.tistory.com/76 [MangKyu's Diary:티스토리]

User의 Id가 Principal 역할을 하고 Password가 Credential역할을 한다. 첫번째 생성자는 인증 전의 객체를 생성하고, 두번째 생성자는 인증이 완료된 객체를 생성한다.

그러면 attemptAuthentication메서드에서는 당연히, 인증전 객체가 생성되는 것이다.

어? 그런데 UsernamePasswordAuthenticationToken을 보면 AbstractAuthenticationToken의 하위클래스인데 AbstractAuthenticationToken은 Authentication을 구현한 추상클래스이다.

그러면 Authentication이 뭐냐? Authentication은 현재 접근하는 주체의 정보와 권한을 담는 인터페이스이다. 해당 Authentication객체는 SecurityContext에 저장되며, SecurityContextHolder를 통해서 SecurityContext에 접근하고, SecurityContext를 통해 Authentication에 접근할 수 있다.

public interface Authentication extends Principal, Serializable {
    // 현재 사용자의 권한 목록을 가져옴
    Collection<? extends GrantedAuthority> getAuthorities();

    // credentials(주로 비밀번호)을 가져옴
    Object getCredentials();

    Object getDetails();

    // Principal 객체를 가져옴.
    Object getPrincipal();

    // 인증 여부를 가져옴
    boolean isAuthenticated();

    // 인증 여부를 설정함
    void setAuthenticated(boolean isAuthenticated) throws IllegalArgumentException;
}
출처: https://mangkyu.tistory.com/76 [MangKyu's Diary:티스토리]

아 그러면 여기서 알 수 있다. 단순히 말하면 Authentication이 id,password를 담은 객체이고, 이걸 구현한게 UsernamePasswordAuthenticationToken이구나 라고 알 수 있다.

이렇게 AuthenticationFilter는 아직 인증이 되지 않은 UsernamePasswordAuthenticationToken을 AuthenticationManager에게 전달한다. AuthenticationManager는 실제로 인증을 처리할 여러개의 AuthenticationProvider를 가지고 있다.

그러면 AuthenticationManager는 뭐고, AuthenticationProvider는 뭐냐?

AuthenticationManager

public interface AuthenticationManager {
    Authentication authenticate(Authentication authentication) 
        throws AuthenticationException;
}
출처: https://mangkyu.tistory.com/76 [MangKyu's Diary:티스토리]

인증에 대한 부분은 AuthenticationManager를 통해서 처리되는데, 실질적으로 처리되는 로직은 AuthenticationManager에 등록된 AuthenticationProvider에 의해서 처리된다. 인증이 성공하면 2번째 생성자를 통해서 인증이 성공한 객체를 생성하여 SecurityContext에 저장한다.

AuthenticationManager를 보면 인터페이스이다. 해당 인터페이스를 구현한 구현체가 ProviderManager인데 실제 인증과정에 대한 로직을 가지고 있는 AuthenticationProvider들을 List로 가지고 있어서 for문을 돌면서 모든 Provider를 조회하면서 authenticate처리를한다.

public class ProviderManager implements AuthenticationManager, MessageSourceAware,
InitializingBean {
    public List<AuthenticationProvider> getProviders() {
        return providers;
    }
    public Authentication authenticate(Authentication authentication)
            throws AuthenticationException {
        Class<? extends Authentication> toTest = authentication.getClass();
        AuthenticationException lastException = null;
        Authentication result = null;
        boolean debug = logger.isDebugEnabled();
        //for문으로 모든 provider를 순회하여 처리하고 result가 나올 때까지 반복한다.
        for (AuthenticationProvider provider : getProviders()) {
            ....
            try {
                result = provider.authenticate(authentication);

                if (result != null) {
                    copyDetails(authentication, result);
                    break;
                }
            }
            catch (AccountStatusException e) {
                prepareException(e, authentication);
                // SEC-546: Avoid polling additional providers if auth failure is due to
                // invalid account status
                throw e;
            }
            ....
        }
        throw lastException;
    }
}
출처: https://mangkyu.tistory.com/76 [MangKyu's Diary:티스토리]

그러면, 우리는 UsernamePasswordAuthenticationToken을 가지고 아이디와 패스워드가 맞는지 등을 확인할 Provider를 만들어야한다.

그런데 가만히 생각해보면, JWT를 사용할때나, 세션을 사용할때나, 혹은 개인 개발환경에 맞게 Provider들이 전부 다를것이다.

public interface AuthenticationProvider {

    // 인증 전의 Authenticaion 객체를 받아서 인증된 Authentication 객체를 반환
    Authentication authenticate(Authentication var1) throws AuthenticationException;

    boolean supports(Class<?> var1);

}
출처: https://mangkyu.tistory.com/76 [MangKyu's Diary:티스토리]

그래서 AuthenticationiProvider가 인터페이스고 해당 authenticate메서드를 구현한 구현체를 우리가 만들어주면 된다.

@RequiredArgsConstructor
@Log4j2
public class CustomAuthenticationProvider implements AuthenticationProvider {

    @Override
    public Authentication authenticate(Authentication authentication) throws AuthenticationException {
        UsernamePasswordAuthenticationToken token = (UsernamePasswordAuthenticationToken) authentication;
        // AuthenticaionFilter에서 생성된 토큰으로부터 아이디와 비밀번호를 조회함
        String userEmail = token.getName();

    }

    @Override
    public boolean supports(Class<?> authentication) {
        return authentication.equals(UsernamePasswordAuthenticationToken.class);
    }

}
출처: https://mangkyu.tistory.com/77 [MangKyu's Diary:티스토리]

SpringSecurity에서는 Username으로 DB에서 데이터를 조회한 다음에, 비밀번호의 일치 여부를 검사한다. 그렇기 때문에 먼저 UsernamePasswordToken으로 부터 아이디를 조회해야한다.

이렇게 AuthenticationProvider에서 id를 조회하면, UserDetailsService로 id를 넘겨줘서 id에 해당하는 실제 User객체를 가져와야한다.

public interface UserDetailsService {

    UserDetails loadUserByUsername(String var1) throws UsernameNotFoundException;

}
출처: https://mangkyu.tistory.com/76 [MangKyu's Diary:티스토리]

UserDetailsService는 인터페이스이고, loadUserByUsername이라고 Username(id)를 통해서 UserDtatils라는 User객체를 반환하는 하나의 메서드만 있다.

import java.util.Collections;

@RequiredArgsConstructor
@Service
public class UserDetailsServiceImpl implements UserDetailsService {

    private final UserRepository userRepository;

    @Override
    public UserDetailsVO loadUserByUsername(String userEmail) {
         return userRepository.findByUserEmail(userEmail).map(u -> new UserDetailsVO(u, Collections.singleton(new SimpleGrantedAuthority(u.getRole().getValue())))).orElseThrow(() -> new UserNotFoundException(userEmail));
    }

}
출처: https://mangkyu.tistory.com/77 [MangKyu's Diary:티스토리]

우리는 userRepository를 주입받아서 userRepository에서 userEmail을 통해서 User객체를 찾은다음에 UserDetailsV0를 만들어서 반환한다.

어? 근데 갑자기 UserDetailsV0는 왜나온걸까? UserDetailsService의 loadUserByUsername메서드의 반환형이 UserDetail이다.

public interface UserDetails extends Serializable {

    Collection<? extends GrantedAuthority> getAuthorities();

    String getPassword();

    String getUsername();

    boolean isAccountNonExpired();

    boolean isAccountNonLocked();

    boolean isCredentialsNonExpired();

    boolean isEnabled();

}
출처: https://mangkyu.tistory.com/76 [MangKyu's Diary:티스토리]

UserDetails는 인터페이스로 User에대한 정보를 반환하는 메서드로 이루어져있다. 그렇다면, UserDetails를 구현한 구현체가 UserDetailsV0인 것이다.

@RequiredArgsConstructor
@Getter
public class UserDetailsVO implements UserDetails {

    @Delegate
    private final UserVO userVO;
    private final Collection<? extends GrantedAuthority> authorities;

    @Override
    public Collection<? extends GrantedAuthority> getAuthorities() {
        return authorities;
    }

    @Override
    public String getPassword() {
        return userVO.getUserPw();
    }

    @Override
    public String getUsername() {
        return userVO.getUserEmail();
    }

    @Override
    public boolean isAccountNonExpired() {
        return userVO.getIsEnable();
    }

    @Override
    public boolean isAccountNonLocked() {
        return userVO.getIsEnable();
    }

    @Override
    public boolean isCredentialsNonExpired() {
        return userVO.getIsEnable();
    }

    @Override
    public boolean isEnabled() {
        return userVO.getIsEnable();
    }
}
출처: https://mangkyu.tistory.com/77 [MangKyu's Diary:티스토리]

해당 구현체를 통해서 User에대한 정보를 반환할 수 있다.

여기서도, 이제 다형성의 힘을 느낄수 있다. UserDetails에 보면 String getPassword(); String getUsername();등으로 이름과 Password등을 반환하는 메서드는 반드시 작성하게 되어있다. 그러나, 꼭 Password만 가지고 구분하는게 아니라, 예를들어, 개개인에게 OTP코드마냥 9821을 발급하고, 이 코드와 Password 두개가 동일해야 로그인이 가능하게 커스텀하고 싶을 수있다.

@RequiredArgsConstructor
@Getter
public class UserDetailsVO implements UserDetails {

    @Delegate
    //userV0의 필드에 String OTP가 있음
    private final UserVO userVO;
    private final Collection<? extends GrantedAuthority> authorities;

    public String getOTP(){
        return userV0.getOTP();
    }

이런식으로 커스텀 할수 있는 확장성이 있다.

그러면 여기까지 정리해보면 우리는 인증이 아직 되지 않은, UsernamePasswordAuthenticationToken으로 부터, ID를 가져왔고, 해당 ID로 부터 DB에서 일치하는 User객체를 가져와서 UserV0를 가져왔다.

그럼 앞으로 해야하는 것은 간단하다. DB에서 가져온 UserV0와 토큰에서의 비밀번호를 비교하면 된다.

CustomAuthenticationProvider 전체 구현

@RequiredArgsConstructor
@Log4j2
public class CustomAuthenticationProvider implements AuthenticationProvider {

    private final UserDetailsService userDetailsService;
    private final BCryptPasswordEncoder passwordEncoder;

    @Override
    public Authentication authenticate(Authentication authentication) throws AuthenticationException {
        UsernamePasswordAuthenticationToken token = (UsernamePasswordAuthenticationToken) authentication;
        // AuthenticaionFilter에서 생성된 토큰으로부터 아이디와 비밀번호를 조회함
        String userEmail = token.getName();
        String userPw = (String) token.getCredentials();
        // UserDetailsService를 통해 DB에서 아이디로 사용자 조회
        UserDetailsVO userDetailsVO = (UserDetailsVO) userDetailsService.loadUserByUsername(userEmail);

        if (!passwordEncoder.matches(userPw, userDetailsVO.getPassword())) {
            throw new BadCredentialsException(userDetailsVO.getUsername() + "Invalid password");
        }

        return new UsernamePasswordAuthenticationToken(userDetailsVO, userPw, userDetailsVO.getAuthorities());
    }

    @Override
    public boolean supports(Class<?> authentication) {
        return authentication.equals(UsernamePasswordAuthenticationToken.class);
    }

}

이제 아까는 String userEmail = token.getName()만 적었고, 나머지 로직을 완성하였다. UserDetailsService로부터 조회한 정보와 입력받은 비밀번호가 동일한지 확인 하였다. AuthenticationProvider도 인터페이스고, UserDetailsService로 부터 가져온 UserDetail도 인터페이스기때문에, 커스텀한 구현체를 적절하게 사용할 수 있다.

여기서는 비밀번호만 확인했지만, 아래와같이 OTP도 같이 확인 할 수 있다.

String Otp = token.getOtp();
if (!passwordEncoder.matches(userPw, userDetailsVO.getPassword()) && userDetailsV0.getOtp() != Otp) {
            throw new BadCredentialsException(userDetailsVO.getUsername() + "Invalid password");
        }

만약 모든 로직을 통과한다면, 인증이 된 UsernamePasswordAuthenticationToken을 발급하기위해서 파라미터가 3개인 생성자를 호출하여서 만들고 반환한다.

AuthenticationProvider를 통해 인증이 완료된 UsernamePasswordAuthenticationToken을 AuthenticationFilter로 반환하고, 해당 Authentication객체(토큰)을 SecurityContextHolder에 저장하면 인증과정이 끝나게 된다.

이렇게 인증과정이 끝난거고, 인가는 따로 적절히 로직을 만들어주면된다. Controller로 요청이 들어오면 해당 토큰에서의 Role을 가져와서 admin이면 실행, 아니면 거절 이런식으로 로직을 완성시키면 된다.

https://yabmoons.tistory.com/128 해당 블로그 글을 보고 문제를 풀었습니다.

이번 문제는 합분해 문제입니다. 만약 N,K가 3,3이라면 3가지 숫자를 가지고 3을 만들어야합니다. 여기서 어떤 알고리즘을 적용할까 했는데, 모듈러 연산을 보고 경우의 수가 너무 많다고 생각했습니다. 각 자리마다 0부터 시작해서 문제를 재귀로 풀어볼까 생각했는데 경우의 수가 너무 많은거같아, 알고리즘을 보았지만 DP라고 했는데 이조차도 DP를 어떻게 적용해야할지 감이 안잡혀서 답을 봤습니다.

일단 N,K가 3,3일때의 경우를 전부 적어보겠습니다. 003 012 102 021 201 111 030 120 210 300 이렇게 10개 입니다.

그렇다면, DP를 어떻게 적용해야할까 생각했는데, 약간의 아이디어를 2293 동전 C++문제에서 가져왔습니다. 문제 바로가기 약간의 설명을 하자면 만약에, 2원을 만들수있는 경우가 3가지라고 가정해보겠습니다. 그러면 3원을 가지고 5원을 만들 수 있는 경우는 몇가지일까요? 바로 3가지입니다.

왜냐하면, 2원+3원은 5원입니다. 그런데 2원을 만들수있는 경우가 3가지이면, 각 3가지 방식에 3원만 넣으면 되는것이기 때문입니다. DP[5]+=DP[5-3]

이처럼, DP는 이전의 내용을 가져와서 더해줘야합니다. 그러면 해당문제에서는 어떤 이전의 내용을 가져와야할까요?

2개를 가지고 0을 만드는 방법을 생각해봅시다. 여기다가 그냥 3을 더하면 3가지숫자로 3을 만드는것일겁니다.

2개를 가지고 1을 만드는 방법을 생각해봅시다. 여기다가 그냥 2을 더하면 3가지숫자로 3을 만드는것일겁니다.

2개를 가지고 2를 만드는 방법을 생각해봅시다. 여기다가 그냥 1을 더하면 3가지숫자로 3을 만드는것일겁니다.

2개를 가지고 3을 만드는 방법을 생각해봅시다. 여기다가 그냥 0을 더하면 3가지숫자로 3을 만드는것일겁니다.

이처럼 //앞이 사용하는 숫자 갯수, 뒤가 만들려는 숫자 DP`[3][3]' = DP[2][0]+DP[2][1]+DP[2][2]+DP[2][3]입니다. 003 -> 두개의 숫자로 0을 만드는경우 012 102 -> 두개의 숫자로 1을 만드는경우 021 201 111 -> 2를 만든느경우 030 120 210 300 -> 3을 만드는경우

for (int i = 0; i <= N; i++) {
        DP[1][i] = 1;
    }

처음에는 어차피 숫자1개로 N을 만드는 방법은 그냥 N을 쓰는수밖에 없습니다. 즉 이 경우는 숫자 1개를 가지고 N을 만드는방법입니다.

//2개를 가지고
    for (int k = 2; k <= K; k++) {
        //0을만드는법,1을 만드는법,,,N을 만드는법
        for (int n = 0; n <= N; n++) {
            //DP[3][3] = DP[2][0] + DP[2][1]... DP[2][3];
            for (int i = 0; i <= n; i++) {
                DP[k][n] += DP[k - 1][i];
            }
            DP[k][n] = DP[k][n] % 1000000000;
        }
    }

첫번째 for문: 숫자 2개를 가지고 K개까지 확인한다. 두번째 for문: 숫자 N까지 만드는방법 세번째 for문: DP`[3][3]' = DP[2][0]+DP[2][1]+DP[2][2]+DP[2][3]이 로직을 구현

정답코드

#include <iostream>

using namespace std;

long long DP[201][201];

int main() {
    int N = 0;
    int K = 0;
    cin >> N >> K;

    for (int i = 0; i <= N; i++) {
        DP[1][i] = 1;
    }

    //2개를 가지고
    for (int k = 2; k <= K; k++) {
        //0을만드는법,1을 만드는법,,,N을 만드는법
        for (int n = 0; n <= N; n++) {
            //DP[3][3] = DP[2][0] + DP[2][1]... DP[2][3];
            for (int i = 0; i <= n; i++) {
                DP[k][n] += DP[k - 1][i];
            }
            DP[k][n] = DP[k][n] % 1000000000;
        }
    }

    cout << DP[K][N] << "\n";
    return 0;
}

해당문제는 저는 DFS를 사용해서 풀었습니다. 다만, 어차피 DFS를 한번만 0,0에서 시작하므로 BFS와 다를것이 없습니다.

판의 0,0은 무조건 공기입니다. 그러므로, dfs(0,0)으로 시작합니다.

void dfs(int i, int j) {
    visited[i][j] = true;
    for (int a = 0; a < 4; a++) {
        int nx = i + dx[a];
        int ny = j + dy[a];
        if (nx >= 0 && nx < N && ny >= 0 && ny < M && !visited[nx][ny]) {
            if (map[nx][ny] == 0) {
                dfs(nx, ny);
            }
            else {
                visited[nx][ny] = true;
                map[nx][ny] = 0;
                cheese++;
            }
        }
    }

}

핵심은 이것입니다. i,j가 0,0이라고 가정하고 상하좌우를 살펴봅니다. 그리고 만약 내가 공기의 좌표인데 만약 다음 좌표가 0으로 공기이다. 그러면 dfs로 재귀호출을해서 다음 공기좌표의 상하좌우를 살펴봅니다.

그러나, 만약 내가 공기인데 다음좌표가 치즈이면, 0으로 갱신하고 cheese를 ++합니다. 중요한것은 방문처리를 치즈도 해줘야한다는 것입니다. 000 011 011 만약 지금 1,0좌표의 공기 0에 있다고 가정하겠습니다. 만약 visited처리를 하지 않고 map만 바꾼다면 000 001 011 이 될것입니다. 그리고 1,0 -> 0,0 -> 0,1 좌표에와서 0,1에서 상하좌우를 살펴봅니다. 앞서서 visited처리를 해주지 않았으므로 0이니까 1,1을 재귀함수로 부르게 됩니다. 그러면 1,1에서 상하좌우를 살펴보게되면 2,2가 1이므로 삭제하게 됩니다.

고로 치즈를 지우면 visited처리를 해줘야합니다.

#include <iostream>
#include <vector>
#include <utility>
#include <string.h>
#include <queue>
#include <algorithm>
using namespace std;

int N;
int M;

int dx[4] = { -1,1,0,0 };
int dy[4] = { 0,0,1,-1 };

int map[101][101];
bool visited[101][101];

int cheese = 0;

void dfs(int i, int j) {
    visited[i][j] = true;
    for (int a = 0; a < 4; a++) {
        int nx = i + dx[a];
        int ny = j + dy[a];
        if (nx >= 0 && nx < N && ny >= 0 && ny < M && !visited[nx][ny]) {
            if (map[nx][ny] == 0) {
                dfs(nx, ny);
            }
            else {
                visited[nx][ny] = true;
                map[nx][ny] = 0;
                cheese++;
            }
        }
    }

}

bool check(int map[101][101]) {
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            if (map[i][j]) return false;
        }
    }
    return true;
}

void solution(int cnt) {
    cheese = 0;
    //이걸로 공기부분 true로 놓기
    dfs(0, 0);

    int temp = 0;

//map에 치즈가 있는지 검사
    bool flag = true;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            if (map[i][j]) { flag = false; break; }
        }
        if (!flag) break;
    }
    //치즈가 없다면 정답
    if (flag) {
        cout << cnt + 1 << "\n";
        cout << cheese;
        return;
    }
    //치즈가 없다면 다시 검사
    memset(visited, false, sizeof(visited));
    solution(cnt + 1);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> N;
    cin >> M;

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            int tmp = 0;
            cin >> tmp;
            map[i][j] = tmp;
        }
    }

    solution(0);
}

출처: https://www.skshieldus.com/download/files/download.do?o_fname=EQST%20insight_Special%20Report_202209.pdf&r_fname=20220926092447242.pdf

SQL Injection이란?

SQL Injection이란 설계된 SQL구문에서 사용자 입력값 검증이 미흡하여, 악의적으로 작동되는 쿼리를 삽입해서 공격하는것이다.

만약 공격자가 관리자의 아이디인 admin의 존재를 알고있지만, 비밀번호는 모를때 공격하는과정이다.

악성 클라이언트가 아이디: admin' -- //나머지는 주석처리 비밀번호: 1234 //주석처리되어 상관없음

Select * from member where id = admin --' and pw = '1234'

이런식으로 '--이후 주석처리로 인해 비밀번호 검증부분이 주석 처리된다. 이를 통해 admin계정에 접속이 가능하다.

공격 유형에 따른 분류

Union SQL Injection Union 연산자는 두개 이상의 select문에 대한 결과를 하나로 묶어 데이터베이스에서 추출한다.

고로 기존의 select문 select * from member where id = 'candi'에다가 union절을 통해서 공격을 실행한다.

조건 1. Select문과 Union Select문의 칼럼수가 동일해야한다. => where 조건절에 Order By절을 이용하여 컬럼 수를 추출한다.(Order By절은 데이터 정렬시 사용되므로, select문의 컬럼갯수보다 많은 숫자를 조회하면 에러를 발생시키므로 컬럼의 갯수를 확인할 수 있다.)

SELECT id, name, email FROM users ORDER BY 1; -- 정상 실행
SELECT id, name, email FROM users ORDER BY 2; -- 정상 실행
SELECT id, name, email FROM users ORDER BY 3; -- 정상 실행
SELECT id, name, email FROM users ORDER BY 4; -- 오류 발생

조건 2. 컬럼은 각 순서별로 동일한 데이터형이어야 한다. => 데이터 형을 알기 위해서 컬럼의 갯수만큼 null문자를 입력해서 해당 컬럼의 데이터형이 숫자인지 문자인지 판단한다.

예를 들어 users에 3개의 컬럼 id,name,email이 있고 각각 int,varchar,varchar의 형태라면, 아까 조건 1을 통해서 컬럼갯수가 3개라는 사실을 파악할 수 있다.

이제 각 컬럼의 데이터 형을 추출하기 위해서 NULL값을 사용하여 테스트를 진행한다.

SELECT id, name, email FROM users
UNION
SELECT NULL, NULL, NULL; -- 정상 실행 (모든 컬럼이 NULL은 모든 데이터형과 호환)

//그 다음, 특정 컬럼에 NULL 대신 숫자 또는 문자열을 넣어 테스트 한다.
-- 첫 번째 컬럼이 숫자형인지 확인
SELECT id, name, email FROM users
UNION
SELECT 1, NULL, NULL; -- 정상 실행 (첫 번째 컬럼이 숫자형)

-- 두 번째 컬럼이 문자열인지 확인
SELECT id, name, email FROM users
UNION
SELECT NULL, 'test', NULL; -- 정상 실행 (두 번째 컬럼이 문자열)

-- 세 번째 컬럼이 문자열인지 확인
SELECT id, name, email FROM users
UNION
SELECT NULL, NULL, 'test@example.com'; -- 정상 실행 (세 번째 컬럼이 문자열)

해당 과정을 거치면, 컬럼갯수와 데이터형을 알아낼 수 있다.

기존의 select문에 union select절을 추가하면, 기존에 id,pw,email이 3개의 컬럼임을 알고 있으므로 id에는 null을 넣고, 나머지에 pw,email컬럼에 union절에 있는 id,pw를 출력시킬 수 있다.

Error Based SQL Injection 데이터베이스의 문법에 맞지 않는 쿼리문 입력 시 반환되는 에러 정보를 기반으로 공격하는 방법이다.

에러를 유발하는 함수중 하나인 CTXSYS.DRITHSX.SN을 사용하여 Member 테이블의 첫번째 컬럼의 패스워드를 조회한 결과 발생한 에러 메시지에서 비밀번호를 획득 할 수 있다.

자세한 사용법보다는 이런 함수를 통해서 유출이 될 수있다 정도로 생각하고 넘어가자.

Blind SQL Injection 참인 쿼리문과 거짓인 쿼리문 삽입시 반환되는 데이터를 비교하여서 데이터를 추출하는 공격이다.

일반적인 SQL Injection은 데이터를 바로 반환받아 공격자가 결과를 확인할 수 있지만, Blind Sql Injection은 데이터를 직접적으로 출력하는게 아니라 쿼리의 참,거짓 결과를 통해서 데이터를 노가다로 알아내는 방식이다.

예를 들어, users테이블에서 username을 추출하는 방식으로

SELECT username FROM users LIMIT 1 OFFSET 0;

해당 쿼리문을 통해서 alice라는 이름을 가져올 수 있다.

SELECT IF(SUBSTRING((SELECT username FROM users LIMIT 1 OFFSET 0), 1, 1) = 'a', 'true', 'false');

If절에는 alice가 나오고, alice의 첫번째 글자가 'a'인지 확인한다. 이떄 substring으로 alice에서 첫번째 글자를 짜른뒤에 확인한느것이다.

SELECT IF(SUBSTRING((SELECT username FROM users LIMIT 1 OFFSET 0), 2, 1) = 'l', 'true', 'false');

다음 sql에서는 2번째 l를 짜르고 'l'과 동일한지 비교한다. 이렇게 반복을 노가다로 계속하다보면 alice라는 이름을 추출할 수 있다.

단순히 대문자 소문자 52개니까 alice만해도 52^5이므로 굉장히 큰 경우의 수가 있으므로, 공격자가 일일히 수행하기보다는 도구를 사용하여 해당 과정을 자동화 한다.

해결방안

Prepared Statement Prepared Statement는 SQl Injection을 방어하는 최선의 보안 대책이며, SQL구문이 미리 컴파일 되어 있어 입력값을 변수로 선언해 두고 필요에 따라 값을 대입하여 처리하는 방식이다.

Select문의 동작과정 Select문은 DBMS 내부적으로 4단계의 과정 Parse,Bind, Execute, Fetch를 거쳐 결과를 출력한다.

Parse를 통해서 select문을 거치면 아래와 같은 파싱트리가 생성된다.

일반적인 Statement는 Parse부터 Fetch까지 모든 과정을 매번 수행한다. 따라서, SQL에 악의적인 영향을 미치는 특수문자나 예약어가 들어간 경우 Parse과정에서 SQL구문의 일부로 작용하여 SQL Injection공격이 가능한다.

예를들어, Select * from member where id = admin --' and pw = '1234' 해당 구문에서 영향을 미치는 특수문자는 --이다. 왜냐하면 구문분석과정에서 --를 통해서 뒤에 pw 조건절은 무시하기 때문이다. 고로 --가 SQL구문의 일부로 작용하여 SQL Injection공격이 가능한것이다.

그러나 Prepared Statement의 동작과정의 경우 약간 다르다. 구문 분석과정을 최초 1회만 수행하여 생성된 결과를 메모리에 저장해 필요할 때마다 사용한다.

이를 통해 두가지 장점을 얻을 수 있다.

1. 미리 구성된 파싱트리를 사용하기 때문에 Statment에 비해 시간을 단축할 수 있다.
2. SQL구문이 미리 컴파일되어 사용자 입력값을 변수로 선언해 값을 대입하여 사용한다.

예시를 들어보자 취약한 Statment 코드

Connection conn = null;
Statement stmt = null;
ResultSet rs = null;
...
String sql = "SELECT * FROM MEMBER WHERE ID = '"+param_id+"' AND PW = '"+param_ passwd+"'";
stmt = conn.createStatement();
rs = stmt.executeQuery(sql);

마약 역기서 param_id는 admin--'이 들어가고 parm_passd에 1234가 들어간다고 치자 그러면 완성된 sql문은 Select * from member where id = admin --' and pw = '1234'이게 되고 stmt.excuteQuery(sql)을 통해서 해당 쿼리문을 parse하고 --가 특수문자로 sql구문의 일부로 작용이된다.

안전한 Prepared Statment코드

String param_id=request.getParameter("id");
String param_passwd=request.getParameter("passwd");
Connection conn = null;
PreparedStatement pstmt = null;
ResultSet rs = null;
…
String sql = "SELECT * FROM MEMBER WHERE ID = ? AND PW = ?";
pstmt.setString(1, param_id);
pstmt.setString(2, param_passwd);
rs = pstmt.executeQuery(sql);

여기서는 사용자의 입력값이 쿼리에 직접 삽입되지 않고, 파라미터 바인딩을 통해서 처리된다.

그래서 admin--'와 같이 입력을해도

SELECT * FROM MEMBER WHERE ID = 'admin--'' AND PW = '1234'

이런식으로 sql의 구문 일부분이 아니라, 바인딩을 통해서 그냥 문자열로 처리가 된다.

Prepared Statement를 사용하는게 불가능하다면?

언제나 Prepared Statement를 사용할 수 있는것은 아니다. 예를들어, Prepared Statement는 데이터를 파라미터로 전달하는 역할을 하기 때문에 Order By 절에서는 사용하지 않는다. 당연한게 Select * from users where age= ? 여기에는 ?에 데이터값을 넣을수 있지만 Select * from users ORDER BY ? => 여기에는 정렬할 컬럼 이름을 넣어야하는데 컬럼 이름을 미리 알고있어야 동적으로 바인딩이 가능하기 때문이다.

또한, 실제 운영에서는 항상 Prepared Statment를 사용할 수 있는것은 아니다.

고로, WhiteList Filter, 입력값 정제등을 통해서 차선책을 고려해야한다.

WhiteList Filter 허용할 문자열을 제외한 모든 문자열을 필터링하는것이다. 입력값 정제 사용자 입력값이 SQL 구문에서 문법적인 의미를 갖지 못하도록 입력값을 다른값으로 치환하는 방법이다. 대표적으로 HashMap을 사용하는것인데, 사용자 입력값이 해시테이블의 값과 매핑을 통해서 정제되기 때문에 SQL구문에는 영향을 미치지 못한다.

또한, 에러 메시지 출력을 제한해야한다. 공격자가 악용할 가능성이 있는 에러 메시지가 노출 될경우 Error Based SQL Injection과 같은 공격이 가능하다. 따라서 Default 에러메시지가 아닌 사전에 정의한 에러 페이지를 반환하도록 대체해야한다.

이번 문제는 알고리즘이라기 보단, 수학을 이용하는 문제였다.

처음에 이 문제를 접근했을때, 2^31이라는 0 ≤ x < y < 2^31 조건을 보자마자, 그냥은 불가능하다고 생각했다.

처음에 그래서 든 생각이 DP를 써야되나? 싶었다. 왜냐하면 0부터 5까지 가야한다고 치자. 맨 처음 0에서 1까지 무조건 이동해야한다. 그 다음 1에서 선택할 수 있는 선택지는 0,1,2이다. 0은 빼고 1,2이니까 재귀로 계속 부르면서 1 -> 2(1칸이동) -> 1,2중에서 선택해서 계속 탐색 1 -> 3(2칸이동) -> 1,2,3중에서 선택해서 계속 탐색 이런식으로 하려했다.

이런식으로 이동 횟수를 누적해가면서 DP배열에다가 넣고 그 다음에 만약 DP에 저장된것보다 크면 return을 통해서 나가기 이런식으로 경우의 수를 줄이려 했다.

그런데, 생각해보면 그러면 DP배열을 y최댓값인 2^31까지 해야하는데 이것또한 불가능하다.

어? DFS로 그러면 이동횟수를 누적해가면서 계산해야하나? 싶었는데 이것도 말이 안되는게 어쨋든 visited를 갱신하려면 배열이 있어야하는데 이것도 불가능했다.

결국 답을 보고 풀었다.

해설

핵심은 문제의 마지막에 있었다. 목적지에 도착하기전에는 무조건 이동거리가 1이어야한다는 것이다.

만약 10에 도착하려면 무조건 9 -> 10으로 이동해야한다. 그렇다면 9에 도착할 수 있는 최대 이동거리는 몇일까 바로 2이다. 왜냐하면 2의 이동거리로 9를 도착해야 9에서 1,2,3의 경우의수에서 1을 골라 10으로 도착할 수 있기 때문이다. 만약 그럼 7에서는 어떨까? 바로 3의 최대거리로 도착해야 2,3,4중에서 2를 선택할 것이다.

고로 이러한 규칙을 생각해보면 1+2+1 최대 이동거리 4 1+2+3+2+1 최대 이동거리 9 1+2+3+4+3+2+1 최대 이동거리 16 ... 이런식이 최대 이동거리가 될 것이다. 이래서 알고리즘이 수학인것이다.

만약 그렇다면 이동해야하는 이동거리가 12인데 최대 이동거리가 9이면 어떻게 할까? 1+2+3+2+1에다가 3을 그냥 끼워넣으면 된다. 1+2+3+3+2+1 그리고 이동횟수를 1증가시키면된다.

만약에 더 이동해야하는 이동거리가 3보다 이하라면 그냥 이동거리를 끼워넣고 이동횟수를 1 증가시키면 된다.

그런데 만약 이동거리가 13인데 최대 이동거리가 9이면 어떻게 할까? 1+2+3+2+1에서 3을 넣고 1을 더 이동해야할것이다. 이러면 결국 4/3이 1.3333이니까 0.333에 해당하는만큼 한번 더 움직여야하므로 2번을 이동을 더하면된다.

코드

#include <iostream>
#include <vector>
#include <utility>
#include <string.h>
#include <algorithm>
using namespace std;

int main() {
    int num = 0;
    cin >> num;
    for (int i = 0; i < num; i++) {
        long long Answer = 0;
        //N은 최대 이동거리
        long long N = 0;
        long long start = 0;
        long long end = 0;
        cin >> start >> end;

        while (N * N <= end-start) {
            N++;
        }
        N--;

        Answer = 2 * N - 1;
        long long extra = (end - start) - (N * N);
        if (extra == 0) {
            //최대거리로 정확히 도착가능
            cout << Answer << "\n";
        }
        else {
            //최대거리안에 갈수 있음
            if (extra <= N) { Answer++; }
            else {
                //만약 13광년인경우 N이 3이다. (13-0)-3*3 = 4로 추가로 4만큼 더가야함 
                //4/3 = 1.3333 -> 올림 이므로 2
                extra = (long long)ceil((double)extra / (double)N);
                Answer += extra;
            }
            cout << Answer << "\n";
        }
    }
    return 0;
}

해당 문제는 DP를 사용해서 푸는 문제입니다.

처음에 그리디로 문제를 접근하여서 풀려 했지만, 실패하였습니다.

그리디

동전 문제는 대부분이 그리디로 풀리기 때문에, 1,2,5로 10원을 만들기 위해서 가장 큰 동전의 경우의 수부터 고려하여서 문제를 풀려했습니다.

가장 큰 동전의 가격이 5원이므로

5원 1개, 2원 1개, 1원 3개 5원 1개, 2원 2개, 1원 1개 5원 2개 2원 1개, 1원 8개 2원 2개, 1원 6개 ...

이런식으로 그리디 풀이를 하려했습니다. 하지만 이도, 구현을 하지 못해 저와 같은 생각을 한 블로그를 참고하여서 코드를 작성하였습니다.

#include <iostream>
#include <vector>
#include <utility>
#include <string.h>
#include <algorithm>
using namespace std;

int n, sum, ans;
vector<int> coin;

void recursive(int curCoinIdx, int curSum) {
    curSum += coin[curCoinIdx]; //5
    if (curSum == sum) ans++;

    //만약 숫자가 넘어가면 다시 돌아가야함
    if (curSum >= sum) {
        curSum -= coin[curCoinIdx];
        return;
    }

    int nextCoinIdx = curCoinIdx;
    while (nextCoinIdx < n) {
        recursive(nextCoinIdx, curSum);
        nextCoinIdx++;
    }
}


int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> n >> sum;
    for (int i = 0; i < n; i++) {
        int temp = 0;
        cin >> temp;
        coin.push_back(temp);
    }
    sort(coin.begin(), coin.end(), greater<>());
    for (int i = 0; i < coin.size(); i++) {
        recursive(i, 0);
    }
    cout << ans;
}

처음에 코인을 받고 가장 큰 가격의 코인부터 확인해야하므로

sort(coin.begin(), coin.end(), greater<>());

정렬을 통해 coin에 5,2,1이 들어가게 하고, 재귀함수를 호출했습니다.

처음에 recursive(0,0)이 호출되면, curSum에 5원이 들어갑니다. nexcoidIdx에 동일하게 5원인 0이 들어가고 호출합니다. 그리고 5원을 다시 더하면 curSum이 10이됩니다. 그러고 Answer에다가 1을 추가합니다.

여기서 중요한것은 우리는 10원짜리를 5원2개를 이용해서하는 경우를 시도한것입니다. 여기서 5원을 다시 빼줘서 5원을 만들고 return을하면 for문으로 다시 돌아와서 1번째인 2원으로 만들 수 있는 경우의 수를 파악하게 됩니다.

이런식으로 재귀함수 호출을 통해서 풀려고했습니다.

그러나 여기서 문제점은 경우의 수가 2^31이라는 것입니다. 이는 애초에 연산이 2^31번 될 수 있다는 말이므로 시간내에 풀이가 불가능함을 의미합니다.

DP

그래서 답을 보고 풀었습니다. 핵심은 간단합니다. 만약 2원을 만들 수 있는 경우의 수가 4가지라고 가정해보도록 하겠습니다. 그렇다면 3원을 가지고 5원을 만들 수 있는 경우의수는 몇가지 일까요? 바로 당연히 4가지 입니다. 왜냐하면, 2원 + 3원이 5원이므로 2원의 경우의수가 바로 5원을 만들 수 있는 경우의 수 이기 때문입니다.

DP배열 0 1 2 3 4 5 6 7 8 9 10 1 0 0 0 0 0 0 0 0 0 0

0을 1로 설정한 이유는 뒤에서 설명 여기서 1원을 가지고 경우의 수를 판단해보도록 하겠습니다. 1원을 가지고 1원을 만드는 방법은 0원을 만드는 방법에서 1원을 더하는 것입니다. 고로 DP[1] = DP[0] + DP[1]임을 알 수 있습니다. 그러면 여기서 제가 처음든 고민은 아 DP0에 있는 경우의 수는 더하는것은 알겠다. 근데 기존의 DP1은 왜더하냐? 당연히 더해야합니다.

만약 Dp`[5]'= 3으로 5원을 만드는 방법이 3가지가 있다고 가정하고, 만약 5원짜리로 다시 계산하면 기존의 5원을 만드는 방법 3가지 + DP[5-5]인 DP[0]원의 경우의 수를 더해야 하기 때문입니다.

DP 0 1 2 3 4 5 6 7 8 9 10 1 1 0 0 0 0 0 0 0 0 0 DP[2]= DP[2-1] + DP[2]입니다.

DP 0 1 2 3 4 5 6 7 8 9 10 1 1 1 0 0 0 0 0 0 0 0 ... DP 0 1 2 3 4 5 6 7 8 9 10 1 1 1 1 1 1 1 1 1 1 1 이 됩니다.

만약 이제 2원이 된다면 DP[2]= DP[2]+DP[2-2]가 됩니다. 이는 이미 DP[2]를 통해서 2원을 만들 수 있는 경우의수 1원 2개사용하기 +2원이 새로 들어왔으므로 2원으로 만들수 있는 경우 dp[0]의 경우의수를 합하면 됩니다.

여기서 DP[0]은 왜 1로 설정해야지를 알 수 있습니다. 그 이유는 DP[0]이 0 이라면 초기에 DP[1]을 DP[0]의 값에다 더해줘야하는데 0을 더할 수 는 없기 때문입니다.

정답코드

#include <iostream>
#include <vector>
#include <utility>
#include <string.h>
#include <algorithm>
using namespace std;
int n, sum, ans;
vector<int> coin;
int DP[10001];
int main() {
    cin >> n;
    cin >> sum;
    for (int i = 0; i < n; i++) {
        int temp = 0;
        cin >> temp;
        coin.push_back(temp);
    }
    sort(coin.begin(), coin.end());
    DP[0] = 1;
    for (int i = 0; i < n; i++) {
        int currentCoin = coin[i];
        for (int j = currentCoin; j <= sum; j++) {
            DP[j] = DP[j] + DP[j - currentCoin];
        }
    }
    cout << DP[sum];
}

멀티태스킹 CPU코어가 1개라고 가정했을때, 프로그램 A의 코드를 0.01초 수행하고, 프로그램 B의 코드를 0.01초정도 수행 이걸 반복하면, 마치 영사기의 사진이 돌아가는 것처럼 동시에 수행되는 것처럼 보일 수 있음 (이걸 시분할기법이라함) 어떤 프로그램이 먼저, 얼만큼 실행되는지는 운영체제의 스케쥴링 기법에 따라 다름.

멀티 프로세싱 진짜 CPU에 코어가 2개가 있어서, 이전에는 하나의 코어가 2개의 프로그램을 동시에 수행했다면, 이제는 두개의 코어가 3개의 프로그램을 동시에 수행하는것.

요즘은 대부분 컴퓨터가 멀티 코어를 사용하므로, 멀티 프로세싱을 하면서 멀티 태스킹도 하는것이다.(왜냐하면 하나의 코어에서 0.01초 수행하고 또 다른 프로그램 0.01초 수행하니까)

프로그램은 단순히 디스크에 있는 파일 조각일 뿐이다. 이걸 더블클릭해서 메모리에 올려야 프로세스가 된다. 그럼 이 프로세스를 cpu가 코드를 main부터 한줄 한줄 실행하면서 프로세스가 실행되는것이다.

그림과 같이 프로세스를 실행하면, 코드: 프로그램코드 힙: 동적 할당 영역 기타: 데이터 섹션(전역변수 및 정적 변수) 등이 생기고

프로세스에는 최소 하나이상의 스레드가 존재한다. 왜냐하면, 스레드가 프로세스내에서 실행되는 작업의 단위이므로,최소한 하나의 스레드가 존재해야 프로그램이 실행될 수 있다.(그래야 최소한 main함수를 실행 시키니까)

정리하자면, 프로세스는 실행 환경과 자원을 제공하는 컨테이너 역할을 하는거고, 스레드는 CPU를 사용해서 직접 코드를 하나하나 실행하는 것이다. 프로세스 자체는 운영체제의 스케줄러에 의해 직접 실행되는것이 아니라, 프로세스 내의 스레드가 실행된다.

여기서 멀티스레드가 존재하는 이유는 하나의 프로그램에서도 동시에 여러작업이 필요하다. 워드 프로그램 - 프로세스 A

• 스레드 1: 문서편집
• 스레드 2: 자동 저장
• 스레드 3: 맞춤법 검사

참고: 각 스레드는 프로세스의 코드 힙 기타 등등을 공유하지만, 각 스레드마다 개별 스택이 있다. 당연히 개별 스택이 존재해야하는 이유는 서로 다른 작업을 동시에 처리하기 위해서는 각각 독립적인 함수 호출 정보와 지역 변수를 관리해야 하기 때문이다.

여기에 있는 스레드 A1의 A1,A2,,,이건 스택이 아니다. 코드 1,2,3,4줄을 뜻하는것이다. 이렇게 코어가 1개 있으면 스레드 1의 A1수행하고 스레드 B1으로 가서 B1실행하고 프로세스를 돌아가면서 해당 스레드의 코드를 한줄 한줄 수행한다. 멀티코어에서도 동일하다.

처음 문제를 접했을때는, 정방향으로 배열을 순회하면서, Max값을 갱신해가면서 누적합을 구해야하나? 이런식으로 접근했는데 도저히 구현이 어려웠는데,

만약 1 1 3 1 1 5라면

앞에 1 1 에서 3에다가 팔아버리면 오답이다, 5에서 팔아야하기 때문이다. 이렇게 앞에서 부터 순회하면 어렵고

이걸 그냥 거꾸로 해서 5 1 1 3 1 1 해서 맨처음에걸 무조건 max로 두고, 그 다음 배열의 원소부터 max보다 작으면 anwer에다가 더하고, 만약 더 큰값이 나타나면 max값을 갱신하면 된다.

배열에 순방향으로 넣고 거꾸로 돌릴바에는, 그냥 deque로 앞에서 부터 넣는 방법을 선택하였다.

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <iostream>
#include <deque>

using namespace std;
int main() {
    int T = 0;
    cin >> T;
    for (int i = 0; i < T; i++) {
        int a = 0;
        cin >> a;

        deque<long long>dq;
        for (int x = 0; x < a; x++) {
            int temp = 0;
            cin >> temp;

            dq.push_front(temp);
        }

        deque<long long>::iterator iter;
        int max = 0;
        long long answer = 0;
        for (iter = dq.begin(); iter != dq.end(); iter++) {
            if (iter == dq.begin()) {
                max = *iter;
            }
            else if (*iter < max) {
                answer += (max - *iter);
            }
            else {
                max = *iter;
            }
        }
        cout << answer << "\n";
    }
}

문제가 참신하고, 난이도도 쉬워서 재미있게 풀었습니다.

문제 바로가기 해당 문제에서 고려해야할 점은, BFS입니다. BFS임을 어떻게 바로 알 수 있냐면, 게임판의 상태가 주어졌을 때, 100번 칸에 도착하기 위해 주사위를 굴려야 하는 횟수의 최솟값을 구해보자. 라는 조건이 있기 때문입니다. 최솟값, 또는 최단거리 이런 문제가 나오면 BFS로 푸는 것이 좋습니다. 그래야, 최단거리가 아닌 노드들은 큐에 넣지 않을 수 있기 때문입니다.

또한, Map이 10 * 10 이라고 Map을 기존에 풀던 방식처럼 int map[10][10]이렇게 놓고 풀지 않아도 되는게 함정입니다. 왜냐하면, 현재 1번 칸이라면 주사위를 굴려서 무조건 2,3,4,5,6,7로만 갈 수 있기때문에, 이차원 배열로 둬서 동서남북으로 이동하는 문제와는 다르기 때문입니다.

    cin >> LC;
    cin >> SC;
    for (int i = 1; i <= 100; i++) {
        map[i] = 100000;
    }
    for (int i = 0; i < LC + SC; i++) {
        int t1 = 0;
        int t2 = 0;
        cin >> t1;
        cin >> t2;
        um[t1] = t2;
    }

    BFS();

1차원 배열 map을 100000으로 초기화 합니다. 이렇게 하는 이유는 바로, 최솟값을 갱신하기 위해서 큰 값으로 두었습니다.

um은 unordered_map<int, int> um; 을 두어서 key-value로 사다리, 뱀을 저장하였습니다.

void BFS() {
    map[1] = 1;
    q.push({1,0});
    while (!q.empty()) {
        int c_idx = q.front().first;
        int N = q.front().second;
        q.pop();
        if (c_idx == 100 && N < result) {
            result = N;
        }
        for (int i = 1; i <= 6; i++) {
            if (1 <= c_idx + i && c_idx + i <= 100) {
                if (um[c_idx + i] > 0) {
                    if (N + 1 < map[um[c_idx + i]]) {
                        q.push({ um[c_idx + i],N + 1 });
                        map[um[c_idx + i]] = N + 1;
                    }
                }
                else {
                    if (N + 1 < map[c_idx + i]) {
                        q.push({ c_idx + i,N + 1 });
                        map[c_idx + i] = N + 1;
                    }
                }
            }
        }
    }
}

여기서는 queue의 첫번째가 현재 위치, 두번째가 주사위를 굴린 횟수입니다.

if (c_idx == 100 && N < result) {
            result = N;
        }

를 통해서 100번째 칸에 도착했을때 주사위를 굴린 최솟값인지 확인합니다.

if (1 <= c_idx + i && c_idx + i <= 100) {

해당 if문은 배열 조건 내에 있는 idx인지 확인합니다.

if (um[c_idx + i] > 0) {
                    if (N + 1 < map[um[c_idx + i]]) {
                        q.push({ um[c_idx + i],N + 1 });
                        map[um[c_idx + i]] = N + 1;
                    }
                }

unorderedmap을 사용하였으므로, c_idx + i 번째에 칸에 사다리나, 뱀이 있다면 움직이는 칸이 있으므로 양수입니다. 고로 해당 되는 칸에 가서 N+1보다 큰지 검사하여서 queue에 넣습니다.

해당 로직은 뱀이나 사다리가 아닐때도 동일합니다.

    else {
                    if (N + 1 < map[c_idx + i]) {
                        q.push({ c_idx + i,N + 1 });
                        map[c_idx + i] = N + 1;
                    }
                }

전체코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <unordered_map>
using namespace std;

int LC = 0;
int SC = 0;
int map[101];
queue<pair<int, int>>q;
unordered_map<int, int> um;
int result = 1000000;

void BFS() {
    map[1] = 1;
    q.push({1,0});
    while (!q.empty()) {
        int c_idx = q.front().first;
        int N = q.front().second;
        q.pop();
        if (c_idx == 100 && N < result) {
            result = N;
        }
        for (int i = 1; i <= 6; i++) {
            if (1 <= c_idx + i && c_idx + i <= 100) {
                if (um[c_idx + i] > 0) {
                    if (N + 1 < map[um[c_idx + i]]) {
                        q.push({ um[c_idx + i],N + 1 });
                        map[um[c_idx + i]] = N + 1;
                    }
                }
                else {
                    if (N + 1 < map[c_idx + i]) {
                        q.push({ c_idx + i,N + 1 });
                        map[c_idx + i] = N + 1;
                    }
                }
            }
        }
    }
}

int main() {
    cin >> LC;
    cin >> SC;
    for (int i = 1; i <= 100; i++) {
        map[i] = 100000;
    }
    for (int i = 0; i < LC + SC; i++) {
        int t1 = 0;
        int t2 = 0;
        cin >> t1;
        cin >> t2;
        um[t1] = t2;
    }

    BFS();
    cout << result;
}