덱을 이용해서, 터뜨릴 풍선을 가장 앞으로 오도록 회전을 시켜준 후에 앞을 pop하고, 이 과정을 덱이 빌 때까지 반복하는 형식으로 문제를 풀었다.

3만큼 뒤에 있는 풍선을 터뜨려야 하므로, 이 경우에는 4번 풍선이 가장 앞으로 와야 한다.

1번 풍선은 삭제가 되었고, 앞에 있는 두 풍선이 뒤로 이동하면 세 번째 풍선이 제일 앞에 올 수 있다. (터진 풍선까지 세서 그 풍선을 제외하고 두 번 이동하는 것이다)

4번 풍선이 삭제가 되고, 이 다음엔 4번 풍선보다 뒤에서 세번째에 있는 풍선이 삭제가 되어야 하는데, 이 경우 뒤에 있는 풍선을 세 번 앞으로 이동시키면 가장 앞에 있는 풍선이 터질 풍선이 된다.

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

int main() {
    int n;
    cin >> n;

    deque<pair<int, int>> d;
    for (int i = 0; i < n; i++) {
        int num;
        cin >> num;
        d.push_back(make_pair(i+1, num));
    }


    while (true) {
        cout << d.front().first << " ";
        int num = d.front().second;
        d.pop_front();

        if (d.empty()) break;

        if (num > 0) {
            for (int i = 0; i < num - 1; i++) { // 양수일 경우 이동숫자-1 만큼 뒤로 이동시킨다
                d.push_back(d.front());
                d.pop_front();
            }

        }
        else {
            for (int i = 0; i < abs(num); i++){ // 음수일 경우 역방향으로 절댓값만큼 앞으로 가져온다
                d.push_front(d.back());
                d.pop_back();
            }
        }
    }

}

Q2. 1543 문서 검색 > 문제 링크

babababa라는 큰 문자열이 있을 때, aba 같은 작은 문자열이 몇번 등장하는지 찾는 간단한 문자열 비교 문제다. 이 문제는 문자열의 모든 지점에서 문자열을 비교하고, 만약 일치하는 경우 해당 문자열 전체를 건너뛰는 방식으로 구현하였다. c++에 존재하는 substr 함수를 통해서 시작점에서 작은 문자열의 길이만큼 문자를 자르고, 이 문자가 작은 문자열과 같은지를 비교하는 방식으로 구현했다.

i=0 일 때 작은 문자열의 크기만큼 문자열을 자르면 bab가 되는데, 이는 작은 문자열 aba와 일치하지 않는다. 그러므로 다음 인덱스에서 다시 탐색을 진행한다.

다음 인덱스에서 작은 문자열의 크기만큼 자르면, 작은 문자열과 일치함을 확인할 수 있다. 이러면 단어를 찾은 것이므로 결과값을 1 증가시키고, 탐색 된 문자열의 끝 지점의 다음 인덱스로 탐색 지점을 옮겨준다

이후 계속해서 탐색을 진행해서 결과값의 개수를 출력하면 된다.

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

int main(){
    string s1, s2;
    // 문제에서 단어에 공백도 포함이라고 했으므로 getline으로 문자열을 입력받는다.
    getline(cin, s1); 
    getline(cin, s2);

    int cnt = 0;
    for (int i = 0; i < s1.length(); i++) {
        if (s1.substr(i, s2.length()) == s2) {
            cnt++;
            // 인덱스를 탐색 된 문자열의 끝 지점의 다음 인덱스로 옮겨준다
            // s2.length() 만큼 옮기고 -1인 이유는 for문을 진행하면서 한번 더 i가 증가하기 때문
            i += s2.length() - 1;
        }
    }

    cout << cnt << endl;
}

Github Repository 생성하기

1. github 사이트에서 new버튼으로 새로운 repository를 생성한다.
2. git init
3. git add .
4. git commit -m "commit message"
5. git remote add origin github주소 - github의 주소로 remote하기
6. git push -u origin master

   branch 사용 기본 push

7. git clone [url]
8. git branch [branchname]
9. git checkout [branchname]
10. 작업
11. git add .
12. git commit -m "commit message"
13. git push origin [branchname]
14. pull request 작성

Git remote url 수정

0. 기존 repository 주소 확인 : git remote -v
1. 기존 repository 연결 해제 : git remote remove origin
2. 새로운 repository 연결 : git remote add origin [새로운 Repository URL]

Git과 연결된 로컬 저장소 변경

.git 폴더를 이동시키면 된다 사진 출처 : https://sedangdang.tistory.com/147

Git 브랜치 생성/삭제

브랜치 생성 : git branch [branchname] 브랜치 삭제 : git branch -d [branchname]

Git 한번 pr 후 새로 시작할 때 과정

1. 메인 branch 이동 후 master 내용 pull git checkout main git pull origin master
2. 작업한 브랜치로 이동 후 master를 해당 브랜치에 merge git merge master

50미터를 가려면 맥주 한 병을 마셔야 하고, 맥주는 20병을 넘을 수 없다. -> 편의점에 한 번 가면 편의점과 1000m 이내에 있는 좌표들로 이동할 수 있다.

그러므로 출발점, 편의점, 도착점의 좌표를 입력받고 모든 좌표들을 비교하여 1000 이내에 있으면 갈 수 있다는 뜻이므로 그래프를 서로 연결시켜준다.

이후 출발점에서부터 그래프 탐색을 시행하여, 도착점의 방문 여부를 파악해서, 방문했으면 그래프가 연결되어 있다는 의미이고, 그것은 즉 갈 수 있는 경로가 있는 것이므로 happy를 출력하고, 방문하지 못했으면 경로가 없는 것이므로 sad를 출력하면 된다.

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

vector<pair<int, int>> street;
vector<int> graph[102];
int visit[102];

int distance(pair<int, int> p1, pair<int, int> p2){
    return abs(p1.first - p2.first) + abs(p1.second - p2.second);
}


void dfs(int now) {
    visit[now] = true;
    for (int i = 0; i < graph[now].size(); i++) {
        int next = graph[now][i];
        if (visit[next] == false)
            dfs(next);
    }
}

int main() {
    int tc;
    cin >> tc;

    while (tc--) {

        street.clear();
        for (int j = 0; j < 102; j++) {
            graph[j].clear();
        }
        memset(visit,false, sizeof(visit));


        int con;
        cin >> con;

        for (int i = 0; i < con + 2; i++) {
            int x, y;
            cin >> x >> y;
            street.push_back(make_pair(x, y));
        }

        for (int j = 0; j < con + 2; j++) {
            for (int k = j + 1; k < con + 2; k++) {
                if (distance(street[j], street[k]) <= 1000) {
                    graph[j].push_back(k);
                    graph[k].push_back(j);
                }
            }
        }

        dfs(0);


        if (visit[con + 1]) cout << "happy" << endl;
        else cout << "sad" << endl;
    }

}

이 때 좌표값은 pair로 만들어 벡터에 저장하고, 출발점은 pair벡터에 가장 먼저 들어가있으므로 인덱스 값이 0이기 때문에 dfs는 0부터 시행한다.

Q2. 1890 점프 > 문제 링크

문제에서 '0' 지점으로 이동할 수 있는 세 가지 경우의 수를 보여주는 그림이다.

시작점은 무조건 거쳐야하므로 dp[0][0]은 1로 초기화 하고, (0,0)의 좌표값이 2이므로 그림에서 파란색으로 칠한 부분으로 이동할 수 있을 것이다. 그러면 해당 부분으로 오는 데 걸리는 경로의 수는 이전 지점까지의 경로의 수를 더해주면 된다.

#include <iostream>
using namespace std;

int n;
int g[101][101] = { 0, };
long long dp[101][101] = { 0, };

int main() {
    cin >> n;

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> g[i][j];
        }
    }

    dp[0][0] = 1;

    for (int x = 0; x < n; x++) {
        for (int y = 0; y < n; y++) {
            int jump = g[x][y];

            if (y + jump < n && y != n-1) dp[x][y + jump] += dp[x][y];  // 왼쪽 이동
            if (x + jump < n && x != n-1) dp[x+jump][y] += dp[x][y]; // 아래쪽 이동
        }
    }

    cout << dp[n - 1][n - 1];

}

모든 점에서 탐색을 하되 시간을 줄이기 위해서 dp값이 0인 좌표에 대해서는 if문을 돌리지 않고 지나쳤다. 먼저 점프할 거리를 구해두고, 점프 이후의 좌표가 모서리를 넘지 않고, 현재 좌표가 모서리 좌표가 아닌 경우에 점프를 수행한다. 이때 점프된 좌표까지 가는 경로의 수는, 현재 좌표까지 오는 데 가능한 경로의 수를 더해주면 된다. 이런식으로 모든 경로를 계산한 후, 마지막 좌표의 dp값(경로의 수)를 출력해주면 된다.

문제에서 준 상황을 분석해보면, 물에 잠긴 지점을 회색으로 표시했을 때 안전구역을 그림으로 표시하면 아래와 같은 형태가 되어 안전 구역이 5개다.

그래서 우선 그래프 정보를 입력 받고 > 물에 잠긴 구역을 표시한 뒤 > 물에 잠기지 않은 점에서 그래프 탐색을 시행하여 탐색이 한 번 끝날 때마다 cnt 변수의 값을 증가 시키면 안전 구역의 개수를 구할 수 있다.

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

int graph[101][101] = { 0 };
int water[101][101] = { 0 };
int check[101][101] = { 0 };
int depth[101];
int n, m, f1, f2;
int cnt = 0, res = 0;
vector<int> result;
int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };

void dfs(int y, int x) {
    check[y][x] = true;

    for (int i = 0; i < 4; i++) { // 인접한 모든 부분 고려해야 하므로
        int ny = y + dy[i];
        int nx = x + dx[i];

        if (ny < 0 || nx < 0 || ny >= n || nx >= n) continue; // 모서리의 경우 continue를 통해 예외처리
        if (water[ny][nx] && !check[ny][nx]) { // 물에 젖지 않고 방문하지 않았을 경우 계속 탐색
            check[ny][nx] = true;
            dfs(ny, nx);
        }
    }
}

int findSafe(int h) {
    for (int i = 0; i < n; i++) { // 물에 잠기는 영역 표시
        for (int j = 0; j < n; j++) {
            if (graph[i][j] < h) water[i][j] = 0;
            else water[i][j] = 1;
        }
    }

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (check[i][j] == 0 && water[i][j] == 1) {
                dfs(i, j);
                cnt++; // 한 번의 dfs가 끝나면 안전 구역의 수를 증가
            }
        }
    }

    return cnt;
}

int main() {
    cin >> n;
    int max = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> graph[i][j];
            // 모든 높이에 대해 안전구역의 수를 구해야 하므로, max 높이까지 for문을 돌리기 위해 max값 구함
            if (graph[i][j] > max) max = graph[i][j]; 
        }
    }

    for (int i = 0; i <= max; i++) {
        // 안전구역의 수를 벡터에 저장
        result.push_back(findSafe(i));
        // 한 높이에 대해 안전 구역을 구했으면, 변수들을 새로 초기화
        cnt = 0;
        for (int k = 0; k < n; k++) {
            for (int t = 0; t < n; t++) {
                check[k][t] = 0;
            }
        }
    }

    cout << *max_element(result.begin(), result.end()) << endl; // 벡터 내에서 최댓값 출력
}

먼저 그래프의 정보를 입력받고, 문제에서 모든 높이에 대해 안전 구역의 수를 구한 뒤 안전 구역의 수가 가장 많은 경우를 출력하라고 했으므로 for문을 구역의 최대 높이까지 돌리기 위해서 max 높이까지 함께 구한다. 이 작업이 끝나면 for문을 통해 안전 구역의 수를 구하게 된다. findSafe함수에 매개변수로 물에 잠기는 지점의 높이를 넘겨서 안전 구역을 구하게 된다. 반복문을 통해서 물에 잠기는 영역을 water 배열에 저장하고, 모든 점 중에서 방문한 적이 없고 물에 잠기지 않은 지역을 대상으로 dfs를 돌린다. dfs는 기본 dfs 코드에 네 방향 인접함을 모두 따지게 수정하고, 물에 젖지않은 점을 탐색하도록 수정했다. 한 번 dfs가 끝나면 하나의 그래프를 찾은 것이므로, cnt 값을 추가하여 그래프 갯수를 세 주고, findSafe가 최종적으로 반환 할 때 리턴시킨다. 이 리턴된 값들을 result 벡터에 저장하고, 벡터의 최댓값을 찾아서 출력시킨다.

Q2. 2644 촌수 계산 > 문제 링크

예제의 상황을 그림으로 그려보면,

그래프에서 경로를 찾아보면 최단경로 그대로 n촌 관계가 형성 되어 있음을 확인할 수 있었다. 그리고 두 번째 예제에서 경로를 찾을 수 없는 경우 -1 출력이 됨도 확인할 수 있었다. 따라서 bfs를 이용해 최단경로를 구하는 로직을 적용해서 문제를 풀었다.

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

int graph[101][101] = { 0 };
int checked[101] = { 0 };
int depth[101];
int n, m, f1, f2;
int cnt = 0, res = 0;

void bfs(int x) {
    queue<int> q;
    q.push(x);
    checked[x] = 1;

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

        for (int i = 1; i <= n; i++) {
            if (graph[x][i] == 1 && checked[i] == 0) {
                q.push(i);
                checked[i] = 1;
                depth[i] = depth[x] + 1;
            }
        }
    }
}

int main() {
    cin >> n >> f1 >> f2 >> m;

    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        graph[a][b] = 1;
        graph[b][a] = 1;
    }

    bfs(f1);
    if (depth[f2] == 0) cout << -1 << endl;
    else cout << depth[f2] << endl;
}

먼저 그래프를 입력받아 노드를 입력받고, 문제에 입력된 부모 노드부터 bfs 탐색을 진행한다. bfs를 진행하면서 가족 관계에 해당하는 노드를 찾으면 그 노드의 depth를 1 증가시켜서 저장 해준다. 그리고 최종적으로 문제에 입력된 자식 노드의 depth를 출력한다. (depth가 0인 경우 가족관계가 아닌 경우이므로 -1을 출력한다.)

문제를 접근하기 위해 규칙을 찾아보았다.

만약 1일차에 상담을 진행한다면, 1일차 상담의 이익 + 4일차(1일차 + 상담을 할 수 없는 3일) 이후 진행한 상담에서의 이익의 합이 최종적으로 상담으로 벌 수 있는 이익이다.
마찬가지로 2일차에 상담을 진행한다면, 2일차 상담의 이익 + 7일차(2일차 + 상담을 할 수 없는 5일) 이후 진행한 상담에서의 이익의 합이 나중에 최종적으로 상담으로 벌 수 있는 이익이다. 그리고 만약 1일차에 상담을 진행하지 않는다면, 나중에 최종적으로 상담으로 벌 수 있는 이익은 2일차 이후 진행한 상담에서의 이익이다.

이런 식으로 상담을 진행 한 상황과, 진행하지 않는 상황의 로직을 분리하여 규칙을 만들 수 있었다. 상담을 진행 한 상황에서의 이익은 그 날의 이익 + (그 날+ 상담을 하지 못하는 날)이후에 진행한 상담에서의 이익, 진행하지 않은 상황에서의 이익은 그 다음날 이후 진행한 상담에서의 이익이 되고, 이를 재귀로 구현할 수 있었다.

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

int dp[16], t[16], p[16] = { 0, };
int n;

int solve(int i) {
    if (i > n) return 0;

    int ret = 0;
    if (i + t[i] <= n + 1) {
        ret = solve(i + t[i]) + p[i];
    }
    return max(ret, solve(i + 1));
}

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> t[i] >> p[i];
    }

    int ans = solve(1);
    cout << ans;
}

코드를 설명해보면, n의 값과 각 상담에 대해 몇일간 상담을 진행하는지, 각 상담의 이익을 입력 받는다. 문제에서는 1일차 이후 전체 상담 과정에서의 이익을 요구했으로 solve(1)을 호출하여 수행한다.

solve함수 안에서는 먼저, 들어간 수가 n을 넘는지를 확인한다. 만약 넘는다면 이미 퇴사한 이후니까 0을 반환한다. n을 넘지 않는 수의 경우에는 해당 일에 상담을 진행하려고 한다면, 시작된 상담일의 종료일이 퇴사일 전인지를 확인한다. 예를 들어 7일차에 상담을 진행하려고 하면 7일차 상담이 2일이 걸리니까 아예 선택을 할 수 없다. 이 조건도 만족시켰다면 해당 일을 선택했을 때의 이익을 "solve(i + t[i](상담이 중단되는 기간)) + 지금 상담에서의 이익"을 통해 구하고, 이를 상담 하지 않았을 때의 이익(하루 뒤 이후의 이익) 과 비교하여 더 큰 값을 결과값으로 지정한다. 이 과정에서 함수는 계속 재귀적으로 호출 될 것이고, 결국 return 되는 solve(1)의 값이 정답이 된다.

Q2. 2293 동전 1 > 문제 링크

단계1) 먼저 1원만을 사용한다면, 1원~10원을 만드는 방법은 전부 1원을 사용하는 단 한가지의 경우이다.

단계2) 그리고 1원과 2원을 모두 쓰는 경우를 테이블에 추가해보면 아래와 같은 형태가 되는데,

0원은 동전을 모두 쓰지 않고 만드는 경우 1가지, 1원은 1원 하나를 쓰는 경우 한가지지만, 2원부터는 1원+1원, 2원의 경우로 나눠지게 된다. 그리고 3원을 만드는 경우, 1+1+1원, 1+2원의 두 가지이다. 그리고 4원을 만드는 경우, 1+1+1+1원, 1+1+2원, 2+2원의 3가지이다.

지금 살펴보고 있는 단계2는, 단계1에서 만들 수 있는 경우의 수에 2를 통해서 만드는 방법을 추가한 경우다.

그러므로 2는 기본적으로 하나가 추가 된다고 생각하여 , 3원에서 2원을 빼면 1원이고, 1원+2원으로 1원을 만드는 경우의 수는 한 가지이므로 총 3원을 만들어내는 경우의 수는 단계1의 수(1) + 단계2에서 추가된 수(1) 을 해서 총 2가지이다.

4원도 살펴보면, 2는 기본적으로 하나가 추가 된다고 생각하여 , 4원에서 2원을 빼면 2원이고, 1원+2원으로 2원을 만드는 경우의 수는 두 가지이므로 총 4원을 만들어내는 경우의 수는 단계1의 수(1) + 단계2에서 추가된 수(2) 을 해서 총 3가지이다.

결국 새로 만들어지는 dp[n]의 값은 이전 dp[n]값 + dp[n-현재 추가된 동전의 종류 크기]를 더한 값이라는 점을 알 수 있다.

이를 바탕으로 1원, 2원, 5원을 모두 이용하는 경우까지 추가해보면

이러한 형태가 되고, 최종적으로 1원, 2원, 5원으로 10원을 만드는 경우의 수는 10가지가 된다.

그래서 점화식은 이전 dp[n]값 + dp[n-현재 추가된 동전의 종류 크기]이므로 최종적으로 dp[j] += dp[j - arr[i]]의 형태로 구현이 되고, 이를 바탕으로 코드를 구현해보면 아래와 같다.

#include <iostream>
using namespace std;

int main() {

    ios_base::sync_with_stdio(false); 
    cin.tie(0);
    cout.tie(NULL);

    int n, m;
    int v[101];
    int dp[10001] = { 0, };

    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        cin >> v[i];
    }

    dp[0] = 1;
    for (int i = 0; i < n; i++) {
        for (int j = v[i]; j <= m; j++) {
            dp[j] += dp[j - v[i]];
        }
    }
    cout << dp[m];
}

배열 형태로 동전의 값들을 입력받고, 0원을 만드는 경우의 수는 1가지이므로 dp[0]은 1로 초기화한다. 그리고 앞서 말한 점화식을 이중 for문으로 구현하여 dp표를 채워나간다.

최종적으로 원했던 값을 인덱스로 갖는 dp테이블 값을 반환하면서 문제가 종료된다.

http://www.kocw.net/home/cview.do?cid=e44bdd9b3a3f9bb5 강의 2강을 듣고, Computer Network : a Top-down approach 내용을 정리한 글입니다.

1.2 network edge

Host

host : network access application을 호스팅한다(실행한다). 사용자의 application message를 packet으로 불리는 chunk로 분할한다. 그 후 link를 통해 packet을 access network로 내보낸다. 패킷 하나를 host에서 내보내는 데 걸리는 시간은 L(패킷의 크기 bit수)/R(링크의 transmission rate)

Link의 분류

• guided media : 물리적인 wire를 사용하는 link(ex. copper-ethernet, fiber-HFC, coax-HFC 등) media 명 - 사용되는 네트워크 HFC : 케이블 회사에서 제공하는 access network와 연관. 윗 페이지 참조
• unguided media : 물리적인 wire를 사용하지 않고 공기중에서 전달 (ex. radio - wifi, cellular)

Physical media

• Twisted pair(TP) : copper cable의 다른 이름. Category 5(이더넷에 주로 사용, 100Mbps), Category 6(10Gbps)으로 나뉜다.
• coaxial cable(=broadband) : bandwidth가 넓은 link.
• fiber optioc cable : 전기 신호가 아닌 light pulses signal을 전달하며, glass fiber로 만들어진다. transmission rate가 매우 높다. light pulses signal을 전달하므로, 주변 electromagnetic noise의 영향을 덜 받는다 > 원거리를 약해지지 않고 이동하기 좋다 > error rate가 낮다
• radio : signal이 electromagnetic spectrum을 통해 전달된다. 물리적인 wire가 없다 > reflection, obstruction by objects, interference과 같은 것들에 유리하다 terrestrial microwave, LAN(wifi), cellular, satellite(위성통신)등에 이용된다.
  • satellite(위성통신)은 위성을 띄우는 높이에 따라 geostationary satellite(높이)와 low-earth orbiting satellite(낮게)로 나뉜다.
  • geostationary satellite가 커버 면적이 더 넓고 end-end delay가 길다.

1.3 network core

circuit switching

• 주로 전화 네트워크에서 사용되는 정보 전달 방식. 유저 메시지를 전달하기 위해서는 무조건 "call"이 있어야 한다.
• 유저 call > call set up(source > destination 경로 결정, 그 경로 상에 자원 예약하기(resource reservation)) > source에서 유저 메시지를 bit로 전환해 link에 밀어넣는다 네트워크의 자원을 분할해놓는 방식이 필요하다. (분할하지 않으면 한 사용자가 link를 사용하면 다른 사람은 link 사용이 불가능하다) call이 들어오면 사용되지 않고 있는 자원의 덩어리를 넘겨준다.
• internet과 같은 data network에는 적합하지 않다.

circuit switching에서의 자원 분할 방식 - FDM VS TDM

• FDM : 주파수 대역을 고정하여 제공한다.
• TDM : 시간을 일정 주기로 분할하여 저장한다.

packet switching

• 자원을 예약하지 않고 (no call setup, no resource reservation) 필요할 때 그때그때 resource를 사용한다.
• 각 packet은 full link capacity를 사용하며 전달된다. > 전달할 data가 있는데 link가 프리하면 그때 link 전체를 사용하여 data를 전달하고, 사용중이면 사용이 끝날 때까지 기다린다. 사용자가 전달할 메시지가 매우 길다면 link를 차지하는 시간이 길어질 것이다. 그러면 다른 사용자가 network를 사용할 수 없을 것이므로, packet이라는 chunk로 정보를 자른다.
• packet switching에는 예약 개념이 없으므로, packet에 목적지 주소가 명시되어 있다.

  packet switching : store and forward

• 기본 개념 : router는 packet을 받으면 목적지 주소를 보고 목적지를 결정하고, 패킷의 일부분이 들어오면 패킷 전체가 받아질 때까지 패킷의 일부분을 저장함 이후 해당 패킷이 완벽하게 다 받아졌을 때만 다른 링크로 전송
• 패킷의 길이가 L이고 bandwidth가 R bps이면, 패킷을 전송하는데 걸리는 시간은 L/R sec이다.

packet switching : Queueing delay

• 라우터에 패킷이 계속해서 들어오고 있는데, 패킷이 들어오는 속도가 라우터가 패킷을 내보내는 속도보다 빠르면 패킷을 저장하는 outer buffer(=outer queue)에 패킷이 계속 쌓이게 된다.
• outer buffer의 크기는 한정적이기 때문에 outer buffer가 꽉차있어 들어오는 패킷이 저장될 공간이 없다면 loss가 발생한다.
• queueing delay와 loss가 발생하는 상황을 congestion이라고 한다.

resource sharing 측면에서의 packet switching vs circuit switching

• 한정된 수의 사용자가 동시에 network를 사용할 확률은 낮으므로, resource sharing 측면에서는 packet switching이 유리하다.
• 그러나 packet switching은 congestion이 발생할 수 있다는 큰 단점이 있다.
• audio/video app와 같은 streaming data는 delay 관리가 굉장히 중요한데, packet switching은 관리를 보장할 수 없다.

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

int main() {
    int n, m;
    cin >> n >> m;

    vector<int> num_list;
    for (int i = 0; i < n; i++) {
        int num;
        cin >> num;
        num_list.push_back(num);
    }

    int res = 0;
    int sub = m;

    for (int i = 0; i < n - 2; i++) {
        for (int j = i+1; j < n - 1; j++) {
            for (int k = j+1; k < n; k++) {
                int sum = num_list[i] + num_list[j] + num_list[k];
                if ((m - sum < sub) && (sum <= m)) {
                    res = sum;
                    sub = m - sum;
                }
            }
        }
    }

    cout << res << endl;
}

반복문을 이용하여 입력받은 모든 수의 합을 계산한 후 그 값이 주어진 수 m보다 작거나 같고, '이때까지의 계산값 중 합이 m과 가장 차이가 적게 날 때의 차'와 '현재 계산값과 m의 차'를 비교했을 때 현재 계산값과 m의 차가 더 작은지를 체크한다. 만약 두 조건을 모두 만족시킬 시 이를 결과값으로 삼고, 차 또한 갱신하여 저장해두는 과정을 반복한다. 그 후 모든 값에 대해 계산을 완료했을 때 저장된 결과값을 출력한다.

Q2. 12581 숨바꼭질2 > 문제 링크

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

int main() {

    int n, k;
    cin >> n >> k;

    int ans_time = 0, ans_cnt = 0;
    queue<pair<int, int>> q; // <위치, 시간> 저장
    int check[100001] = { 0, };

    q.push({ n,0 });

    while (!q.empty()){
        int now = q.front().first;
        int time = q.front().second;
        q.pop();
        check[now] = true;

        if (now == k) {
            if (ans_cnt == 0) { 
                // 완전히 처음 방문한 경우
                ans_time = time;
                ans_cnt++;
            }
            else if (ans_time == time) {
                // 이미 최소시간으로 방문한 경우, 최소 시간으로 방문했는지 추가 확인 필요
                ans_cnt++;
            }
        }


        if (now - 1 >= 0 && !check[now - 1]) {
            q.push({ now - 1,time + 1 });
        }

        if (now + 1 < 100001 && !check[now + 1]) {
            q.push({ now + 1,time + 1 });
        }

        if (2 * now < 100001 && !check[2 * now]) {
            q.push({ 2 * now,time + 1 });
        }
    }

    cout << ans_time << '\n' << ans_cnt << '\n';
}

문제를 요약하면 수빈이와 동생의 위치가 주어질 때 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지, 가장 빠른 시간으로 찾는 방법이 몇 가지 인지 구하는 문제이다. 수빈이의 위치와 동생의 위치가 같아질 때까지 최단경로를 탐색 해 시간과 방법의 수를 구하는 문제이므로, BFS로 문제를 풀었다.

우선 기본적으로 큐에서 원소를 pop 할 때 visited 배열을 true로 바꿔준다. push 하는 시점에 visited를 갱신하면 중복 방문이 불가능하기 때문이다.

이후의 과정은 동생을 만난 상황과 만나지 않은 상황으로 나뉘는데, 동생과 수빈이가 만나지 않은 경우에는 수빈이는 1초에 현재 위치 +1 or -1, or x2 만큼 이동할 수 있으므로, 수빈이가 이동 가능한 경로를 모두 큐에 담는다. 이 때 각 원소에서 시간은 지금 방문해있는 노드까지 도달하기 걸린 시간 + 1초로 계산하고, 위치는 각 상황에 맞게(+1, -1, x2) 갱신하여 넣는다. 그리고 동생과 수빈이의 위치가 같아졌을 때(만났을 때), 처음으로 현재 위치와 동생의 위치가 같아지게 된 상황에서는 그 상황이 최단 시간일 것이므로 ans_time에 저장한다. 이후에도 현재 위치와 동생의 위치가 같아지면 동생을 찾는 다른 방법이 더 있는 것이므로, 시간을 비교해서 최단 시간에 방문한 경로인지를 체크하여 해당하는 경우 방법의 수또한 추가한다. 이렇게 모든 방문을 마친 후 결과값을 출력한다.

http://www.kocw.net/home/cview.do?cid=e44bdd9b3a3f9bb5 강의 1강을 듣고, Computer Network : a Top-down approach 내용을 정리한 글입니다.

1.1 What is the Internet?

What's the Internet? (인터넷의 구성 요소)

• host(=end system) : 인터넷에 연결되는 장치. 사용자 애플리케이션을 hosting 하고 있다는 의미에서 host, 네트워크에 가장자리에 있다는 의미로 end system으로도 불림
• packet switch : 사용자의 메시지를 목적지를 찾아가게 해주는 컴퓨터. router, switches가 패킷(데이터+헤더로 구성된 정보의 묶음)을 link를 통해 전달한다.
• communication links : host와 router를 연결한다.
• internet : network of network. small network들이 연결되면 internet이라고 부른다.
• protocol : 정보의 송수신을 제어하는 일련의 모든 규칙들. 표준화가 이루어져야 통신이 가능하므로(모두 같은 방식으로 대화해야 하므로) protocol의 표준화가 중요하다 > IETF가 발표하는 RFC라는 표준안에 따라 통신한다.

What's a protocol? (프로토콜에서 정의하고 있는 내용)

프로토콜은 메시지의 포맷, 메시지를 보내고 받는 순서, 메시지를 받았을 때 어떻게 해야하는 지를 정의한다.

1.2 network edge

A closer look at network structure

• network edge : host(client와 server로 분리된다)
• access network : access network를 통해 host들이 연결된다.

Access networks and physical media

access network에서 중요하게 따져봐야 할 것은?

• bandwidth(=transmission width) : Access network를 구분짓는 중요한 변수. 단위시간 당 실어나를 수 있는 비트수를 계산한 것 (Mbps, Gbps의 단위를 가짐)
• shared or dedicated? : 여러명이 network를 share 하는 경우 내가 사용하는 bandwidth가 한정적이고, 보안에 취약하다.

Access net : DSL (digital subscriber line)

전화회사에서 access network를 제공하는 경우

결과적으로 data, voice 모두 DSL line을 통해 이동한다. 일반적으로 upstream bandwidth : 1Mbps, downstream bandwidth : 10Mbps로 그닥 빠르지 않다.

Access net : cable network

cable회사에서 access network를 제공하는 경우

HFC(hybrid fiber coax) : 케이블 회사에서 제공하는 access network를 칭하는 말. host에서 cable headend까지는 coax로 연결되지만, headend끼리 연결될 때에는 더 큰 bandwidth가 필요해 fiber로 연결된다. 따라서 hiber link와 coax link의 조합으로 이루어져있다.

일반적으로 upstream bandwidth : 2Mbps, downstream bandwidth : 30Mbps지만 shared이므로 무조건 빠르진 않다.

Access net : home network (집안 내부 network)

일반적인 집의 모습을 사용해봤을 때, 하나의 기기가 인터넷에 연결되는 것이 아니라, 여러개의 기기를 함께 연결한다.

따라서 router를 통해 집에 있는 network 장비를 묶어준다. 이 router에 유무선으로 여러 host가 연결된다. 이후 router가 headend나 central office에 연결되면서 multiplexting과정을 거친다. 보통 회사에서 network를 구성해줄 때 router와 access point(무선연결장치)를 한 박스로 구성해주는 경우가 많다.

Enterprise access networks (Ethernet)

ethernet switch에 여러 개의 기기가 연결되어 있고, 이는 회사 전체를 묶는 router에 연결되어 있다. 이 router가 ISP의 router에 직접 연결되면서 인터넷을 이용할 수 있다. (cable 회사 등이 필요한 home network와는 다르다)

Enterprise access networks (Wireless access networks)

기기가 직접 access point에 연결된다. wireless Lans(wifi) : 건물 안과 같은 작은 범위에서 사용 가능. 대역폭이 높다. wide-area wireless access(cellular) : 보다 넓은 범위에서 사용 가능.

기존의 테스트 파일에 @SpringBootTest, @Transactional 어노테이션만을 추가한다.

• @SpringBootTest : 스프링 컨테이너와 테스트를 함께 실행
• @Transactional : 테스트 시작 전에 트랜잭션을 시작하고, 테스트 완료 후에 항상 롤백한다

• BeforeEach, AfterEach를 사용할 필요가 없다. 트랜잭션이란? DB에 insert call을 하면, 커밋하기 전까진 DB에 반영되지 않는다.

12. JPA

JPA : SQL도 JPA가 직접 만들어서 실행해주는 방식. SQL보다는 객체 중심의 설계에 더 집중할 수 있어 개발 생산성을 높여준다. ORM : Object Relational Mapping . 객체와 relational database의 테이블을 매핑한다.

• JPA 엔티티 매핑 @Entity 어노테이션 추가. @Id나 @Column과 같은 어노테이션을 사용하여 테이블의 컬럼값을 관리한다.

  @Entity
  public class Member {
     @Id 
     @GeneratedValue(strategy = GenerationType.IDENTITY)
     private Long id;
  
    @Column("username")
    private String name
  }

• 리포지토리 관리 EntityManager를 주입하여 동작시킨다. 해당 코드를 실행하면 jpa가 insert 쿼리 진행시켜서 모든 설정을 수행한다.

 private final EntityManager em;
 public JpaMemberRepository(EntityManager em) {
     this.em = em;
 }
 public Member save(Member member) {
     em.persist(member);
     return member;
 }

 public List<Member> findAll() {
     return em.createQuery("select m from Member m", Member.class).getResultList();
 }

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

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

    bool check[31];
    memset(check, 0, sizeof(check));

    for (int i = 0; i < 28; i++) {
        int num;
        cin >> num;
        check[num] = true;
    }

    for (int i = 1; i < 31; i++) {
        if(!check[i]) cout << i << '\n';
    }

}

수가 입력되었는지 저장할 배열 check를 선언한 후 false로 모두 초기화한다. 이후 28개의 수를 입력 받으면서, 해당 수의 값을 index로 갖는 배열 값을 true로 변경한다. 그리고 for문을 이용해 값이 false인 배열 부분의 index 값을 출력한다.

Q2. 2668 숫자 고르기

먼저 두 배열에서 같은 인덱스 값을 가지는 값들을 연결해 그래프로 만들어 보면, 문제의 답이 되는 1,3,5는 사이클을 형성하고 있다는 공통점을 확인할 수 있었다.

그래서 그래프 탐색을 통해 싸이클이 존재하는 지를 확인하고, 사이클을 이루는 원소들은 result 배열에 값을 추가하는 방식으로 코드를 구현했다.

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

int arr[101] = { 0 };
int visited[101] = { 0 };
vector<int> result;

void dfs(int current, int start) {
    if (visited[current]) {
        if (current == start) {
            result.push_back(start);
        }
    }
    else {
        visited[current] = 1;
        dfs(arr[current], start);
    }
}

int main() {

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


    for (int i = 1; i <= n; i++) {
        memset(visited, 0, sizeof(visited));
        dfs(i, i);
    }

    // 결과 출력
    cout << result.size() << endl;
    sort(result.begin(), result.end());
    for (int i = 0; i < result.size(); i++)
        cout << result[i] << endl;

}

먼저 배열에 값들을 입력받고 방문을 체크할 배열을 모두 false로 초기화한다. 이후 dfs를 시행하는데, 이 때 어디서부터 탐색을 진행했는 지 알도록 start 변수도 매개변수로 계속 함께 넘겨준다. 이미 방문한 노드에 다시 방문하게 됐는데 현재 노드 값과 시작 노드 값이 같으면 사이클이 만들어진 경우이므로, 해당 시작 노드의 값은 결과 집합의 값이 될 수 있다. 그렇게 확인 된 값을 결과가 될 집합에 수를 추가하고, 이 과정을 모든 원소에 대해 반복한 후 result 벡터를 정렬하여 벡터의 크기와 원소들을 출력한다.

• 컨트롤러 : 웹 MVC의 컨트롤러 역할
• 서비스 : 핵심 비즈니스 로직 구현
• 리포지토리 : 데이터베이스에 접근, 도메인 객체를 DB에 저장하고 관리
• 도메인 : 비즈니스 도메인 객체 예) 회원, 주문, 쿠폰등의 데이터 객체

9. 테스트 케이스 작성 (JUnit 활용)

given - when - then(결과 확인) 형태로 코드를 구성한다. assert는 테스트가 실패했을 시, 테스트 시의 기댓값과 실제값을 직접 보여주어 유용하다.

@AfterEach
 public void afterEach() {
     repository.clearStore();
 }

@Test
 public void save() {
     //given
     Member member = new Member();
     member.setName("hi");

     //when
     repository.save(member);

     //then
     Member result = repository.findById(member.getId()).get();
     assertThat(result).isEqualTo(member);
    Assertions.assertEquals(member, result); // 위 코드와 기능이 동일하다. 

    IllegalException e = arrertThrows(IllegalException.class, ()-> memberService.join(member2));
   // 뒷 함수에서 IllegalException 에러가 터질 것으로 기대된다 -> 터지면 테스트 성공
 }

test 안에 package를 선택해서 test하면 package 안의 모든 파일에 대해 test를 실행한다. 모든 test는 순서 상관 없이 실행되므로, test 이후에 repository를 clear 할 수 있는 함수를 @afterEach 안에 생성하여 테스트에 사용한 모든 데이터를 지워줘야 한다. 그리고 @beforeEach에서 DI와 관련된 코드를 수행한다.

10. 스프링 빈과 의존관계

스프링 빈 : 스프링 컨테이너에 등록되어 스프링이 관리하는 객체 컴포넌트 스캔 : @Component 애노테이션이 있으면 자동으로 스프링 빈에 등록된다. @Service, @Controller 와 같은 애노테이션에는 @Component가 포함되어 있다. 이 때 Application 파일이 있는 폴더의 모든 하위 폴더에서만 컴포넌트 스캔이 진행된다.

의존관계 : 컨트롤러가 서비스를 통해서 비즈니스 로직을 수행한다. 이 때 컨트롤러가 서비스에 의존한다고 표현한다. DI(의존성 주입) : 생성자에 @Autowired 가 있으면 스프링이 연관된 객체를 스프링 컨테이너에서 찾아서 연결 해준다.

private final MemberService memberService;

@Autowired
 public MemberController(MemberService memberService) { 
     this.memberService = memberService;
 }

    Project : Gradle project
    Language : Java
    Spring Boot : (SNAPSHOT)이 붙어있지 않은 가장 최근 버전
    Metadata : Group, Artifact 임의로 설정
    Dependencies : Spring web, Thymeleaf(html 템플릿 엔진) 등 기본 선택
       Packaging: jar
    Java : 11

build.gradle : spring 설정 파일 -dependencies에서 프로젝트에 설치된 library 확인 가능

SpringBootApplication은 Tomcat을 내장하고 있어서, tomcat 웹서버를 자체적으로 띄우면서 spring boot가 같이 올라온다.

2. 스프링 라이브러리

• maven이나 gradle 같은 빌드 툴들은 의존관계를 관리한다. 한 라이브러리를 땡겨오면 의존관계가 있는 라이브러리(그 라이브러리를 사용하기 위해 필요한 다른 라이브러리)를 모두 땡겨온다.

• gradle 새로고침 하는 화면 아래에서 dependencies를 선택하여 라이브러리 의존 관계를 확인할 수 있다. ( (*)은 중복제거 )

• System.out.println 대신 logging으로 출력하도록 해야한다. slf4j, logback에 대해 더 공부해보기

• Junit : 테스트에 필요한 라이브러리/ assertj, mockito는 편리한 테스트를 도와주는 역할

3. Thymeleaf 템플릿 엔진

컨트롤러에서 문자를 return하면 뷰리졸버가 html 파일을 찾아 처리한다. 이 때 model을 이용해서 관련 data를 넘길 수 있다. 아래는 model을 이용한 data 전달의 예시다.

- controller 함수
 @GetMapping("hello")
     public String hello(Model model) {
     model.addAttribute("data", "hello!!");
     return "hello";
     }

- 뷰 html 내부
    <p th:text="'안녕하세요. ' + ${data}" >안녕하세요. 손님</p>

4. 빌드 및 실행

프로젝트 폴더에서 ./gradlew build. 이후 build/libs 폴더에 java -jar 프로젝트명-0.0.1-SNAPSHOT.jar 파일 실행

5. 정적 컨텐츠

서버에서 아무 처리도 하지 않고 화면을 그대로 내려주는 방식 spring이 컨트롤러의 내용을 찾았는데 없을 때 시행되므로, 컨트롤러보다 우선순위가 낮다. 인터넷에서 localhost:8080/{파일명}.html 형태로 접근

6. MVC와 템플릿 엔진

템플릿 엔진 : jsp, php를 이용하여 html을 동적으로 바꿔 내려주는 방식 MVC : Model, View, Controller가 분리되어 있는 방식 3번에 있는 코드와 같은 형태가 MVC 형태로 코딩 된 것이다.

@GetMapping("hello-mvc")
     public String helloMvc(@RequestParam("name") String name, Model model) {
     model.addAttribute("name", name);
     return "hello-template";
 }

위와 같은 코드에서 localhost:8080/hello-mvc?name="spring"과 같은 형태로 parameter를 넘겨준다. 뷰리졸버가 thymeleaf 템플릿 엔진 처리를 통해 변환된 html을 반환한다.

7. API

json과 같은 데이터 포맷으로 데이터를 전달하고, 화면은 client가 처리하는 방식 @ResponseBody 어노테이션이 필요하고, 뷰리졸버를 동작시키지 않고 html body에 데이터를 그대로 내려주는 방식이다. (HttmpMessageConverter가 동작된다) 아래와 같은 방식으로 코드를 작성하면 {"name" : "spring"}과 같은 json형태가 뷰에 출력된다.

 @GetMapping("hello-api")
 @ResponseBody // 필수
 public Hello helloApi(@RequestParam("name") String name) {
     Hello hello = new Hello();
     hello.setName(name);
     return hello;
 } 

1. EC2 인스턴스 생성 EC2 기본개념 게시글에서 5번 항목을 참조하여 EC2 서버를 연결한다. 이 때 EC2 인스턴스의 보안 그룹 인바인드 규칙에 HTTP, 8080, SSH 등을 아래와 같은 형태로 추가해 서버를 생성한다.

2. EC2에 Jenkins & Docker 설치 내 PC의 bash에서는 apt-get이 작동하지 않아 yeju님의 CTIP 환경 구축 - 3. AWS EC2에 Jenkins & Docker 설치 게시글을 참고하여 설치하였다.

   설치 전 패키지 업데이트 : sudo yum update -y
   
   JAVA 설치 : sudo yum install java-1.8.0-openjdk-devel.x86_64 -y
   
   git 설치 : sudo yum install git -y
   
   Docker 설치 : sudo yum install docker -y
   Docker 서비스 실행 : sudo service docker start
   
   Jenkins 설치 :
   sudo wget -O /etc/yum.repos.d/jenkins.repo \
   https://pkg.jenkins.io/redhat-stable/jenkins.repo
   sudo rpm --import https://pkg.jenkins.io/redhat-stable/jenkins.io.key
   sudo yum upgrade
   sudo yum install jenkins -y
   Jenkins 서비스 실행 : sudo service jenkins start
   
   이후 http://Personal IP 주소:8080 으로 접속하고,
   sudo cat /var/lib/jenkins/secrets/initialAdminPassword 를 입력하여 비밀번호를 확인 한 후 
   이 정보를 바탕으로 Jenkins 서버에 접속하여 초기 id 비밀번호를 설정한다.

3. Jenkins Setting

   • jenkins에서 sudo 사용을 위한 권한 설정

     git bash에서 sudo vi /etc/sudoers 입력 후 아래 사진에 해당하는 부분을 사진처럼 편집

   • Jenkins create item 소스 코드 관리에 해당하는 github의 주소를 기입한다. 그 후 credentials에 add > Jenkins 버튼을 눌러 아래 사진과 같이 github 정보를 입력한다. 이 때 password는 github access token을 사용한다. build step을 Execute shell로 설정한 후 command에 ./gradlew clean build를 입력한다.

1. EC2 인스턴스의 보안 그룹 인바인드 규칙에 HTTP, 8080, SSH 등 추가

2. EC2 인스턴스 접속 후 기본 설치

• 깃헙 설치

  sudo yum install git

• 자바 설치

  설치 가능한 java 버전 확인 : sudo yum list | grep jdk
  자바 설치 : sudo yum install java-1.8.0-openjdk
  javac 설치 : sudo yum insall java-1.8.0-openjdk-devel.x86_64

  

3. 배포 절차

   git clone https://github.com/haeun-i/EC2TEST.git
   cd [프로젝트명(github 프로젝트 이름)] ex.EC2TEST
   sudo chmod 777 ./gradlew 
   ./gradlew build

   -> clone할 때 깃헙에서 로그인 방식의 인증을 지원하지 않고 access token 형식으로 바뀌어서 어려움을 겪었으나 장상현님 블로그를 보고 해결했다. 로그인 시에는 username에는 github 이름(나의 경우 haeun-i), password에는 access token의 비밀번호를 Shift+Insert를 통해 입력해 인증했다.
   

4. jar 파일 생성 확인 후 실행

   cd build/libs
   ls (파일 명 확인)
   java -jar demo-0.0.1-SNAPSHOT.jar

   

• 동물 보호소에 들어온 모든 동물의 정보를 ANIMAL_ID순으로 조회 -> SELECT, ORDER BY를 사용하여 풀이

  SELECT * FROM ANIMAL_INS
  ORDER BY ANIMAL_ID;

  
  

2. 역순 조회하기

• 동물 보호소에 들어온 모든 동물의 이름과 보호 시작일을 조회. 이때 결과는 ANIMAL_ID 역순으로 정렬
• DESC를 이용해 역순으로 정렬이 가능하다. 오름차순으로 정렬하고 싶은 경우 ASC를 사용하여 정렬할 수 있다. (EX. ORDER BY DEPNO ASC, SAL DESC)

  SELECT NAME, DATETIME FROM ANIMAL_INS
  ORDER BY ANIMAL_ID DESC

  
  

3. 아픈 동물 찾기

• 동물 보호소에 들어온 동물 중 아픈 동물의 아이디와 이름을 조회. 이때 결과는 아이디 순으로 정렬
• WHERE문에 조건 붙여서 코드 작성

  SELECT ANIMAL_ID, NAME FROM ANIMAL_INS
  WHERE INTAKE_CONDITION='Sick'

  
  

4. 어린 동물 찾기

• 동물 보호소에 들어온 동물 중 젊은 동물의 아이디와 이름을 조회. 이때 결과는 아이디 순으로 정렬
• not구문을 사용하여 풀이. not을 사용할 때는 일반 조건 형태와 똑같이 구문 작성 후 앞에 not을 붙이는 형태다.

  SELECT ANIMAL_ID, NAME FROM ANIMAL_INS
  WHERE NOT INTAKE_CONDITION = 'Aged'

  
  

5. 동물의 아이디와 이름

• 동물 보호소에 들어온 모든 동물의 아이디와 이름을 ANIMAL_ID순으로 조회하는 SQL문을 작성

  SELECT ANIMAL_ID, NAME FROM ANIMAL_INS

  
  

6. 여러 기준으로 정렬하기

• 동물 보호소에 들어온 모든 동물의 아이디와 이름, 보호 시작일을 이름 순으로 조회. 단, 이름이 같은 동물 중에서는 보호를 나중에 시작한 동물을 먼저 보여줘야 한다.
• 2번 풀이 참조

  SELECT ANIMAL_ID, NAME, DATETIME FROM ANIMAL_INS
  ORDER BY NAME ASC, DATETIME DESC

  
  

7. 상위 n개 레코드

• 동물 보호소에 가장 먼저 들어온 동물의 이름 조회
• 상위 n개의 레코드는 LIMIT n을 통해서 조회할 수 있다.

  SELECT NAME FROM ANIMAL_INS
  ORDER BY DATETIME LIMIT 1;

• Elastic Computing Cloud (안전하고 확장성 있는 컴퓨팅 서비스)
• Instances(서버), Container(도커나 쿠버네티스에 사용), Serverless(lambda, 서버없이 동작하는 코드 실행), Hybrid 등으로 구성되어 있다.
• 초당으로 요금이 계산된다 -> 사용하지 않으면 정지 필수
• ELB, Auto Scaling, S3등 다양한 서비스와 연동 가능
• EC2는 AZ 기반이므로, 고가용성을 위해서는 MultiAZ(둘 이상의 AZ를 이용해 둘 이상의 서버 구축)를 통해 가용성을 확보해야 한다.
  

2. EC2 관련 서비스

• EC2 : 서버, CPU에 해당함
• EBS(Elastic Block Storage) : EC2의 블록 저장장치, SSD, AZ 서비스
• EBS Snapshot : EBS 백업 데이터
• VPC : Virtual Private Cloud : EC2가 연결되는 사설 네트워크 망, 리전 기반 -> MultiAZ를 가능하게 함
• Subnet : VPC의 하위망. AZ 서비스로 EC2는 subnet에 위치함
• ENI : 가상 네트워크 인터페이스, 랜카드, AZ 서비스
• security group : EC2의 방화벽, 포트 접근 제어
• Auto scaling : 트래픽에 맞춰 서버를 늘리거나 줄이거나 해주는 서비스
• AMI : EC2의 백업. 사용자가 원하는 시점에 AMI를 생성하고 이를 통해 그 지점부터 EC2를 시작하는게 가능하다.
  

3. EC2 실습

• 콘솔 EC2-> Amazon linux AMI를 선택 -> 프리티어 -> 이후 기본값들
• 태그 추가 무조건 "Name" 필수 ex) Name inf-demo 꼴로
• 키 페어가 없으면 아무도 ec2에 접근할 수 없다.
  

4. EC2 접속

• 인스턴스 -> 연결 -> EC2 인스터스 연결에서 연결 버튼만 누르기
• 중지 : 컴퓨터를 끈 것과 같은 상태. 요금이 계속 나온다.
• 종료 : 서버를 완전히 삭제하는 것
  

5. Git bash를 이용해 접속하기

• 인스턴스 > 연결 > SSH 클라이언트 이용해서 도움말 참고
• 폴더에 프라이빗 key 파일 이동
• chmod 400 inf-demo.pem
• ssh -i "inf-demo.pem" ec2-user@ec2-3-35-135-234.ap-northeast-2.compute.amazonaws.com
• 인바운드 규칙 위치무관으로 해야 접속 가능
  

6. elastic-ip 연결

• 중지 후 재시작하면 IP가 변경된다. -> 고정 IP가 필요하다면 elastic-ip를 연결해야 한다.
• 탄력적 IP 주소 할당 -> 작업-> 탄력적 IP주소 연결 -> 인스턴스 선택
• elastic-ip 연결해놓은 인스턴스가 중지 상태이면 과금이 된다. 사용하지 않을 시 무조건 반환 해야 함.
  

• AWS의 대표적인 서비스
• 객체 스토리지
• 파일 업로드, 다운로드, 검색 가능
• 무제한 용량
• 다양한 인증 / 권한 부여 제공
  

2. 특징

• 리전 기반 서비스
• 매우 안전
• CDN 서비스와 연동 가능
• s3를 정적인 컨텐츠에서 서버처럼 사용 가능
• 필요에따라 버저닝 기능 사용 가능
  

3. 사용예

• 클라우드 저장소 (개인 파일 보관 용도)
• 서비스의 대용량 파일 저장소 (이미지, 동영상, 빅데이터)
• 서비스 로그 저장 및 분석 (서버에 저장되는 것은 안정성, 비용 측면에서 좋지않음)
• AWS 아데나를 이용한 빅데이터 업로드 및 분석
• 서비스 사용자의 데이터 업로드 서버 (이미지 서버, 동영상 서버)
• 중요한 파일은 EC2의 SSD(EBS)에 저장하지 말고 S3에 저장해야 함.
  

4. 기본 실습 1

• 버킷(객체(파일)을 저장하기 위한 컨테이너) 생성

    버킷의 이름은 글로벌하게 유니크 해야한다.
    (전세계적으로 같은 이름이 존재해선 안된다.)

• 파일 업로드

    s3에 올라가는 파일들은 무조건 고유한 URL을 갖게 된다. -> 버킷이 비공개이므로 기본적으로는 웹에서 볼 수 없지만, 권한 조정을 통해 가능하다.

• 폴더 사용 폴더 생성은 가능하지만, 실제로는 폴더가 아닌 prefix 개념이다.
• 파일 옮기기 복사 : 작업 > 복사 > 폴더명 변경

• 버킷을 삭제하기 전에 먼저 버킷 내부를 비워야 한다. (파일 하나하나 삭제 해야 하는 번거로움이 있음)
• 버킷 삭제 클릭 시 뜨는 팝업에서 버킷 비우기를 선택하여 한 번에 삭제 하는 것이 편리하다.

• key: 버킷 안의 오브젝트를 식별하는 데 사용 버킷안에 폴더를 생성할 수 잇는데, 폴더는 사실 키의 접두사일 뿐이다. 예시를 들어서 설명하면 https://honux-inf.s3.amazonaws.com/2021-1/avartar.png 에서 2021-1/avatar는 폴더이기도 하지만, 버킷안의 오브젝트를 식별하는데 사용하는 key이다. 버킷 이름 : honux-inf, prefix(폴더) : 2021-1, 파일명 : avatar.png key : 2021-1/avatar.png
• versioning은 on/off가 가능하다.

• ACL(Access Control List) : 객체마다 ACL 지정 가능. 간단한 제어에 사용
• Bucket Policy : IAM Policy와 유사한 문법. ACL보다 복잡하고 세부적으로 지정 가능
• IAM을 이용한 제어 : IAM 사용자에게 버킷 접근 권하능ㄹ 주기 위해 사용
• PresignedURL : URL을 이용하여 임시 권한을 부여하는 기능. 매우 유용함.

• 파일 public으로 만들어보기 ```

1. 버킷을 퍼블릭으로 만든다. 생성 시에 버킷 접근 권한을 허용할 수 있도록 만들 수 있지만, 아무 설정도 건드리지 않으면 퍼블릭이 아닌 상태로 만들어진다. 만약 허용하지 않았다면 객체 선택 > 권한에서 퍼블릭 액세스 비활성화 차단을 해제하면 된다.
2. 파일을 퍼블릭으로 만든다. 객체작업 > 퍼블릭으로 설정 (현재는 안되는 것 같다) ```

• ACL 살펴보기

  파일에 접속하여 권한 > ACL 편집

• bucket policy로 특정 폴더에 접근 권한 주기

  디렉토리 이하의 모든 파일을 public으로 바꾸고 싶을 때 사용
  버킷 권한의 버킷 정책을 수정한다. 편집 > 정책 생성기
  - Policy type : S3 Bucket Policy 
  - Effect : Allow 
  - Principal : * 
  - Action : GetObject
  - ARN 주소 기입 + /*

9. CLI로 S3 사용하기 -> 생략

   
   

10. S3 웹 호스팅

    • 정적 웹 호스팅? S3를 웹 서버 처럼 사용가능 (정적인 웹페이지 한정)
    • RouteS3를 이용해서 DNS 연동 가능 이 경우 버킷 이름이 도메인 이름과 같아야함 (ex. www.honux.io)
    1. 버킷을 버킷 정책을 이용하여 public으로 만든다.
    2. 버킷 속성에 정적 웹사이트 호스팅 활성화 인덱스 문서 - index.html 에러 문서 - error.html
       

11. Multipart 업로드

• CLI, SDK 사용 시 단일 PUT 사용으로 5GB까지 업로드 가능(싱글파일 업로드) 관리 콘솔은 160GB까지
• Multipart Upload : 큰 파일을 쪼개서 병렬적으로 업로드. 5TB까지 가능

12. 추가 사용에 유용한 정보

• 스토리지 클래스를 변경하면 요금을 절약할 수 있다.
• 라이프 사이클 규칙 지정을 통해 수명 관리가 가능하다.

실습으로 배우는 AWS 핵심 서비스 강좌를 정리했습니다.

1. 관리 콘솔 ( AWS Management Console )

   Root Acoount : 회원 가입 때 사용한 이메일 계정
   즉시 IAM 사용자를 생성해서 사용하는 것을 권장한다.
   Root account는 MFA 등을 이용해서 이중화를 하는 것이 안전하다.

2. AWS Global Infra https://www.infrastructure.aws/

   region : 2개 이상의 AZ의 모임. 각 region은 각각 다른 AWS 서비스를 제공한다.
   AZ(Availability zones) : 하나 이상의 데이터 센터로 구성됨
   엣지 로케이션(PoP) : CDN, DNS 서비스를 제공
   
   서울 리전 : ap-northeast-2

3. IAM admin 사용자 추가하기

   1. IAM 서비스로 이동
   2. Admin 그룹 생성 및 권한 부여
   - 그룹 이름 설정 후 'AdministratorAccess' 정책 추가 (모든 Action, resource 허용)하여 그룹 생성
   3. Admin 사용자 생성
   - 사용자 이름 임의 지정, AWS Management Console 액세스 체크, 비밀번호 재설정 해제 후 
    사용자를 그룹에 추가
   4. IAM 어드민 유저로 로그인
   - 사용자 추가 후에 csv 파일을 받으면 login link가 생기는데 이 링크로 항상 로그인 해서 계정에 접근하면 된다.
   
   Admin을 만들어서 사용하는 이유? 이 계정이 노출되어 있을 때 root account를 이용해 admin 유저를 제어할 수 있기 때문이다.

4. IAM 개발자 id 추가

   1. developer 그룹 생성 및 권한 부여
   - 그룹 이름 설정 후 'PowerUserAccess' 정책 추가 
    (admin 계정 보다는 권한이 작아야 하므로, resource는 사용할 수 있지만 계정 정보 관련에는 대부분 접근할 수 없음)하여 그룹 생성
   2. 개발자 사용자 생성
   - 사용자 이름 임의 지정, AWS Management Console 액세스 체크, 비밀번호 재설정 해제
   3. IAM 개발자 계정으로 로그인
   - 어드민 계정과 동일하게 로그인 가능하지만, IAM 서비스엔 접근이 불가능하다.

5. 로그인 URL 변경

   IAM 대시보드에서 변경 가능하다.
   계정의 별칭을 지정함으로써 회원 번호 부분이 별칭으로 바뀌는데, 
   이 별칭을 사용해서 바로 로그인이 가능하다.

6. IAM policy

   AWS Identity and Access Management
   : AWS 리소스에 대한 액세스를 안전하게 제어할 수 있는 웹 서비스. 
   사용자가 리소스를 사용하려고 할 때 권하능ㄹ 세부적으로 조정하는 서비스
   
   - Resource? 자원. AWS에서는 컴퓨팅, 스토리지, 네트워크 등
   - Access : 리소스를 조작 및 제어하는 것

   Authentication(인증) -> Authorization(권한 부여) -> resource(자원)
   

AWS에서 인증을 담당하는 주체는? User (id, key방식 두 가지 존재) 권한 부여를 담당하는 주체는? Policy

IAM Group

• 공통의 권한을 가지는 사용자의 집합
• 그룹을 생성 후 IAM Policy 연결
• 그룹에 사용자 추가
• 그룹 내 사용자는 그룹과 연결된 Policy의 권한을 부여받음.

IAM User

• 그룹의 IAM Policy에 따라 권한을 부여받음. (사용자에게 직접 Policy를 추가할 수도 있음.)
• IAM User의 인증방식과 사용 용도 1) ID/PASSWORD 방식 : 관리 콘솔에서 사용 2) AcessKey ID / Secret Access Key : CLI, SDK, Web API에서 사용
• Long term credential이라고도 함(영구적인 권한이므로)

7. IAM Policy의 종류

   - AWS 관리 정책
   AWS가 미리 만들어 놓은 정책, 사용자는 편집 불가능
   - 사용자 관리 정책
   사용자가 직접 생성한 정책
   기존 정책으로부터 생성 및 수정 또는 직접 생성 가능
   GUI 편집기 / JSON 편집기 모두 사용 가능(GUI 편집기가 조금 더 쉽다)
   Effect : 허용, 거부
   Action : api(행동) ex)"Action" : "s3:*" - s3만 사용가능
   Resource : aws resource(ec2, s3와 같은)
   - Inline 정책
   1회성 정책. 재사용이 안됨

8. IAM Role ```

• 특정 개체에게 리소스의 접근 권한을 부여하기 위해 사용 (IAM 사용자, AWS 서비스, 다른 계정, AWS 관리계정)
• Short term credential(임시 자격 증명) - 사용할 때만 잠깐 권한 부여
• 주로 AWS 서비스들이 직접 다른 AWS 서비스를 제어하기 위해 사용함. 사용자나 응용 프로그램에서 일시적으로 AWS 리소스에 접근 권한을 얻을 때도 사용

9. IAM Role의 주요 구성요소 ```

• Role ARN : 역할을 호출하기 위해 필요. role을 식별하기 위한 식별자. role의 주소(url)
• IAM policy : 이 역할이 어떤 권한을 부여할 수 있는가
• 신뢰 관계 : 어떤 개체가 IAM Role을 호출할 수 있는가
• 그 외 유지시간, 이름 등도 필요

임시 자격증명이기 때문에 보안상 유리하다.

10. IAM Role 사용예

• EC2 role : ec2 인스턴스에게 aws 서비스 접근 권한을 부여

• Lambda Execution Role: 람다에서 s3로부터 파일을 읽고 싶을 때 role에 권한 지정

• 다른 계정의 사용자에게 내 계정의 DynamoDB에 임시 접근 권한 부여

• 안드로이드 앱이 S3로 직접 동영상을 업로드 할 때 사용

  ARN(Amazon Resource Name) 아마존에서 리소스를 유일하게 식별할 수 있는 구분자

  형태 : arn:partition:service:region:account-id:resource-id ex) arn:aws:iam::123456789:user/honux

  arn:aws:s3:::mybucket/folder/file1  

11. Switch Role

    역할 변경을 위해서는 먼저 admin 사용자로 로그인 후
    1. 역할 만들기
    다른 AWS 계정(보통 AWS서비스를 많이 쓴다)
    -> 정책 선택 (IAM 권한을 주려면 IAMFullAccess) 
    2. 신뢰관계 편집 
    Principal 부분의 url 뒷 부분의 'root' 부분을 권한을 주고 싶은 사용자의 이름으로 바꾼다.
    3. 역할 변경
    권한을 받은 객체의 아이디로 로그인 해서 역할 전환(이름부분 클릭을 통해 접속가능)
    계정, 생성한 역할 이름, 표시이름 및 색상 지정하면 역할 전환됨. 

12. CLI 사용법 ``` CLI : AWS Command Line Interface

13. 사용자에게 access key를 만든다.

14. aws configure 명령으로 기본 설정 access key 로그인 region name : ap-northeast-2 (알파벳 생략) output format : none

15. 이후 aws s3 ls 와 같은 명령어를 사용 가능하다.

설정 내용은 aws 폴더에서 credential, config에서 확인 가능하다. ```

접속

mysql 접속

MYSQL -u 유저명 -p 패스워드 -h 호스트

mysql -u root -p 123456 -h localhost

조회

데이터베이스 조회

SHOW DATABASES;

테이블 전체 목록 조회

SHOW TABLES;

테이블 상세정보 조회

DESCRIBE testtable;
EXPLAIN testtable;

두 가지 모두 사용 가능하다.

테이블 내의 데이터 조회

SELECT 컬럼명1, 컬럼명2, .. FROM 테이블명;

SELECT id, name, phone FROM testtable;
SELECT name, phone FROM testtable WHERE phone LIKE '%5678';
SELECT * FROM testtable ORDER BY id DESC; 

이 때 ASC: 오름차순, DESC : 내림차순 정렬이다. 

생성

데이터 베이스 생성

CREATE DATABASE testdb;
USE testdb;

테이블 생성

CREATE TABLE testtable (
    -> id int NOT NULL auto_increment primary key,
    -> name VARCHAR(15) NOT NULL,
    -> phone VARCHAR(15) NOT NULL
    -> );

테이블 내의 데이터 삽입

INSERT INTO 테이블명 [컬럼1, 컬럼2, ...] VALUES (값1, 값2, ...);

INSERT INTO table_name VALUES (1105, '테스트', '대한민국');
INSERT INTO table_name (id, name) VALUES (1105, '테스트');

테이블 컬럼 추가

ALTER TABLE 테이블명 ADD 추가할컬럼명 컬럼타입 DEFAULT 디폴트값
ALTER TABLE 테이블명 ADD COLUMN 추가할컬럼명 컬럼타입 DEFAULT 디폴트값 컬럼위치

ALTER TABLE user ADD level int DEFAULT 1;
ALTER TABLE 'rank' ADD COLUMN 'ranking' INT(10) DEFAULT 0 AFTER 'user_id' // user_id 뒤에 추가
ALTER TABLE 'rank' ADD COLUMN 'ranking' INT(10) DEFAULT 1 FIRST // 테이블 맨 앞에 추가

수정

테이블 내의 데이터 수정

UPDATE 테이블명 SET 컬럼1 = 수정값1 [, 컬럼2 = 수정값2 ...] [WHERE 조건];

UPDATE table_name SET country = '대한민국';
UPDATE table_name SET name = '테스트 변경', country = '대한민국' WHERE id = 1105;

테이블 컬럼명 변경

ALTER TABLE 테이블명 CHANGE 기존컬럼명 변경할컬럼명 컬럼타입

ALTER TABLE user CHANGE socre score int;

삭제

테이블 내의 데이터 삭제

DELETE FROM 테이블명 [WHERE 조건];

DELETE FROM table_name;
DELETE FROM table_name WHERE id = 1105;

foreign key 무시하고 강제 삭제

SET foreign_key_checks = 0; 
DELETE 관련 명령
SET foreign_key_checks = 1; 

전체 삭제

DROP TABLE testtable;
DROP DATABASE testdb;

테이블 컬럼 삭제

ALTER TABLE 테이블명 DROP COLUMN 컬럼명
ALTER TABLE user DROP COLUMN level;

출처 확장형 뇌 저장소 리충닷컴 개발자가 되기위한 첫 걸음

• Average Case Complexity worst case가 pivot이 mininum이거나 maximum일 때 이고, 중간값일 경우에 best case이므로 평균 case일때는 pivot이 1/4n이거나 3/4n 위치에 있을 때이다.
  

n개의 원소를 partion할 때 각 level에서 걸리는 총 시간 : O(n) 트리의 높이 k는 n*(34)^k = 1을 활용해서 k=log4/3n ≤ θ(logn) 따라서 평균 수행시간은 O(n) * logn = O(nlogn)

• In-Place Quick-Sort

  in-place 알고리즘? 추가적인 place를 필요로 하지 않는 알고리즘 -> quick-sort에 필요한 L, E, G를 index를 나눔으로써 한 배열에서 분리할 수 있다.
  
  
  

[Merge sort]

• Merge sort 진행 방식

  재귀 함수를 사용하여 주어진 배열을 원소가 하나가 될 때까지 나눈다. 그 후 역으로 재귀가 풀리면서 두 배열의 첫 원소를 비교하여 더 작은 원소를 새로운 배열에 넣는 형태로 나누어진 배열들을 병합하여 정렬한다.

• Worst Case Complexity

  W (n) = W (n/2) + W (n/2) [분할과정에서의 연산 수] + Wmerge (n) (이 때 Wmerge (n) = n-1, W (1) = 0)