고민의 흔적

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까지 풀면 중요한 알고리즘은 다 풀었습니다. 개념 복습을 하면서 다시 문제 풀고 문제 복습을 하는 순서로 공부를 해야겠습니다.

로그인, 쿠키와 세션, JWT 토큰

HTTP란?

stateless 하다. 연결을 끊는 순간 사용자와 서버의 통신이 끝나며 상태 정보는 유지하지 않는 특성이 있다.

브라우저에서 상태를 유지하는 방법

• 쿠키와 세션
• 토큰 기반 방식

세션

서버와 클라이언트의 연결이 활성화된 상태

세션 ID

웹 서버 메모리에 저장되는 클라이언트에 대한 유니크한 ID(서버 또는 데이터베이스에 저장)

쿠키

• 키 - 값으로 구성된 작은 데이터 조각
• 쿠키에 담긴 데이터는 브라우저에서 관리된다. 하지만 보통 만료 날짜를 서버에서 설정한다.
• 이름, 값, 만료 날짜 등으로 구성

쿠키와 세션

1. 처음 로그인 -> 쿠키, 세션 ID 생성 그 이후 다시 요청했을 때 HTTP 헤더에 쿠키를 포함시켜 요청한다.
2. 해당 쿠키에 맞는 세션 ID로 전에 로그인했던 아이디인지 확인
3. 로그인을 유지

XSS(Cross Site Scripting)

쿠키는 클라이언트에서 자바스크립트로 조회가 가능하다. 공격자들이 자바스크립트로 쿠키를 가로채고자 시도를 하는데 이를 XSS라고 한다.

해결 방법 : HTTP Only Cookie 또는 secure cookie를 사용한다.

• Set-Cookie : 쿠키명 = 쿠키값; path=/ ; secure
• Set-Cookie : 쿠키명 = 쿠키값; path=/ ; HttpOnly

보통은 HTTP 관련 라이브러리에 적혀있는 대로 사용한다.

ex) axios.defaults.withCredentials = true;

쿠키 - 세션 방식의 단점

로그인할 때마다 세션 ID를 저장해야 돼서 로그인 중인 유저의 수가 늘어난다면 서버의 메모리 과부하 등 악영향을 미친다. 

토큰 기반 인증 방식

JWT토큰 인증은 토큰 기반 인증서버를 통해서 하게 하고 서버는 stateless 하게 내버려 두자. 요청 -> 토큰 생성 -> 이후 사용자가 토큰을 헤더(authoriztion 키에 넣어서 요청, 이 토큰을 기반으로)

JWT(JSON Web Token, RFC 7519)

헤더, 페이로드, 서명으로 이루어져 있으며 JSON 객체로 인코딩 된다. 메세지 인증, 암호화에 사용

Header

어떠한 방법의 서명 알고리즘을 사용할 것인가에 대한 정보

Payload

데이터, 토큰 발급자, 토큰 유효기간(인증이 필요한 최소한의 정보만)

Signature

헤더에 정의된 알고리즘으로 인코딩된 헤더와 페이로드를 합친 값, 그리고 비밀키를 기반으로 생성된 서명 값

JWT 장점

사용자가 인증되면 사용자는 모든 시스템에서 사용할 수 있는 보안 토큰을 받습니다. 즉, 단일 엔드포인트를 생성해서 다른 모든 서버 간의 API 상호작용을 인증할 수 있다는 점에서 좋다.

JWT의 주요한 이점은 사용자 인증에 필요한 모든 정보는 토큰 자체에 포함하기 때문에 별도의 인증 저장소가 필요 없다.

확장성, 디버깅, 사이즈가 작음, JWT토큰 자체가 독립적이다.

JWT 단점

더 많은 필드가 추가되면 토큰이 비대해져 트래픽에 영향

탈취하여 디코딩하면 데이터를 볼 수 있다.

브라우저 렌더링 과정

1. DOM 트리 구축

하나의 html 페이지는 div, span 등 각각의 요소를 가진다. 각 요소는 하나하나 노드로 설정이 되어 트리 형태로 저장된다. 이를 DOM 트리라고 한다. 예를 들어 div > span, span이 있다면 div라는 부모 노드 밑에 span이라는 자식 노드가 2개 생기는 것이다.

2. 렌더 트리와 렌더 레이어 생성

각각의 노드는 CSS파서에 의해 정해진 스타일 규칙이 적용되어 있다. span.color="red"는 노드 색깔이 빨간색이다 등을 말한다. 이런 규칙에 따라 CSSOM이라는 트리가 만들어지고 미리 만들어놓은 DOM트리 내에 있는 노드와 함께 렌더 객체가 생성되며 이들이 모여 병렬적인 렌더 트리가 생성된다. 상속적인 스타일은 부모 노드에만 위치하도록 설계하는 등의 최적화를 거쳐 렌더 레이어가 완성된다.

3. 렌더 레이어를 대상으로 Layout설정

이때 좌표는 보통 부모를 기준으로 설정된다. Global Layout은 브라우저 사이즈가 증가하거나 폰트 사이즈가 커지면 변경된다.

4. 렌더레이어를 대상으로 칠하기

픽셀마다 점을 찍듯 칠한다. 이를 레스터화라고도 한다.

5. 레이어 합치기 및 표기

각각의 레이어로부터 비트맵이 생성되고 GPU에 텍스처로 업로드된다. 그다음 택스처들은 서로 합쳐져 하나의 이미지로 렌더링 되며 화면으로 출력된다.

웹 브라우저의 캐시

대표적인 캐시로는 웹 브라우저의 작은 저장소 쿠키, 로컬 스토리지, 세션 스토리지가 있다. 이러한 것들은 보통 사용자의 커스텀한 정보나 인증 모듈 관련 사항들을 웹 브라우저에 저장해서 추후 서버에 요청할 때 자신을 나타내는 아이덴티티나 중복 요청 방지를 위해 쓰인다.

쿠키

쿠키는 만료기한이 있는 키 - 값 저장소이다. same site 옵션을 strict로 설정하지 않았을 경우 다른 도메인에서 요청했을 때 자동 전송되며, 4KB까지 데이터를 저장할 수 있고 만료기한을 정할 수 있다. 쿠키를 설정할 때는 document.cookie로 쿠키를 볼 수 없게 httponly 옵션을 거는 것이 중요하며, 클라이언트 또는 서버에서 만료기한 등을 정할 수 있는데 보통 서버에서 만료기한을 정한다.

로컬 스토리지

로컬 스토리지는 만료기한이 없는 키 - 값 저장소이다. 10MB까지 저장할 수 있으며 웹브라우저를 닫아도 유지되고 도메인 단위로 저장, 생성된다. 클라이언트에서만 수정 가능하다.

세션 스토리지

세션 스토리지는 만료기한이 없는 키 - 값 저장소이다. 탭 단위로 세션 스토리지를 생성하며, 탭을 닫을 때 해당 데이터가 삭제된다. 5MB까지 저장이 가능하다. 클라이언트에서만 수정 가능하다.

HTTP의 상태 코드

1xx(정보)

요청을 받았으며 프로세스를 계속한다.

2xx(성공)

요청을 성공적으로 받았으며 인식했고 수용한다.

• 200 OK : 요청을 성공적으로 되었습니다.
• 201 Created : 요청이 성공적이었으며 그 결과로 새로운 리소스가 생성되었다.

3xx(리다이렉션)

요청 완료를 위해 추가 작업 조치가 필요하다

• 301 Moved perma nently : 이 응답 코드는 요청한 리소스의 URI가 변경되었음을 의미한다. 변경된 새로운 URI를 응답에서 주는 것이 좋다.

4xx(클라이언트 오류)

요청의 문법이 잘못되었거나 요청을 처리할 수 없다.

• 400 Bad Request : 이 응답은 잘못된 문법으로 인하여 서버가 요청을 이해할 수 없음을 의미한다.
• 401 Unauthorized : 클라이언트의 인증이 되지 않음을 의미한다.

5xx(서버 오류)

서버가 명백히 유효한 요청에 대해 충족을 실패했다.

• 500 Internal Server Error : 서버에 오류가 있음을 의미한다.

HTTP의 메서드

POST : 자원을 생성

보통 하위 자원을 생성한다. 성공적으로 생성되면 HTTP 상태 201을 반환

GET : 읽기

성공 시 200, 오류의 경우 가장 자주 404(Not Found) 또는 400(Bad Request)을 반환한다. 데이터를 수정, 삭제하는데 반드시 사용하면 안 된다.

PUT : 업데이트(전체 자원)

요청을 보낼 때 전체를 보내야 한다.

PATCH : 업데이트(일부 자원)

요청을 보낼 때 수정하는 일부분을 보내야 한다.

DELETE : 삭제

REST API

API란?

API는 소프트웨어와 소프트웨어 사이 데이터 전송을 가능하게 하는 프로그램이다.

Uniform-Interface

자원들이 각각의 독립적인 인터페이스를 가져야 한다.

• 웹페이지를 변경했다고 웹 브라우저를 업데이트하는 일은 없어야 된다.
• HTTP 명세나 HTML 명세가 변경되어도 웹페이지는 잘 작동해야 한다.

REST API 아키텍처 규칙

1. Self - descriptive messages

HTTP Header에 타입을 명시하고 각 메시지(자원)들은 MIME types에 맞춰 표현되어야 한다.

예를 들어. json을 반환한다면 application/json으로 명시해주어야 한다. MIME types는 문서, 파일 등의 특성과 형식을 나타내는 표준이다. 'font/ttf', 'text/plain', 'text/csv' 등

2. HATEOAS 구조

하이퍼링크에 따라 다른 페이지를 보여줘야 하며 데이터마다 어떤 URL에서 원했는지 명시해주어야 한다.

3. Stateless

이 규칙은 HTTP 자체가 Stateless이기 때문에 HTTP를 이용하는 것만으로도 만족된다. 즉 REST API를 제공해주는 서버는 세션(session)을 해당 서버 쪽에 유지하지 않는다는 의미이다.

4. Cacheable

HTTP는 원래 캐싱이 된다. 새로고침을 하면 304가 뜨면서 원래 있던 js와 css이미지 등을 불러오는 것을 볼 수 있다. 이러한 캐싱은 네트워크 요청을 줄여주며 이는 UX 향상에도 도움이 된다. 네트워크 요청 시 해당되는 자원들을 복사해서 메모리에 저장해두었다가 또 같은 요청 시 네트워크 요청을 하지 않고 브라우저 메모리에 있던 자원을 다시 반환한다. HTTP 메서드 중 GET에 한정되며 Cache-Control:max-age=100(100초) 이런 식으로 한정된 시간을 정할 수가 있다. 캐싱된 데이터가 유효한지 판단하기 위해 Last-modifed와 Etag를 쓴다. Etag는 전달되는 값에 태그를 붙여서 캐싱되는 자원인지를 확인해주는 것이다.

5. Client-Server 구조

클라이언트와 서버가 서로 독립적인 구조를 가져야 한다. 물론 이는 HTTP를 통해 가능한 구조이다. 서버에서 HTTP 표준만 지킨다면 웹에서는 그에 따른 화면이 잘 나타나게 된다. 서버는 API를 제공하고 그 API에 맞는 비즈니스 로직을 처리하면 된다. 클라이언트에서는 HTTP로 받는 로직만 잘 처리하면 된다.

6. Layered System

계층구조로 아키텍처를 만들 수 있다는 것을 뜻한다.

URI 규칙

1. 동작은 HTTP 메서드로 해야 한다. 수정 = put, 삭제 = delete, 추가 = post, 조회 = get을 이용해야 한다. 예를 들어 /books/delete/1 이렇게 표기하면 안 된다.
2. 확장자는 표기하지 말아야 한다.
3. 동사가 아닌 명사로만 표기해야 한다. 유저가 책을 소유한다라고 하려면 유저/유저아이디/inclusion/책/책 아이디
4. URI는 계층적인 내용을 담고 있다. /집/아파트/전세 이런 식으로 내려가야 한다.
5. 소문자로 쓰며 너무 길 경우에는 *****-**** 를 쓴다.
6. HTTP 응답 상태 코드를 활용한다.

도서관 시스템의 REST API 예시

get('/books/') : 모든 책을 조회한다.

post('/books/booksid') : 책을 생성한다.

put('/books/'booksid) : 책을 수정한다.

get('/books/booksid') : 특정 책을 조회한다.

put('/users/userid/books/booksid') : 어떤 유저가 특정 책을 빌린다.

patch('/users/userid/books/booksid') : 어떤 유저가 특정 책을 빌린다.

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문제를 풀었습니다. 두 번째 푼 문제는 아이디어를 떠올리는데 안 떠올라서 풀지 못했습니다. 알고리즘 문제를 잘 풀고 싶습니다. 아직은 많이 부족한 것 같습니다. 열심히 나아가겠습니다.

쿠버네티스 입문반 Introduction to Docker

첫 수업으로 Introduction to Docker 강의를 들었습니다. 구글 클라우드 환경에서 터미널에 접속해 docker를 실행하고 실습하는 시간이 되었습니다. docker기본을 배우고 듣는 수업이라 어려운 수업은 아니였습니다. 강의가 영어로 되어있어 살짝 힘든 것 말고는 좋은 학습이 될 것 같습니다. 혹시 몰라 구글에서 사용하는 아이디는 모자이크 처리하였습니다.

구글 클라우드 쉘에 접속한 모습입니다. 여기서 쿠버네티스 실습을 진행합니다.

docker run hello-world

위의 사진을 잘 보시면 Unable to find image를 보실 수 있습니다. docker 데몬은 hello-world 이미지를 검색했지만 로컬에서 이미지를 찾지 못해서 Docker Hub라는 공개 레지스트리에서 이미지를 가져와서 해당 이미지에서 컨테이너를 생성하고 컨테이너를 실행했습니다.

docker images

docker images 명령어입니다. 이 스크린 샷은 못 찍었습니다. 이미지 목록을 확인하는 명령어입니다.

docker run hello-world

정상적으로 실행되었습니다. Hello from Docker !

docker ps

docker ps 명령어입니다. 실행 중인 컨테이너가 없습니다. 이전에 실행한 hello-world 컨테이너가 이미 종료되었습니다. 

docker ps -a

종료된 컨테이너를 포함하여 모든 컨테이너를 보려면 docker ps에서 - a 옵션만 추가시켜주면 됩니다.

mkdir test
cd test

test 디렉터리를 만들고 test 디렉터리에 들어갑니다. 

cat > Dockerfile <<EOF
# 공식 Node 런타임을 부모 이미지로 사용 
FROM node:lts
# 컨테이너의 작업 디렉터리를 /app으로 설정 
WORKDIR /app
# 현재 디렉터리 내용을 /app으로 설정
ADD . /app
# 컨테이너의 포트 80을 외부에서 사용할 수 있도록 설정.
EXPOSE 80
# 컨테이너가 실행될 때 node를 사용하여 app.js를 실행합니다. 
CMD ["node", "app.js"]
EOF

dockerfile을 만드는 방법에 대한 설명입니다. 간단하게 실습하는 것이라 명령어에 잘 모르실 경우 제 블로그 참고 바랍니다.

https://lusida-coding.tistory.com/35?category=1031465 

cat > app.js <<EOF
const http = require('http');
const hostname = '0.0.0.0';
const port = 80;
const server = http.createServer((req, res) => {
    res.statusCode = 200;
    res.setHeader('Content-Type', 'text/plain');
    res.end('Hello World\n');
});
server.listen(port, hostname, () => {
    console.log('Server running at http://%s:%s/', hostname, port);
});
process.on('SIGINT', function() {
    console.log('Caught interrupt signal and will exit');
    process.exit();
});
EOF

노드 애플리케이션 파일을 만듭니다. 포트 80에서 수신 대기하고 Hello World를 출력하는 간단한 HTTP 서버입니다.

docker build -t node-app:0.1 .

이미지를 빌드합니다. "."은 현재 디렉터리를 의미하므로 Dockerfile이 있는 디렉토리 내에서 이 명령어를 실행해야 합니다.

node은 기본 이미지이며 node-app빌드한 이미지입니다. node먼저 제거하지 않고는 node-app을 제거할 수 없습니다. 이미지의 크기는 VM에 비해 상대적으로 작습니다.

docker run -p 4000:80 --name my-app node-app:0.1

방금 빌드한 이미지를 기반으로 컨테이너를 실행합니다. 현재 터미널에서 실행되는 것을 확인하실 수 있습니다.

curl http://localhost:4000

--name은 원하는 경우 컨테이너의 이름을 지정할 수 있습니다.호스트 의 -p포트 4000을 컨테이너의 포트 80에 매핑하도록 명령어를 작성했다. 이제 http://localhost:4000. 포트 매핑이 없으면 localhost의 컨테이너에 연결할 수 없습니다. 다른 터미널을 열고 서버를 테스트합니다. Hello World가 정상적으로 출력되는 것을 확인하실 수 있습니다.

docker stop my-app && docker rm my-app

컨테이너를 중지하고 컨테이너를 지우는 명령어입니다.

docker run -p 4000:80 --name my-app -d node-app:0.1

컨테이너를 백그라운드에서 실행하려면(터미널 세션에 연결되지 않음) -d옵션을 지정해야 합니다.

docker logs my-app

컨테이너의 로그를 확인하는 명령어입니다.

docker logs -f [container_id]

 컨테이너가 실행될 때 로그의 출력을 실시간으로 확인하려면 -f옵션을 사용하면 됩니다.

docker build -t node-app:0.2 .

app.js파일에서 Hello World를 Hello Cloud로 수정 후 node-app:0.2로 빌드를 진행하였습니다.

2단계에서 기존 캐시 계층을 사용하고 있음을 알 수 있습니다. 3단계부터 에서 변경했기 때문에 레이어가 수정됩니다.

docker run -p 8080:80 --name my-app-2 -d node-app:0.2
curl http://localhost:8080
curl http://localhost:4000

새 이미지 버전으로 다른 컨테이너를 실행합니다. 호스트 포트 4000은 이미 사용 중이기 때문에 사용할 수 없습니다. 컨테이너를 실행 후 curl로 8080과 4000에 접속 테스트를 진행하였습니다. 8080에는 모자이크로 잘리긴 했으나 Hello to Cloud가 출력되었고 4000에는 수정하기 전인 Hello World가 출력되었습니다.

docker exec -it [container_id] bash

실행 중인 컨테이너 내에서 Bash 세션을 시작할 때는 명령어 마지막에 bash라고 지정해주면 됩니다. docker exec -it를 사용하면 pseudo-tty를 할당하고 표준 입력을 열린 상태로 유지하여 컨테이너와 상호 작용할 수 있습니다. bash는 Dockerfile에 WORKDIR지정된 디렉터리(/app)에서 실행되었습니다.

docker inspect [container_id]

Docker inspect를 사용하여 Docker에서 컨테이너의 메타데이터를 확인할 수 있습니다.

docker inspect --format='{{range .NetworkSettings.Networks}}{{.IPAddress}}{{end}}' [container_id]

docker tag node-app:0.2 gcr.io/[project-id]/node-app:0.2

도커를 푸시를 해주려면 컨테이너에 태그가 붙어있어야 합니다. 제 개인 도커 레파지토리에 푸시를 하려면 제 도커 레파지토리 이름 태그를  붙여줘야 합니다.

docker push gcr.io/[project-id]/node-app:0.2

도커를 gcr에 푸시하는 명령어입니다. 

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