공부 기록

n개의 섬 사이에 다리를 건설하는 비용(costs)이 주어질 때, 최소의 비용으로 모든 섬이 서로 통행 가능하도록 만들 때 필요한 최소 비용을 return 하는 문제이다.

=> 최소비용신장트리 중 Prim 알고리즘 사용

최소비용신장트리:

2020/07/19 - [알고리즘 공부/boj] - boj 1197: 최소 스패닝 트리

import java.util.*;
class Solution {
	public int solution(int v, int[][] costs) {
		LinkedList<Edge>[] pair = new LinkedList[v + 1];
		HashSet<Integer> vSet = new HashSet<Integer>();
		for (int i = 0; i < v; i++) {
			pair[i] = new LinkedList<Edge>();
			vSet.add(i);
		}

		for (int i = 0; i < costs.length; i++) {
			int start = costs[i][0];
			int end = costs[i][1];
			long cost = costs[i][2];

			pair[start].add(new Edge(end, cost));
			pair[end].add(new Edge(start, cost));
		}

		int currentNode = 1;
		int answer = 0;
		vSet.remove(1);

		PriorityQueue<Edge> pq = new PriorityQueue<Edge>();
		pq.addAll(pair[currentNode]);

		while (!vSet.isEmpty()) {
			Edge minEdge = pq.poll();

			if (vSet.contains(minEdge.v)) {
				answer += minEdge.cost;
				currentNode = minEdge.v;
				vSet.remove(currentNode);
				pq.addAll(pair[currentNode]);
			}
		}
		return answer;
	}
}

class Edge implements Comparable<Edge> {
	int v;
	long cost;

	public Edge(int v, long cost) {
		this.v = v;
		this.cost = cost;
	}

	@Override
	public int compareTo(Edge o) {
		return Long.compare(this.cost, o.cost);
	}
}

start -> end까지 지나는 다리 각각의 최솟값에 대한 최댓값을 구하는 문제이다.

이분탐색으로 중량을 정해두고 BFS로 다리를 지나갈 수 있는지 확인하면 쉽게 풀리는 문제이다.

이렇게 풀 경우 서로 같은 두 도시 사이에 여러 개의 다리가 있다는 조건을 딱히 생각해 줄 필요가 없다.

import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int v = in.nextInt();
		int e = in.nextInt();

		LinkedList<Bridge> bridges[] = new LinkedList[v + 1];
		for (int i = 1; i <= v; i++) {
			bridges[i] = new LinkedList<Bridge>();
		}

		int max = 0;
		for (int i = 0; i < e; i++) {
			int start = in.nextInt();
			int end = in.nextInt();
			int size = in.nextInt();

			max = Math.max(max, size);

			bridges[start].add(new Bridge(end, size));
			bridges[end].add(new Bridge(start, size));
		}

		int start = in.nextInt();
		int end = in.nextInt();

		System.out.println(findMinimumWeight(start, end, bridges, max));
	}

	public static int findMinimumWeight(int from, int to, LinkedList<Bridge> bridges[], int end) {
		boolean[] isVisited = new boolean[bridges.length];

		int start = 0;
		int max = 0;

		while (start <= end) {
			int mid = (start + end) / 2;

			if (BFS(from, to, bridges, mid, isVisited)) { // 가능하니까 일단 결과 저장 후 중량을 더 늘려보자
				max = Math.max(max, mid);
				start = mid + 1;
			} else {
				end = mid - 1;
			}
		}
		return max;
	}

	public static boolean BFS(int start, int end, LinkedList<Bridge> bridges[], int maxSize, boolean[] isVisited) {
		clearVisit(isVisited);

		Queue<Integer> queue = new LinkedList<Integer>();

		queue.add(start);
		isVisited[start] = true;

		while (!queue.isEmpty()) {
			int now = queue.poll();

			if (now == end) {
				return true;
			}

			for (Bridge bridge : bridges[now]) {
				if (!isVisited[bridge.destination] && maxSize <= bridge.size) {
					queue.add(bridge.destination);
					isVisited[bridge.destination] = true;
				}
			}
		}

		return false;
	}

	public static void clearVisit(boolean[] isVisited) {
		Arrays.fill(isVisited, false);
	}
}

class Bridge {
	int destination;
	int size;

	public Bridge(int destination, int size) {
		this.destination = destination;
		this.size = size;
	}

	@Override
	public boolean equals(Object o) {
		Bridge bridge = (Bridge) o;
		return destination == bridge.destination;
	}

	@Override
	public int hashCode() {
		return Objects.hash(destination);
	}
}

시뮬레이션 문제이다. 시키는대로만 구현하면 된다.

행렬이 범위만 주의하도록 하자 1 ≤ r ≤ R, 1 ≤ c ≤ C

import java.util.*;

public class Main {
	public static int dr[] = { -1, 1, 0, 0 };
	public static int dc[] = { 0, 0, 1, -1 };

	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int row = in.nextInt();
		int col = in.nextInt();
		int n = in.nextInt();
		int mat[][] = new int[row + 1][col + 1];

		Shark sharks[] = new Shark[n + 1];
		for (int i = 1; i <= n; i++) {
			int r = in.nextInt();
			int c = in.nextInt();
			int s = in.nextInt();
			int d = in.nextInt();
			int z = in.nextInt();

			sharks[i] = new Shark(i, r, c, s, dr[d - 1], dc[d - 1], z);
			mat[r][c] = i;
		}

		int sum = 0;

		for (int i = 1; i <= col; i++) {
			sum += getShark(i, mat, sharks);
			moveShark(mat, sharks, row, col);
		}
		System.out.println(sum);
	}

	public static int getShark(int col, int[][] mat, Shark[] sharks) {
		for (int i = 0; i < mat.length; i++) {
			if (mat[i][col] != 0) {

				int size = sharks[mat[i][col]].size;
				sharks[mat[i][col]] = null;
				mat[i][col] = 0;

				return size;
			}
		}
		return 0;
	}

	public static void moveShark(int[][] mat, Shark[] sharks, int maxRow, int maxCol) {
		for (int i = 1; i < sharks.length; i++) {
			Shark shark = sharks[i];

			if (shark != null) {
				mat[shark.row][shark.col] = 0;
				shark.move(maxRow, maxCol, shark.speed);
			}
		}

		for (int i = 1; i < sharks.length; i++) {
			Shark shark = sharks[i];

			if (shark != null) {
				if (mat[shark.row][shark.col] == 0) {
					mat[shark.row][shark.col] = i;
				} else {
					Shark beforeShark = sharks[mat[shark.row][shark.col]];
					if (beforeShark.size > shark.size) {
						sharks[i] = null;
					} else {
						sharks[mat[shark.row][shark.col]] = null;
						mat[shark.row][shark.col] = i;
					}
				}
			}
		}
	}
}

class Shark {
	int name;
	int row;
	int col;
	int speed;
	int dr;
	int dc;
	int size;

	public Shark(int name, int row, int col, int speed, int dr, int dc, int size) {
		this.name = name;
		this.row = row;
		this.col = col;
		this.speed = speed;
		this.dr = dr;
		this.dc = dc;
		this.size = size;
	}

	public void changeDirection() {
		this.dr = -dr;
		this.dc = -dc;
	}

	public void move(int maxRow, int maxCol, int move) {
		// 상어가 이동하려고 하는 칸이 격자판의 경계를 넘는 경우에는 방향을 반대로 바꿔서 속력을 유지한채로 이동한다.
		if (move == 0) {
			return;
		}

		int newRow = row + dr * move;
		int newCol = col + dc * move;
		if (newRow > 0 && newCol > 0 && newRow <= maxRow && newCol <= maxCol) {
			row = newRow;
			col = newCol;
			return;
		}

		if (newRow <= 0) {
			row = 1;
			changeDirection();
			move(maxRow, maxCol, 1 - newRow);
			return;
		}
		if (newCol <= 0) {
			col = 1;
			changeDirection();
			move(maxRow, maxCol, 1 - newCol);
			return;
		}
		if (newRow > maxRow) {
			row = maxRow;
			changeDirection();
			move(maxRow, maxCol, newRow - maxRow);
			return;
		}
		if (newCol > maxCol) {
			col = maxCol;
			changeDirection();
			move(maxRow, maxCol, newCol - maxCol);
			return;
		}

	}
}

문제 조건

1. 건물을 건설하는데 순서가 존재한다.

2. 건물 건설은 동시에 가능하다

이 문제는 전형적인 위상정렬 문제이다.

아래와 같이 건물을 건설하는 데에 필요한 정보는 아래 2가지 정보이며, 예제 1에 적용해 보자

- 기다려야 하는 시간 building

- 건물을 건설하기 위해 먼저 건설해야 하는 노드의 개수 parentNum

<time=0>



<time=10>

parentNum[i] = 0인 노드부터 건설하면 된다. 큐에 넣어서 순차적으로 처리해 보자

빌딩을 건설해 주고 나면 i를 부모 노드로 하는 자식 노드들의 parentNum을 하나씩 줄여준다.

<time=110>

빌딩은 동시에 건설이 가능하기 때문에,

같은 depth의 노드들의 building 중 최댓값을 time에 더해주도록 한다.

마지막으로 최종 목표 destination node가 나타나면 바로 건설 시간을 더해준 후 리턴해준다.

풀이 코드는 아래와 같다.

import java.util.*;

public class Main {
	public static int max = 0;

	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int test = in.nextInt();
		for (int t = 0; t < test; t++) {
			int v = in.nextInt();
			int e = in.nextInt();
			int building[] = new int[v + 1];

			for (int i = 1; i <= v; i++) {
				building[i] = in.nextInt();
			}

			LinkedList<Integer> childs[] = new LinkedList[v + 1];
			LinkedList<Integer> parents[] = new LinkedList[v + 1];
			for (int i = 1; i <= v; i++) {
				childs[i] = new LinkedList<Integer>();
				parents[i] = new LinkedList<Integer>();
			}

			int[] parentNum = new int[v + 1];

			for (int i = 0; i < e; i++) {
				int parentNode = in.nextInt();
				int childNode = in.nextInt();

				childs[parentNode].add(childNode);
				parents[childNode].add(parentNode);
				parentNum[childNode]++;
			}

			int destination = in.nextInt();

			System.out.println(calculateTime(destination, building, parentNum, childs, parents));
		}
	}

	public static int calculateTime(int destination, int[] building, int[] parentNum, LinkedList<Integer> childs[],
			LinkedList<Integer> parents[]) {
		boolean[] isVisited = new boolean[building.length];

		Queue<Integer> queue = new LinkedList<Integer>();
		for (int i = 1; i < building.length; i++) {
			if (parentNum[i] == 0) {
				if (i == destination) { // 바로 건설 가능한 경우
					return building[i];
				}

				queue.add(i);
			}
		}

		while (!queue.isEmpty()) {
			int now = queue.poll();
			isVisited[now] = true;

			for (int node : childs[now]) {
				parentNum[node]--;

				if (!isVisited[node] && parentNum[node] == 0) {
					queue.add(node);

					int max = 0;
					for (int parent : parents[node]) {
						max = Math.max(max, building[parent]);
					}
					building[node] += max;

					if (node == destination) {
						return building[destination];
					}
				}
			}
		}

		return building[destination];
	}
}

조금 어려웠던 점은 아래와 같은 반례를 생각하지 못했어서 맞왜틀을 고민했었다.

올바르게 시간을 구하기 위해서는 부모 노드들 또한 저장해야해야 했는데, 다른 스터디원들에 비해 실행 시간이 너무 오래 걸려서

한 번 생각해 봐야겠다...

문제 조건

'우수 마을'로 선정된 마을 주민 수의 총 합을 최대로 해야 한다.
2. '우수 마을'끼리는 서로 인접해 있을 수 없다.
3. '우수 마을'로 선정되지 못한 마을은 적어도 하나의 '우수 마을'과는 인접해 있어야 한다.

이 문제의 경우는 우수 마을에 포함할지 말지 모두 구한 후 조건에 맞는지 확인하는 방식으로 푼다면 O(2^N)으로 시간초과가 날 것이다.

'우수 마을'로 선정된 마을 주민 수의 총 합을 최대로 해야 한다. => DP를 사용하면 될 것 같다.

우수마을의 경우 트리 형태이고, 이 트리에서 DP를 사용해서 문제를 풀어야 한다.

이 문제에선, 부모 노드를 우수 마을에 포함할 경우, 자식노드는 우수 마을에 포함하면 안된다.

그리고 일반 마을이 부모 노드일 경우, 자식 노드에는 우수 마을이 있어야 한다.(합을 최대로 구해야 하니까)

dp[i][0]: i번 마을이 우수 마을이 아니었을 때 i번 마을을 루트로 하는 서브 트리의 우수 마을들 인구수의 최댓값
dp[i][1]: i번 마을이 우수 마을이었을 때 i번 마을을 루트로 하는 서브 트리의 우수 마을들 인구수의 최댓값

아무 노드나 루트로 삼고 DFS를 진행한다. => 1로 시작하자

왜냐면 조건중에

나라는 트리(Tree) 구조로 이루어져 있으며, 즉 마을과 마을 사이를 직접 잇는 N-1개의 방향 없는 길이 있으며,

모든 마을은 연결되어 있다. 는 조건이 있기 때문이다.

이 문제에서 주어진 문제는 방향이 없는 연결을 가지는 트리이며, 모든 노드가 루트 노드가 될 수 있다.

DFS를 사용한 이유는 순회를 하면서 우수마을 조건에 포함하고 포함하지 않는 식의 백트래킹을 이용하기 위해서이다.

리프노드에 도달하게 되면,

노드 5와 같이 다시 거슬러 올라오면서 dp값을 채우도록 한다.

노드 2까지 올라오면 다른 분기점으로 내려가면서

마찬가지로 방문하지 않은 노드까지 찾아내려간다.

결론적으로 업데이트된 dp의 최종 결과는 아래와 같다.

그리고 이를 적용한 코드는 아래와 같다

import java.util.*;

public class Main {
	public static int max = 0;

	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int n = in.nextInt();
		int people[] = new int[n + 1];
		LinkedList<Integer> connections[] = new LinkedList[n + 1];

		for (int i = 1; i <= n; i++) {
			people[i] = in.nextInt();
			connections[i] = new LinkedList<Integer>();
		}

		for (int i = 1; i < n; i++) {
			int a = in.nextInt();
			int b = in.nextInt();
			connections[a].add(b);
			connections[b].add(a);
		}

		/*
		 * dp[i][0]: i번 마을이 우수 마을이 아니었을 때 i번 마을을 루트로 하는 서브 트리의 우수 마을들 인구수의 최댓값,
		 * 
		 * dp[i][1]: i번 마을이 우수 마을이었을 때 i번 마을을 루트로 하는 서브 트리의 우수 마을들 인구수의 최댓값
		 * 
		 */
		int dp[][] = new int[n + 1][2];
		boolean isVisited[] = new boolean[n + 1];
		int start = 1;
		dfs(start, isVisited, people, dp, connections);

		System.out.println(Math.max(dp[start][0], dp[start][1]));
	}

	public static void dfs(int root, boolean[] isVisited, int[] people, int[][] dp, LinkedList<Integer> connections[]) {
		isVisited[root] = true;
		for (int next : connections[root]) {
			if (!isVisited[next]) {
				dfs(next, isVisited, people, dp, connections);
			}
		}
		dp[root][0] = 0;
		dp[root][1] = people[root];
		for (int next : connections[root]) {
			dp[root][0] += Math.max(dp[next][0], dp[next][1]);
			dp[root][1] += dp[next][0];
		}
	}
}

주의할 점은 top down방식으로 dp를 업데이트 하게 되면 분기점 등에서 겹치는 값이 생길 수 있으므로

botton up 방식으로 값을 업데이트 하도록 해야 한다.

Use the Flyweight Pattern when one instance of a class can be used to provide many virtual instances

Flyweight 패턴은 비용이 큰 자원을 공통으로 사용할 수 있도록 만드는 패턴이다.
자원에 대한 비용은 크게 두가지로 나눠 볼 수 있다.

1. 중복 생성될 가능성이 높은 경우.
중복 생성될 가능성이 높다는 것은 동일한 자원이 자주 사용될 가능성이 매우 높다는 것을 의미한다. 이런 자원은 공통 자원 형태로 관리하고 있다가 요청이 있을 때 제공해 주는 편이 좋다.

2. 자원 생성 비용은 큰데 사용 빈도가 낮은 경우.
이런 자원을 항상 미리 생성해 두는 것은 낭비이다. 따라서 요청이 있을 때에 생성해서 제공해 주는 편이 좋다.

이 두가지 목적을 위해서 Flyweight 패턴은 자원 생성과 제공을 책임진다. 자원의 생성을 담당하는 Factory 역할과 관리 역할을 분리하는 것이 좋을 수 있으나, 일반적으로는 두 역할의 크기가 그리 크지 않아서 하나의 클래스가 담당하도록 구현한다.

출처 - https://effectiveprogramming.tistory.com/entry/Flyweight-%ED%8C%A8%ED%84%B4

예를 들어 새로운 조경 설계 애플리케이션에서 나무 객체를 추가하려고 한다.

애플리케이션에서 나무는 X, Y 위치를 가지면서 나이에 따라 동적인 크기로 그릴 수 있다고 하자.

이 경우 나무를 나타나는 것은 문제없지만,

대규모의 큰 나무 숲을 만들 경우, 각각의 나무에 대해 위치 정보와 나이 대한 정보를 관리하며 

Tree 인스턴스를 생성하고 제거하면서 프로그램이 느려질 수 있다.

이러한 경우 수천 개의 Tree 오브젝트가있는 대신 Tree 인스턴스는 하나만 존재하고, 모든 트리의 상태를 유지하는 클라이언트 오브젝트가 있도록 시스템을 설계 하는 것이 바로 Flyweight 패턴이다.

위 클래스 다이어그램에서 보는 바와 같이 Tree 객체와 이 자원을 관리하는 매니저 클래스 TreeManager 클래스로 바꿀 수 있다.

Tree의 경우 여러 경우를 미리 생성해두고 이를 Manager에서 관리하게 된다.

이를 코드로 구현해보면 아래와 같다.

.

장점

• 런타임시 객체 인스턴스 수를 줄여 메모리를 절약한다.
• 많은 virtual 개체의 상태를 단일 위치로 중앙 집중화한다.

단점

• 일단 구현하면 클래스의 단일 논리적 인스턴스가 다른 인스턴스와 독립적으로 동작 할 수 없다.

언제 사용하는가?

• 클래스의 많은 인스턴스가 필요할 때 사용되며, 그리고 그 객체들을 모두 동일하게 제어할 때 사용한다.

Use the Bridge Pattern to vary not only your implementations, but also your abstractions.

브리지 패턴은 추상층을 분리하여 각자 독립적으로 변형 및 확장이 가능하도록 만드는 패턴이다.

즉, 기능과 구현에 대해 두 개의 별도의 클래스로 구현한다.

예를 들어 TV 리모컨용 코드를 작성한다고 하자. 일단 각 리모컨으로 할 수 있는 여러가지 기능들이 있다.

이 기능들 중에 RCAControl, SonyControl이라는 두가지 기능이 있다고 해보자. 그런데 이 리모컨을 사용하는 여러가지 TV 모델들(LG, Samsung)도 있을 수 있다.

단순하게 생각했을 때, 왼쪽과 같이 리모컨이라는 동일한 추상화를 기반으로 TV의 각 모델마다 서로 다른 기능을 구현해 볼 수 있을 것이다.

하지만, 문제는 리모컨의 기능과 TV 모델들이 바뀔 수 있다는 점이다. 여러 TV에서 구현을 다양화할 수 있도록 리모컨은 이미 추상화했지만, 리모컨의 기능이 개선될때마다 TV 모델들의 구현 또한 변경되어야 할 수 있다.

뿐만 아니라, 리모컨의 기능이 추가된다면 해당 리모컨 기능에 대한 구현을 해야 한다.

이러한 경우에 Bridge 패턴을 이용하면 두 가지를 별도의 클래스 계층 구조에 배치하여 구현과 추상화를 다양화할 수 있다.

즉, 구체적인 클래스들 간의 의존성을 배제시킬 수 있다.

위 클래스 다이어그램에서 보는 바와 같이 RemoteControl과 TV는 각각 인터페이스이다.

그리고 구체적인 의존 관계는 이 인터페이스들 간에만 존재하기 때문에 이렇게 브리지를 사용하면 두 계층 구조의 양쪽을 독립적으로 변경할 수 있다.

이를 코드로 구현해보면 아래와 같다.

.

장점

• 인터페이스에 (의존하지 않도록) 구현을 분리한다.
• 추상화와 구현은 독립적으로 확장 될 수 있다.
• 구체적인 추상화 클래스에 대한 변경 사항은 클라이언트에 영향을주지 않는다.

단점

• 복잡성이 증가한다.

언제 사용하는가?

• 여러 플랫폼에서 실행해야하는 그래픽 및 윈도우 시스템에 유용하다.
• 다른 방식으로 인터페이스와 구현을 변경해야 할 때 유용하다.

end point에는 7 layer가 존재하지만, 라우터에는 network layer까지만 존재한다.

하위 계층에서 상위 계층에게 서비스를 제공하는 것이다.

Application layer

ex) chrome 브라우저 등: user program

client process와 server process의 의사 소통(다른 컴퓨터 상에 존재하는 프로세스 간 통신)

⇒ os에서 이를 위해 `소켓`이라는 인터페이스를 만들어 놓음.

• 서버
  • always-on host
  • 고정된 ip 주소
  • data centers for scaling
• 클라이언트
  • communication with server
  • may be intermittently connected
  • may have dynamic ip addresses
  • do not communicate directly with each other

소켓의 주소 = ip address + port

• ip 주소: 인터넷 상의 컴퓨터 주소
• port: 같은 인터넷 상의 특정 컴퓨터의 소켓

왜 웹 서버들이 동일한 포트를 쓸까? (80) 

www.google.com → DNS → ip 주소로 변환(default port:80)

서버는 24시간 켜져 있어야 하고, 주소가 일정해야 한다. 주소를 해석해 주는 것이 DNS인데, 
포트 넘버까지 다른 것 보다 같도록 정하는 것이 더 효율적이기 때문이다. 
즉, DNS에서 포트 넘버까지 다 만들어 주어야 하기 때문이다.

transport 계층에서 이러한 서비스가 제공되면 좋겠다는 희망 사항

• data integrity: 보낸 데이터가 유실되지 않고 온전하게 목적지까지 도착했으면 좋겠다. ⇒ transport layer(tcp)에서 제

• throughput: 보낸 데이터가 최소 ~~ bps, 전달 용량에 대한 희망 사항

• timing: 보낸 데이터가 ~~ 시간 안에 도착 했으면 좋겠다.

• security: 내가 보낸 데이터가 안전 했으면 좋겠다.

  ⇒ 나머지는 제공x

HTTP

hypertext transfer protocol

hypertext: text 인데 중간 중간에 다른 텍스트를 가리키는 링크가 존재

• tcp 프로토콜을 사용
  • request, response 이전에 connection을 생성한다.
• stateless
  • HTTP는 단순해서 요청 들어오면 응답을 보내주고 끝이다. 상대방의 상태 등을 기억하지 않는다.

1. non-persistent HTTP: connection 맺은 뒤 통신 완료 후 connection을 끊는 경우

2. persistent HTTP: connection 맺은 뒤 통신 완료 후 connection을 끊지 않고 재 사용하는 경우

- 실제로는 Pipeline과 persistent HTTP가 결합된 방식을 사용

소켓

client process와 server process간의 통신

os가 제공해주는 api의 일종으로, os에는 application layer의 하위 계층들이 구현되어있다. 즉, application layer와 os 사이를 이어주는 transport layer 인터페이스를 사용해 주어야 한다. os에는 transport layer를 tcp와 udp, 2가지 방식을 구현한다. application layer는 이 구현되어 있는 소켓 중에 tcp, udp 둘 중 하나의 방식을 선택한다.

1. tcp socket = socket stream

• 신뢰성 제공 및 순서대로 전송(연결성)
• bidirectional

• tcp socket function

• int socket(int domain, int type, int protocol)
  • type: udp인지 tcp인지
  • 리턴 값은 생성된 소켓의 id

• int bind(int sockfd, struct socketaddr* myaddr, int addrlen)
  • 생성한 소켓의 id를 사용해서 특정 포트에 바인딩 하겠다.
  • 클라이언트에서 바인드 함수를 사용하지 않는 이유는, 바인드 함수는 특정 소켓을 어떤 포트에 바인드 해주는 개념인데, 클라이언트는 특정 포트에 바인드 할 필요가 없기 때문이다. (아무 포트나 쓰면 됨)

• int listen(int sockfd, int backlog)
  • 방금 생성한 소켓을 listen 용도로 사용할 것이며, 동시에 request가 들어올 경우, 최대 n개까지 큐에 담아 놓고 순서대로 처리하겠다.

• int accept(int sockfd, struct sockaddr* cliaddr, int* addrlen)
  • 다 준비 되었으니 클라이언트로부터 연락을 기다리겠다.
  • 이 함수는 실행 되면 block되어 있다가 클라이언트로부터 요청이 들어오면 리턴 된다. 리턴이 될 때, 두 번째 파라미터에 클라이언트의 ip와 port 주소가 저장된다. (=서버에 클라이언트의 주소가 저장된다)

2. udp socket = socket datagram

• 신뢰성을 제공하지 않으며 no order guarantees (비연결성)
• no notion of connection: app indicates destination for each packet
• can send or receive

• udp socket function

• int sendto(int sockfd, char* buf, size_t nbytes, int flags, struct sockaddr* destaddr, int addrlen)

• int close(int sockfd)
  • 데이터 교환이 끝난 후, 최종적으로 close해 주어야 다른 프로세스가 사용할 수 있다.

소켓의 경우, 프로그램이 에러 등이 나서 cntrl+c/z 등을 눌러 멈추면 프로세스는 죽지만, 그 프로세스에서 바인드 한 포트는 한동안 release 되지 않고 가지고 있다. 그래서 같은 포트를 쓸 수 없는 경우가 있다.

아래 시스템 콜을 쓰면 cntrl+c 등을 눌러줄 때 소켓 관련 자료 구조들이 다 release된다.

#include<signal.h>
void cleanExit(){exit(0);}

in socket code:
signal(SIGTERM, cleanExit);
signal(SIGINT, cleanExit);

presentation layer

운영체계의 한 부분으로 입력, 출력되는 데이터를 하나의 표현 형태로 변환하는 계층으로 필요한 번역을 수행한다.

즉 두 장치가 일관되게 전송 데이터를 서로 이해할 수 있도록 하는 역할이다.

해당 계층은 클라이언트 구현중에 데이터 교환 포맷을 맞추려고 내가 직접 수행해 준 적이 종종 있던거 같다.

데이터 표현이 상이한 응용 프로세스의 독립성을 제공하고, 암호화 한다.

표현 계층(Presentation layer)은 코드 간의 번역을 담당하여 사용자 시스템에서 데이터의 형식상 차이를 다루는 부담을 응용 계층으로부터 덜어 준다. MIME 인코딩이나 암호화 등의 동작이 이 계층에서 이루어진다.

예를 들면, EBCDIC로 인코딩된 문서 파일을 ASCII로 인코딩된 파일로 바꿔 주는 것,

해당 데이터가 TEXT인지, 그림인지, GIF인지 JPG인지의 구분 등이 표현 계층의 몫이다.

• 사용자의 명령어를 완성 및 결과 표현. 포장/압축/암호화

+ 보안 규약 정의

TLS/SSL : 암호화 프로토콜

• Transport layer Secure:
• Secure Socket layer:

ex) HTTP/HTTPS -> TLS/SSL 기술이 사용 된다.

• private key & foreign key 작동 원리

session layer

SSH/TLS 제공

응용 간의 제어 역할을 수행하는 통신 세션을 구성하는 계층으로 통신장치 간의 상호작용을 설정하고 유지하며, 동기화하여 사용자 간의 세션(포트)연결이 유효한지 확인하고 설정하는 역할을 한다.

데이터가 통신하기 위한 논리적인 연결을 담당하는데, 해당 논리적인 연결을 세션이라 하는거 같다. 근데 세션이 정확히 어떤건지 이해가 안된다. 세션에 대한 [https://88240.tistory.com/190] 여기의 설명이 좋은거 같다.

데이터가 통신하기 위한 논리적인 연결을 말한다. 통신을 하기위한 대문이라고 보면 된다.

하지만 4계층에서도 연결을 맺고 종료할 수 있기 때문에 우리가 어느 계층에서 통신이 끊어 졌나 판단하기는 한계가 있다.

그러므로 세션 계층은 4 계층과 무관하게 응용 프로그램 관점에서 봐야 한다.

세션 설정, 유지, 종료, 전송 중단시 복구 등의 기능이 있다.

세션 계층(Session layer)은 양 끝단의 응용 프로세스가 통신을 관리하기 위한 방법을 제공한다.

동시 송수신 방식(duplex), 반이중 방식(half-duplex), 전이중 방식(Full Duplex)의 통신과 함께, 체크 포인팅과 유휴, 종료, 다시 시작 과정 등을 수행한다.

이 계층은 TCP/IP 세션을 만들고 없애는 책임을 진다.

통신하는 사용자들을 동기화하고 오류복구 명령들을 일괄적으로 다룬다.

통신을 하기 위한 세션을 확립/ 유지 /중단 (운영체제가 해줌)

소켓을 만드는 layer

↔ 쿠키: 중요 정보 x, 하이 재킹 당하기 쉽기 때문에