풀이

문제에서 주어진 순서대로 진행하면 되는 시뮬레이션 문제이다.

코드

import java.util.*;
import java.io.*;

public class Main {
    static int[] dr = {0, -1, 0, 1};
    static int[] dc = {-1, 0, 1, 0};
    static int[][] drc = {{-1, -1}, {-1, 1}, {1, 1}, {1, -1}};
    static int[][] board;
    static int[][] herbicide;
    static int n, m, kYear, c;
    static int[] maxLoc;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        kYear = Integer.parseInt(st.nextToken());
        c = Integer.parseInt(st.nextToken());
        board = new int[n][n];
        herbicide = new int[n][n];

        for(int i = 0; i < n; i++){
            String[] str = br.readLine().split(" ");
            for(int j = 0; j < n; j++){
                board[i][j] = Integer.parseInt(str[j]);
            }
        }

        int year = 0;
        int answer = 0;
        while(year < m){
            // 나무의 성장
            growTree();

            // 나무를 번식
            board = breadTree();

            // 제초제 위치 선정
            maxLoc = new int[3];
            setLocation();
            // 남은 제초제 기간 감소
            decreaseHerbicide();

            // 제초제 살포
            startHerbicide();

            // 결과
            answer += maxLoc[2];
            year++;
        }

        System.out.println(answer);
    }

    public static void growTree(){
        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++){
                if(board[i][j] <= 0)
                    continue;
                int nearTree = 0;
                for(int k = 0; k < 4; k++){
                    int nr = i + dr[k];
                    int nc = j + dc[k];

                    if(nr < 0 || nr >= n || nc < 0 || nc >= n || board[nr][nc] <= 0 || herbicide[nr][nc] > 0)
                        continue;

                    nearTree++;
                }

                board[i][j] += nearTree;
            }
        }
    }

    public static int[][] breadTree(){
        int[][] nboard = new int[n][n];
        Queue<int[]> q = new LinkedList<>();

        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++){
                if(board[i][j] == -1){
                    nboard[i][j] = -1;
                }
                if(board[i][j] <= 0) continue;
                nboard[i][j] = board[i][j];
                for(int k = 0; k < 4; k++){
                    int nr = i + dr[k];
                    int nc = j + dc[k];

                    if(nr < 0 || nr >= n || nc < 0 || nc >= n || board[nr][nc] > 0 || board[nr][nc] == -1 || herbicide[nr][nc] > 0)
                        continue;

                    q.offer(new int[]{nr, nc});
                }

                int cnt = q.size();

                while(!q.isEmpty()){
                    int[] rc = q.poll();

                    nboard[rc[0]][rc[1]] += board[i][j] / cnt;
                }
            }
        }

        return nboard;
    }

    public static void setLocation(){
        for(int i = 0; i < n; i++){
                for(int j = 0; j < n; j++){
                    if(board[i][j] <= 0) continue;
                    int treeCnt = board[i][j];
                    for(int k = 0; k < 4; k++){
                        treeCnt += countTree(i, j, k);
                    }
                    if(treeCnt > maxLoc[2]){
                        maxLoc[0] = i;
                        maxLoc[1] = j;
                        maxLoc[2] = treeCnt;
                    }
                }
            }
    }

    public static int countTree(int row, int col, int dir){
        int treeCnt = 0;
        int nr = row;
        int nc = col;
        for(int i = 0; i < kYear; i++){
            nr += drc[dir][0];
            nc += drc[dir][1];
            if(nr < 0 || nr >= n || nc < 0 || nc >= n || board[nr][nc] <= 0)
                return treeCnt;     

            treeCnt += board[nr][nc];
        }

        return treeCnt;
    }

    public static void startHerbicide(){
        int row = maxLoc[0];
        int col = maxLoc[1];

        board[row][col] = 0;
        herbicide[row][col] = c;

        for(int i = 0; i < 4; i++){
             spreadHerbicide(row, col, i);
        }
    }

    public static void spreadHerbicide(int row, int col, int dir){
        int nr = row; 
        int nc = col;

        for(int i = 0; i < kYear; i++){
            nr += drc[dir][0];
            nc += drc[dir][1];

            if(nr < 0 || nr >= n || nc < 0 || nc >= n || board[nr][nc] == -1)
                return;

            herbicide[nr][nc] = c;

            if(board[nr][nc] == 0)
                return;

            board[nr][nc] = 0;

        }
    }

    public static void decreaseHerbicide(){
        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++){
                if(herbicide[i][j] > 0){
                    herbicide[i][j]--;
                }
            }
        }
    }
}

코드

import java.io.*;
import java.util.*;

public class Main {
    /*
        dfs를 사용하여 A, B를 번갈아가며 이동시킨다.
        A가 먼저 이동할 때 B의 차례에서 이동가능한 칸이 없으면서 동일한 위치에 갈 수 있는 경우를 찾는다.
    */
    public static int[] dr = {0, -1, 0, 1};
    public static int[] dc = {-1, 0, 1, 0};
    public static boolean[][] isMove;
    public static int answer;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int K = Integer.parseInt(br.readLine());
        StringTokenizer st;
        isMove = new boolean[5][5];
        int moveCnt = 23;
        for(int i = 0; i < K; i++){
            st = new StringTokenizer(br.readLine());
            int r = Integer.parseInt(st.nextToken()) - 1;
            int c = Integer.parseInt(st.nextToken()) - 1;

            isMove[r][c] = true;
            moveCnt--;
        }

        answer = 0;
        isMove[0][0] = true;
        isMove[4][4] = true;
        dfs(0, 0, 4, 4, moveCnt, true);
        System.out.println(answer);


    }

    public static void dfs(int ar, int ac, int br, int bc, int moveCnt, boolean flag){

        if(flag){
            for(int i = 0; i < 4; i++){
                int nr = ar + dr[i];
                int nc = ac + dc[i];

                if(nr < 0 || nr >= 5 || nc < 0 || nc >= 5 || isMove[nr][nc]) continue;
                isMove[nr][nc] = true;
                dfs(nr, nc, br, bc, moveCnt - 1, !flag);
                isMove[nr][nc] = false;
            }
        }
        else{
            for(int i = 0; i < 4; i++){
                int nr = br + dr[i];
                int nc = bc + dc[i];

                if(nr < 0 || nr >= 5 || nc < 0 || nc >= 5) continue;
                if(moveCnt == 0){
                    if(ar == nr && ac == nc){
                        answer++;
                        return;
                    }
                    else continue;
                }
                if(isMove[nr][nc]) continue;
                isMove[nr][nc] = true;
                dfs(ar, ac, nr, nc, moveCnt - 1, !flag);
                isMove[nr][nc] = false;
            }
        }

    }
}

풀이

N번째 문자를 찾을 수 있는 depth를 구한 후 재귀를 통해 정답을 찾았다. 이전 depth의 부분에 N번째 위치가 포함된다면, 재귀를 통하여 depth를 낮추면서 t가 0이 될 때 정답을 구할 수 있다. 그 외에는 현재 depth인 t에 따라 정답을 구할 수 있다.

코드

import java.io.*;
import java.util.*;

public class Main {
    static List<Integer> list;
    static char answer;
    static boolean flag;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());

        list = new ArrayList<>();
        String moo = "moo";
        list.add(3);
        // 최대 depth를 구함
        int t = 0;
        for(int i = 1; i <= N; i++){
            int n = list.get(i - 1) * 2 + i + 3;
            list.add(n);
            if(n >= N){
                t = i;
                break;
            }
        }

        flag = false;
        moo(t, N);
        System.out.println(answer);

    }

    public static void moo(int t, int N){
        if(flag) return;

        if(t == 0){
            answer = getChar("moo", N - 1);
            flag = true;
            return;
        }

        int mid = t + 3;
        int prevLen = list.get(t - 1);

        if(prevLen >= N){
            moo(t - 1, N);
        }
        else if(prevLen + mid >= N){
             String str = "moo";
            for(int i = 0; i < t; i++){
                str += "o";
            }
            answer = getChar(str, N - prevLen - 1);
            flag = true;
        }
        else{
            moo(t - 1, N - prevLen - mid);
        }
    }

    public static char getChar(String str, int n){
        return str.charAt(n);
    }
}

1번째 위치는 1, 2번째 위치는 2... 와 같이 각 위치에 가중치를 부여하여 해당 숫자의 총 가중치 합을 구한다. 이 때, 항상 변형된 데이터는 원래의 위치보다 앞으로 가도록 변형되어 있으므로 가장 가중치가 낮은 값은 위치가 변경되었을 가능성이 크다. 따라서 해당 숫자의 가중치 합에서 최소 가중치를 빼서 최종 가중치를 구한다. 이 가중치 순서대로 숫자를 오름차순 정렬하면 정답이 나온다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;


public class Main {
    static class Node implements Comparable<Node>{
        int n, w;
        public Node(int n, int w){
            this.n = n;
            this.w = w;
        }

        @Override
        public int compareTo(Node n){
            return this.w - n.w;
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        List<Integer>[] data = new ArrayList[3];
        for(int i = 0; i < 3; i++){
            data[i] = new ArrayList<>();
            st = new StringTokenizer(br.readLine());
            for(int j = 0; j < N; j++){
                data[i].add(Integer.parseInt(st.nextToken()));
            }
        }

        PriorityQueue<Node> pq = new PriorityQueue<>();
        for(int i = 0; i < N; i++){
            int aw = i + 1;
            int bw = data[1].indexOf(data[0].get(i)) + 1;
            int cw = data[2].indexOf(data[0].get(i)) + 1;
            int sw = aw + bw + cw - Math.min(aw, Math.min(bw, cw));

            pq.add(new Node(data[0].get(i), sw));
        }

        StringBuilder sb = new StringBuilder();
        while(!pq.isEmpty()){
            sb.append(pq.poll().n).append(" ");
        }

        System.out.println(sb);


    }
}

import java.util.*;
import java.io.*;

/*
    입력으로 받은 값을 set에 저장해 놓고, 하니씩 제외시켜보면서 연속하여 동일한 숫자가 나오는 최대 값을 찾는다.
*/
public class Main {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        StringTokenizer st;
        List<Integer> list = new ArrayList<>();
        Set<Integer> set = new HashSet<>();
        for(int i = 0; i < N; i++){
            st = new StringTokenizer(br.readLine());
            int n =Integer.parseInt(st.nextToken());
            list.add(n);
            set.add(n);
        }
        int maxCnt = 0;
        for(Integer K : set){
            int prevNum = -1;
            int cnt = 0;
            for(int i = 0; i < list.size(); i++){
                int currNum = list.get(i);
                if(currNum == K) 
                    continue;
                else if(prevNum == currNum) 
                    cnt++;
                else 
                    cnt = 0;
                prevNum = currNum;
                maxCnt = Math.max(maxCnt, cnt);
            }
        }
        System.out.println(maxCnt + 1);
    }
}

import java.util.*;
import java.io.*;

/*
    숫자들을 더했을 때 각각의 자릿수가 10을 넘지 않으면서 최대한 더할 수 있는 숫자의 개수를 구해야 한다.
    이차원 리스트를 사용하여 숫자의 자리수를 분리하여 사용하였고, 백트래킹을 통하여 모든 경우의 수를 고려하면서 찾는다.
    Ex) 522가 입력으로 주어졌을 때
    list.get(0)은 522를 나타냄
    list.get(0).get(0)는 522의 첫번째 자리수인 2를 나타냄
    list.get(0).get(2)는 522의 세번째 자리수인 5를 나타냄
*/
public class Main {
    static List<List<Integer>> list;
    static int answer;
    public static void main(String[] args) throws IOException{

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());

        // 초기화
        list = new ArrayList<>();
        for(int i = 0; i < n; i++){
            list.add(new ArrayList<>());
        }

        // 하나의 숫자를 받아서 자리수를 분리하여 리스트에 담는다.
        for(int i = 0; i < n; i++){
            int num = Integer.parseInt(br.readLine());
            while(num > 0){
                int a = num % 10;
                num /= 10;
                list.get(i).add(a);
            }
        }

        int[] sum = new int[9];
        answer = 0;
        backTracking(0, 0, sum);
        System.out.println(answer);
    }

    public static void backTracking(int cnt, int idx, int[] sum){
        // 현재 더한 숫자의 개수를 최대로 계속 갱신한다.
        if(cnt > answer){
            answer = cnt;
        }

        for(int i = idx; i < list.size(); i++){
            List<Integer> l1 = list.get(i);
            // 더하는 것이 가능하다면 각 자리수에 현재 숫자를 넣는다.
            if(isPossible(l1, sum)){
                int[] nSum = sum.clone();
                for(int j = 0; j < l1.size(); j++){
                    nSum[j] += l1.get(j);
                }
                backTracking(cnt + 1, i + 1, nSum);
            }
        }
    }

    // 더하려고 하는 숫자의 자리수를 나눈 list l1과 현재 각 자리의 숫자를 가지고 있는 sum을 가지고 각 자리수 계산
    public static boolean isPossible(List<Integer> l1, int[] sum){
        for(int i = 0; i < l1.size(); i++){
            if(sum[i] + l1.get(i) >= 10)
                return false;
        }

        return true;
    }
}

import java.util.*;
import java.io.*;

public class Main {
    /*
        A의 연속 부분 수열 중 B의 수열과 패턴이 일치하는 연속 부분 수열을 찾아야 한다.
        A의 연속 부분 수열을 고른 후 정렬한 뒤 B와 비교했을 때 각 인덱스가 동일하게 차이가 난다면 아름다운 수에 해당한다.
    */
    static List<Integer> A;
    static List<Integer> B;
    public static void main(String[] args) throws IOException{
        A = new ArrayList<>();
        B = new ArrayList<>();

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        // 입력값 받기
        int N = Integer.parseInt(br.readLine());
        StringTokenizer st;
        for(int i = 0; i < N; i++){
            st = new StringTokenizer(br.readLine());
            int num = Integer.parseInt(st.nextToken());
            A.add(num);
        }

        int M = Integer.parseInt(br.readLine());
        for(int i = 0; i < M; i++){
            st = new StringTokenizer(br.readLine());
            int num = Integer.parseInt(st.nextToken());
            B.add(num);
        }

        // 부분 수열과 비교할 수 있도록 미리 B를 정렬
        Collections.sort(B);

        // M개의 수를 골라서 부분수열을 만든 뒤 정렬하여 B와 비교한다.
        int cnt = 0;
        StringBuilder sb = new StringBuilder();
        for(int i = 0; i + M <= N && i < N; i++){
            List<Integer> part = new ArrayList<>();
            for(int j = 0; j < M; j++){
                part.add(A.get(i + j));
            }
            Collections.sort(part);

            // 연속 부분 수열이 아름다운 수열인지 판별
            if(isBeautiful(part)){
                cnt++;
                sb.append(i + 1).append("\n");
            }
        }
        System.out.println(cnt);
        System.out.println(sb);
    }

    // 연속 부분 수열과 B 수열의 인덱스별 차이가 같다면 true, 다르면 false
    public static boolean isBeautiful(List<Integer> part){
        int diff = part.get(0) - B.get(0);
        for(int i = 1; i < part.size(); i++){
            if(part.get(i) - B.get(i) != diff){
                return false;
            }
        }
        return true;
    }
}

ICMP(Internet Control Message Protocol)은 호스트와 라우터가 서로 간에 네트워크 계층 정보를 주고받기 위해 사용된다.

라우팅 알고리즘

Link-State Routing Algorithm

목적지까지의 최단거리를 계산하기 전에 모든 라우터들은 네트워크 상황을 알고 있다. 따라서 사전에 서로 간의 정보를 전체 네트워크에 브로드캐스트 한다. Link-State 알고리즘은 발명자의 이름을 따서 다익스트라 알고리즘 이라고 부른다.

Distance-Vector Routing Algorithm

Link-State 알고리즘이 네트워크의 전체 정보를 이용하는 알고리즘인 반면에, DV 알고리즘은 반복적이고 비동기적이며 분산적이다. 각 노드는 하나 이상의 직접 연결된 이웃으로부터 정보를 받고, 계산을 수행하며, 계산된 결과를 다시 그 이웃들에게 배포한다는 점에서 분산적이다. 또한 이웃끼리 더 이상 정보를 교환하지 않을 때 까지 프로세스가 지속된다는 점에서 반복적이다.

Dx(y) = min{c(x,v) + Dv(y)}

• 각 이웃 노드 v중에서 x에 집적 접속된 이웃 노드까지의 비용 c(x,v)
• 노드 x의 거리 벡터, 즉 x로부터 N에 있는 모든 목적지 y로의 비용 예측값을 포함하는 벡터 Dx = [Dx(y): y in N]
• 이웃 노드들의 거리 벡터들, 즉 v가 x의 이웃이라고 하면 Dv = [Dv(y): y in N]

Link-State 와 Distance-Vector의 비교

DV와 LS 알고리즘은 경로를 계산할 때 서로 대비되는 방법을 취한다. DV 알고리즘에서 각 노드는 오직 직접 연결된 이웃과만 메시지를 교환하지만, 자신으로부터 네트워크 내 모든 노드로의 최소 비용 추정값을 이웃들에게 제공한다. LS 알고리즘은 전체 정보를 필요로 한다. 각 노드는 다른 모든 노드와 브로트캐스트를 통해 통신하지만, 오직 자신에 직접 연결된 링크의 비용만 알린다.

인터넷에서 AS 내부 라우팅

AS(autonomous system)은 동일한 관리 제어하에 있는 라우터의 그룹으로 구성된다. AS는 고유한 AS 번호를 가지고 있으며, IP 주소처럼 ICANN의 지역 등록 기관에 의해 할당된다. 같은 AS 안에 있는 라우터들은 동일한 라우팅 알고리즘을 사용하고 상대방에 대한 정보를 갖고 있다. AS 내부에서 동작하는 라우팅 알고리즘을 AS 내부 라우팅 프로토콜(intra-autonomous system routing protocol)이라고 한다.

ISP간의 라우팅 : BGP

인터넷의 모든 AS 간의 라우팅은 BGP(Border Gateway Protocol)라고 불리는 AS 간 라우팅 프로토콜을 사용한다.

BGP의 역할

AS 내에 있는 목적지에 대해서는 라우터의 포워딩 테이블 엔트리들이 해당 AS의 AS 내부 라우팅 프로토콜에 의해 결정된다. 하지만 목적지가 AS 외부에 있다면 BGP가 필요하다. BGP에서는 패킷이 특정한 목적지 주소를 향해서가 아니라 CIDR 형식으로 표현된, 주소의 앞쪽 prefix를 향해 전달된다.

1. 이웃 AS를 통해 도달가능한 서브넷 prefix 정보를 얻는다. BGP는 각 서브넷이 자신의 존재를 인터넷 전체에 알릴 수 있도록 한다.
2. 서브넷 주소 prefix로의 가장 좋은 경로를 결정한다. 라우터는 특정한 주소 prefix를 향한 2개 이상의 경로를 알 수도 있다. 가장 좋은 경로를 결정하기 위해 라우터는 BGP의 경로 결정 프로시저를 수행한다.

AS 내부에서는 최단 루트로 이동하지만, AS를 넘나드는 상황에서는 최단루트로 가지 않는다. AS를 이동하는 것은 비용이 드는 과정이므로, 적당히 돈이 적게 드는 방향으로 이동한다.

Reference

KOCW - 컴퓨터 네트워크 컴퓨터 네트워킹 하향식 접근

풀이

이동방향이 아래와 오른쪽밖에 없으므로 현재 위치에서 올 수 있는 방향은 위와 왼쪽 방향에서 오는 것이다. 따라서 현재 위치에 도달하는 방법의 수는 (왼쪽 칸까지 오는 방법의 수) + (위쪽 칸까지 오는 방법의 수) 가 된다.

단, 가장 위쪽 칸의 경우는 왼쪽에서 오는 경로만 고려하고, 가장 왼쪽 칸의 경우에는 위쪽에서 오는 경로만 고려하도록 한다.

코드

import java.util.*;

class Solution {
    public int solution(int m, int n, int[][] puddles) {
        int[][] dp = new int[n][m];
        boolean[][] isPuddle = new boolean[n][m];

        for(int[] p : puddles){
            isPuddle[p[1] - 1][p[0] - 1] = true;
        }
        dp[0][0] = 1;

        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
                if(isPuddle[i][j]){
                    dp[i][j] = 0;
                    continue;
                }
                if(i != 0){
                    dp[i][j] += dp[i - 1][j] % 1000000007;
                }
                if(j != 0){
                    dp[i][j] += dp[i][j - 1] % 1000000007;
                }

            }
        }


        return dp[n - 1][m - 1] % 1000000007;
    }
}

풀이

꼭대기에서 바닥으로 내려갈 때 양쪽 아래 대각선으로만 이동 가능하고, 이동 시 값을 더하여 최종적으로 바닥의 최대 값을 찾는 문제이다. dp를 사용하여 현재 위치에서 이전의 값에서 가져올 수 있는 가장 큰 값을 가져오는 것을 반복하면서 바닥으로 내려가면 결과적으로 최대값을 찾을 수 있다고 판단하였다.

현재 층을 i, 위치를 j라고 할 때, 이전 층 i - 1의 값들 중에서 j - 1 번째의 수와 j번째의 수 중 최대 값을 가져오면 된다. 이때 현재 층의 0번째와 마지막 수 는 더 큰 값을 비교할 필요 없이 이전 층의 첫번째와 마지막을 가져오면 된다.

코드

class Solution {
    public int solution(int[][] triangle) {
        int answer = 0;
        int n = triangle.length;
        int[][] dp = new int[n][];

        for(int i = 0; i < n; i++){
            dp[i] = new int[i + 1];
        }


        dp[0][0] = triangle[0][0];

        for(int i = 1; i < n; i++){
            for(int j = 0; j < triangle[i].length; j++){

                if(j == 0){
                    dp[i][j] = dp[i - 1][j];
                }
                else if(j == triangle[i].length - 1){
                    dp[i][j] = dp[i - 1][j - 1];
                }
                else{
                    dp[i][j] = Math.max(dp[i - 1][j - 1], dp[i - 1][j]);
                }
                dp[i][j] += triangle[i][j];
            }
        }

        for(int i = 0; i < dp[n - 1].length; i++){
            answer = Math.max(answer, dp[n - 1][i]);
        }

        return answer;
    }
}

DP를 적용하려는 문제는 다음과 같은 조건을 가지고 있어야 한다.

• 중복 부분문제 구조(Overlapping subproblems)
• 최적 부분문제 구조(Optimal substructure)

중복 부분문제 구조

• 큰 문제를 이루는 작은 문제들을 먼저 해결하고 작은 문제들의 최적 해(Optimal Solution)를 이용하여 순환적으로 큰 문제를 해결한다. 이 때 순환적인 관계를 명시적으로 표현하기 위해서 DP에서는 수학적 도구인 점화식을 사용한다.
• DP는 문제의 순환적인 성질 때문에 이전에 계산되어졌던 작은 문제의 해가 다른 어딘가에서 필요하게 되는데 이를 위해 DP에서는 이미 해결된 작은 문제들의 해들을 배열을 만들어 저장해놓는다.
• 저장된 해들이 다시 필요할 때 마다 해를 얻기 위해 다시 문제를 재계산하지 않고 참조를 통하여 중복된 계산을 피하게 된다.

최적 부분문제 구조

• DP가 최적화에 대한 어느 문제에나 적용될 수 있는 것은 아니다. 주어진 문제가 최적의 원칙을 만족해야 DP를 효율적으로 적용 가능하다.
• 최적의 원칙은 어떤 문제에 대한 해가 최적일 때 그 해를 구성하는 작은 문제들의 해 역시 최적이어야 한다는 것이다. DP의 방법자체가 큰 문제의 최적 해를 작은 문제의 최적해 들을 이용하여 구하기 때문에 만약 큰 문제의 최적해가 다른 문제들의 최적화의 해들로 구성되지 않는다면 이 문제는 DP를 적용할 수 없다.

분할 정복과 비교하면?

분할 정복과 DP는 둘 다 부분 문제로 분할하여 해결 방법을 찾는다. 하지만 큰 차이점이 있는데, 분할 정복은 부분 문제들간의 연관이 없고, DP는 부분 문제들간의 연관이 있다는 점이다.

홈 네트워크에서 IP 장치들은 각각의 주소를 가진다. 하지만 WAN 환경에서는 이 IP 주소를 사용할 수 없다. 이 네트워크 주소들은 그 네트워크의 내부에 있는 장비들에게만 의미가 있다. 이 주소 블록을 사용하는 네트워크는 글로벌 환경에서 엄청 많기 때문이다. 이는 NAT 라우터를 통하여 글로벌에서 하나의 IP 주소를 갖는 하나의 장비로 동작하도록 한다.

NAT 라우터에서 NAT 변환 테이블을 사용하여, 그 테이블에 IP 주소와 포트 번호를 포함하도록 함으로써 WAN에서 같은 목적지의 IP 주소를 갖는 데이터그램이 도착하더라도 내부 호스트를 알 수 있게 된다.

하지만 NAT 라우터를 사용하게 되면 서버의 역할은 하지 못한다. 외부에서 패킷이 도착할 때 어떤 내부 호스트가 받을 지는 IP 주소를 통하여 결정해야 하지만 NAT 라우터는 포트 번호를 통하여 결정한다. 특정 프로세스를 찾을 때 사용할 때 포트 번호를 사용해야 되지만, NAT는 그렇게 하지 않음으로써 서버로의 운영은 불가능 하게 된다.

동적 호스트 구성 프로토콜(DHCP)

호스트에 IP 주소를 할당하는 것은 수동으로 구성 가능하지만 일반적으로 DHCP(Dynamic Host Configuration Protocol) 를 더 많이 사용한다. DHCP는 호스트가 IP 주소를 자동으로 얻을 수 있게 하며, 네트워크 관리자는 해당 호스트가 네트워크에 접속하고자 할 때마다 동일한 IP 주소를 받도록 하거나, 다른 임시 IP 주소를 할당하도록 DHCP를 설정한다.

DHCP

• plug-and-play protocol or zero-configuration protocol
• client-server protocol

새로운 호스트가 도착할 경우의 DHCP 시나리오

1. DHCP discover 새롭게 도착한 호스트는 상호작용할 DHCP를 발견한다. 이는 DHCP discover message를 사용하여 수행되며, 클라이언트는 포트 67번으로 UDP 패킷을 보낸다. UDP 패킷은 IP 데이터그램으로 캡슐화된다. 호스트는 자신이 접속할 네트워크의 IP 주소를 알지 못하고, 해당 네트워크의 DHCP 서버 주소도 모른다. 따라서 DHCP 클라이언트는 DHCP 발견 메시지를 포함하는 IP 데이터그램을 생성하여, 이 데이터그램을 서브넷에 연결된 모든 노드로 브로드캐스트 한다.

   • DHCP 서버 포트번호 : 67
   • DHCP 클라이언트 포트번호 : 68
   • 출발지 IP : 0.0.0.0
   • 목적지 IP : 255.255.255.255

2. DHCP offer DHCP discover message를 받은 DHCP 서버는 DHCP offer message를 클라이언트로 응답한다. 이때에도 다시 IP 브로드캐스트 주소 255.255.255.255를 사용하여 서브넷의 모든 노드로 이 메시지를 브로드캐스트 한다. 서브넷에는 여러 DHCP 서버가 존재하기 때문에 가장 최적의 위치의 DHCP 서버를 선택하기 위하여 모든 노드로 브로드캐스트 한다.

   서버 제공 메시지는 다음의 내용을 포함한다.

   • transaction ID
   • 클라이언트에 제공된 IP 주소
   • 네트워크 마스크
   • IP 주소 임대 기간

3. DHCP request 클라이언트는 DHCP offer message를 받아 선택할 것이고, 선택된 서버에게 DHCP request message로 응답한다.

4. DHCP ACK 서버는 DHCP request messsage에 대해 요청된 파라미터를 확인하는 DHCP ACK message로 응답한다.

Reference

KOCW - 컴퓨터 네트워크 컴퓨터 네트워킹 하향식 접근

Forwarding and Routing

네트워크 계층의 근본적인 역할은 송신 호스트에서 수신 호스트로 패킷을 전달하는 것이다. 이를 위한 네트워크 계층의 중요한 기능 두가지는 다음과 같다.

• forwarding

  • 패킷이 라우터에 도달했을 때 라우터는 그 패킷을 목적지로 향하는 다음 라우터로 전달하는 것
  • 하드웨어에서 실행

• routing

  • 송신자가 수신자에게 패킷을 전송할 때 네트워크 계층은 패킷 경로를 결정해야 한다. 이러한 경로 계산 알고리즘을 routing algorithm(forwarding table을 만드는 방법)이라 한다.
  • 출발지에서 목적지로 가는 경로를 결정하는 것
  • 소프트웨어에서 실행

네트워크 라우터에서 필수 불가결한 요소는 forwarding table이다. 라우터는 도착하는 패킷 헤더의 필드값을 조사하여 패킷을 전달하고, 이 값을 라우터의 forwarding table의 내부 색인으로 사용한다.

Internet Protocol(IP)

IP datagram foramt

• TTL(time-to-live)

  • 네트워크에서 데이터그램이 무한히 순환하지 않도록 한다(routing loop). 이 필드값은 라우터가 데이터그램을 처리할 때마다 감소한다. TTL의 필드가 0이 되면 라우터가 이 데이터그램을 폐기한다.

• upper layer

  • IP 데이터그램이 최종 목적지에 도착했을 때만 사용되며, 이 필드값은 IP 데이터그램에서 데이터 부분이 전달될 목적지의 트랜스포트 계층의 특정 프로토콜을 명시한다.

• source and destination IP address

  • 출발지가 데이터그램을 생성할 때, 자신의 IP 주소를 출발지 IP 주소 필드에 삽입하고 목적지 IP 주소를 목적지 IP 주소 필드에 삽입한다.

IPv4

• unique 32-bit number

• identifies an interface(on a host, on a router, ..)

• Represented in dotted-quad notaion

  • Ex) 193.32.216.9

Hierarchical Addressing: IP prefixes

• Network and host portions(left and right)
• 12.34.158.0/24 -> 24-bit prefix with 2^8 addresses
• Ex) 12.34.158.5 -> 00001100  00100010  10011110    00000101                          <-------Network(24bits)--------> <-Host(8bits)->

/24는 subnet mask이며 32비트 주소의 왼쪽 24비트가 서브넷 주소라는 것을 가리킨다.

Classful Addressing

• Class A(0*): 첫 8비트가 네트워크 주소 -> 2^7개 존재, 호스트 -> 2^24개
• Class B(10*): 첫 16비트가 네트워크 주소 -> 2^16
• Class C(110*): 첫 24비트가 네트워크 주소 -> 2^24

Classless InterDomain Routing(CIDR)

32비트 IP주소를 두 부분으로 나누고, 이것은 다시 점으로 된 십진수 형태의 a.b.c.d/x를 가진다. x는 주소 첫 부분의 비트 수이다.

Subnets

라우터를 거치지 않고 데이터를 보낼 수 있는 IP의 집합(하나의 라우터 인터페이스로 연결), Subnet 파트에 해당하는 주소가 같다.

Reference

KOCW - 컴퓨터 네트워크 컴퓨터 네트워킹 하향식 접근

코드

import java.util.*;

class Solution {
    public int[] solution(int[][] edges, int[] target) { 
        // tree 초기화
        int n = edges.length + 1;
        List<Integer>[] tree = new ArrayList[n];
        for(int i = 0; i < n; i++){
            tree[i] = new ArrayList<>();
        }

        // tree 값 입력
        for(int i = 0; i < edges.length; i++){
            int p = edges[i][0];
            int c = edges[i][1];
            // 넣어줄 때 배열 인덱스에 맞춰서 저장
            tree[p - 1].add(c - 1);
        }

        int TC = 0;
        // tree 오름차순 정렬
        for(int i = 0; i < n; i++){
            Collections.sort(tree[i]);
            // 해당 노드가 리프노드이면서 타겟이 있다면 숫자를 떨어뜨려야 하는 노드
            if(tree[i].isEmpty() && target[i] > 0){
                TC++;
            }
        }

        // 현재 노드가 몇 번 지나갔는지 체크
        int[] pass = new int[n];
        // 현재 노드가 보유하고 있는 숫자 개수
        int[] count = new int[n];
        // 방문 노드인지 저장
        boolean[] visited = new boolean[n];
        // 리프 노드 저장
        List<Integer> leafNode = new ArrayList<>();

        while(TC > 0){
            // 루트노드
            int node = 0;

            // 숫자떨어뜨리면서 리프노드까지 내려가기
            while(tree[node].size() > 0){
                /*
                    노드의 순서를 정하는 방법
                    노드의 작은 순서대로 이동 -> 정렬해놨으니 0번부터 시작하면된다.
                    방문횟수 % 자식노드의 수 -> 0 ~ 자식노드의 횟수 - 1 까지 차례대로 나옴
                */
                node = tree[node].get(pass[node]++ % tree[node].size());
            }

            // 리프 노드에 떨어진 숫자 증가
            count[node]++;
            leafNode.add(node);

            // 리프 노드의 숫자가 모두 1이라고 할 때, target보다 크다면 조건 만족 X
            if(count[node] > target[node]){
                return new int[]{-1};
            }

            // 리프노드를 방문하지 않았고, 노드의 총 합이 target보다 크다면 해당 노드는 만족 O
            // 개수 * 3이 타겟보다 크다면 해당 리프노드는 target 값을 만족 O
            if(!visited[node] && count[node] * 3 >= target[node]){
                visited[node] = true;
                TC--;
            }
        }

        // 정답을 넣을 배열
        List<Integer> result = new ArrayList<>();

        // 리프노드를 하나씩 꺼내서 숫자 대입
        for(int i = 0; i < leafNode.size(); i++){
            int num = leafNode.get(i);
            count[num]--;

            for(int j = 1; j <= 3; j++){
                // 개수 * 1이 target - j 보다 작거나 같고, 개수 * 3이 target - j보다 클 경우 target값 만족 가능
                if(count[num] <= target[num] - j && count[num] * 3 >= target[num] - j){
                    target[num] -= j;
                    result.add(j);
                    break;
                }
            }
        }

        // List -> Array
        int[] answer = new int[result.size()];
        for(int i = 0; i < result.size(); i++){
            answer[i] = result.get(i);
        }

        return answer;
    }
}

congestion : 너무 높은 속도로 데이터를 데이터를 보내려고 시도해서 혼잡이 일어남 -> 패킷 유실(queue 꽉 참) -> 딜레이 발생(queuing delay)

Ex1) 2개의 송신자와 무한 버퍼를 갖는 하나의 라우터

패킷 유실 X, 재전송 X 호스트 A에서 호스트 B로 R/2만큼의 공간을 사용해서 데이터를 보낸다. 이때 R/2를 사용하기 전까지는 전송에 따른 처리량이 비례하여 증가하는데, 전송량이 R/2를 넘어가면 링크는 R/2를 초과하여 전송할 수 없다. 따라서 평균 지연은 점점 커지고 라우터의 큐잉된 패킷은 제한되지 않으므로 출발지와 목적지 사이의 평균 지연은 무제한이 된다. 즉, 패킷 도착률이 링크 용량에 근접함에 따라 큐잉 지연이 커진다.

Ex2) 2개의 송신자, 유한 버퍼를 가진 하나의 라우터

패킷 유실 O, 패킷 유실 시 재전송 O

1) buffer overflow로 인하여 패킷 유실시, 송신자는 재전송을 수행 2) timeout으로 인한 재전송, 실제로 유실 되지 않아도 congestion때문에 딜레이가 생기므로 timeout 발생 R/2의 데이터를 보낸다고 했을 때, 재전송이 있으므로 실제로 보내는 의미있는 데이터는 R/2보다 작다.

Ex3) 4개의 송신자와 유한 버퍼를 갖는 라우터, 그리고 멀티홉 경로

데이터가 라우터 A, B, C, D를 지나가는 경로로 수신된다고 할 때, 라우터 D에서 congestion때문에 패킷을 버려야 하는 상황이라면 버려지는 지점까지 패킷을 전송하는 데 사용된 상위 라우터에서의 전송 용량은 낭비된 것이다. congestion -> retransmission -> 의미있는 데이터 양 감소 -> 자원낭비

혼잡 제어에 대한 접근법

혼잡 상태를 파악하는 방식은 2가지가 있다.

• 종단 간 혼잡 제어

  • 네트워크에서 혼잡의 존재는 단지 관찰된 네트워크 동작(패킷 손실 및 지연)에 기초하여 종단 시스템이 추측
  • 종단 시스템은 TCP 세그먼트 손실(타임아웃 또는 삼중의 중복확인)을 네트워크 혼잡의 발생 표시로 생각하고, TCP는 그에 따라서 window 크기를 줄인다.

• 네트워크 지원 혼잡 제어

  • 라우터들은 네트워크 안에서 혼잡 상태와 관련하여 송신자나 수신자 또는 모두에게 직접적인 피드백을 제공한다. 이 피드백은 링크의 혼잡을 나타내는 하나의 비트처럼 간단하다.
  • 라우터는 자신이 출력 링크에 제공할 수 있는 전송률을 송신자에게 명확히 알릴 수 있게 해준다.

TCP 혼잡 제어

전통적인 TCP의 혼잡 제어

송신 측에서 동작하는 TCP 혼잡 제어 매커니즘은 추가적인 변수인 congestion window인 cwnd를 추적하고, congestion window는 TCP 송신자가 네트워크로 트래픽을 전송할 수 있는 속도에 제약을 가한다.

AIMD (Additive Increase Multicative Decrease)

송신 측이 transmission rate(window size)를 패킷 손실이 일어날 때까지 증가시키는 식의 접근법이다.

• additive increase : 송신 측의 window size를 손실을 감지할때까지 매 RTT 마다 1 MSS씩 증가시킨다.
• multiplicative decrease : 손실을 감지했다면 송신측의 window size를 절반으로 감소시킨다.

슬로 스타트

TCP 연결이 시작될 때, cwnd 값은 일반적으로 1MSS로 초기화되고, 전송 세그먼트가 첫 번째로 확인응답을 받을 때 마다 1MSS씩 증가시킨다. Ex) 1개의 세그먼트 -> 2개의 세그먼트 -> 4개의 세그먼트 그래서 TCP 전송률은 작은 값으로 시작하지만 슬로스타트 단계 동안에 지수적으로 증가하게 된다.

이러한 지수적 증가는 다음과 같은 상황에서 종료된다.

• 패킷 유실이 발생할 때(Timeout, 3duplicated Acks)
  • 초기 버전인 TCP Tahoe는 cwnd 값을 1로 설정하고 새로운 슬로 스타트를 시작한다.
  • 후기 버전인 TCP Reno는 Timeout인 경우에는 cwnd 값을 1로 설정하고 새로운 스타트를 시작하지만, 3duplicated Acks인 경우는 새로운 ssthresh 값에서 부터 시작한다.
  • Timeout의 경우는 모든 패킷이 전달되지 못할 만큼 네트워크의 상태가 좋지 않다는 것이며, 3duplicated Acks인 경우 일정 패킷만 유실된 경우이므로, Timeout보다는 네트워크 상태가 좋다.
• TCP 송신자는 두 번째 상태 변수인 ssthresh(slow start threshhold)의 값이 cwnd의 값과 동일하다면, 슬로 스타트는 종료되고 TCP는 RTT마다 하나의 MSS만큼 cwnd를 증가시킨다(혼잡 회피 모드). ssthresh의 값은 congestion이 마지막으로 검출된 시점의 cwnd 값의 반이다.

Reference

KOCW - 컴퓨터 네트워크 컴퓨터 네트워킹 하향식 접근

풀이

회전수와 회전했을 때 나오는 문자를 입력으로 받아, 최종적으로는 마지막 문자로부터 시계방향으로 출력하는 문제이다. 단 알 수 없는 문자는 "?"로 출력, 나올 수 없는 경우는 "!"를 출력한다. 나올 수 없는 경우는 다음과 같다.

1. 바퀴에서 같은 문자는 존재하지 않으므로, 같은 문자가 다른 위치에서 발견되었을 때
2. 바퀴의 같은 위치에서 다른 문자가 나올 때

이 경우는 "!"를 출력한다.

양 끝에서 삽입과 제거가 가능할 수 있는 LinkedList 자료구조를 사용하였다. 회전 수 만큼 앞쪽에서 빼서 뒤쪽으로 넣어주고, 가장 앞에 있는 문자를 비교하여 "?"일 경우에는 입력의 문자를 넣어주었다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

    public static void main(String[] args) throws IOException {
        // 입력 값 받기
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());

        LinkedList<String> list = new LinkedList<>();
        boolean[] checked = new boolean[26];

        for(int i = 0; i < N; i++){
            list.add("?");
        }
        String answer = "";
        for(int i = 0; i < K; i++){
            st = new StringTokenizer(br.readLine());
            int cnt = Integer.parseInt(st.nextToken());
            String alpha = st.nextToken();

            for(int j = 0; j < cnt; j++){
                list.addLast(list.removeFirst());
            }

            String str = list.removeFirst();
            int idx = 'Z' - alpha.charAt(0);
            // 같은 알파벳은 다시 나올 수 없다.
            if("?".equals(str) && checked[idx]){
                answer = "!";
                break;
            }
            // ?이거나, 같은 위치의 같은 알파벳이라면 가능하다
            else if("?".equals(str) || str.equals(alpha)){
                list.addFirst(alpha);
                checked[idx] = true;
            }
            // 같은 위치에서는 다른 알파벳이 나올 수 없다.
            else if(!str.equals(alpha)){
                answer = "!";
                break;
            }
        }

        /*
              시계방향으로 출력하는데 linkedlist의 가장 앞과 끝을 잇는다고 
            생각하면 현재 가리키는 문자는 idx가 0인 원소이다
            이때 한바퀴 돌린다면 다음 가리키는 원소는 linkedlist 사이즈의 - 1에 
            해당하는 원소이므로 가장 뒤에 있는 원소부터 차례대로 출력된다.
        */
        if("".equals(answer)){
            list.addLast(list.removeFirst());
            while(!list.isEmpty()){
                answer += list.removeLast();
            }
        }

        System.out.println(answer);
    }
}

풀이

큐의 크기 N이 주어질 때, N개 안에서 최소한의 시프트로 수를 뽑아내는 문제이다. 뽑아내려는 수의 위치를 알고 있을 때, 전체 큐의 사이즈에서

1) 중간위치보다 왼쪽에 있다면 왼쪽 시프트 2) 중간위치보다 오른쪽에 있다면 오른쪽 시프트 하여 뽑고자 하는 원소를 큐의 가장 앞에 위치시키는 것이 최소한의 횟수로 시프트를 시키는 것이라고 생각하였다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

    public static void main(String[] args) throws IOException {
        // 입력 값 받기
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        List<Integer> list = new ArrayList<>();

        for(int i = 1; i <= N; i++){
            list.add(i);
        }

        int answer = 0;

        st = new StringTokenizer(br.readLine());
        for(int i = 0; i < M; i++){
            int ele = Integer.parseInt(st.nextToken());
            // 뽑고자 하는 원소의 위치찾기
            int idx = list.indexOf(ele);

            // 오른쪽으로 시프트해서 뽑는게 더 빠름(3번연산)
            if(idx >= (list.size() + 1) / 2){
                for(int j = 0; j < list.size() - idx; j++){
                    answer++;
                    list.add(0, list.remove(list.size() - 1));
                }
            }
            // 왼쪽 시프트해서 뽑는게 더 빠름(2번연산)
            else{
                for(int j = 0; j < idx; j++){
                    answer++;
                    list.add(list.remove(0));
                }
            }
            // 정답뽑기(1번연산)
            list.remove(0);
        }
        System.out.println(answer);
    }
}

TCP는 송신자와 수신자의 버퍼를 오버플로우 시키는 것을 방지하기 위해 애플리케이션에게 흐름 제어 서비스(flow-control service) 를 제공한다. 수신자의 버퍼 상태에 따라 송신자가 보내는 속도를 조절한다. TCP는 송신자가 수신 윈도(receive window)변수를 유지하여 흐름 제어를 제공한다. 수신 윈도는 수신 측에서 가용한 버퍼 공간이 얼마나 되는지를 송신자에게 알려주는 데 사용된다.

Recieve Buffer의 남은 공간이 없는 경우

만약 수신 측의 receive buffer에 공간이 없고, 수신자는 송신 측에 새로 보낼 데이터가 더이상 없을 때, 송신자는 수신 측의 receive buffer에 대한 상황을 더 이상 알 수 없다. 이를 위하여 송신자는 주기적으로 1Byte 세그먼트를 보내본다. 만약 수신자가 세그먼트를 받는다면 ACK가 수신자로부터 올 것이고, buffer 상황도 알 수 있게 된다.

Silly Window Syndrome

송신, 수신측 응용 프로그램이 데이터 처리 단위가 작거나 저속일 때, 최소 IP 및 TCP의 헤더가 각각 20 바이트 씩 총 40 바이트가 부가적으로 붙여지며 이는 네트워크의 자원을 낭비하는 결과가 된다.

Sender:Nagle's algorithm

1. 송신자는 1Byte라도 보낼 데이터가 있다면 송신한다.
2. 세그먼트를 만들고, 데이터를 채우면서 기다린다. 2-1. 데이터를 Maximum size(536Byte)만큼 채웠으면 보낸다. 2-2. 방금 보낸 세그먼트에 대한 ACK를 받았다면 데이터를 덜 채웠어도 보낸다.

Receiver

• 하나의 Maximum사이즈의 세그먼트를 받을 수 있는 공간이 있을 때 까지 receive buffer 사이즈를 0으로 보낸다.
• 세그먼트를 받은 후 일정 기간 기다렸다가 ACK를 보낸다.

TCP 연결 관리

3-way handshake

1. 클라이언트 TCP는 서버 TCP에게 특별한 TCP 세그먼트인 SYN 세그먼트를 송신한다. 세그먼트에 담긴 값은 다음과 같다.
   • SYNbit = 1
   • Sequence number = x
2. 서버는 TCP SYN 세그먼트를 추출하여 연결에 TCP 버퍼와 변수를 할당한다. 그리고 클라이언트 TCP로 연결 승인 세그먼트를 송신한다. 이 세그먼트는 SYNACK 세그먼트라고도 불린다.
   • SYNbit = 1
   • Sequence number = y
   • ACKbit = 1
   • ACKnum = x + 1
3. 연결 승인 세그먼트를 수신하면, 클라이언트는 연결에 버퍼로아 변수를 할당한다. 그 후 클라이언트 호스트는 서버로 또 다른 세그먼틀 송신한다. 이는 서버의 연결 승인 세그먼트를 확인하는 것이다.
   • ACKbit = 1
   • ACKnum = y + 1

다음 단계들이 완료되면, 클라이언트와 서버 호스트들은 각각 서로에게 데이터를 포함하는 세그먼트를 보낼 수 있다.

TCP 연결종료

1. 클라이언트가 FINbit = 1 로 설정한 뒤 세그먼트를 보낸다.
2. 서버는 이 세그먼트를 수신하면, 서버는 클라이언트에게 확인응답 세그먼트를 보낸다. 그 후 FIN 비트가 1로 설정된 자신의 종료 세그먼트를 송신하다.
3. 마지막으로 클라이언트는 서버의 종료 세그먼트에 확인응답을 한다. 이 시점에서 두 호스트의 모든 자원 할당은 해제된다. 확인응답이 유실될 경우를 대비해서 클라이언트는 대기시간을 가진 후에 자원 할당을 해제한다.

Reference

KOCW - 컴퓨터 네트워크 컴퓨터 네트워킹 하향식 접근

• point-to-point

  • 단일 송신 동작으로 한 송신자가 여러 수신자에게 데이터를 전송하는 멀티캐스팅은 불가능

• reliable, in-order byte stream

  • 유실되지 않고, 에러없이 송수신된다.
  • 보낸 순서대로 도착한다.

• full duplex data

  • 전이중 서비스 제공
  • A 와 B에게 TCP 연결이 있을 때 A -> B, B -> A 가능

• connection-oriented

  • 데이터 전송을 위하여 두 프로세스는 핸드셰이크를 해야 한다.

TCP 세그먼트 구조

• 출발지와 목적지 포트 번호(source and destination port number) : multiplexing, demultiplexing에 사용
• 순서 번호(sequence number) : 송신측의 sequence number
• 확인응답 번호(acknowledgement number) : 수신측의 sequence number
• 수신 윈도(receive window) : flow control에 사용, 수신자가 받아들이려는 바이트의 크기를 나타냄
• 헤더 길이(header length) : 32비트 워드 단위로 TCP 헤더의 길이를 나타냄
• 인터넷 체크섬(checksum) : 에러 판별

순서 번호와 확인응답 번호

TCP는 데이터를 구조화되어 있지 않고 단지 순서대로 정렬되어 있는 바이트 스트림으로 본다. 세그먼트에 대한 순서 번호는 세그먼트에 있는 첫 번째 바이트의 바이트 스트림 번호이다. Ex) 100Byte data에서 첫번째 세그먼트가 04Byte -> 순서 번호 = 0, 두번째 세그먼트 번호가 510Byte -> 순서 번호 = 5

TCP는 호스트 A가 호스트 B로 데이터를 송신하는 동안에 호스트 B로부터 데이터를 수신하게 해주는 전이중 방식이다. 호스트 B로부터 도착한 각 세그먼트는 B로부터 A로 들어온 데이터에 대한 순서 번호를 가진다. 이때 이 세그먼트에 호스트 A가 삽입하는 확인응답 번호는 호스트 A가 호스트 B로부터 다음에 받을 바이트의 순서 번호이다. 즉, A가 보낸 세그먼트의 확인응답 번호가 10이라면 A는 B가 보낸 순서 번호의 9번까지는 정상적으로 수신했다는 뜻이다.

왕복 시간(RTT) 예측과 타임아웃

TCP에서 타임아웃은 세그먼트가 전송된 시간부터 긍정 확인응답될 때까지의 시간인 연결의 왕복 시간(round-trip time, RTT)보다 좀 더 커야된다. 그렇지 않다면 불필요한 재전송이 발생한다.

TCP가 송신자와 수신자 사이의 왕복 시간을 예측하는 것은 SampleRTT를 통하여 이루어진다. SampleRTT는 세그먼트가 송신된 시간으로부터 그 세그먼트의 긍정응답이 도착한 시간까지의 시간 길이이다. SampleRTT는 라우터의 혼잡, 종단 시스템의 부하 변화 등의 이유로 세그먼트마다 달라지며, 이러한 변동성 때문에 SampleRTT는 불규칙적이다. 따라서 대체로 RTT를 추정하기 위하여 SampleRTT값의 평균값을 채택한다.

신뢰적인 데이터 전송

TCP 프로토콜은 단일 재전송 타이머를 사용하며 타이머는 send buffer에 가장 앞에 위치하고 있으며, timeout이 발생하면 타이머가 위치한 버퍼의 세그먼트를 재전송한다. 또한 타이머가 sequence number 100을 가리키고 있을 때, ACK가 120이 온다면 수신측에서는 119번까지는 정상적으로 받은 것이므로 버퍼에서 119번까지 제거하고 120번부터 내보내며, 타이머를 다시 설정한다.

빠른 재전송

타임아웃이 유발하는 재전송의 한 가지 문제는 타임아웃의 주기가 길다는 것이다. 세그먼트를 유실했을 때, 긴 타임아웃 주기는 잃어버린 패킷을 다시 보내기 전에 송신자를 오랫동안 기다리게 해서 종단 간 지연을 증가시킨다. 타임 아웃이 발생하기 전에 패킷손실을 발견하는 방법은 중복ACK(duplicate ACK) 이다. 송신자는 많은 양의 세그먼트를 연속적으로 보낼 수 있으므로, 만약 하나의 세그먼트를 잃어버린다면 많은 연속적인 중복 ACK가 존재할 수 있다. 만약 TCP 송신자가 같은 데이터에 대해 3개의 중복 확인응답을 수신한다면, 타임 아웃이 발생하지 않더라도 그 번호에 해당하는 세그먼트를 재전송한다. 이때 처음 받은 ACK는 제외하고 3개의 중복 확인응답이므로, 총 4개의 ACK를 받는 것이다.

Reference

KOCW - 컴퓨터 네트워크 컴퓨터 네트워킹 하향식 접근

풀이

추천인을 계속해서 찾아나가야되므로, 빠르게 찾을 수 있는 map을 사용하였다. key값으로 자신의 이름, value로 클래스를 하나 만들어서 추천인 이름과, 자신의 이익을 기록하였다.

코드

import java.util.*;

class Solution {

    class Node{
        String name, referral;
        int profit;

        public Node(String enroll, String referral, int profit){
            this.name = name;
            this.referral = referral;
            this.profit = profit;
        }

    }
    public int[] solution(String[] enroll, String[] referral, String[] seller, int[] amount) {
        Map<String, Node> groupMap = new HashMap<>();

        // map 정보 입력
        for(int i = 0; i < enroll.length; i++){
            String name = enroll[i];
            String ref = referral[i];
            groupMap.put(name, new Node(name, ref, 0));
        }

        for(int i = 0; i < seller.length; i++){
            String name = seller[i];
            int price = amount[i] * 100;

            // 추천인에게 10%의 이익을 준다.
            while(!"-".equals(name) && price >= 1){
                int parentProfit = price / 10;
                int myProfit = price - parentProfit;

                // 자기 자신의 이익을 추가
                Node node = groupMap.get(name);
                node.profit += myProfit;
                groupMap.put(name, node);

                // 추천인 정보로 갱신
                name = node.referral;
                price = parentProfit;
            }
        }

        int[] answer = new int[enroll.length];
        for(int i = 0; i < answer.length; i++){
            answer[i] = groupMap.get(enroll[i]).profit;
        }

        return answer;
    }
}