0%

작성일 Edited on In Disqus:

Github에서 코드 확인하기 - 클릭

Redux

Redux는 페이스북에서 만든 자바스크립트 라이브러리이다. 앞서 말한 Flux의 아이디어를 발전시키되 복잡성을 줄였다. React만 사용해도 되지만 대규모 애플리케이션의 경우 상태 관리하기가 힘들어진다. 그래서 Redux를 사용해 상태 관리를 하는 것이다.

Redux의 개념

Redux의 기본 개념은 Flux의 기본 개념과 동일하다. 언급하지 않은 게 있는데, 바로 구독(Subscribe)과 리듀서(Reducer)라는 개념이다.

구독(Subscribe)

구독은 원하는 스토어를 설정해서 그 스토어에서 값을 받아온다고 생각하면 된다. 개념이 유튜브의 구독과 거의 똑같다. 원하는 채널(스토어)을 구독하고 그 채널의 동영상(데이터)를 본다는 것에 비유하면 이해하기가 쉽다. Redux의 내장함수에는 구독 함수가 존재하지만, react-redux를 사용하면 connect 함수가 대신 해준다. 따라서 직접 구독 함수를 사용할 일은 거의 없다.

리듀서(Reducer)

액션은 무언가가 일어난다는 사실만을 기술한다. 애플리케이션의 상태가 어떻게 바뀌는지 정해주는 것은 리듀서가 할 일이다.

Redux로 카운터 만들기

결과 미리보기

result
플러스, 마이너스는 표시된 수를 더하고 뺀다. 랜덤 버튼을 누르면 랜덤한 숫자가 표시된다. 정말 심플한 카운터다.

시작하기

React 프로젝트를 생성하고 redux, react-redux를 전부 설치한다. redux는 리덕스 모듈이고, react-redux는 리액트에서 리덕스를 사용하기 위한 보조 패키지이다.

1
2
3
4
5
6
7
8
# React 프로젝트 생성하기
$ create-react-app redux-counter

# 폴더 이동
$ cd redux-counter

# redux, react-redux 전부 설치하기
$ yarn add redux react-redux

디렉토리 구조

주요 디렉토리 구조는 다음과 같다.

1
2
3
4
5
6
7
8
9
src
├── App.js
├── index.js
├── actions
│   └── index.js
├── reducers
│   └── index.js
└── components
    └── Counter.js

actions 폴더에서는 프로젝트의 모든 action을, reducers 폴더에는 프로젝트의 모든 reducer를 관리한다. 이건 아주 간단한 애플리케이션이기 때문에 index.js 파일 하나만 있으면 된다.

컴포넌트 만들기

일단 뷰를 먼저 만들어준다. Counter 컴포넌트를 만들고 App.js에서 불러와주면 된다.

App.js

1
2
3
4
5
6
7
8
9
10
11
import React, { Component } from "react";
import "./App.css";
import Counter from "./components/Counter.js";

class App extends Component {
  render() {
    return <Counter />;
  }
}

export default App;

/components/Counter.js

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
import React, { Component } from "react";

class Counter extends Component {
  render() {
    return (
      <div>
        <p>0</p>
        <button>+</button>
        <button>-</button>
        <button>random</button>
      </div>
    );
  }
}

export default Counter;

액션 만들기

액션 타입과 액션 생성 함수를 정의한다. 액션은 무언가가 일어난다는 사실만을 적어준다. 액션 생성 함수를 정의할 때는 export를 해주어야 나중에 컴포넌트에서 불러올 수 있다.

/actions/index.js

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// 액션 타입 정의
export const INCREMENT = "INCREMENT";
export const DECREMENT = "DECREMENT";
export const RANDOM_NUMBER = "RANDOM_NUMBER";

// 액션 생성 함수 정의
export function increment() {
  return {
    type: INCREMENT
  };
}

export function decrement() {
  return {
    type: DECREMENT
  };
}

export function random_number() {
  return {
    type: RANDOM_NUMBER
  };
}

리듀서 만들기

리듀서는 애플리케이션의 상태가 어떻게 바뀌는지를 알려준다. 리듀서가 여러 개일 때는 redux의 내장함수인 combineReducers를 사용해서 리듀서를 하나로 합치는 작업을 한다. 지금 만드는 카운터는 정말 심플해서 리듀서가 하나밖에는 없지만 한번 사용해보았다.

/reducers/index.js

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
// 액션과 내장함수 combineReducers 불러오기
import { INCREMENT, DECREMENT, RANDOM_NUMBER } from "../actions";
import { combineReducers } from "redux";

// 초기 상태(값) 정의
const initialState = {
  number: 0
};

// 리듀서 작성
const counter = (state = initialState, action) => {
  switch (action.type) {
    case RANDOM_NUMBER:
      return {
        ...state,
        number: Math.floor(Math.random() * 10)
      };
    case INCREMENT:
      return {
        ...state,
        number: state.number + 1
      };
    case DECREMENT:
      return {
        ...state,
        number: state.number - 1
      };
    default:
      return state;
  }
};

const counterApp = combineReducers({
  counter
  // 다른 리듀서를 만들면 이 아래에 적어준다
});

export default counterApp;

switch-case 문으로 각 액션마다 어떻게 상태가 바뀌는지를 정해준다. 이것도 마찬가지로 export를 해주어야 한다. export한 리듀서는 스토어를 만들 때 사용한다.

스토어를 만들고 연동하기

Redux 라이브러리 안에 있는 createStore 함수를 사용해서 스토어를 만들어준다. 스토어는 아까 export한 리듀서로 만들 수 있다. 그리고 react-redux 라이브러리안에 있는 Provider 함수를 사용해서 createStore 함수로 만든 스토어를 연동해주면 된다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
import React from "react";
import ReactDOM from "react-dom";
import "./index.css";
import App from "./App";
import * as serviceWorker from "./serviceWorker";

// createStore와 리듀서 불러오기
import { createStore } from "redux";
import counterApp from "./reducers";

// Provider 불러오기
import { Provider } from "react-redux";

// 스토어 만들기
const store = createStore(counterApp);

// Provider 사용해서 기존의 App 감싸주기
ReactDOM.render(
  <Provider store={store}>
    <App />
  </Provider>,
  document.getElementById("root")
);

serviceWorker.unregister();

connect 함수를 사용해 스토어 연동하기

마지막으로 컴포넌트에 리덕스 스토어 안에 있는 값과 액션 생성 함수를 연결해주면 된다. 이건 react-redux의 내장함수 connect 함수를 사용하면 된다. connect 함수로 연동한 스토어에서 받아오는 값과 액션 생성 함수는 this.props로 접근이 가능하다.

스토어를 연동하기 전에 mapStateToProps와 mapDispatchProps의 개념을 알아야 한다. mapStateToProps는 스토어 안에 있는 값을 props로 전달해주고, mapDispatchProps는 액션 생성 함수를 props로 전달해준다.

지금 만든 스토어에는 값이 number, 액션 생성 함수는 increment, decrement, random_number가 전부이다. number는 mapStateToProps를 사용해 props로 전달하고, increment, decrement, random_number는 mapDispatchProps를 사용해 props로 전달한다.

/components/Counter.js

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
// 액션 생성 함수와 react-redux의 내장함수 connect 불러오기
import React, { Component } from "react";
import { connect } from "react-redux";
import { increment, decrement, random_number } from "../actions";

class Counter extends Component {
  render() {
    return (
      <div>
        <p>{this.props.number}</p>
        <button onClick={this.props.handleIncrement}>+</button>
        <button onClick={this.props.handledecrement}>-</button>
        <button onClick={this.props.handleRandom}>random</button>
      </div>
    );
  }
}

// 스토어 안에 있는 값을 props로 전달
const mapStateToProps = state => {
  return {
    number: state.counter.number
  };
};

// 액션 생성 함수를 props로 전달
// 모든 액션은 dispatch를 통해 store에 전달된다는 것을 잊지 말자
const mapDispatchProps = dispatch => {
  return {
    handleIncrement: () => {
      dispatch(increment());
    },
    handledecrement: () => {
      dispatch(decrement());
    },
    handleRandom: () => {
      dispatch(random_number());
    }
  };
};

// connect 함수 사용해서 컴포넌트에 리덕스 스토어 연동
export default connect(mapStateToProps, mapDispatchProps)(Counter);

Reference

  • Redux 공식 문서(한글)
  • Velopert님 블로그

작성일 Edited on In Disqus:

Baekjoon Online Judge - 2193

Review

example

  • 이미지를 보고 규칙을 찾아보면, 주어진 수가 n일 때 n - 1, n - 2를 해서 원하는 값들을 찾을 수가 있다.
  • 점화식은 이렇다. dp[i] = dp[i - 2] + dp[i - 1]

Code (JAVA)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
import java.io.*;

public class Main {

  public static void main(String args[]) throws IOException{
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    int n = Integer.parseInt(br.readLine());
    long dp[] = new long[n + 1];

    dp[0] = 0;
    dp[1] = 1;

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

    System.out.println(dp[n]);
  }
}

작성일 Edited on In Disqus:

Baekjoon Online Judge - 10844

Review

  • 쉽게 말하자면 끝수-1을 변수 j라고 했을 때, 계단수는 j+1, j-1이 됨.
  • 예를 들어 자릿수가 3이고 27의 계단수를 구한다고 했을 때, 계단수는 27(7-1), 27(7+1)로 각 276, 278이 된다.
  • 구하려는 끝수를 변수 i이라고 한다면, 점화식은 다음과 같다.
  • dp[i][j] = dp[i-1][j-1] + dp[i-1][j+1]
  • 시작이 0일 경우, 끝이 9일 경우의 처리를 반드시 해주어야 한다.

Code (JAVA)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
import java.io.*;

public class Main {

  public static void main(String args[]) throws IOException{
    int[][] dp = new int[101][10];
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    int n = Integer.parseInt(br.readLine());
    int MOD = 1000000000;
    long sum = 0;

    for(int i = 1; i <= 9; i++) {
      dp[1][i] = 1;
    }

    for(int i = 2; i <= n; i++) {
      for(int j = 0; j <= 9; j++) {
        if(j == 0) {
          dp[i][0] = dp[i - 1][1] % MOD;
        } else if(j == 9) {
          dp[i][9] = dp[i - 1][8] % MOD;
        } else {
          dp[i][j] = (dp[i - 1][j - 1] + dp[i - 1][j + 1]) % MOD;
        }
      }
    }


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

    System.out.println(sum % MOD);
  }
}

작성일 Edited on In Disqus:

Baekjoon Online Judge - 2748

Review

  • 점화식으로 푸는 피보나치 수.
  • 백준 10844 풀다가 너무 스트레스받아서 이거 풀었음…ㅡㅡ;;
  • 11727번이랑 풀이가 비슷하다. 아니 똑같다고 봐도 무방.
  • 점화식은 문제에 나와있으니 그대로 적용해서 풀면 된다.

Code (JAVA)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
import java.io.*;

public class Main {

  public static void main(String args[]) throws IOException{
    BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
    int n = Integer.parseInt(bf.readLine());
    long memo[];

    memo = new long[n + 1];

    memo[0] = 0;
    memo[1] = 1;

    for(int i = 2; i <= n; i++) {
      memo[i] = memo[i - 1] + memo[i - 2];
    }

    System.out.println(memo[n]);
  }
}

작성일 Edited on In Disqus:

Baekjoon Online Judge - 11727

Review

  • 백준 11726번 문제를 조금만 바꾸면 된다.
  • 2x2 타일이 추가된 것이므로, 그 말인 즉슨 n-2인 경우가 2배가 된다는 것이다.
  • 점화식은 A[n] = A[n-1] + A[n-2] * 2
  • 참고로 memo[2]일 경우의 값을 3으로 바꿔주어야 한다. 직사각형이 2x2 크기인 경우의 경우의 수가 3이기 때문.

Code 1 (JAVA)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
import java.io.*;

public class Main {

  static long[] memo;

  public static long tile(int n) {
    if(n == 1) {
      memo[1] = 1;
      return memo[1];
    } else if(n == 2) {
      memo[2] = 3;
      return memo[2];
    } else if(memo[n] != 0) {
      return memo[n] %= 10007;
    } else {
      memo[n] = tile(n - 1) + tile(n - 2) * 2;
      return memo[n] %= 10007;
    }
  }

  public static void main(String args[]) throws IOException{
    BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
    int input = Integer.parseInt(bf.readLine());
    memo = new long[input + 1];
    System.out.println(tile(input));
  }
}

Code 2 (JAVA)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
import java.io.*;

public class Main {

  public static void main(String args[]) throws IOException{
    BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
    int input = Integer.parseInt(bf.readLine());
    long[] memo;

    memo = new long[1001];

    memo[1] = 1;
    memo[2] = 3;

    for(int i = 3; i <= input; i++) {
      memo[i] = (memo[i-1] + memo[i-2] * 2) % 10007;
    }

    System.out.println(memo[input]);
  }
}

작성일 Edited on In Disqus:

자바스크립트 this 바인딩

자바스크립트의 this는 현재 실행 문맥이다. 여기서 현재 실행 문맥이라는 건 무엇을 뜻할까? 바로 호출자를 뜻한다.
호출자는 크게 세 가지로 나뉘어진다. 첫 번째는 객체의 메소드, 두 번째는 함수, 그리고 마지막으로 생성자 함수이다. 만약 this가 나온다면 이 세 가지 경우 중 하나이니 누가 호출했는지 보고 this가 어떤 의미를 가지는지를 따져보면 된다. 이를 함수 호출 패턴이라고 하며, 자바스크립트의 this 는 함수 호출 패턴에 따라 this 가 어떤 객체의 this 가 될 지 정해진다. 이를 this 바인딩이라고 한다.
바인딩(biding)의 사전적 의미는 묶이다인데, 누가 호출했는지에 따라 this가 호출자에게 묶인다는 의미로 이해하면 그나마 이해하기 쉬워진다.

1. this 바인딩의 호출 패턴

  • 객체의 메소드를 호출할 때의 this 바인딩
  • 함수를 호출할 때의 this 바인딩
  • 생성자 함수를 호출할 때의 this 바인딩

1.1 객체의 메소드 호출할 때 this 바인딩

자신을 호출한 객체에 바인딩이 된다.

1
2
3
4
5
6
7
8
9
10
11
12
13
var obj = {
  sayName: function() {
    console.log(this.name);
  }
};

var kim = obj;
kim.name = "kim";
kim.sayName(); // "kim"

var lee = obj;
lee.name = "lee";
lee.sayName(); // "lee"

1.2 함수를 호출할 때 this 바인딩

전역 객체(window)에 바인딩이 된다.

1
2
3
4
5
6
7
8
9
var val = "Hello";

var func = function() {
  console.log(this.val);
};
func(); // "Hello"
console.log(this.val); // "Hello"
console.log(window.val); //  "Hello"
console.log(this === window); // true

하지만 함수 호출에서의 this 바인딩은 내부 함수를 호출할 때도 그대로 적용이 된다. 아래 예제를 보면, 결과가 2,3,4 로 나와야 할 것 같지만 그렇게 나오지 않는다. 왜냐면 자바스크립트가 내부 함수 호출 패턴을 정해놓지 않았기 때문에, 내부 함수도 함수 취급을 받아 이러한 결과가 나온 것이다.
따라서 함수 호출 패턴 패턴 규칙에 따라 내부 함수의 this 는 전역 객체(window)에 바인딩된다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
// 전역 변수 value 정의
var value = 100;

// myObject 객체 생성
var myObject = {
  value: 1,
  func1: function() {
    this.value += 1;
    console.log("func1() called. this.value : " + this.value);

    // func2() 내부 함수
    func2 = function() {
      this.value += 1;
      console.log("func2() called. this.value : " + this.value);

      // func3() 내부 함수
      func3 = function() {
        this.value += 1;
        console.log("func3() called. this.value : " + this.value);
      };

      func3(); // func3() 내부 함수 호출
    };
    func2(); // func2() 내부 함수 호출
  }
};
myObject.func1(); // func1() 메소드 호출

위와 같은 상황을 피하려면, 부모 함수의 this 를 내부 함수가 접근 가능한 다른 변수에다 저장해야 한다. 보통 this 값을 저장하는 변수의 이름을 that 이라고 짓는다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
// 내부 함수 this 바인딩
var value = 100;

var myObject = {
  value: 1,
  func1: function() {
    var that = this; // 부모 함수의 this를 that으로 저장

    this.value += 1;
    console.log("func1() called. this.value : " + this.value);

    func2 = function() {
      that.value += 1;
      console.log("func2() called. this.value : " + that.value);

      func3 = function() {
        that.value += 1;
        console.log("func3() called. this.value : " + that.value);
      };
      func3();
    };
    func2();
  }
};

myObject.func1(); // func1 메소드 호출

1.3 생성자 함수를 호출할 때 this 바인딩

new 로 생성자 함수를 생성한 객체에 바인딩이 된다.

1
2
3
4
5
6
7
8
9
var Person = function(name) {
  this.name = name;
};

var kim = new Person("kim");
console.log(kim.name); //kim

var lee = new Person("lee");
console.log(lee.name); //lee

작성일 Edited on In Disqus:

Baekjoon Online Judge - 1110

Review

  • 단순 계산 문제.
  • 처음에는 input을 String으로 받아 charAt으로 자리를 따져가며 풀었는데 내가 너무 어렵게 접근한 거였더라… 역시 머리가 나쁘면 몸이 고생한다.
  • 나머지와 나누기 연산으로 각 자릿수를 구한 다음에 문제가 하라는대로 하면 된다.

Code (JAVA)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
import java.io.*;

public class Main {
  
  public static void main(String args[]) throws IOException{
    BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
    int input = Integer.parseInt(bf.readLine());
    
    int number = input;
    int cnt = 0;
    
    do {
      int left = number / 10;
      int right = number % 10;
      int hap = left + right;
      
      number = (right * 10) + (hap % 10);
      cnt++;
      } while(input != number);
    
    System.out.println(cnt);
  }
}

작성일 Edited on In Disqus:

Baekjoon Online Judge - 11726

Review

  • 타일링을 하나하나 그려서 깨달음을 얻은 문제.
  • 전반적인 건 피보나치 수열과 비슷하다.
  • 맨 앞이 1이 될 경우, 2가 될 경우를 전부 계산하면 된다.
  • 점화식은 A[n] = A[n-1] + A[n-2]
  • 금방 풀은 줄 알았는데 자꾸 틀렸다고 하길래 보니까 10007로 나눈 나머지를 출력하지 않아서 그런 거였다. 920을 입력할 경우 답이 음수가 나왔는데(오버플로우) 정답에 나누기를 하지 말고 중간에 더할 때부터 나머지 값을 계산했더니 정답이 나왔다.
  • 다른 사람들이 푼 걸 보니까 for문으로 많이 풀었더라… 나는 피보나치 함수 풀었던 거 재활용하느라 함수를 만들어서 풀었다.

Code (JAVA)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
import java.io.*;

public class Main {
  
  static long[] memo;
  
  public static long tile(int n) {
    if(n == 1) {
      memo[1] = 1;
      return memo[1];
    } else if(n == 2) {
      memo[2] = 2;
      return memo[2];
    } else if(memo[n] != 0) {
      return memo[n] %= 10007;
    } else {
      memo[n] = tile(n - 1) + tile(n - 2);
      return memo[n] %= 10007;
    }
  }
  
  public static void main(String args[]) throws IOException{
    BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
    int input = Integer.parseInt(bf.readLine());
    memo = new long[input + 1];
    System.out.println(tile(input));
  }
}

작성일 Edited on In Disqus:

Baekjoon Online Judge - 1463

Review

인덱스 횟수
1 0
2 1
3 1

위 테이블을 보면, 1은 만들 필요가 없으니까 0, 2와 3은 2로 3으로 나누어 떨어지고, 몫이 1이 나오니까 횟수가 1이다. 그렇다면 4부터는 어떻게 구할까?

| 인덱스 | 횟수 |
| 4 | 3, 1 또는 2, 1 |

4를 1로 만드는 최솟값을 구해야 하는 경우, 4를 1로 뺐을 때 3이 되고, 3의 값은 1이므로 총 두 번이 된다. 하지만 4를 2로 나누는 경우 몫이 2가 되는데, 2의 값은 1이므로 3으로 나누었을 때와 마찬가지로 총 두 번이 된다. 이러나저러나 4를 1로 만드는 최솟값은 2가 되는 것이다.

| 인덱스 | 횟수 |
| 5 | 4, 3, 1 또는 4, 2, 1 |

다시 5를 예로 들자면, 5는 3이나 2로 나누어 떨어지지 않으므로 무조건 1을 빼고 시작해야 한다. 5-1=4인데, 4의 횟수는 아까 구한 2이다. 따라서 5의 최솟값은 4의 연산 횟수(2) + 빼기 연산(1) = 3이 된다.

이렇게 10까지 반복하면 아래와 같은 테이블이 만들어지게 된다.

인덱스 횟수
1 0
2 1
3 1
4 3, 1 또는 2, 1
5 4, 3, 1
6 3, 1 또는 2, 1
7 6, 3, 1
8 4, 3, 1
9 3, 1
10 9, 3, 1

각 인덱스의 최솟값을 담은 배열을 A라고 했을 때, 점화식은 다음과 같다.

  • 1을 뺐을 때: A[n - 1] + 1
  • n % 2 == 0일 때: A[n / 2 == 0] + 1
  • n % 3 == 0일 때: A[n / 3 == 0] + 1

횟수를 계산해야 하기 때문에 1을 더한다. 각 케이스의 값을 비교해 최소값을 찾아내서 A[n] 배열에 넣어주면 된다.

Code (JAVA) - Bottom-up

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
import java.util.*;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    int[] arr = new int[n + 1];
    arr[0] = arr[1] = 0;

    for(int i = 2; i <= n; i++) {
      arr[i] = arr[i - 1] + 1;

      if(i % 2 == 0 && arr[i] > arr[i / 2] + 1) {
        arr[i] = arr[i / 2] + 1;
      }

      if(i % 3 == 0 && arr[i] > arr[i / 3] + 1) {
        arr[i] = arr[i / 3] + 1;
      }

    }
    System.out.println(arr[n]);
    sc.close();
  }
}

Code (JAVA) - Top-down

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
import java.io.*;

public class Main {
  
  static int[] dp;
  
  public static int dp(int n) {
    if(n <= 1) {
      return 0;
    } else if(dp[n] != 0) {
      return dp[n];
    } else {
      dp[n] = dp(n - 1) + 1;
      if(n % 3 == 0 && dp[n] > dp(n / 3) + 1) {
        dp[n] = dp(n / 3) + 1;
      }
      if(n % 2 == 0 && dp[n] > dp(n / 2) + 1) {
        dp[n] = dp(n / 2) + 1;
      }

    }
    return dp[n];
  }
  
  public static void main(String args[]) throws IOException{
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    int N = Integer.parseInt(br.readLine());
    dp = new int[N + 1];
    System.out.println(dp(N));

  }
}

Code (Javascript)

  • 역시 백준에서 자바스크립트 입력은… 노우…
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
var fs = require('fs');
var input = fs.readFileSync('/dev/stdin').toString().split("\n");
var X = parseInt(input[0]);

// 1부터 3까지의 값을 미리 넣어준다.
// 편의를 위해 인덱스는 1부터 시작한다
let dp = [0, 0, 1, 1];

for (let i = 4; i <= X; i++) {
  // -1을 뺄 때, 2로 나눌 때, 3으로 나눌 때의 값을 비교해 최소값을 알아냄
  // -1을 했을 때
  dp[i] = dp[i - 1] + 1;
  // 3으로 나누어 떨어지는 수일 때
  if (i % 3 === 0) dp[i] = Math.min(dp[i], dp[i / 3] + 1);
  // 2로 나누어 떨어지는 수일 때
  if (i % 2 === 0) dp[i] = Math.min(dp[i], dp[i / 2] + 1);
}

console.log(dp[X])

작성일 Edited on In Disqus:

Baekjoon Online Judge - 9095

Review

  • 각 앞자리 수에 1,2,3이 나올 경우를 생각하면 된다. 예를 들어 숫자 4는 3을 만들었을 때의 경우의 수, 2를 만들었을 때의 경우의 수, 1을 만들었을 때의 경우의 수를 전부 추가하면 된다.
    example
  • 점화식으로 나타내면 이렇다. A[n] = A[n-3] + A[n-2] + A[n-1]

Code (JAVA)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
import java.util.*;

public class Main {
  public static void main(String args[]) {
    Scanner sc = new Scanner(System.in);
    int[] arr = new int[11];
    int T, n;

    arr[1] = 1;
    arr[2] = 2;
    arr[3] = 4;

    T = sc.nextInt();

    for(int i = 0; i < T; i++) {
      n = sc.nextInt();
      for(int j = 4; j<=n; j++) {
        arr[j] = arr[j-1] + arr[j-2] + arr[j-3];
      }
      System.out.println(arr[n]);
    }
    sc.close();
  }
}