숫자형 이넘

기본 값

타입 스크립트 enum에서 별도의 값을 지정하지 않으면 숫자형 이넘이 되며 아래와 같이 0부터 차례대로 값을 할당받게 된다.

enum Shoes{
  Nike,
  Adidas
}

Shoes.Nike //0
Shoes.Adidas //1

직접 값을 할당하는 방법

이넘을 정의할 때 각 값에 대해 직접 값을 할당해주면 된다.

enum Shoes{
  Nike = 10000,
  Adidas = 20000
}

Shoes.Nike //10000
Shoes.Adidas //20000

문자형 이넘

enum Shoes{
  Nike = '나이키',
  Adidas = '아디다스'
}

Shoes.Nike //나이키
Shoes.Adidas //아디다스

이넘 활용

정의한 이넘은 타입처럼 사용할 수 있다. 아래 예시를 보자.

enum Answer{
  Yes = "yes",
  No = "no"
}

function processAnswer(answer: Answer) {
  if (answer === Answer.Yes) {
    console.log("NICE~");
  }else if (answer === Answer.No) {
    console.log("WHY ?");
  }
}

//string은 에러를 나타내게 된다. 
//이넘에서 제공하는 데이터만 전달할 수 있게 된다.
processAnswer(Answer.Yes);

예시를 보면 processAnswer라는 함수의 인자로 전달할 answer의 타입을 string으로 할수도 있지만 Answer로 제한해주고 있는 모습니다. 이렇게 타입을 지정해줄 경우 조건문에 따라 특정 로직을 실행하는 등의 작업이 좀 더 명확해진다.

별칭과의 차이점은?

우선 나는 타입 별칭과 무엇이 다른가 궁금했다. 큰 차이는 아래와 같다.

• 타입 별칭도 interface와 동일하게 복잡한 레벨의 타입을 지정할 수 있지만 타입 별칭은 타입을 새로 추가하는 것이 아니고 말 그대로 별명을 붙여주는 것이다.
• 타입 별칭은 interface처럼 상속이 되지 않는다.

interface 정의 방식 소개

변수

interface User {
  name: string;
  age: number;
}

let minseok: User;

함수 구조 정의하기

interface fooFunction {
  // 인자는 괄호를 이용해 표시
  // 반환 타입도 함수 정의와 동일하게 뒤에 표시
  (a: number, b: number): number;  
}

인덱싱 방식 정의하기

interface stringArray {
  //인덱싱 방식 자체를 정의
  //숫자로 인덱싱 할 수 있는 것은 string만 가능하게 됨
  [index: number]: string
}

딕셔너리

interface stringRegexDictionary {
  [key: string]: RegExp;
}

let obj: stringRegexDictionary = {
  //아래 경우는 에러가 발생하게 됨
  //key 값이 string인 경우에 정규표현식이 위치해야함
  cssFile: "hello"
  //아래 경우는 interface와 동일하므로
  //에러가 발생하지 않음
  jsFile: /\.js$/
}

interface 상속하기

//상속될 interface
interface Person{
  name: string;
  age: number;
}

//Person interface를 상속할 interface
//Person을 확장했으므로 name과 age는 모두 가지고 있음
interfae Developer extends Person{  
  skills: string[]
}

const minseok: Developer = {
  name: "minseok",
  age: 0,
  skills: ["js", "java", "Dart"]
}

연산자를 이용한 type 정의

union type

function logMessage(message: any): void {
  console.log(message);
}

어떤 메시지를 출력해주는 함수를 위와 같이 정의하고자 합니다. message 인자로 string, number가 모두 들어올 수 있다고 생각해서 any라고 타입을 지정해주었습니다. 하지만 이런식으로 타입스크립트를 사용하면 자바스크립트를 사용하는 것과 차별점이 없습니다. 이런 상황을 위한 연산자를 이용한 타입 정의를 알아보겠습니다.

function logMessage(message: string | number): void {
  console.log(message);
}

위와 같은 타입을 union type이라고 하며 string과 number 모두 전달할 수 있게 됩니다. 또한 이렇게 union type을 사용할 경우 타입스크립트의 장점을 아래와 같이 살릴 수 있게 됩니다.

function logMessage(message: string | number): void {
  if(typeof message === "number") {
    //message는 타입 number로 추론되는 상황
    message.
  }else {
    //message가 타입 string으로 추론되는 상황

  }
}

그런데 아래 예시를 보자. 유니온 타입이 포함하는 타입의 공통적인 부분만을 허용하는 것을 확인할 수 있다.

interface Developer {
  name: string;
  skills: string[];
}

interface Person {
  name: string;
  age: number;
}

function getSomeone(someone: Developer | Person) {
  //에러 발생하지 않음
  someone.name
  //에러 발생
  someone.age
  someone.skills
}

인터섹션 타입

인터섹션의 타입에 포함하는 모든 타입을 만족하는 타입을 의미하게 된다. 아래와 같은 경우의 foo는 어떤 타입도 만족할 수 없게 된다. string이면서 number이면서 boolean인 변수는 존재할 수 없으므로

let foo: string & number & boolean;

interface Developer {
  name: string;
  skills: string[];
}

interface Person {
  name: string;
  age: number;
}

function getSomeone(someone: Developer & Person) {
  //Developer와 Person을 모두 
  //포함하게 되는 타입이므로
  //에러 발생하지 않음
  someone.name
  someone.age
  someone.skills
}

$npm install vuex

폴더 및 파일 생성

일반적으로 아래와 같이 폴더를 구조를 갖고 파일을 생성하는것이 일반적입니다.

|--src
  |--store
    |-- store.js

store.js

import Vue from 'vue';
import Vuex from 'vuex';

Vue.use(Vuex);

export const store = new Vuex.Store({
    state: { ... },
    getters: { ... },
    mutations: { ... },
    actions: { ... }            
});

src / main.js

(...)
import { store } from './store/store';

new Vue({
  el: "#app",
  store,
  render: h => h(App)
})

state

사용 예시

data를 사용하듯이 state를 정의해주고 this.$store.state를 통해 접근하여 해당하는 값을 사용할 수 있습니다.

// store.js
state: {
  messgae: "hello world"
}

// App.vue
<span>{{ this.$store.state.message }}</span>

getters

state값에 접근하는 속성이자 computed()처럼 미리 연산된 값을 접근하는 속성

• getters는 첫번째 인자로 store의 state를 받습니다.

사용 예시

// store.js
export const store = new Vuex.store({
  state: {
    message: "hello",
    name: "world"
  },
  getters: {
    getMessage(state) {
      return state.message;
    }
    getGreet(state) {
      reutrn state.message + state.name;
    }
  }
})

// App.vue
<h1>{{ this.$store.getters.getGreet }}</h1>

mutations

• state의 값을 변경할 수 있는 유일한 메서드
• mutations는 첫번째 인자로 store의 state를 받습니다.
• commit()을 통해 접근하여 메서드를 호출합니다. 인자로 메서드명을 문자열로 전달하면 일치하는 메서드가 실행됩니다.
• commit()의 두번째 인자는 객체로 전달해주어야 합니다.

사용 예시

// store.js
export const store = new Vuex.store({
  state: {
    num: 10
  },
  mutations: {
    modifyNum(state, payload) {
      console.log(payload.str);
      return state.num += payload.num;
    }    
  }
})

// App.vue
this.$store.commit("modifyNum", {
  str: "hello world",
  num: 10
});

왜 Mutations를 통해 state에 접근해야 할까?

• Mutations를 이용하지 않으면 어느 component가 state를 변경했는지 추적하기 어렵고 반응성이 떨어진다.
• 개발자 도구를 통한 개발 이점.

actions

• actions는 첫번째 인자로 store의 state를 받습니다.
• 비동기 처리 로직을 처리하는 메서드(Mutations의 비동기 버전)입니다.

사용 예시

주의! 아래 예시는 실제로 동작하진 않습니다.

// store.js
export const store = Vuex.Store({
  state: {
    num: 10
  },
  mutations: {
    modifyNum(state, payload) {
      console.log(payload.str);
      return state.num += payload.num;
    }    
  },
  actions: {
    delayModifyNum(state) {
      //외부에서 $store.commit과 동일
      setTimeout(() => {
        context.commit("modifyNum");
      }, 1000);
    }
  }
})

// App.vue
// actions delayModifyNum을 호출
this.$store.dispatch("delayModifyNum");

참고

• 캡틴 판교 inflearn 중급 강의

앱이 복잡해짐에 따라 데이터의 흐름을 관리 및 예측하기 어려워졌습니다. 이런 문제를 해결하고자 나온 상태 관리 라이브러리인 동시에 상태 관리 패턴이 Vuex입니다.

문제 상황

• MVC 패턴의 문제 기능 추가 및 변경에 따라 생기는 문제점 및 결과를 예측하기 어렵습니다. 아래는 이런 문제를 시각화한 이미지입니다.

여러개의 컴포넌트에서 같은 데이터를 업데이트해야 하고 있다면? 동기화를 어떻게 해주고 있나요?

해결을 위한 등장

• Flux 패턴 데이터 흐름을 단방향으로 유지하는 Flux패턴의 등장

• Vuex 컨셉

  • state 컴포넌트간에 공유하는 데이터
  • view 데이터를 표시하는 화면
  • action 사용자의 입력에 따라 데이터를 변경하는 메서드

• Vuex 구조 데이터 -> 비동기 로직 -> 동기 로직 -> 컴포넌트 -> 데이터 -> (...)

same-origin 판단 기준 same-origin판단을 위한 기준으로 protocol, host, port가 있습니다.

https://velog.io/를 기준으로 https가 protocol, host가 velog.io를 의미하며 port는 명시되어 있지 않습니다.

domain이 다르더라도 통신이 가능하도록 HTML5에서 추가된 스펙이 바로 CORS(Cross Origin Resource Sharing)입니다.

CORS 적용 방법 : client

클라이언트에서는 기존의 동일 도메인 요청과 동일하게 구현하면 됩니다. same-origin이 아닐 경우 XMLHttpRequest 객체가 preflight, actual 요청을 자동으로 처리하게 됩니다.

CORS 적용 방법 : server

• Access-Control-Allow-Origin CORS를 허용할 domain을 입력합니다. *을 입력하면 모든 domain에 대해 CORS를 허용합니다. 모든 domain에 대해 CORS를 허용할 경우 보안에 취약해지므로 주의합니다.
• Access-Control-Allow-Methods CORS를 허용할 method를 입력합니다. 유의할 점으로 CORS의 preflight 과정에서 OPTIONS method가 사용되므로 OPTIONS 메서드를 허용해주어야합니다.

참고

• 구루비 저장창고
• MDN

한 문제를 중첩 반복문과 투 포인터로 해결해보고 비교 과정을 통해 원리를 알아봅니다.

문제

양수로 이루어진 길이 N의 배열이 주어지고 자기 자신을 포함한 일정 구간의 배열을 부분 배열이라고 칭합시다. 이 때 부분 배열에 포함되는 수의 합이 m이 되는 경우의 수를 구해봅니다.

문제는 투 포인터를 활용해서 해결해야 하는 대표적인 문제로 중첩 반복문을 이용해 해결하면 시간 초과가 나도록 N을 크게 설정해놓는 문제가 많습니다.

중첩 반복문을 통해 해결

시간 복잡도는 생각하지 않고 중첩 반복문을 이용한 풀이는 아래와 같습니다. 부분합을 미리 구해놓고 for문 2개를 중첩해서 해결하였습니다.

import java.util.*;

class Main{
  public static void main(String[] args){
import java.util.*;

class Main{
  public static void main(String[] args){
    int[] numbers = {/*배열*/};
    int m = /*목표 합*/;

    int[] sum = new int[numbers.length+1];

    int now = 0;
    for(int i = 1; i<numbers.length+1; i++){
      now += numbers[i-1];
      sum[i] = now;
    }

    int answer = 0;

    for(int i=1; i<numbers.length+1; i++){
      for(int j=i; j<numbers.length+1; j++){
        if(sum[j] - sum[i-1] == m){
          answer++;
        }
      }
    }

    System.out.print(answer);
  }
}

투 포인터를 이용한 해결

안쪽 for문을 담당하던 변수 j를 for문 밖으로 빼서 선언했습니다. 이렇게 되면 j와 i 모두 배열을 한번만 탐색하게 됩니다.

이렇게 할 수 있는 이유는 무엇일까요? 투 포인터를 어떤 문제에 적용할 수 있을지에 대한 근본적인 질문입니다. 예를 들어 i를 고정시켜보겠습니다. i가 고정된 상태에서 j가 오른쪽으로 이동하면 수열의 합은 커집니다. 작아지진 않습니다. j가 고정된 상태에서 i가 움직이면 수열의 합은 작아집니다. 커지진 않습니다. 그래서 서로에게 종속적이지 않고 따로 움직이는게 가능합니다.

import java.util.*;

class Main{
  public static void main(String[] args){
import java.util.*;

class Main{
  public static void main(String[] args){
    int[] numbers = {/*배열*/};
    int m = /*목표 합*/;

    int[] sum = new int[numbers.length+1];

    int now = 0;
    for(int i = 1; i<numbers.length+1; i++){
      now += numbers[i-1];
      sum[i] = now;
    }

    int answer = 0;

    int j = 1;
    for(int i=1; i<numbers.length+1; i++){
      for(; j<numbers.legnth+1; j++){
        if(sum[j] - sum[i-1] == m){
          answer++;
        }else if(sum[j] - sum[i-1] > m)
          break;
      }
    }

    System.out.print(answer);
  }
}

결론

실제 중첩 반복문을 투 포인터로 변경함으로써 어떤 방식으로 투 포인터가 동작하는지 알아보았습니다. 투 포인터를 변수로 나누어 억지로 적용하려고 하면 직관적이지 않습니다. 위와 같은 과정을 충분히 익히는게 중요하다고 생각합니다.

Callback Stack

• JavaScript는 싱글 스레드 언어입니다.
• JavaScript는 하나의 콜 스택을 갖습니다.
• JavaScript는 동시에 하나의 작업만 처리할 수 있습니다.

위 세 문장은 같은 의미를 갖습니다. 실제로 우리가 작성한 코드는 차례차례 하나의 CallStack에 쌓이고 실행되고 난 후에 Stack에서 pop되는 과정이 일어납니다.

Web APIs

그런데 JavaScript가 싱글 스레드 언어라면 동시에 여러 작업을 할 수 없어야할텐데 우리는 동시에 애니메이션도 처리하고 사용자의 입력도 처리하고 데이터도 받아오는 것을 많이 목격했습니다. 즉 JavaScript는 non-blocking언어 입니다. 부드러운 UI를 위해 어떤 작업이 진행중이라고 다른 작업을 막지 않는다는 의미입니다. 어떻게 싱글 스레드로 이것이 가능할까요?

바로 비동기 함수가 Call Stack에서 실행되면 Web APIs로 넘기기 때문입니다. Web APIs에 있다가 실행할 타이밍이 되면 해당하는 콜백함수를 메시지로 또 다른 곳으로 넘기게 됩니다. 이곳은 바로 Message Queue입니다.

Message Queue

Message Queue에도 Call Stack처럼 메시지가 차곡차곡 쌓이게 됩니다. 하지만 자료구조 특성상 먼저 들어온 메시지가 먼저 나가게 됩니다. 그리고 언제 나가게 되냐면 Call Stack이 비게 되면 Message Queue에 있던 한개의 메시지가 Call Stack에 올라가게 됩니다. 그리고 바로 이것이 Event Loop 입니다. Call Stack과 Message Queue를 지켜보다가 Call Stack이 비어 있고 Message Queue에 message가 있다면 Call Stack으로 보내는 것이죠.

정리

위의 과정을 한번 정리해보도록 하겠습니다. 정리를 위해서 위 과정을 시각화해둔 loupe 사이트를 활용하였습니다.

코드

버튼에 클릭 이벤트에 대한 리스너를 달아주었고 이벤트 발생시 실행을 원하는 콜백함수도 달아주었습니다.

const btn = document.querySelector('button');
btn.addEventListener('click', function onClick() {
    console.log('You clicked the button!');  
});

console.log("Welcome");

과정의 시각화

1. 콜 스택에 addEventListener가 올라갑니다.

2. 비동기 함수이므로 이것을 Web APIs로 보냅니다.

3. 콜 스택에 console.log("Welcome")이 올라갑니다.

4. Welcome을 콘솔창에 출력시키고 콜스택에서 console.log("Welcome")이 내려갑니다.

5. button click event가 발생하면 콜백함수를 Message Queue(Callback Queue)로 보냅니다.

6. Call Stack이 비어있으므로 event loop에 의해 Call Stack에 올라갑니다. 콜백함수인 onClick함수 내부에 console.log()도 Call Stack에 쌓이게 됩니다.

7. 최종적으로 console.log()까지 실행되면 차례대로 Call Stack에서 내려오게 됩니다.

추가로 만약에 버튼을 여러번 눌렀다면 어떻게 처리할까요? 예상하신대로 이벤트가 일어났으므로 먼저 Message Queue에 여러개가 쌓이게 되겠죠. 그리고 순서대로 Call Stack이 빌 때마다 Event Loop에 의해 Call Stack에 올라가게 됩니다.

결론

Event Loop를 무엇이다 라고 딱 말할 수 있다면 대단한 내공의 사람이라고 한 이유를 아마 이해하셨으리라 생각합니다. Event Loop가 무엇인지 알아보았고 그 과정에서 싱글 스레드 기반의 JavaScript가 어떻게 여러 개의 작업을 동시에 처리하는지를 알 수 있었습니다.

참고

• What the heck is the event loop

사이클에 대해 이야기하기 전에 2가지 사실을 짚고 넘어갑니다.

1. 정점 n개, 간선 n-1개인 그래프는 트리이다.

그렇지 않습니다. 하지만 역인 트리이면 정점 n개 간선 n-1개를 갖는다는 맞습니다.

2. 정점 n개, 간선 n개인 그래프는 정확히 한개의 사이클을 갖는다.

맞습니다. 간선의 개수가 정점의 개수와 같다면 하나의 사이클이 존재하게 됩니다.

그렇다면 사이클을 어떻게 찾을 수 있을까요?

[2] 사이클을 찾기 위해 필요한 2가지

1. DFS로 그래프를 탐색하고나서 탐색 경로를 살펴보면 트리가 된다.

<DFS 경로를 표시한 그래프>

주어진 그래프를 딱보면 사이클이 있는 그래프네요. 이 그래프를 정점 1을 루트로 DFS 탐색을 하고 탐색한 경로를 빨간색으로 표시한것이 아래 이미지입니다. 빨간색 이미지를 보면 어떻나요? 트리를 이루고 있죠? 트리의 정의는 무엇인가요? 임의의 두 노드를 잇는 경로는 유일해야하죠. DFS는 어떤가요? 같은 노드를 여러번 방문하나요? 그렇지 않죠 그래서 DFS경로를 표시하면 위와 같이 트리가 됩니다.

2. 트리는 어디서부터 왔는지를 이용하면 visited배열 없이 DFS 탐색이 가능하다.

DFS 탐색시에 많은 분들이 visited 배열을 이용해서 방문한 노드를 확인하는데 사용하실거라 생각합니다. 그런데 트리에서는 visited 배열 없이도 DFS탐색을 할 수 있습니다. 현재 탐색 중인 노드의 부모를 표시하면 가능합니다. 다음 방문할 노드가 현재 노드의 부모라면 다시 방문하지 않는것이죠.

코드로는 아래와 같이 직전 노드가 어디인지만 표시해주면 됩니다.

dfs(int now, int from){
  for(int next : list[now]){
    //다음에 방문할 노드가 현재 노드의 부모라면 방문하지 않는다.
    if(next == from){
      continue;
    }
    dfs(next, now);
  }
}

// dfs를 시작할때는 자기 자신을 부모로 해줘도 됩니다.
dfs(1,1);

위 그래프에서 빨간색은 실제 탐색 경로를 나타내면 파란색은 탐색을 시도했으나 부모와 같아서 방문하지 않은 것을 의미합니다.

[3] 사이클 찾기

그럼 이제 우리는 사이클을 찾는데 필요한 두가지 조건을 모두 알았습니다. 이제 사이클을 찾고 사이클에 존재하는 정점을 모두 출력해보도록 하겠습니다.

먼저 조건은 정점 n개, 간선 n개를 갖는 그래프입니다. 우리가 위에서 배운대로 무조건 한개의 사이클을 갖습니다. 우리는 이 그래프를 DFS탐색을 할 겁니다. 탐색을 하기 위해 우리는 visited배열과 노드의 부모 노드 표시 두가지를 사용할 겁니다. 탐색 경로로 우리는 트리를 얻게 될 겁니다.

이제 사이클을 찾기 위해 한가지 트릭을 더합니다. 우리는 그래프를 찾기 위해 n-1개의 간선을 탐색했을 것이고 남은 1개의 간선이 바로 사이클을 찾는 키가 됩니다. 부모 노드와 다음 노드를 이용해 표시했음에도 visited한 정점을 발견한다면 바로 정점에 의해 사이클이 형성된 것이란걸 알 수 있습니다.

끝과 끝을 찾았지만 갈길이 멀군요.. 사이클에 포함된 정점들은 어떻게 찾을 까요? 바로 아래와 같이 찾을 수 있습니다. 방문할 때마다 이 정점이 어디서부터 온지를 저장해놓으면 돼요.

6은 5에서 왔고 5는 2에서 왔고 2는 1에서 왔고 1은 사이클의 끝과 끝이니까 더 확인할 정점은 없다. 따라서 1, 2, 5, 6이 사이클을 이루는 정점이다 라는 결론을 얻을 수 있습니다.

[4] 관련 문제

서울 지하철 2호선 이라는 문제 입니다. 위에 적힌 설명과 BFS에 대한 지식이 있다면 충분히 해결가능하니 꼭 풀어보시기 바랍니다. 사실 이 포스트를 적게 된 원인이 된 문제입니다. 여러번 풀어보았는데 풀때마다 새로운 실수를 해서 반나절씩 시간을 잡아먹더라구요.. 뭔가 희한한 문제입니다. 차근히 풀어보시면 쉽게 푸실거라 생각합니다. 이걸 풀고나면 지하철 탈 때 재밌습니다. ㅋㅋㅋ

k개의 소수가 있습니다. 이 소수들 중에서 몇개를 곱해 얻게 되는 수들을 정렬하여 n번째 수를 구하는 문제 입니다. 얻게 되는 수에는 주어진 소수 자체도 포함시킵니다.

• 소수 개수 k <= 100
• n <= 100000

접근

먼저 몇개의 소수를 곱해 얻을 수 있는 수를 어떻게 구하면 좋을까요?

사실 중복 사용이 가능하기 때문에 얻을 수 있는 숫자는 무한개 입니다. 따라서 숫자를 모두 구하고 정렬해서 n번째 숫자를 알아내는건 불가능합니다. 결국 작은 수부터 순서대로 n번째 까지 구해야 하는데요.

이를 위해 그래프를 탐색(bfs, dfs)하듯이 탐색하며 n번째 수를 구해볼건데요. 이때 bfs의 큐 대신 우선 순위 큐를 사용해봅니다. 물론 bfs는 아닙니다. 우선순위에 따라 순서가 바뀌므로 최단 거리를 구하는 것이 아니기 때문입니다.

예를 들어 소수 2, 5, 7 세개가 주어지면 맨 처음 큐에는 2,5,7을 넣어주겠죠. 2가 가장 작으므로 맨 처음 나와서 2, 5, 7을 곱해 다시 큐에 넣어줄 겁니다. 그러면 큐에는 5, 7, 4, 10, 14가 들어있게 되고 우선 순위 큐이므로 4, 5, 7, 10, 14로 들어가 있을 겁니다. 다음 턴에서 4가 나오게 되겠죠. 여기서 주목할 점은 일반적인 큐라면 5가 나왔을 텐데 우선 순위 큐를 이용함으로써 더 작은 4가 먼저 나오게 되고 문제에서 구하라고 한 정렬하여 n번째 숫자를 구하는데 가까워 집니다.

그런데 이렇게 하다보면 중복 처리에 대한 문제가 생깁니다. 예를 들어 10같은 경우에는 2x5, 5x2 등으로 두번이나 등장하게 됩니다. 이런 중복은 어떻게 처리해주면 될까요?

1.check 배열

배열을 사용해주는건 말도 안됩니다. 최대 가능한 정답이 $2^{31}-1$까지 가능하기 때문에 이 모든 수를 배열에 넣어주면 21억x1byte= 21기가바이트는 말도 안됩니다.

2. 중복되는 숫자가 등장하면 모두 poll시키기

우선순위 큐를 이용해 방문하다보니 중복되는 숫자들은 연속으로 있게 됩니다.따라서 숫자를 poll시키고 뒤에 숫자가 같다면 큐에서 계속 제거해주는 방법을 사용할 수 있습니다. 그치만 이 방법을 사용하면 이 모든 중복되는 숫자가 결국 큐에 들어가기 때문에 이 역시 메모리가 초과됩니다.

3. 큐에 중복되는 수를 넣지 않는 방법

큐에 중복되는 수를 아예 넣지 않기 위해 언제 중복이 발생하나 생각해봅니다. 같은 숫자의 조합으로 곱하면 중복이 발생하겠죠? 같은 숫자의 조합을 피하려면 어떻게 하면 좋을까요?

예를 들어 우리가 이중 for문으로 주어진 숫자에서 숫자 두개를 고르는 방법을 모두 출력하려면 어떻게 할까요? 중복사용은 허용하구요. 고전적으로 아래와 같은 방법 많이들 사용하실거라 생각합니다. j=i을 사용해서 i보다 앞에 오는 수는 보지 않는거죠 왜냐하면 다른 조합에서 보게 될 테니까요. 총 6개가 나오는데요. $_3H_2$($_4C_2$)에 의해 맞는 결과네요.

int[] numbers = {1, 2, 3};

for(int i = 0; i<3; i++){
  for(int j = i; j<3; j++){
    System.out.println(numbers[i]+" "+numbers[j]);
  }
}

// 1 1
// 1 2
// 1 3
// 2 2
// 2 3
// 3 3

자 그럼 이걸 생각하고 소수의 곱으로 중복되는 수를 피하려면 어떻게 하면 될까요? 현재 수를 소인수분해해서 가장 큰 소인수보다 크거나 같은 소수만 사용하는 겁니다. 또 예를 들어보면 현재 수가 5라고 하면 가장 큰 소인수보다 크거나 같은 5, 7만 곱할 수 있습니다. 이렇게 되면 아까처럼 10이 중복되는 일이 없습니다. 숫자 n의 가장 큰 소인수를 구하는 코드는 아래와 같습니다.

static int getMaxPrimeFactor(int n){
  int returnValue = -1;

  for(int i = 2; i*i<=n; i++){
    while(n % i == 0){
      returnValue = i;
      n /= i;
    }
  }

  if(n != 1){
    return n;
  }

  return returnValue;
}

n != 1일때 그대로 n을 출력해버린건 우리가 n을 2부터 나눠봤기 때문이에요. 왜냐하면 1로만 나누어지는 소인수가 있었다면 그것이 가장 큰 소인수이고 for문을 통해 거르지 못했기 때문입니다. 이런 예로 $2^2 * 3 * 13$ 같은 경우가 있겠네요.

최종적으로 위의 방법들을 적용해서 n번째 수를 출력해주면 정답이 됩니다.

코드

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

class baek__2014 {

    static int factorization(int n) {
        int max = -1;

        for (int i = 2; i * i <= n; i++) {
            while (n % i == 0) {
                max = i;
                n /= i;
            }
        }

        if (n != 1)
            max = n;

        return max;
    }

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

        String[] temp = br.readLine().split(" ");

        int k = Integer.parseInt(temp[0]);
        int n = Integer.parseInt(temp[1]);

        int[] prime = new int[k];
        temp = br.readLine().split(" ");
        for (int i = 0; i < k; i++) {
            prime[i] = Integer.parseInt(temp[i]);
        }

        PriorityQueue<Integer> q = new PriorityQueue<>();

        q.add(1);
        int cnt = -1;
        int answer = -1;

        while (true) {
            int now = q.poll();
            cnt++;

            if (cnt == n) {
                answer = (int) now;
                break;
            }

            int max = factorization(now);

            for (int p : prime) {
                if (p < max)
                    continue;

                long nex = (long) now * p;

                if (nex < (long) (1 << 30) * 2)
                    q.add((int) nex);
            }
        }

        System.out.print(answer);

    }
}

최소 스패닝 트리란 그래프(트리 아닙니다)의 모든 정점들을 연결하는 부분 그래프 중에서 그 가중치의 합이 최소인 트리를 의미합니다.

<그림 1>의 그래프에서 최소 스패닝 트리는 <그림 2>의 형태를 띄게 됩니다. 가중치가 10인 경로는 제외되었습니다. 예시에선 유일했지만 최소 스패닝 트리가 여러개일 수 있습니다.

<그림 1>	<그림 2>

최소 스패닝 트리 구하기 - kruskal 알고리즘

1. 모든 간선을 저정하고 가중치 순으로 정렬합니다. 혹시 정렬이 싫다면 priorityQueue를 사용해도 되지만 정렬하는게 맞다고 생각합니다.

   //e개의 간선을 저장할 배열
   Edge[] edges = new Edge[e];
   

//e개의 간선 정보를 for문을 통해 입력 받아 저장 for(int i = 0; i<e; i++){ String[] temp = br.readLine().split(" "); int u = Integer.parseInt(temp[0]); int v = Integer.parseInt(temp[1]); int weigth = Integer.parseInt(temp[1]);

edges[i] = new Edge(u, v, weight); }

Arrays.sort(edges);

2. 모든 간선을 for문을 통해 돌면서 고를 수 있으면 고릅니다. 
고를 수 있으면 고른다는 것은 바로 사이클을 형성하지 않는 것을 의미합니다. 즉 이미 경로가 생성된 두 정점을 이으면 안된다는 의미입니다.(트리는 두 정점을 잇는 경로가 유일) 경로가 생성된 정점 여부를 판단하기 위해 [Union-Find](https://velog.io/@since-1994/Union-Find-BOJ-17619-개구리-점프)를 사용합니다. 

```java
int[] parent = new int[n];

for(int i = 0; i<n; i++){
  parent[i] = i;
}

for(int i = 0; i<e; i++){
  int u = edges[i].start;
  int v = edges[i].end;

  if(find(u) == find(v))
      continue;

  union(u, v);
}

3. for문을 모두 돌고나면 최소 스패닝 트리가 형성됩니다.

*과정을 따라가다보면 결국 최소 스패닝 트리를 구한 과정은 결국 트리 구성에 사용된 간선 중 최대 가중치의 최소값을 구하기 위한 과정과 동일하다는 것을 알 수 있습니다. *

문제

간선의 정보를 입력받아 최소 스패닝 트리의 가중치의 합을 구하시오.

접근

최소 스패닝 트리를 구해주고 가중치의 값을 출력해주면 됩니다 :)

코드

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

class Edge implements Comparable<Edge> {
    int v1;
    int v2;
    int w;

    Edge(int v1, int v2, int w) {
        this.v1 = v1;
        this.v2 = v2;
        this.w = w;
    }

    public int compareTo(Edge that) {
        Integer u = this.w;
        Integer v = that.w;

        return u.compareTo(v);
    }
}

class baek__1197 {

    static int find(int n, int[] parent) {
        return parent[n] == n ? parent[n] : (parent[n] = find(parent[n], parent));
    }

    static void union(int a, int b, int[] parent) {
        int r1 = find(a, parent);
        int r2 = find(b, parent);

        parent[r1] = r2;
    }

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

        String[] temp = br.readLine().split(" ");

        int v = Integer.parseInt(temp[0]);
        int e = Integer.parseInt(temp[1]);

        int[] parent = new int[v + 1];
        Edge[] edges = new Edge[e];
        for (int i = 1; i <= v; i++) {
            parent[i] = i;
        }

        for (int i = 0; i < e; i++) {
            temp = br.readLine().split(" ");

            int a = Integer.parseInt(temp[0]);
            int b = Integer.parseInt(temp[1]);
            int w = Integer.parseInt(temp[2]);

            edges[i] = new Edge(a, b, w);
        }

        Arrays.sort(edges);

        int answer = 0;

        for (Edge edge : edges) {
            int a = edge.v1;
            int b = edge.v2;

            int r1 = find(a, parent);
            int r2 = find(b, parent);

            if (r1 == r2)
                continue;

            answer += edge.w;
            union(r1, r2, parent);
        }

        System.out.print(answer);

    }
}

Union-Find란?

Union-Find는 자료구조 트리를 활용해 집합을 표현하는 자료구조이며 집합간의 합치거나(Union) 원소가 어느 집합에 포함되어 있는지를 찾는(Find) 연산이 매우 빠른 것이 특징입니다.

빠르게 찾는 다는 것은 최적화가 이루어졌을 때 대부분의 경우에서 상수 시간의 복잡도를 보이게 됩니다

Find

Union-Find의 시작은 대부분 원소 한개로 이루어진 여러개의 집합으로 시작합니다.

• {1}, {2}, ... {n}

이러한 집합을 1차원 배열에 저장해 주도록 하겠습니다. parent라는 배열을 만들고 자기 자신을 parent로 지정해주면 됩니다. 부모 노드를 의미하게 됩니다.

• parent[1] = 1, parent[2] = 2, ... parent[n] = n

만약 1을 루트로 갖는 집합과 2를 루트로 갖는 집합을 합친다고 하면 둘 중 하나의 루트를 다른 루트의 자식으로 연결해주면 됩니다.(결국 이게 Union인데 아래에서 더욱 자세히 설명하도록 하겠습니다.) 합친 결과로 아래처럼 되겠네요.

• parent[1] = 1, parent[2] = 1, ... parent[n] = n

자 그럼 이 상황에서 1과 2가 같은 집합에 들어있다는건 어떻게 알 수 있을까요?

아래처럼 어떤 원소를 입력받아 그 원소가 포함된 트리의 루트를 반환해주는 함수를 만들어주고 1과 2가 포함된 집합의 루트가 같다면 두 원소는 같은 집합에 포함되어 있다는 뜻이 됩니다. 그리고 이 루트를 반환해주는 함수가 바로 Union-Find의 Find가 됩니다.

static int find(int x, int[] parent){
  return parent[x] == x? parent[x] : find(parent[x]);
}

if(find(1) == find(2))
    System.out.print("1과 2는 같은 집합에 있다");

여기까지 해준다면 find의 시간 복잡도는 $O(N)$이 됩니다. 왜냐하면 아래와 같은 상황이 있을 수도 있기 때문입니다.

그러면 이 복잡도를 줄이기 위해서 어떤 방법이 있을까요?

경로 압축

바로 경로 압축이란 방법을 사용할 수 있습니다. 경로 압축의 아이디어는 바로 집합의 모든 노드의 부모를 루트 노드로 바꾸는 겁니다. 이걸 하기 위한 코드는 매우 간단합니다.

static int find(int x, int[] parent){
  return parent[x] == x? parent[x] : (parent[x] = find(parent[x]);
}

위의 경로 압축 전 코드에서 parent[x] = find(parent[x])만 수정해주었습니다. 결국 쭉쭉 타고 올라가면서 모든 노드의 parent를 루트 노드로 바꾸게 됩니다.

Union

Find에서도 언급했지만 Union은 집합 두개를 합치는 방법으로 합칠 두 원소의 루트 노드를 찾고 그 노드 두개를 부모 자식 관계로 연결해주면 됩니다. 코드는 아래와 같습니다.

static void union(int a, int b){
  int x = find(a, parent);
  int y = find(b, parent);

  parent[x] = y;
}

두 원소의 루트 노드를 찾고 둘 중 하나의 루트를 다른 루트의 부모로 만들어 줍니다. 자 그럼 한번 생각해봅시다. Union이 이루어지고 해당 집합에 대한 find가 이루어지면 또 경로 압축 과정이 있을 겁니다. 이 경로 압축 과정을 좀 덜 하려면 어떻게 하면 좋을까요?

small to large

바로 집합의 크기가 큰 노드를 부모로 만들어주면 됩니다. 자식이 된 부분이 경로 압축이 이루어질 부분이기 때문입니다. 이를 위해서는 집합의 크기를 저장할 배열이 추가로 필요하게 됩니다. size배열이라고 하겠습니다.

집합 {1, 2}과 {3} 이 있고 2, 3을 union하는 순서는 아래와 같습니다.

1. 사이즈는 다음과 같다. size[2] = 2, size[3] = 1
2. 루트를 찾는다. find(2) = 1, find(3) = 3
3. 합친다. parent[3] = 1, size[2] += size[3]

위의 과정을 코드로 나타내면 아래와 같습니다.

static void union(int a, int b){
    int x = find(a, parent);
    int y = find(b, parnet);

    if(size[x] > size[y])
      swap(x, y);

    parent[x] = y;
    size[y] += size[x];
}

이제 Union-Find를 이용해 문제를 해결해보겠습니다.

문제

통나무에서 통나무로 이동 가능한 조건이 주어집니다. 통나무 N개에 대한 좌표가 주어지고 임의의 통나무 두개를 query로 주어지면 이동이 가능한지를 출력해야하는 문제입니다.

• 통나무의 개수 N <= 100000
• query의 개수 Q <= 100000

  접근

  통나무 간의 이동이 가능한 통나무들을 하나의 집합으로 만들어줍니다. query가 주어졌을 때 같은 집합에 포함된 통나무라면 1을 출력해주면 됩니다.
• 집합 구성 과정 만약에 모든 통나무를 이중 포문 으로 돌아주면서 두 통나무가 이동 가능할때마다 두 집합을 union해준다고 하면 약 100억의 시간 복잡도를 갖습니다. 당연히 안되겠죠..
• 정렬을 해주자 자 이럴 때 먼저 x1을 기준으로 통나무 배열을 정렬해줍니다. 정렬된 순서에서는 뒤의 통나무의 시작점이 앞의 통나무의 시작점보다 작은 값을 갖는 일은 없게 됩니다. 이렇게 되면 뒤 통나무의 시작점이 앞 통나무의 끝점보다 커지게 되면 그 뒤 통나무부터는 더이상 보지 않아도 됩니다. 일종의 백트래킹이죠.. 사실 정확히 어느 정도의 시간 복잡도를 갖는지는 예상 못했지만.. proof of AC라고 하죠.. 맞더라구요.. 그러므로 증명 완료.! 시각적으로 나타내면 아래의 <그림1>과 같습니다. <그림1>과 같은 상황에서 통나무3부터는 통나무1이나 통나무2와 더이상 같은 집합이 될 수 없죠.

• 의문이 든다면? 혹시 몇몇 분은 위의 <그림2>와 같은 상황은 어떻게 하냐고 할 수 있습니다. 분명히 통나무 4도 통나무1을 포함하는 집합에 포함되야 하는데 말이죠. 그치만 이런 상황은 통나무1에 대해 통나무 2, 3, 4,,,n까지 보는 과정에서 체크되었기 때문에 걱정하지 않아도 됩니다.

• 이 부분의 코드

  for (int i = 1; i <= n; i++) {
  for (int j = i + 1; j <= n; j++) {
    if (nodes[i].x2 >= nodes[j].x1) {
      union(nodes[i].idx, nodes[j].idx, parent, size);
    } else {
      break;
    }   
  }
  }

코드

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

class Node implements Comparable<Node> {
    int x1;
    int x2;
    int idx;

    Node(int idx, int x1, int x2) {
        this.idx = idx;
        this.x1 = x1;
        this.x2 = x2;
    }

    public int compareTo(Node that) {
        if (this.x1 < that.x1) {
            return -1;
        } else if (this.x1 == that.x1) {
            return 0;
        }
        return 1;
    }
}

class baek__17619 {

    static int find(int a, int[] parent) {
        return a == parent[a] ? a : (parent[a] = find(parent[a], parent));
    }

    static void union(int a, int b, int[] parent, int[] size) {
        int r1 = find(a, parent);
        int r2 = find(b, parent);

        if (size[r1] > size[r2]) {
            int temp = r1;
            r1 = r2;
            r2 = temp;
        }

        parent[r1] = r2;
        size[r2] += size[r1];
    }

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

        int n = Integer.parseInt(temp[0]);
        int[] parent = new int[n + 1];
        int[] size = new int[n + 1];
        Node[] nodes = new Node[n + 1];
        for (int i = 1; i <= n; i++) {
            parent[i] = i;
            size[i] = 1;
        }
        int q = Integer.parseInt(temp[1]);

        nodes[0] = new Node(-1, -1, -1);
        for (int i = 1; i <= n; i++) {
            temp = br.readLine().split(" ");
            nodes[i] = new Node(i, Integer.parseInt(temp[0]), Integer.parseInt(temp[1]));
        }

        Arrays.sort(nodes);

        for (int i = 1; i <= n; i++) {
            for (int j = i + 1; j <= n; j++) {
                if (nodes[i].x2 >= nodes[j].x1) {
                    union(nodes[i].idx, nodes[j].idx, parent, size);
                } else {
                    break;
                }
            }
        }

        StringBuilder sb = new StringBuilder();
        while (q-- > 0) {
            temp = br.readLine().split(" ");
            int u = Integer.parseInt(temp[0]);
            int v = Integer.parseInt(temp[1]);

            int r1 = find(u, parent);
            int r2 = find(v, parent);

            if (r1 == r2) {
                sb.append(1 + "\n");
            } else {
                sb.append(0 + "\n");
            }
        }
        System.out.print(sb);
    }
}

대부분의 경우 this의 값은 함수를 호출한 방법에 의해 결정됩니다. 실행중에는 할당으로 설정할 수 없고 함수를 호출할 때 마다 다를 수 있습니다. ES5는 함수를 어떻게 호출했는지 상관하지 않고 this 값을 설정할 수 있는 bind 메서드를 도입했고, ES2015는 스스로의 this 바인딩을 제공하지 않는 화살표 함수를 추가했습니다. MDN Web Docs

위 글을 읽고 의문점이 하나도 없었다면 아래 글은 읽지 않으셔도 좋습니다. 의문점이 하나라도 있었다면 읽어보는걸 추천드립니다.

문맥(context) 별 this 사용 예시

this를 알아보기 위해 전역 문맥과 함수 문맥을 알아볼 필요가 있습니다. 왜냐하면 자바스크립트에서 this는 runtime에 문맥에 따라 결정되기 때문입니다.

이와 달리 다른 언어에서의 this는 함수가 정의된 객체를 가리키기 때문에 헷갈릴 수 있습닌다.

전역 문맥에서의 this

전역 실행 문맥에서 this는 전역 객체를 참조하며 웹 브라우저에서의 전역 객체는 window 입니다. 그래서 아래와 같이 this와 window를 비교하면 true를 확인할 수 있습니다.

console.log(this === window); // true

그래서 전역 문맥에서 변수를 선언하면 결국 전역 객체인 window의 property가 된다고 할 수 있고 아래와 같은 결과가 타당하다고 생각할 수 있게 됩니다.

a = 37;
console.log(window.a); // 37

this.b = "MDN";
console.log(window.b); // "MDN"
console.log(b); // "MDN"

함수 문맥에서의 this

함수 문맥에서의 this는 시작에 있던 글처럼 함수를 호출한 방법에 의해 좌우됩니다.

• 직접 호출

  function f2(){
  return this;
  }
  

f2() === window; // true

위와 같은 결과가 된건 함수를 호출할 때 함수 f2를 객체의 메서드나(객체의 프로퍼티가 함수면 메서드) 속성으로써 호출한 것이 아니라 this의 값이 따로 설정되지 않았고 이런 상황에서 브라우저에서는 기본값인 window를 참조하기 때문입니다.

- 객체의 메서드로 호출

```javascript
const test = {
  prop: 42,
  func: function() {
    return this.prop;
  },
};

console.log(test.func());
// expected output: 42

함수가 호출될 때 test란 객체의 메서드로 호출되었으므로 func내에서의 this는 test를 가리키게 되고 test.prop인 42를 콘솔창에서 볼 수 있게 됐습니다.

bind

맨 위의 글을 다시 읽어보면 어떻게 호출됐는지 상관하지 않고 this 값을 설정할 수 있는 bind에 대해 언급하고 있습니다. bind는 언제 사용될까요? 먼저 일반적으로 함수의 호출방법에 따라 this가 가리키는 것이 달라졌었습니다. 그런데 내가 원하는 객체를 가리키고 싶다면 어떻게 할까요? 바로 bind를 사용하면 됩니다.

• bind를 사용하지 않고 직접 호출

a = "저는 전역 변수입니다";

function f() {
  return this.a;
}

console.log(f());//저는 전역 변수입니다.

위의 결과를 이해하셨나요? 이해되지 않으셨다면 전역 문맥에서의 this를 다시 한번 확인해주세요.

• bind를 사용하고 호출한 경우

a = "저는 전역 변수입니다";

function f() 
  return this.a;
}

var o = {
  a: "저는 객체 o의 프로퍼티 입니다.",
};

var g = f.bind(o);

console.log(g()); //저는 객체 o의 프로퍼티 입니다.

bind의 인자로 원하는 객체를 전달해주면 바인딩 된 새로운 함수를 return 해줍니다.

그러면 bind를 여러번 할 수 있을까요?

a = "저는 전역 변수입니다";

function f() {
  return this.a;
}

var o = {
  a: "저는 객체 o의 프로퍼티 입니다.",
};

var o1 = {
  a: "저는 객체 o1의 프로퍼티 입니다.",
};

var g = f.bind(o);
var h = g.bind(o1);
var i = f.bind(o1);

console.log(g()); //저는 객체 o의 프로퍼티 입니다.
console.log(h()); //저는 객체 o의 프로퍼티 입니다.
console.log(i()); //저는 객체 o1의 프로퍼티 입니다.

위의 결과를 정리해보면 이미 바인딩 된 함수는 다른 객체로 다시 바인딩되지 않고 바인딩 되지 않은 함수에 대해서는 여러번 바인딩 가능한 걸 알 수 있습니다.

화살표 함수에서의 this

우리는 이제 this를 어느정도 알고 바인딩이 무엇인지도 알고 있습니다. 그러면 스스로의 this 바인딩을 제공하지 않는 함수라는건 어떤 의미일까요?

화살표 함수에서 this를 참조하면 화살표 함수가 아닌 평범한 외부 함수에서 this 값을 가져옵니다. 이러한 특성은 콜백 함수로 전달할 때 매우 유용합니다. 아래 코드를 보고 결과값을 예상해주세요.

const classA = {
  className: "classA",
  students: [
    {
      name: "minseok",
      age: 28,
    },
    {
      name: "hee",
      age: 28,
    },
  ],

  printName() {
    this.students.forEach(function (student) {
      console.log(this.className + " " + student.name);
    });
  },
};

classA.printName();

오호 아래 결과를 예상하셨나요? 그럼 너무 잘 이해하셨네요. 혹시 저 코드의 의도는 아마 각 이름마다 클래스명을 붙여주고 싶었던 것 같아요. 바로 이럴 때 화살표 함수가 유용합니다.

undefined minseok
undefined hee

const classA = {
  className: "classA",
  students: [...],
  printName() {
    this.students.forEach((student) => {
      console.log(this.className +" "+ student.name);
    });
  },
};

classA.printName();

위처럼 화살표 함수를 사용하게 되면 가장 가까이에 있는 일반 함수의 this와 동일하게 사용하게 되고 그것은 바로 printName이죠 printName의 this는 classA를 가리키고 있으므로 아래와 같은 결과를 콘솔창에서 볼 수 있게 됐습니다.

classA minseok
classA hee

call, apply

call, apply 메서드 두개 모두 bind와 매우 유사하지만 전달하는 인자나 실행 순간이 조금 다릅니다. 예시를 통해 확인해봅니다.

call

a = "저는 전역 변수입니다";

function f(param) {
  console.log(this.a + " "+ param);
}

var o = {
  a: "저는 객체 o의 프로퍼티 입니다.",
};

f.call(o, "저는 params 입니다");
//저는 객체 o의 프로퍼티 입니다. 저는 params 입니다.

보시는 것과 같이 call은 바인딩과 동시에 parameter도 전달할 수 있고 실행까지 하는 메서드 입니다.

apply

apply는 call과 비슷하지만 parameter를 배열의 형태로 전달하여 실행시킵니다.

a = "저는 전역 변수입니다";

function f(param) {
  console.log(this.a + " " + param);
}

var o = {
  a: "저는 객체 o의 프로퍼티 입니다.",
};

f.apply(o, ["저는 params 입니다"]); //저는 객체 o의 프로퍼티 입니다. 저는 params 입니다.

인터넷 사용 기록을 삭제하려고보니 위와 같은 화면이 나옵니다. 사용 기록, 쿠키 및 기타 사이트 데이터, 캐시된 이미지 및 파일 삭제 여부를 고르라고 합니다. 아니 근데 쿠키를 지우면 대부분의 사이트에서 로그아웃 된다고 합니다.

❓쿠키를 삭제하면 왜 로그아웃이 될까요?

쿠키가 없다면 단순히 Request와 Response만으로 모든 것이 이루어집니다. 정확히는 이전에 통신했던 내용을 기억할 수 없습니다. 그래서 로그인을 하고나서 다른 페이지로 이동하면 로그인 했던 내용을 기억하지 못해서 다시 로그인을 해줘야하는거죠.

쿠키는 이런 상황에서 이전의 통신 내용을 기억하는 역할을 합니다. 쿠키가 상태가 없는 HTTP 프로토콜에서 상태정보를 기억하고 있는 역할을 하고 있었으므로 삭제하면 대부분의 사이트에서 로그아웃 된다고 하는 겁니다.

쿠키는 로그인 용도로만 사용될까요?

그렇지 않습니다. 아래와 같이 다양한 용도로 사용되고 있습니다.

• 세션 관리 서버에 저장해야 할 로그인, 장바구니, 게임 스코어 등의 정보 관리
• 개인화 사용자 선호, 테마 등의 세팅
• 트래킹 사용자 행동을 기록하고 분석하는 용도

🏃🏻‍♀️이제 쿠키의 여정을 따라가 봅시다.

1. 브라우저 -> 서버

hello.world 에게 첫 접속 요청을 보냅니다. 이때는 헤더에 쿠키에 관련된 정보는 없군요.

• Request Headers

  GET /index.html HTTP/1.1
  Host: www.hello.world
  ...

2. 서버 -> 브라우저

서버에서 브라우저로 요청에 대한 응답을 보냅니다. 쿠키가 담겨 있군요. theme과 같은 쿠키는 sessionToken과 달리 expires를 따로 정해주지 않아서 session 쿠키가 됩니다. session 쿠키는 브라우저가 닫힐 때 만료되게 됩니다.

• Response Headers

  HTTP/1.0 200 OK
  Content-type: text/html
  Set-Cookie: theme=light
  Set-Cookie: sessionToken=abc123; Expires=Wed, 09 Jun 2021 10:18:14 GMT
  ...

3. 브라우저 -> 서버

같은 호스트에게 다른 페이지로 이동을 위한 요청을 보냅니다. 이전에 서버에 의해 저장된 쿠키를 담아서 요청을 보냅니다. 그러면 서버에서는 이 쿠키를 받아보고 이전에 이런 내용을 주고 받앗구나 라는 걸 알게 됩니다.

• Request Headers

  GET /spec.html HTTP/1.1
  Host: www.hello.world
  Cookie: theme=light; sessionToken=abc123
  …

🚨 session 쿠키, permanent 쿠키

• Session cookie 쿠키의 여정을 보다가 만료 시점을 따로 정해주지 않으면 session쿠키가 된다고 했습니다. 즉 브라우저가 닫히면 사라지는 쿠키입니다.
• Permanent cookie 이와 달리 Expires나 Max-Age로 만료일을 정해주면 permanent 쿠키가 되며 누군가 지우지 않는다면 브라우저를 꺼도 만료일까지 살아있습니다.

그럼 이 쿠키는 어디에 저장되어있을까요?

바로 사용자의 컴퓨터에 저장되어 있습니다. 원한다면 열어볼 수도 있습니다. 일반적으로는 서버에 의해 사용자쪽에 저장되지만 자바스크립트를 이용해 클라이언트쪽에서도 설정이 가능합니다. 이렇게 저장된 쿠키는 동일한 서버에 재요청을 보낼때마다 함께 보내지게 됩니다.(물론 다른 서버에서 만든 쿠키까지 전송하진 않습니다.) 그럼 이제 쿠키의 최대 용량이 4KB인게 조금은 이해가 갑니다. 매 요청마다 전송해야하는데 1MB만 되어도 1000번 왔다갔다하면 1GB가 됩니다. 서버쪽에서의 부담이 매우 커지겠죠.

[궁금하면 읽어보세요] 세션은 무엇인가요?

쿠키를 찾아보면 세션에 대한 이야기도 따라오는게 자연스럽습니다. 두 개가 뭔가 관련이 있는 것 같은데 세션은 무엇인지 느낌이 안 올 수 있습니다. 우선 세션 자체는 서버에 저장됩니다. 서버에 저장된 세션의 id를 쿠키를 통해 저장한다고 생각하면 됩니다. 이렇게 하는 이유는 쿠키에 모든 정보를 저장하고자 하니 보안에 취약하므로 정보는 서버에 저장하되 정보의 키가 되는 값을 쿠키에 저장하는 것입니다. 결국 세션도 쿠키를 이용하는 방법 중 하나입니다.

웹 스토리지

웹 스토리지도 쿠키처럼 클라이언트 쪽에 정보를 저장할 수 있는 storage로 HTML5에서 추가되었습니다. 통신시마다 전송하지 않는다는 점이 쿠키와의 큰 차이점입니다. 이러한 특성으로 브라우저별로 다르지만 쿠키의 최대 용량 4KB와 달리 약 5MB의 상대적으로 큰 최대 용량을 갖습니다. 웹 스토리지는 Local Storage와 Session Storage 2가지가 있습니다.

Local Storage

사용자가 지우지 않는다면 데이터가 영구적으로 지워지지 않습니다.

데이터 삽입

문자열의 형태로 저장하므로 객체를 저장하고 싶다면 JSON.stringify를 사용해서 문자열로 변환 후 저장해주어야합니다.

localStroage.setItem(<KEY>, <VALUE>);

데이터 조회

문자열로 저장되어있으므로 객체를 받아오고 싶다면 JSON.parse를 이용해객체로 변환 해주어야합니다.

const data = localStorage.getItem(<KEY>);

Session Storage

데이터 삽입 삭제 조회를 위한 메서드는 localStorage와 동일합니다. 하지만 브라우저 탭을 닫으면 localStorage와 달리 데이터가 사라지는 점이 다릅니다.

참조

1. [Web][조금 더 자세히]도대체 왜 이름이 쿠키인걸까?, 상태를 저장하는 http cookie

2. MDN HTTP 쿠키

3. 위키피디아 쿠키

B는 완전 이진 트리가 아니다.

최대 힙에 포함된 부모 노드는 자식 노드에 들어있는 값보다 크고 최소 힙에 포함된 부모 노드는 자식 노드에 들어있는 값보다 작습니다. 그래서 최대 최소 값을 찾는데 매우 유용합니다.

최대 힙

최대 힙에서는 루트 노드가 가장 큰 값을 갖습니다. 또한 완전 이진 트리이므로 N개가 들어있다면 트리의 높이는 logN이 됩니다.

최대 힙 삽입

• 가장 마지막 위치에 삽입할 수를 위치시킨다. 완전 이진 트리이므로 가장 왼쪽 위치가 마지막 위치가 된다.
• 부모와 비교하며 현재 노드가 더 크면 위치를 바꾼다.
• 부모와 비교하여 현재 노드가 작으면 멈춘다. 그 위치가 삽입 위치가 된다.
• 최대 높이 만큼 탐색하게 되므로 복잡도 $O(logN)$으로 가능합니다.

최대 힙 제거

• 제거할 노드를 루트로 하느 서브 트리에서 가장 마지막 위치의 노드를 제거할 노드의 위치로 옮긴다. (일단 target제거 완료)

• 루트에서 시작하여 자식과 비교하며 자식이 더 크면 위치를 바꾸며 반복한다.
• 자식이 작거나 없다면 멈춘다.
• 최대 높이 만큼 탐색하게 되므로 복잡도 $O(logN)$으로 가능합니다.

  최소 힙

  루트 노드가 트리에서 가장 작은 값이 되는 구조입니다.

  최소 힙 삽입

  최대 힙 삽입과 부등호만 반대로 해주면 구현 가능합니다.

최소 힙 삭제

최대 힙 삭제와 부등호만 반대로 해주면 구현 가능합니다.

JAVA에서의 힙

JAVA에서 우선순위에 따라 정렬되는 PriorityQueue의 내부에는 Heap으로 구현되어 있으며 기본적으로는 최소값이 우선 순위가 높은 최소 힙입니다. 만약 최대 힙으로 바꾸고 싶다면

• Comparator를 이용하거나

  PriorityQueue<Integer> q = new PriorityQueue<>(1, 비교자)

• 값 자체에 -1을 곱해주는 방법

총 2가지로 가능합니다.

이진 탐색 트리는 한 노드를 기준으로 왼쪽 자식 노드를 루트로 하는 서브 트리의 모든 노드 값은 현재 노드보다 작은 값을 갖고 오른쪽 자식 노드를 루트로 하는 서브 트리의 모든 노드 값은 현재 노드보다 큰 값을 갖는다.

이진 탐색 트리 삽입

삽입할 노드가 들어갈 위치를 찾고($O(logN)$) 현재 노드보다 작으면 왼쪽 크면 오른쪽에 삽입

이진 탐색 트리 삭제

삭제도 삽입과 마찬가지로 먼저 삭제할 노드의 위치를 찾는다. 찾은 후에 아래 3가지 경우로 나뉘게 된다.

삭제할 노드의 자식이 0개인 경우

리프 노드를 제거하는 것이므로 부모 노드와 자식 노드의 관계를 끊어주기만 하면 된다.

삭제할 노드의 자식이 1개인 경우

삭제할 노드의 부모 노드와 삭제 할 노드의 자식 노드를 이어준다. 한개이므로 이진 트리를 벗어나지 않는다.

삭제할 노드의 자식이 2개인 경우

• 1. 삭제 대상 노드를 삭제한다.
• 2. 삭제 대상 노드의 자리를 대신할 노드를 찾아야 한다.
• 3. 왼쪽 자식 노드를 루트로 하는 서브 트리의 모든 값보다는 크고 오른쪽 자식 노드를 루트로 하는 서브 트리의 모든 값보다는 작아야 한다. 즉 왼쪽 서브 트리의 최대 값이나 오른쪽 서브 트리의 최소 값이 삭제된 노드를 대신할 수 있다.
• 4-1. 이진 탐색 트리의 최소 값은 왼쪽 자식을 타고 가다가 리프 노드가 나오면 된다.
• 4-2. 이진 탐색 트리의 최대 값은 오른쪽 자식을 타고 가다가 리프 노드가 나오면 된다.
• 5. 4-1과 4-2중 한 값으로 삭제된 노드를 대신하면 삭제 과정이 완료된다.

임의의 루트 있는 트리의 간선 정보가 주어질 때 정점을 주면 정점을 루트로 하는 서브 트리에 포함된 정점의 개수를 구하는 문제입니다.

접근

1. dfs를 사용할건데요. dfs를 작성할때 일반적으로는 check 배열이나 visited 배열을 사용해서 방문한 정점을 체크하실텐데요. 트리에서는 check배열없이도 dfs를 진행할 수 있습니다. 그 이유는 트리에서 한 정점 u에 다른 정점 v로 부터 왔다고 했을 때 그 v정점에 다시 방문하지 않는다면 모든 정점에는 딱 한번만 방문하게 됩니다.

• 트리의 특징
  • 임의의 두 정점 u와 v에 대해 단순 경로는 유일하다
  • 사이클이 없는 무방향 연결 그래프이다.
  • 간선의 개수가 정점의 개수보다 하나 작다.

2. 1번의 코드를 살펴보면 아래와 같습니다. check배열이 없기 때문에 코드도 매우 간결합니다.

    static void dfs(int now, int before) {
        for (int next : list[now]) {
            if (next == before)
                continue;
            dfs(next, now);
        }
    }
   
    dfs(root,root);

3. 위와 같이 dfs를 진행한다고 했을 때 sub트리에 포함된 정점을 구하기 위해서 정점의 개수를 길이로 하는 배열을 하나 만들겠습니다. 이 배열을 sub배열이라고 할게요. dfs에서 now 정점을 시작으로 before를 제외한 now정점과 연결된 모든 정점을 방문할텐데요.이 과정에서 점화식을 세워보면 $sub[now] = 1 +\sum sub[next]$가 됩니다. 1은 now정점 자기자신을 포함하기 위해 더해주었습니다.

코드(JAVA)

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

class baek__15681 {
    static ArrayList<Integer>[] list;
    static int[] sub = new int[100001];

    static void dfs(int now, int before) {
        sub[now] += 1;
        for (int next : list[now]) {
            if (next == before)
                continue;
            dfs(next, now);
            sub[now] += sub[next];
        }
    }

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

        String[] temp = br.readLine().split(" ");

        int n = Integer.parseInt(temp[0]);
        int r = Integer.parseInt(temp[1]);
        int q = Integer.parseInt(temp[2]);

        list = new ArrayList[n + 1];

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

        for (int i = 0; i < n - 1; i++) {
            temp = br.readLine().split(" ");
            int u = Integer.parseInt(temp[0]);
            int v = Integer.parseInt(temp[1]);

            list[u].add(v);
            list[v].add(u);
        }

        dfs(r, r);

        StringBuilder sb = new StringBuilder();
        while (q-- > 0) {
            int qq = Integer.parseInt(br.readLine());
            sb.append(sub[qq] + "\n");
        }

        System.out.print(sb);

    }
}

$npm install node-sass or $yarn add node-sass

project

project
  |--src
   +|--Component.scss
   +|--Component.js

Component.scss

$red: red;

@mixin square($size){
    width: $size*1px;
    height: $size*1px;
}

.box{
  background: $red;
  @include square(1);
}

Component.js

import './Component.scss';

const Component = () => {
  return <div className="box">
  </div>;
}

결과

실행중인 앱 중에서 재실행할 비용과 현재 점유중인 메모리가 주어지고 새로운 앱을 실행하기 위해 앱을 종료시킬 최소 비용을 구하는 문제입니다.

• 실행중인 앱의 개수 N <= 100

• 실행할 앱의 메모리 M <= 10000000

• 실행중인 앱을 재실행하기 위한 비용 c <= 100

• 실행중인 앱의 메모리 m의 합 <= 10000000

  접근

  문제를 읽어보면 knapsack문제와 유사한 구조라는 걸 알 수 있습니다. 그러면 knapsack 문제를 생각해봅니다. 각 물건에 대한 가치와 무게가 주어지고 제한된 무게를 담을 수 있는 가방에 넣을 수 있는 최대가치를 구합니다. 각 변수를 현재 문제와 연결해봅니다

• 가치 => 실행중인 앱을 종료하여 얻는 메모리

• 무게 => 실행중인 앱을 종료 후 재실할 때 필요한 비용

즉 제한된 비용에 대해 최대 가치를 얻는 문제로 바꿔 생각할 수 있습니다. 이런 방법으로 문제를 해결하기 위해서 우리는 2차원 배열이 필요하며 그 배열의 크기는 100x100x100입니다. 100만이죠. 또한 하나의 배열을 구하기 위한 호출 횟수는 2회이므로 200만의 복잡도로 문제가 해결가능합니다. 주의 사항으로 답을 구하기 위해서는 0부터 최대 비용 까지 for문을 돌며 해당하는 최대 가치가 M을 넘으면 for문을 종료하고 답을 출력해주면 됩니다.

knapsack문제와 유사하지만 최대가치를 구하는 것이 아니라 원하는 가치에 대한 최소비용을 구하는 문제라 접근이 조금은 어려울 수 있었던 문제라고 생각합니다.

knapsack 문제의 정석 풀이

코드

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

class Pair {
    int m;
    int c;

    Pair(int m, int c) {
        this.m = m;
        this.c = c;
    }
}

class baek__7579 {
    static Pair[] pairs = new Pair[101];
    static int[][] d = new int[100 * 100 + 1][101];

    static int go(int c, int n) {
        if (c <= 0) {
            if (c == 0)
                return 0;
            return -20000000;
        }
        if (n < 0)
            return 0;

        if (d[c][n] != -1)
            return d[c][n];

        d[c][n] = Math.max(go(c - pairs[n].c, n - 1) + pairs[n].m, go(c, n - 1));

        return d[c][n];
    }

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

        String[] temp = br.readLine().split(" ");
        int n = Integer.parseInt(temp[0]);
        int m = Integer.parseInt(temp[1]);

        temp = br.readLine().split(" ");
        String[] temp1 = br.readLine().split(" ");

        for (int i = 0; i < n; i++) {
            int memory = Integer.parseInt(temp[i]);
            int cost = Integer.parseInt(temp1[i]);
            pairs[i] = new Pair(memory, cost);
        }

        for (int i = 0; i < 100 * 100 + 1; i++) {
            for (int j = 0; j < 101; j++) {
                d[i][j] = -1;
            }
        }

        for (int i = 0; i < 100 * 100 + 1; i++) {
            if (go(i, n - 1) >= m) {
                System.out.print(i);
                return;
            }
        }
    }
}

문제는 요약하기가 쉽지 않아 링크 참고 바랍니다.

접근

1. 정말 놀라운 사실은 바로 행과 열이 서로 영향을 미치지 않는다는 겁니다. 이게 어떤 말인지 알기 위해 이런 생각을 해봅니다. 1차원 배열이 있다고 생각하고 사탕 줍기 대회의 규칙과 비슷하게 사탕을 주으면 양 옆에 사탕이 없어진다고 생각해봅니다. 이런 상황에서 최대의 결과를 얻기 위해서 어떻게 하면 될까요?
2. $d[N]$을 N번째 index까지 최대 결과라고 정의합니다.
3. 그렇다면 현재 N번째 index의 사탕을 주을지 안주을지 두가지 경우로 나누어 점화식을 세울 수 있습니다. $d[N] = MAX(d[N-2]+a[N], d[N-1])$
4. 여기서부터 생각을 좀 더 확장해 문제에 적용해봅니다. 각 행에 대해 3번과 같은 과정을 통해 해당 행에서 구할 수 있는 최대 사탕값을 구합니다. 그럼 우리는 각 행에서 구할 수 있는 최대값을 얻습니다.
5. 위와 같은 결과를 얻게 되면 우리는 다시한번 비슷한 과정을 반복하는 점화식을 세울 수 있습니다. 행마다의 최대값과 구분되게 d대신 e를 사용하겠습니다. $e[N] = MAX(e[N-2]+e[N], e[N-1])$

코드

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

class baek__5721 {
    static int[][] map;
    static int[][] d;
    static int[][] d2;

    static int go(int n, int m) {// 열에서 큰거
        if (m < 0)
            return 0;

        if (d[n][m] != -1)
            return d[n][m];

        d[n][m] = Math.max(go(n, m - 2) + map[n][m], go(n, m - 1));

        return d[n][m];
    }

    static int go2(int n, int m) {
        if (n < 0)
            return 0;

        if (d2[n][m] != -1)
            return d2[n][m];

        d2[n][m] = Math.max(go2(n - 2, m) + go(n, m), go2(n - 1, m));

        return d2[n][m];
    }

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

        StringBuilder sb = new StringBuilder();
        while (true) {
            String[] temp = br.readLine().split(" ");
            int r = Integer.parseInt(temp[0]);
            int c = Integer.parseInt(temp[1]);
            if (r == 0 && c == 0)
                break;

            map = new int[r][c];
            d = new int[r][c];
            d2 = new int[r][c];

            for (int i = 0; i < r; i++) {
                temp = br.readLine().split(" ");
                for (int j = 0; j < c; j++) {
                    map[i][j] = Integer.parseInt(temp[j]);
                    d[i][j] = -1;
                    d2[i][j] = -1;
                }
            }

            sb.append(go2(r - 1, c - 1) + "\n");
        }
        System.out.print(sb);
    }
}

서윤이의 최대 공부시간 N이 주어지고 각 과목에 필요한 공부시간과 중요도가 주어진다. 최대 공부시간안에 가장 큰 중요도를 출력하는 문제입니다.

• 최대 공부시간 1<= N <= 10000
• 과목 수 1 <= K <= 1,000

접근

1. 매우 전형적인 knapsack problem 입니다.
2. $d[N][M]$을 0 - M번째 과목들을 대상으로 최대 N시간을 써서 얻을 수 있는 가장 큰 중요도로 정의합니다.
3. M번째 과목을 들을지 안들을지를 이용해서 이런 점화식을 세웁니다.

• 안듣는 경우 $d[N][M-1]$
• 듣는 경우 $d[N-t[M]][M-1]+v[M]$

$d[N][M] = Math.max(d[N][M-1], d[N-t[M]][M-1]+v[M])$

4. 초기값에 대하여 헷갈린다면 아래를 생각해보자. 사실 제가 초기값을 정하는게 헷갈려서 적어봅니다..
   • n < 0 n이 0보다 작으면 주어진 시간보다 더 많이 썼다는 것이므로 모든 값을 상쇄시킬 정도로 작은 값인 - 최대 과목 수 x 최대 중요도를 return해줍니다.
   • n == 0 주어진 시간에 맞게 시간을 썼다는 것이므로 0을 return 해줍니다.
   • m < 0 주어진 과목이 없으므로 어떻게 해도 0밖에 될 수 없습니다. 따라서 0을 return 합니다.

JAVA 코드

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

class baek__17845 {
    static int[][] d = new int[10001][1000];
    static int[] v;
    static int[] t;

    static int go(int n, int k) {
        if (n <= 0) {
            if (n == 0)
                return 0;
            return -100000000;
        }
        if (k < 0)
            return 0;

        if (d[n][k] != -1)
            return d[n][k];

        d[n][k] = Math.max(go(n, k - 1), go(n - t[k], k - 1) + v[k]);

        return d[n][k];
    }

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

        String[] temp = br.readLine().split(" ");

        int n = Integer.parseInt(temp[0]);
        int k = Integer.parseInt(temp[1]);

        v = new int[k];
        t = new int[k];
        for (int i = 0; i < k; i++) {
            temp = br.readLine().split(" ");
            v[i] = Integer.parseInt(temp[0]);
            t[i] = Integer.parseInt(temp[1]);
        }

        for (int i = 0; i < n + 1; i++) {
            for (int j = 0; j < k; j++) {
                d[i][j] = -1;
            }
        }

        System.out.print(go(n, k - 1));
    }
}