고민의 흔적

83번 선물 전달

내가 떠올린 풀이 해설

완전 순열이라는 개념을 사용하는 문제이다. 완전 순열은 n개의 원소의 집합에서 원소들을 재배열할 때 이전과 같은 위치에 배치되는 원소가 1개도 없을 때를 말한다. arr[n] 배열의 의미를 n명일 때 선물을 교환할 수 있는 모든 경우의 수로 정한다. n명이 존재한다고 가정하고 A와 B라는 학생에게 선물을 줬다고 가정하자 이때는 교환 방식이 2가지가 존재한다.

선물을 교환하는 2가지 방식

1. B도 A에게 선물을 줬을 때 : N명 중 2명이 교환을 완료했으므로 남은 경우의 수는 arr[n - 2]
2. B는 A가 아닌 다른 친구에게 선물을 전달할 때 : N명 중 B만 받은 선물이 정해진 상태이므로 남은 학생은 N - 1이며 경우의 수는 arr[n - 1]이다

A는 자기 자신이 아닌 N - 1명에게 선물을 전달 할 수 있다. 이 과정으로 경우의 수를 구하는 점화식은 arr[N] = (N - 1) * (arr[N - 2] + arr[N - 1]) 

정확한 풀이

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

public class Baek1947 {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		long mod = 1000000000;
		long[] arr = new long[1000001];
		arr[1] = 0;
		arr[2] = 1;
		for(int i = 3; i <= n; i++) {
			arr[i] = (i - 1) * (arr[i - 2] + arr[i - 1]) % mod;
		}
		System.out.println(arr[n]);
	}
}

84번 1로 만들기

내가 떠올린 풀이 해설

사용할 수 있는 3가지 연산을 바텀-업 방식으로 구현할 수 있는지 연습하는 문제이다. 

1. 점화식 형태와 의미를 도출한다. 

arr[i] : i 에서 1로 만드는 데 걸리는 최소 연산 횟수

2. 점화식을 구한다.

arr[i] = arr[i - 1] + 1 // 1을 빼는 연산이 가능함
if(i % 2 == 0) arr[i] = min(arr[i], arr[i / 2] + 1) // 2로 나누는 연산이 가능함
if(i % 3 == 0) arr[i] = min(arr[i], arr[i / 3] + 1) // 3으로 나누는 연산이 가능함

3. 점화식을 이용해 arr배열을 채운다.

4. arr[n] 을 출력한다.

정확한 풀이

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

public class Baek1463 {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		int cnt = 0;
		int[] arr = new int[n + 1];
		arr[1] = 0;
	
		for(int i = 2; i <= n; i++) {
			arr[i] = arr[i - 1] + 1;
			if(i % 2 == 0) {
				arr[i] = Math.min(arr[i], arr[i / 2] + 1);
			}
			if(i % 3 == 0) {
				arr[i] = Math.min(arr[i], arr[i / 3] + 1);
			}
		}
		System.out.println(arr[n]);
	}
}

오늘의 회고

오늘은 조합 1문제와 DP문제를 풀었습니다. 점화식 세우는 방법이 너무 어렵습니다.. 지금까지 혼자 잘 공부해왔지만 불안한 감도 있어서 프로그래머스에서 [커뮤러닝/6기] 코딩 테스트 실력 UP 강의를 자부담비 10%와 내일배움카드가 90%를 지원해준다고 해서 신청하게 되었습니다. 선발된 과정에 충실하게 공부해서 실력을 한층 더 높이는 계기가 되었으면 좋겠습니다. 하반기에 원하는 기업에 입사하고 싶습니다.

1. 기본형과 참조형

1bit = 2진수 한자리

1byte = 8bit

기본형

오직 8개 (boolean, char, byte, short, int, long, float, double)

정수형 : byte 1byte, short 2byte, int 4byte, long 8byte

실수형 : float 4byte, double 8byte

논리형 : boolean 1byte

문자형 : char 2byte (java에서는 2바이트 유니코드를 사용하기 때문)

실제 값을 저장

참조형

기본형 8개를 제외한 모든 것 (String, System 등)

참조형 변수는 객체의 주소를 저장하기 위한 것

메모리 주소를 저장(4byte : 32bit JVM 또는 8byte : 64bit JVM)

2. 조건 연산자

조건식에 결과에 따라 연산 결과를 달리한다.

조건식 ? 식1 : 식2

조건식이 참이면 식1 거짓이면 식2

3. for문에 이름을 붙인다.

loop1 : for(int i = 0; i < n; i++) {
	for(int j = 0; j < n; j++) {
		break; → 안쪽 for문만 끝난다.
        break loop1; → loop1이라는 이름이 붙은 반복문이 끝난다.
	}
}

4. 객체지향

클래스

정의 : 객체를 정의해 놓은 것

용도 : 클래스는 객체를 생성하는 데 사용

객체

정의 : 실제로 존재하는 것, 사물 또는 개념

용도 : 객체가 가지고 있는 기능과 속성에 따라 다름

객체 = 속성(변수) + 기능(메서드)

객체 : 모든 인스턴스를 대표하는 일반적 용어

인스턴스 : 특정 클래스로부터 생성된 객체 객체와 인스턴스는 같은 단어

1. 객체의 생성
클래스명 변수명; // 클래스의 객체를 참조하기 위한 참조변수를 선언
변수명 = new 클래스명(); // 클레스의 객체를 생성 후, 객체의 주소를 참조변수에 저장  

ex)
TV t;  // TV클래스 타입의 참조변수 t를 선언
t = new TV(); // TV인스턴스 생성한 후, 생성된 TV인스턴스의 주소를 t에 저장

TV t = new TV();

2. 객체의 사용
t.channel = 7; // TV인스턴스의 맴버변수 channel의 값을 7로 한다.
t.channelDown(); // TV인스턴스의 메서드 channelDown()을 호출  

5. 객체 배열

객체 배열 == 참조 변수 배열

6. 클래스의 정의

클래스 == 데이터 + 함수

1. 변수 : 하나의 데이터를 저장하는 공간
2. 배열 : 같은 종류의 여러 데이터를 하나로 저장할 수 있는 공간
3. 구조체 : 서로 관련된 여러 데이터(종류 관계 x)를 하나로 저장할 수 있는 공간
4. 클래스 : 데이터와 함수의 결합(구조체 + 함수)

7.  선언 위치에 따른 변수의 종류

class Variables { // 클래스 영역
	int iv;  // 인스턴스 변수
    static int cv; // 클래스 변수(static 변수, 공유변수)
    
    void method() {  // 메소드 영역
    	int lv = 0; // 지역변수    
    }
}

8. 클래스 변수와 인스턴스 변수

class Card {
	String kind; // 무늬
    int number;  // 숫자
    
    static int width = 100;  // 폭
    static int height = 250; // 너비
}

Card c = new Card();
// 인스턴스 변수
c.kind = "HEART";
c.number = 5;
// 클래스 변수
Card.width = 200;
Card.height = 300;

9. 메서드

메서드의 장점

• 코드의 중복을 줄일 수 있다.
• 코드의 관리가 쉽다.
• 코드를 재사용할 수 있다.
• 코드가 간결해서 이해하기 쉬워진다.

메서드 작성

• 반복적으로 수행되는 여러 문장을 메서드로 작성
• 하나의 메서드는 한 가지 기능만 수행하도록 작성

MyMath mm = new MyMath(); // 1. 먼저 인스턴스를 생성한다.
long value = mm.add(1L, 2L); // 2. 메서드를 호출한다.

long add(long a, long b) {
	long result = a + b;
    return result;  // 반환타입이 void가 아닌 경우, 반드시 return문 필요
}
1. main 메서드에서 메서드 add를 호출한다. 인수 1L과 2L이 메서드 add의 매개변수 a, b에 각각 복사(대입)된다.
2. 메서드 add의 괄호 {} 안에 있는 문장들이 순서대로 실행된다.
3. 메서드 add의 모든 문장이 실행되거나 return문을 만나면, 호출한 메서드(main메서드)로 되돌아와서 이후의 문장들을 실행한다.

10. 호출 스택(call stack)

스택 : 밑이 막힌 상자, 위에 차곡차곡 쌓인다.

넣을 때

꺼낼 때

호출 스택

1. 메서드가 수행에 필요한 메모리가 제공되는 공간
2. 메서드가 호출되면 호출 스택에 메모리 할당, 종료되면 해제

class CallStack {
	public static void main(String[] args) {
    	System.out.println("Hello");
    }
}

아래에 있는 메서드가 위의 메서드를 호출한 것

맨 위의 메서드 하나만 실행 중, 나머지는 대기 중

11. 기본형 매개변수

기본형 매개변수 : 변수의 값을 읽기만 할 수 있다. (read only)

참조형 매개변수 : 변수의 값을 읽고 변경할 수 있다. (read & write)

82번 사전

내가 떠올린 풀이 해설

a와 z의 개수가 각각 N, M개일 때 이 문자들로 만들 수 있는 모든 경우의 수는 N + M 개에서 N개를 뽑는 경우의 수 또는 N + M개에서 M개를 뽑는 경우의 수와 동일하다. arr배열을 초기화하고, 점화식으로 값을 계산해 저장한다. 몇 번째 문자열을 표현해야 하는지를 나타내는 변수를 K라고 하자 현재 자릿수에서 a를 선택했을 때 남아 있는 문자들로 만들 수 있는 모든 경우의 수는 T이다. T와 K를 비교해 문자를 선택한다. 문자 선택 기준은 T >= K : 현재 자리 문자를 a로 선택 T < K : 현재 자리 문자를 Z로 선택하고, K = K - T로 업데이트 

ex) a = 2, z = 2이고 a를 선택했을 때 나머지 문자열로 만들 수 있는 경우의 수는 arr[남은문자 총 개수 : 3][남은 z개수 : 2]

arr [3][2] = 3 >= k(2)이므로 a 확정 -> z는 2개 남음

arr [3][2] = 3 < k(2)이므로 z 확정 -> z는 1개 남음 -> K = K - T = 1로 업데이트

arr [1][1] = 1 >= k(1)이므로 a 확정 -> z는 1개 남음

arr [0][1] = 1 < k(2)이므로 z 확정

정확한 풀이

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

public class Baek1256 {

	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());
		int k = Integer.parseInt(st.nextToken());
		int [][] arr = new int[202][202];
		for(int i = 0; i <= 200; i++) {  // 조합 테이블 초기화 
			for(int j = 0; j <= i; j++) {
				if(j == 0 || j == i) {
					arr[i][j] = 1;
				}
				else {
					arr[i][j] = arr[i - 1][j - 1] + arr[i - 1][j];
					if(arr[i][j] > 1000000000) { //k 범위가 넘어가면 범위의 최댓값 
						arr[i][j] = 1000000001;
					}
				}
			}
		}
		if(arr[n + m][m] < k) { // 주어진 자릿수로 만들 수 없는 K번째 수이면 
			System.out.println(-1);
		}
		else {
			// a를 선택했을 때 남은 문자로 만들 수 있는 모든 경우의 수가 K 보다 크면 
			while(!(n == 0 && m == 0)) {
				if(arr[n - 1 + m][m] >= k) {
					System.out.print("a");
					n--;
				}
				else { // 모든 경우의 수가 k보다 작으면 
					System.out.print("z");
					k = k - arr[n - 1 + m][m]; // k값 업데이트 
					m--;
				}
			}
		}
	}
}

오늘의 회고

오늘은 캐치 콘에서 하는 세미나 참가로 조합 문제 1문제를 풀었습니다. 이제 조합 문제 1문제가 남았고 이제 DP를 들어갈 차례입니다. DP까지 풀면 중요한 알고리즘은 다 풀었습니다. 개념 복습을 하면서 다시 문제 풀고 문제 복습을 하는 순서로 공부를 해야겠습니다.

80번 조약돌 꺼내기

내가 떠올린 풀이 해설

단순하게 확률로 풀었습니다. 조약돌 개수를 배열에 담아서 한 색깔의 조약돌만 뽑을 확률을 색깔별로 모두 구하고 각각의 확률을 더해 정답으로 출력했다.

ex) 5개 조약돌이 있는 색만 뽑을 확률 : 5/18 * 4/17

정확한 풀이 1

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

public class Baek13251 {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int M = Integer.parseInt(br.readLine());
		
		int[] cnt = new int[M];
		double sum = 0.0;
		StringTokenizer st = new StringTokenizer(br.readLine());
		for(int i = 0; i < M; i++) {
			cnt[i] = Integer.parseInt(st.nextToken());
			sum += cnt[i];
		}
		int K = Integer.parseInt(br.readLine());
		
		double answer = 0.0;
		for(int i = 0; i < M; i++) {
			double max = 1.0;
			for(int j = 0; j < K; j++) {
				max *= (cnt[i] - j) / (double)(sum - j);
			}
			answer += max;
		}
		System.out.println(answer);
	}
}

81번 순열의 순서

내가 떠올린 풀이 해설

이 문제는 조합 문제와 다르게 순열의 개념을 알아야 풀 수 있다. 순열은 순서가 다르면 다른 경우의 수로 인정된다. N자리로 만들 수 있는 순열의 경우의 수를 구해야 한다는 것이 이 문제의 핵심이다. 먼저 각 자리에서 사용할 수 있는 경우의 수를 구한다. 각 자리에서 구한 경우의 수를 모두 곱하면 모든 경우의 수가 나온다. 4자리로 표현되는 모든 경우의 수는 4! = 24이다. N자리로 만들 수 있는 순열의 모든 경우의 수는 N!이다.

k번째 순열 출력하기

1. 주어진 값(k)과 현재 자리(n) - 1에서 만들 수 있는 경우의 수를 비교한다.
2. 1에서 k가 더 작아질 때까지 경우의 수를 배수(cnt)로 증가시킨다.(순열의 순서를 1씩 늘림)
3. k가 더 작아지면 순열에 값을 저장하고 k를 k - (경우의 수 * (cnt - 1))로 업데이트한다.
4. 순열이 완성될 때까지 1 ~ 3을 반복하고 완료된 순열을 출력한다.

입력된 순열 순서 구하기

1. N자리 순열의 숫자를 받아 몇 번째 순서의 숫자인지 확인한다.(현재 숫자 - 자기보다 앞 숫자 중 이미 사용한 숫자)
2. 해당 순서 * (현재 자리 - 1에서 만들 수 있는 순열의 개수)를 k에 더한다.
3. 모든 자릿수에 관해 1 ~ 3을 반복한 후 K값을 출력한다.

정확한 풀이

import java.io.*;
import java.util.*;
public class Baek1722 {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		
		ArrayList<Integer> arr[] = new ArrayList[n];
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		int m = Integer.parseInt(st.nextToken());
		long f[] = new long[21];
		int[] s = new int[21];
		boolean visit[] = new boolean[21];
		f[0] = 1;
		for(int i = 1; i <= n; i++) {  // 팩토리얼 초기화 -> 각 자리수에서 만들 수 있는 경우의 수 
			f[i] = f[i - 1] * i;
		}
		
		if(m == 1) {
			long k = Long.parseLong(st.nextToken());
			for(int i = 1; i <= n; i++) {
				for(int j = 1, cnt = 1; j <= n; j++) {
					if(visit[j]) {
						continue;  // 이미 사용한 숫자는 사용할 수 없음 
					}
					if(k <= cnt * f[n - i]) { // 주어진 k에 따라 각 자리에 들어갈 수 있는 수 찾기 
						k -= ((cnt - 1) * f[n - i]);
						s[i] = j;
						visit[j] = true;
						break;
					}
					cnt++;
				}
			}
			for(int i = 1; i <= n; i++) {
				System.out.print(s[i] + " ");
			}
		}
		else {
			long k = 1;
			for(int i = 1; i <= n; i++) {
				s[i] = Integer.parseInt(st.nextToken());
				long cnt = 0;
				for(int j = 1; j < s[i]; j++) {
					if(visit[j] == false) {
						cnt++;   // 미사용 숫자 개수 만큼 카운트 
					}
				}
				k += cnt * f[n - i]; // 자릿수에 따라 순서 더하기 
				visit[s[i]] = true;
			}
			System.out.println(k);
		}
	}
}

오늘의 회고

오늘은 조합 중에 좀 어려운 문제 2문제를 풀었습니다. 두 번째 푼 문제는 아이디어를 떠올리는데 안 떠올라서 풀지 못했습니다. 알고리즘 문제를 잘 풀고 싶습니다. 아직은 많이 부족한 것 같습니다. 열심히 나아가겠습니다.

HTTP/1.0

HTTP/1.0은 기본적으로 한 연결당 하나의 요청을 처리하도록 설계되어있다. 서버로부터 파일을 가져올 때마다 TCP의 3-way-handshake를 계속해서 열어야 하기 때문에 RTT가 증가하는 단점이 있다.

RTT

패킷이 목적지에 도달하고 나서 다시 출발지로 돌아오기까지 걸리는 시간, 패킷 왕복 시간

RTT 증가를 해결하기 위한 방법

매번 연결할 때마다 RTT가 증가하니 서버에 부담이 많이 가고 사용자 응답 시간이 길어졌다. 이를 해결하기 위해 이미지 스플리팅, 코드 압축, 이미지 Base64 인코딩을 사용했다.

이미지 스플리팅

많은 이미지를 다운로드하게 되면 과부하가 걸리기 때문에 많은 이미지가 협쳐 있는 하나 이미지를 다운로드하고, 이를 기반으로 background-image의 position을 이용해 이미지를 표기하는 방법이다.

코드 압축

코드압축은 코드를 압축해 개행 문자, 빈칸을 없애서 코드의 크기를 최소화하는 방법이다.

개행 문자, 띄어쓰기 등이 사라져 코드가 압축되면 코드 용량이 줄어든다.

이미지 Base64 인코딩

이미지 파일을 64진법으로 이루어진 문자열로 인코딩하는 방법이다. 이 방법을 사용하면 서버와의 연결을 열고 이미지에 대해 서버에 HTTP 요청을 할 필요가 없다는 장점이 있다. 하지만 Base64 문자열로 변환할 경우 37% 정도 크기가 더 커지는 단점이 있다.

HTTP/1.1

매번 TCP 연결을 하는 것이 아니라 한 번 TCP 초기화를 한 이후에 keep-alive라는 옵션으로 여러 개의 파일을 송수신할 수 있게 바뀌었다. 한번 TCP 3-way-shake 가 발생하면 그다음부터 발생하지 않는 것을 볼 수 있다. 하지만 문서 안에 포함된 다수의 리소스(이미지, css, script)를 처리하려면 요청할 리소스 개수에 비례해서 대기 시간이 길어지는 단점이 있다.

HOL Blocking

HOL Blocking은 네트워크에서 같은 큐에 있는 패킷이 그 첫 번째 패킷에 의해 지연될 때 발생하는 성능 저하 현상이다. 예를 들어 image.jpg와 style.css, data.xml을 다운로드받을 때 보통은 순차적으로 잘 받아지지만 image.jpg가 느리게 받아진다면 그 뒤에 있는 것들이 대기하게 되며 다운로드가 지연되는 상태가 된다.

무거운 헤더 구조

HTTP/1.1의 헤더에는 쿠키등 많은 메타데이터가 들어 있고 압축이 되지 않아 무거웠다.

HTTP/2.0

HTTP/2.0은 HTTP/1.x 보다 지연 시간을 줄이고 응답 시간을 더 빠르게 할 수 있으며 멀티플렉싱, 헤더 압축, 서버 푸시, 요청의 우선순위를 처리를 지원하는 프로토콜이다.

멀티플렉싱

멀티플렉싱이란 여러 개의 스트림을 사용하여 송수신한다는 것이다. 이를 통해 특정 스트림의 패킷이 손실되었다고 하더라도 해당 스트림에만 영향을 미치고 나머지 스트림은 멀쩡하게 동작할 수 있다. 멀티플렉싱을 통해 단일 연결을 사용하여 병렬로 여러 요청을 받을 수 있고 응답을 줄 수 있다. 이렇게 되면 HTTP/1.x에서 발생하는 HOL Blocking을 해결할 수 있다.

스트림

시간이 지남에 따라 사용할 수 있게 되는 일련의 데이터 요소를 가리키는 데이터 흐름

헤더 압축

HTTP/1.x에서 크기가 큰 헤더의 문제를 HTTP/2.0에서는 헤더 압축을 써서 해결하는데, 허프만 코딩 압축 알고리즘을 사용하는 HPACK 압축 형식을 가진다.

허프만 코딩

문자열을 문자 단위로 쪼개 빈도수를 세어 빈도가 높은 정보는 적은 비트 수를 사용하여 표현하고, 빈도가 낮은 정보는 비트 수를 많이 사용하여 표현해서 전체 데이터의 표현에 필요한 비트 양을 줄이는 원리이다.

서버 푸시

HTTP/1.1에서는 클라이언트가 서버에 요청을 해야 파일을 다운받을 수 있었다면, HTTP/2는 클라이언트 요청 없이 서버가 바로 리소스를 푸시할 수 있다.

HTTPS

HTTP/2는 HTTPS 위에서 동작한다. HTTPS는 애플리케이션 계층과 전송 계층 사이에 신뢰 계층인 SSL/TLS 계층을 넣은 신뢰할 수 있는 HTTP 요청이다.

SSL/TLS

SSL/TLS는 전송 계층에서 보안을 제공하는 프로토콜이다. 클라이언트와 서버가 통신할 때 SSL/TLS를 통해 제삼자가 메시지를 도청하거나 변조하지 못하도록 한다. SSL/TLS를 통해 공격자가 서비인 척하며 사용자 정보를 가로채는 네트워크 상의 인터셉터를 방지할 수 있다.

SSL/TLS는 보안 세션을 기반으로 데이터를 암호화하며 보안 세션이 만들어질 때 인증 메커니즘, 키 교환 암호화 알고리즘, 해싱 알고리즘이 사용된다. 참고로 TLS 1.3은 사용자가 이전에 방문한 사이트로 다시 방문한다면 SSL/TLS에서 보안 세션을 만들 때 걸리는 통신을 하지 않아도 된다. 이를 0-RTT라 한다.

보안 세션

보안 세션이란 보안이 시작되고 끝나는 동안 유지되는 세션을 말하고, SSL/TLS는 핸드셰이크를 통해 보안 세션을 생성하고 이를 기반으로 상태 정보 등을 공유한다. 클라이언트와 서버와 키를 공유하고 이를 기반으로 인증, 인증 확인 등의 작업이 일어나는 단 한 번의 1-RTT가 생긴 후 데이터를 송수신하는 것을 볼 수 있다. 클라이언트에서 사이퍼 슈트를 서버에 전달하면 서버는 받은 사이퍼 슈트의 암호화 알고리즘 리스트를 제공할 수 있는지 확인한다. 제공할 수 있다면 서버에서 클라이언트로 인증서를 보내는 인증 메커니즘이 시작되고 이후 해싱 알고리즘 등으로 암호화된 데이터의 송수신이 시작된다.

사이퍼 슈트

사이퍼 슈트는 프로토콜, AEAD 사이퍼 모드, 해싱 알고리즘이 나열된 규약을 말하며 다섯 개가 있다.

• TLS_AES_128_GCM_SHA256
• TLS_AES_256_GCM_SHA384
• TLS_CHACHA20_POLY1305_SHA256
• TLS_AES_128_CCM_SHA256
• TLS_AES_128_CCM_8_SHA256

TLS_AES_128_GCM_SHA256에는 세가지 규약이 들어 있는데 TLS는 프로토콜, AES_128_GCM은 AEAD 사이퍼 모드, SHA256은 해싱 알고리즘을 뜻한다.

AEAD 사이퍼 모드

AEAD는 데이터 암호화 알고리즘이며 AES_128_GCM 등이 있다. 예를 들어 AES_128_GCM이라는 것은 128비트의 키를 사용하는 표준 블록 함호화 기술과 병렬 계산에 용이한 암호화 알고리즘 GCM이 결합된 알고리즘을 뜻한다.

암호화 알고리즘

키 교환 암호화 알고리즘으로는 대수곡선 기반의 ECDHE 또는 모듈식 기반의 DHE를 사용한다. 둘 다 디피-헬만 방식을 근간으로 만들어졌다.

디피-헬만 키 교환 암호화 알고리즘

디피-헬만 키 교환 암호화 알고리즘은 암호키를 교환하는 하나의 방법이다.

처음에 공개 값을 공유하고 각자의 비밀 값과 혼합한 후 혼합 값을 공유한다. 각자 비밀 값과 또 혼합한다. 그 이후에 공통의 암호키가 생성되는 것이다.

SHA-256 알고리즘

SHA-256 알고리즘은 해시 함수의 결괏값이 256비트인 알고리즘이며 해싱을 해야 할 메세지에 1을 추가하는 등 전처리를 하고 전 처리된 메시지를 기반으로 해시를 반환한다.

HTTPS 구축 방법

직접 CA에서 구매한 인증키를 기반으로 HTTPS 서비스를 구축하거나, 서버 앞단의 HTTPS를 제공하는 로드밸런서를 두거나, 서버 앞단에 HTTPS를 제공하는 CDN을 둬서 구축한다.

HTTP/3

TCP 위에서 돌아가는 HTTP/2와는 달리 HTTP/3은 QUIC이라는 계층 위에서 돌아가며, TCP 기반이 아닌 UDP 기반으로 돌아간다.

QUIC는 TCP를 사용하지 않기 때문에 통신을 시작할 때 번거로운 3-way-handshake과정을 거치지 않아도 된다. QUIC는 첫 연결 설정에 1-RTT만 소요된다. QUIC는 순방향 오류 수정 메커니즘이 적용되었다. 전송한 패킷이 손실되었다면 수신 측에서 에러를 검출하고 수정하는 방식이며 열악한 네트워크 환경에서도 낮은 패킷 손실률을 자랑한다.

조합

조합은 n개의 숫자에서 r개를 뽑는 경우의 수를 뜻한다. 조합과 비교되는 순열은 n개의 숫자 중 r개를 뽑아 순서를 고려해 나열할 경우의 수를 이야기한다. 순열과 조합의 차이는 순서의 고려 유무이다. 조합은 실제 알고리즘 코딩 테스트에서 순열보다 조합의 출제 빈도수가 높고, 응용할 문제도 많다. 조합은 동적 계획법의 시작이라고 볼 수 있다. 따라서 알고리즘에서 조합을 구현할 때는 수학 공식을 코드화하지 않고 점화식을 사용해 표현한다.

조합의 점화식

1. 특정 문제를 가정하기

   5개 데이터에서 3개를 선택하는 조합의 경우의 수를 푸는 문제로 가정

2. 모든 부분 문제가 해결된 상황이라고 가정하고 지금 문제 생각하기

   먼저 5개의 데이터 중 4개를 이미 선택이 완료된 데이터라고 가정한다. 그리고 마지막 데이터의 선택 여부에 따른 경우의 수를 계산한다. 만약 마지막 데이터를 포함해 총 3개의 데이터를 선택하려면 선택이 완료됐다고 가정한 4개의 데이터에서 2개를 선택해야 된다. 마지막 데이터를 포함하지 않고 총 3개의 데이터를 선택하려면 이전 데이터 4개 중 3개를 선택해야 한다. 2가지 경우의 수를 합치면 데이터 5개 중 3개를 선택하는 경우의 수가 나온다.

5개 중 3개를 선택하는 경우의 수 점화식

D[5][3] = D[4][2] + D[4][3]

조합 점화식

D[i][j] = D[i - 1][j] + D[i - 1][j - 1]

점화식이 간단하므로 외울 수도 있지만, 원리를 정확하게 이해하는 것이 문제 응용하기 유리하다.

78번 부녀회장이 될 테야

내가 떠올린 풀이 해설

a층의 b호에 살려면 자신의 아래층(a - 1)의 1호부터 b호까지 사람들의 수의 합만큼 사람들을 데려와 살아야 한다를 보고 점화식을 세워야 한다. 0층의 사람들은 i호에 i명이 살고 있다고 한다. arr[0][r] = r 모든 층의 1호는 0층 1호부터 1명이어서 모든 층이 1명이다. arr[j][1] = 1 a - 1층의 1호부터 b호까지의 점화식은 arr[j][r] = arr[j][r - 1] + arr[j - 1][r]이다. 

정확한 풀이

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

public class Baek2775 {
	static int k, n;
	static int[][] arr;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(br.readLine());
		for(int i = 0; i < T; i++) {
			k = Integer.parseInt(br.readLine());
			n = Integer.parseInt(br.readLine());
			arr = new int[15][15];
			for(int j = 1; j < 15; j++) {
				for(int r = 1; r < 15; r++) {
					arr[0][r] = r;
					arr[j][1] = 1;
					arr[j][r] = arr[j - 1][r] + arr[j][r - 1];
				}
			}
			System.out.println(arr[k][n]);
		}
	}
}

79번 다리 놓기

내가 떠올린 풀이 해설

이 문제는 M개의 사이트에서 N개를 선택하는 문제로 변경할 수 있다. 겹치지 않게 하려면 동쪽에서 N개를 선택한 후 서쪽과 동쪽의 가장 위쪽의 사이트에서부터 차례대로 연결할 수 밖에 없기 때문이다. 조합 문제로 변형해 풀 수 있다. 조합 점화식은 많은 문제에서 응용되기 때문에 꼭 알고 있어야 한다.

정확한 풀이

import java.io.*;
import java.util.*;
public class Baek1010 {
	static long[][] arr;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		arr = new long[31][31];
		for(int i = 0; i <= 30; i++) {
			arr[i][0] = 1;
			arr[i][i] = 1;
			arr[i][1] = i;
		}
		for(int i = 2; i <= 30; i++) {
			for(int j = 1; j < i; j++) {  // 고르는 수 개수가 전체 개수를 넘을 수 없다 .
				arr[i][j] = arr[i - 1][j - 1] + arr[i - 1][j]; // 조합 점화식 
			}
		}
		int T = Integer.parseInt(br.readLine());
		for(int i = 0; i < T; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			int n = Integer.parseInt(st.nextToken());
			int m = Integer.parseInt(st.nextToken());
			System.out.println(arr[m][n]);
		}
	}
}

오늘의 회고

오늘은 조합 문제 2문제를 풀었습니다. 어렵지 않고 기본 문제였고 점화식을 세우는 방법에 대해 학습할 수 있었습니다. 조합 점화식은 꼭 이해하고 암기가 되어 있어야할 것 같습니다. 장마라 습하고 눅눅해서 불쾌지수가 높아지는데 다들 파이팅입니다.

76번 이항 계수 1

내가 떠올린 풀이 해설

조합에서 가장 기본이 되는 문제이다. 일반 점화식을 이용하면 쉽게 해결할 수 있는 문제이다. n과 k를 입력받고 DP 배열을 선언한다. 배열은 arr [n + 1][n + 1] 그리고 DP 배열의 값을 다음과 같이 초기화한다. arr [i][1] = i -> i 개 중 1개를 뽑는 경우의 수는 i개 arr[i][0] = 1 -> i 개 중 1개도 선택하지 않는 경우의 수는 1개 arr[i][i] = i -> i 개 중 i 개를 선택하는 경우의 수는 1개이다. 점화식으로 DP 배열의 값을 채운다. arr[i][j] = arr[i - 1][j] + arr[i - 1][j - 1] 마지막으로 arr [n][k] 값을 출력한다.

정확한 풀이

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

public class Baek11050 {

	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());
		int[][] arr = new int[n + 1][n + 1];
		for(int i = 0; i <= n; i++) {
			arr[i][0] = 1; // i 개에서 1개도 선택하지 않는 경우의 수는 0개 
			arr[i][i] = 1; // i 개에서 모두 선택하는 경우의 수는 1개 
			arr[i][1] = i; // i 개에서 1개 선택 경우의 수는 i개 
		}
		for(int i = 2; i <= n; i++) {
			for(int j = 1; j < i; j++) { // 고르는 수의 개수가 전체 개수를 넘을 수 없음 
				arr[i][j] = arr[i - 1][j - 1] + arr[i - 1][j]; // 조합 점화식 
			}
		}
		System.out.println(arr[n][k]);
	}
}

내가 떠올린 풀이 해설

바로 앞에 문제와 비슷한 문제이다 n의 값이 커지고 결괏값을 10,007로 나눈 나머지를 출력하라는 요구사항이 있다. 모듈러 연산의 특성을 이용해 문제를 풀었다. 모듈러 연산은 덧셈에 관해 위와 같이 각각 모듈러를 하고, 모듈러 연산을 수행한 것과 두 수를 더한 후 수행한 것의 값이 동일하므로 이 문제에서 arr배열에 결괏값이 나올 때마다 모듈러 연산을 수행하는 로직을 추가하면 문제를 해결할 수 있다.

모듈러 연산의 특성

(A mod N + B mod N) mod N = (A + B) mod N

정확한 풀이

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

public class Baek11051 {

	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());
		int[][] arr = new int[n + 1][n + 1];
		int pow = 10007;
		for(int i = 0; i <= n; i++) {
			arr[i][0] = 1;
			arr[i][i] = 1;
			arr[i][1] = i;
		}
		for(int i = 2; i <= n; i++) {
			for(int j = 1; j < i; j++) {
				arr[i][j] = (arr[i - 1][j - 1] + arr[i -1][j]) % pow;
			}
		}
		System.out.println(arr[n][k]);
	}
}

오늘의 회고

오늘은 DP 문제를 풀기 위해 먼저 학습해야 되는 조합에 대해서 학습하고 조합에 관련된 기본 문제 2문제를 풀었습니다. DP가 알고리즘 문제 풀이에서 2번째로 중요하다고 들었습니다. 매번 출제되는 문제인 만큼 확실하게 학습하고 넘어가겠습니다.