문제

https://www.acmicpc.net/problem/1717

주안점

n(1 ≤ n ≤ 1,000,000), m(1 ≤ m ≤ 100,000)

n과 m의 범위가 커 유니온 파인드를 사용하지 않는다면 시간초과가 나온다.

구조

유니온 파인드를 이용한 기본적인 구조

코드

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

int n,m,t,a,b;
int p[1000001];

int finnd(int n){
    if(p[n]<0) return n;
    p[n] = finnd(p[n]);
    return p[n];
}

void merge(int a, int b){
    a = finnd(a);
    b = finnd(b);
    if(a==b) return;
    p[b] = a;
}

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

    cin>>n>>m;
    fill(p, p+n+1, -1);
    for(int i=0; i<m; i++){
        cin>>t>>a>>b;
        if(t) {
            cout<<(finnd(a)==finnd(b) ? "YES" : "NO")<<"\n";
        }
        else merge(a,b);
    }
}

쿠버네티스의 개념

• 대표적인 도커 오케스트레이션 툴
  • 도커
  • 도커 컴포트
  • 도커 오케스트레이션
    • Clustering : 여러 개의 컨테이너를 합쳐 하나의 시스템으로 만들어 컨테이너를 배치
    • Auto-placement : 여러 개의 서버를 가지므로 어떤 컨테이너를 어떤 서버에 적절히 배치하는가
    • Auto-restart : 장애로 인해 컨테이너를 새로 띄운다.
    • 무중단 배포 : 신규 컨테이너를 배포할 때 중단 없이 배포한다.
• 네임스페이스
  • 논리적인 클러스터
  • 개별적인 Access control 정책, 네트워크 정책
• 리소스
  • Pod : docker container와 유사하다, 최소단위
  • Node : 서버
  • Sevice : 네크워크 담당
• 앱 정의서
  • 리소스의 정의 (YAML 파일 형식 - 선언형 명령)
• Desired State : 바라는 상태
  • 쿠버네티스는 현재 상태가 있고 바라는 상태로 가려한다.
  • YAML 파일로 바라는 상태를 수정 → 현재 상태가 바라는 상태로 변경됨 ⇒ 기존에 현재 상태가 여러가지 이유로 리소스가 삭제 되거나 바뀌어도 바라는 상태로 계속 바뀌게 되는 형식이다.
  • 이러한 방식으로 새로운 기능이 추가된다.
• 라벨 & 셀렉터
  • 리소스에 label을 달 수 있다.
  • selector를 통해서 해당 라벨을 가지고 있는 리소스를 선택할 수 있다.

쿠버네티스의 아키텍처

• 마스터 노드와 워커 노드가 존재
• Master
  • kube-api-server
    • 쿠버네티스의 모든 컴포넌트와 통신하는 역할
    • 모든 컴포넌트의 리퀘스트를 받고 리스폰스 하는 역할
    • 워커노드와 다리 역할
  • etcd
    • api 서버로부터 들어온 데이터를 저장 및 제공해주는 역할
    • RDB가 아닌 Key-Value 형태의 데이터
    • 쿠버네티스 안의 모든 메타정보를 저장하고있다.
  • kube-scheduler
    • Auto-Placement 기능 : 어떤 노드가 가능한지 확인 (Scheduling)
  • kube-controller manager
    • current state와 desire state를 확인하며 달라지면 kube-scheduler를 통해서 리소스 관리
    • 루프를 통해서 지속적으로 확인
  • cloud-controller manager
    • public cloud를 사용하는 경우 통신 기능 제공
• Woker
  • kubelet
    • kube-api-server로 부터 어떤 컨테이너를 실행해야 하는지 전달 받아 실제로 컨테이너를 실행한다.
    • 워커노드의 상태를 전달
  • kube-proxy
    • 컨테이너간의 네트워크를 담당

쿠버네티스의 장점

• 컨테이너 스케줄링이 편리
• Auto Scaling을 통해 확장성이 좋다
• 모니터링이 쉬워진다.
• 장애에 견고해진다.
• Hybrid / 멀티 클라우드 구현 ( aws, google, micro azure, on-promise )

문제

https://www.acmicpc.net/problem/14716

주안점

기본적인 BFS에서 사용하는 상,하,좌,우 에다가 대각선이 포함된 이동을 한다.

구조

BFS를 통하여 Visited로 확인하며 몇번 BFS를 돌았는지 확인

코드

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

int row,col,ret,y,x;
int a[254][254], visited[254][254];
queue<pair<int,int>> q;

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

int main() {
    cin>>row>>col;
    for(int i=0; i<row; i++){
        for(int j=0; j<col; j++){
            cin>>a[i][j];
        }
    }
    for(int i=0; i<row; i++){
        for(int j=0; j<col; j++){
            if(a[i][j]==1 && visited[i][j]==0){
                ret++;
                visited[i][j] = 1;
                q.push({i,j});
                while(q.size()){
                    tie(y,x) = q.front(); q.pop();
                    for(int k=0; k<8; k++){
                        int ny = y+dy[k];
                        int nx = x+dx[k];
                        if(ny>=row || nx>=col || nx<0 || ny<0) continue;
                        if(visited[ny][nx]==1 || a[ny][nx]==0) continue;
                        visited[ny][nx] = 1;
                        q.push({ny,nx});
                    }
                }
            }
        }
    }
    cout<<ret<<"\n";
}

1. MSA 란?

 - Micro Service Architecture의 줄임말

 - 말 그대로 작은 단위의 서비스로, 독립적으로 관리, 배포 가능한 각각의 독립적인 기능을 제공하는 서비스 아키텍쳐를 의미한다.

2. MSA의 목표

 - 빠르게 개발해 지속적으로 배포할 수 있어야 한다.

 - 수동 혹은 자동으로 쉽게 스케일링할 수 있어야 한다.

3. MSA의 장점

 - 플랫폼의 각 서비스는 개별적으로 배포, 업그레이드할 수 있다. API 가 명확하기 때문에 다른 서비스의 수명 주기와 상관 없이 서비스를 업그레이드할 수 있다.

 - 플랫폼의 각 서비스를 다른 컴포넌트와 상관 없이 여러 서버로 Scale Out할 수 있어 고가용성 요구사항을 충족하거나 대용량 트래픽 처리하는데에 유용하다.

 - 각 서비스는 모듈화가 되어있고 각 모듈으느 Message Driven API 방식으로 통신하는데 이러한 방식은 빠른 개발과 쉬운 유지보수를 할 수 있게 한다.

4. MSA의 단점

 - 서비스의 새 인스턴스를 추가하려면 수동으로 로드밸런서를 구성하고 새 노드를 설정해야한다. 이 과정에서 오류가 발생하기 쉽다.

 - 통신하는 다른 시스템에서 오류가 발생했을 때 플랫폼 전체로 전이된다는 근본적인 문제가 있다.

 - 플랫폼 전체를 모니터링하는 과정이 훨씬 더 복잡하다.

 - 모든 서비스의 인스턴스 구성을 일관성 있게 최신 상태로 유지하는 작업에도 반복적인 수작업이 발생하며 이에 따른 품질 문제가 발생할 수 있다.

 - 테스트가 어렵다.

5. MSA의 전제 조건

 - 아무것도 공유하지 않는 아키텍처를 유지해야한다.

 - 명확한 인터페이스를 통해서만 통신해야한다.

 - 개별적인 런타임 프로세스로 배포해야 한다. (= 도커 컨테이너와 같이 독립된 런타임 프로세스로 실행해야한다.)

6. MSA의 디자인 패턴

 1) 서비스 검색 : 클라이언트가 마이크로서비스와 그 인스턴스를 찾을 수 있어야 한다.

  - 인스턴스는 자동으로 등록 및 등록 해지한다.

  - 요청사항은 사용가능한 인스턴스 중 하나로 라우팅된다.

 2) 에지 서버 : 일부 마이크로서비스만 외부에 공개하고 그외의 서비스는 외부에서 접근하지 못하도록 숨기는게 바람직하다.

 3) 리액티브 마이크로서비스

  - 논블로킹 I/O를 사용해 스레드가 할당되지 않게 한다.

 4) 구성 중앙화

  - 마이크로서비스 집합에 대한 구성 정보를 한 곳에 저장하고 환경별 설정을 지원한다.

 5) 로그 분석 중앙화

  - 각 서비스를 제공하는 인스턴스를 감지하고 로그를 한곳에 수집한다.

문제

https://www.acmicpc.net/problem/2292

주안점

1. 입력을 잘 보면 범위가 크므로 절대 배열을 사용하여 할당을 한 후에 해당 값을 찾으려 하면 안된다. => 수학적으로 해결

2. N이 1인경우 처리

구조

각 껍질(?)의 가장 큰 수는 6의 배수로 증가한다.

코드

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

long long n;
long long ret = 1;
long long num = 1;

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

    cin>>n;
    if(n == 1) {
        cout<<ret<<"\n";
        return 0;
    }
    while(num < n) {
        if(num == n) break;
        num += ret*6;
        ++ret;
    }
    cout<<ret<<"\n";
}

2021년 10월 9일 용인 임장을 다녀왔다.

용인에는 수지구, 기흥구, 처인구가 있다.

수지구와 기흥구는 어느정도 발전이 있었고 처인구만 남았다. 이제 처인구 차례이다. 그래서 기흥구와 처인구를 중심으로 임장을 다녀왔다. 기흥구를 갔다온 이유는

오산에서 강남까지 지하철이 생기기 때문이다. 아직 역과 위치가 정확이 정해지지 않아 여러가지 후보군이 있는데 이를 확인하러 갔다왔다.

용인 임장의 포인트는 3가지다.

1. 기흥 ~ 오산 지하철 분석

2. 지하철 위치 후보군 확인

3. 용인 시청

1. 아래 사진은 기흥 ~ 오산 수인분당선 예측이다.

기흥에서부터 시작돼 오산이 종점인 분당선으로 위 예상대로 지어진다면 가장 수혜지역은 오산이 될 것이다. 오산은 지하철 망이 좋지 않으나 갑자기 동탄으로 직행하는 노선 + 수인분당선이 생기게 된 것이다....

2-1. 우선 민속촌 역이다. 민속촌은 관광지로 사용될 수 있어 무조건 들어올 것이다. 민속촌 입구 삼거리나 보라지구 입구 삼거리로 예상된다. 민속촌 입구 삼거리에는 약간의 공터가 있어 이곳에 들어올 수 있을것 같다.

2-2. 여기서 부터 예측하기 어려운데 첫 번째 후보는 기흥 호수공원을 끼고 있는 한보라 마을과 고매동이다.

고매동은 이렇다할 개발이 없어 이곳에 역이 들어온다면 크게 혜택을 받을 곳이다. 또한 경부고속도로를 끼고 있다. 

또 한곳은 이 근처에 가장 큰 단지를 형성하고 있는 공세동 대주피오레 아파트 앞이다.

대주 피오레 아파트에는 이미 커다랗게 지하철이 들어온다고 현수막이 크게 걸려있다.

대주 피오레 아파트는 단지가 매우 크고 깔끔했다.

3. 용인 시청은 처인구에 위치해 있다. 각 시는 시청을 중심으로 발전할 수 밖에 없다.

하지만 현재의 용인 시청 주변은 번화가가 아닌 그저 아파트 몇채 뿐인 동네일 뿐이었다.

처인구는 크다. 하지만 우선적으로 개발 될 지역은 아무래도 용인.에버라인일 것이다. 에버라인을 따라가면 에버라인 도로를 중심으로 좌우로 아파트 단지만 있는것을 볼 수 있었다.

=> 기흥 ~ 오산 수인분당선은 용인과 오산의 큰 호재이다. 위치 확정을 유심히 지켜보자, 용인시청 주변으로 잘 확인 해 보자.

문제

https://www.acmicpc.net/problem/2636

주안점

BFS로 보통은 치즈를 순회할 생각을 하지만 치즈가 없는 구간을 순회하며 체크 후 치즈 삭제

구조

BFS로 체크해가면서 순회하고 삭제하고 순회하고 삭제하고

코드

#include<bits/stdc++.h>
using namespace std;
vector<pair<int,int>> v;
int visited[104][104], a[104][104];
int row,col,x,y,cnt,leave;

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

int main() {
    cin>>row>>col;
    for(int i=0; i<row; i++){
        for(int j=0; j<col; j++){
            cin>>a[i][j];
        }
    }
    queue<pair<int,int>> q;

    while(true){
        memset(visited,0,sizeof(visited));
        v.clear();
        visited[0][0] = 1;
        q.push({0,0});
        while(q.size()){
            tie(y,x) = q.front(); q.pop();
            for(int k=0; k<4; k++){
                int ny = y+dy[k];
                int nx = x+dx[k];
                if(ny>=row || nx>=col || ny<0 || nx<0) continue;
                if(visited[ny][nx]) continue;
                if(a[ny][nx] == 1) {
                    visited[ny][nx] = 1;
                    v.push_back({ny,nx});
                    continue;
                }
                visited[ny][nx] = 1;
                q.push({ny,nx});
            }
        }
        if(v.size() == 0) break;
        leave = v.size();
        for(pair<int,int> b : v)
            a[b.first][b.second] = 0;
        cnt++;
    }
    cout<<cnt<<"\n";
    cout<<leave<<"\n";
}

문제

https://www.acmicpc.net/problem/1931

주안점

해당 문제는 완전탐색이나, 동적 프로그래밍을 사용하는 방법도 있을것이다. 

하지만 그리디로도 풀이가 가능하다.

구조

회의실 사용 시작 시각과 종료 시각을 pair로 받아 정렬 후에 그리디 알고리즘으로 순차적으로 입실 가능할 때마다 입실한다.

코드

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

vector<pair<int,int>> v;
int n,t,tt,timee,ret;

int main() {
    cin>>n;
    for(int i=0; i<n; i++){
        cin>>t>>tt;
        v.push_back({tt,t});
    }
    sort(v.begin(), v.end());

    for(pair<int,int> vv : v){
        if(vv.second>=timee){
            timee = vv.first;
            ret++;
        }
    }
    cout<<ret<<"\n";
}