[백준/1699] 제곱수의 합

작성일 2018-11-07 Edited on 2020-05-05 In 백준 Disqus:

Baekjoon Online Judge - 1699

Review

무조건 큰 제곱수로 곱해서 구하는 것이 답이 아니다. 따라서 주어진 수를 구할 수 있는 모든 제곱수로 구해 본 다음 최소값을 찾으면 된다.

Code (JAVA)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

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());
    int[] DP= new int[N + 1];
    
    for(int i = 1; i <= N; i++) {
      DP[i] = i;
    }
    
    for(int i = 1; i <= N; i++) {
      for(int j = 1; j * j <= i; j++) {
        DP[i] = Math.min(DP[i], DP[i - j*j] + 1);
      }
    }
    
    System.out.println(DP[N]);
  }
  
}

[백준/1912] 연속합

작성일 2018-10-31 Edited on 2020-05-05 In 백준 Disqus:

Baekjoon Online Judge - 1912

Review

이전까지 더한 값+현재값과 현재값을 비교해 더 큰 값이 DP[]에 들어가고, 이전까지의 최대값(max)과 현재의 DP[] 값을 비교해 더 큰 값이 max 변수에 들어가면 된다.
따라서 점화식은 DP[i] = max(DP[i-1] + A[i], A[i])
그런데… 왜 맞는데… 틀리지?
그건 내가 max 변수의 값을 0으로 초기화했기 때문임
초기화 잘못해서 네 번 틀린 사람 나야 나 나야 나

Code (JAVA)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

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());
    int[] DP = new int[N + 1];
    int[] A = new int[N + 1];
    int max;
    StringTokenizer st = new StringTokenizer(bf.readLine());
    
    for(int i = 1; i <= N; i++) {
      A[i] = Integer.parseInt(st.nextToken());
    }

    DP[1] = A[1];
    max = A[1];
    
    for(int i = 1; i <= N; i++) {
      DP[i] = Math.max(DP[i - 1] + A[i], A[i]);
      max = Math.max(max, DP[i]);
    }
    
    System.out.println(max);
  }
  
}

[백준/11055] 가장 큰 증가 부분 수열

작성일 2018-10-29 Edited on 2020-05-05 In 백준 Disqus:

Baekjoon Online Judge - 11055

Review

백준 11053 문제랑 비슷…
하지만 DP[i] < DP[j] + A[i]를 만족하는 경우에만 최대값이 될 수 있다.
이 부분을 몰라서 네 번이나 틀림.

Code (JAVA)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

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());
    int[] A = new int[N + 1];
    int[] DP = new int[N + 1];
    int ans = 0;
    StringTokenizer st = new StringTokenizer(bf.readLine());
    
    for(int i = 1; i <= N; i++) {
      A[i] = Integer.parseInt(st.nextToken());
    }
    
    for(int i = 1; i <= N; i++ ) {
      DP[i] = A[i];
      for(int j = 1; j < i; j++) {
        if(A[i] > A[j] && DP[i] < DP[j]+A[i]) {
          DP[i] = DP[j] + A[i];
        }
      }
      if(ans < DP[i]) {
        ans = DP[i];
      }
      
    }
    
    System.out.println(ans);
    
  }
  
}

[백준/11054] 가장 긴 바이토닉 부분 수열

작성일 2018-10-29 Edited on 2020-05-05 In 백준 Disqus:

Baekjoon Online Judge - 11054

Review

이 문제는 가장 긴 증가하는 부분 수열(LIS)을 두 번 활용하면 되는 문제이다.

이렇게 오른쪽, 왼쪽 방향으로 진행하는 LIS의 길이를 구해 각 배열에 저장한 다음, 그 두 배열의 값이 최대가 되는 지점이 바로 정답이 된다.

오른쪽으로 진행하는 LIS의 값은 DP 배열에 저장하고, 왼쪽으로 진행하는 LIS의 값은 R 배열에 저장한다. 따라서 아까 말했듯이, DP[i]+R[i]로 나온 값들 중의 최대값이 바로 정답이 되는 것이다.

그런데 왜 정답은 7인데 더한 값은 8일까? 바로 가운데 값이 중복되기 때문에 그렇다.

DP배열의 LIS: 1, 2, 3, 4, 5
R배열의 LIS: 1, 2, 5
총 길이: 1, 2, 3, 4, 5, 5, 2, 1

이렇게 5가 중복이 되기 때문에 1을 빼줘야 정답이 된다.

Code (JAVA)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

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());
    int[] A = new int[N + 1];
    int[] DP = new int[N + 1];
    int[] R = new int[N + 1];
    int ans1 = 1;
    int ans2 = 1;
    int max = 0;
    StringTokenizer st = new StringTokenizer(bf.readLine());

    for(int i = 1; i <= N; i++) {
      A[i] = Integer.parseInt(st.nextToken());
    }

    // 오른쪽으로 진행
    for(int i = 1; i <= N; i++) {
      DP[i] = 1;
      for(int j = 1; j <= i; j++) {
        if(A[i] > A[j]) {
          DP[i] = Math.max(DP[i], DP[j] + 1);
        }
      }
      ans1 = Math.max(ans1, DP[i]);
    }

    // 왼쪽으로 진행
    for(int i = N; i >= 1; i--) {
      R[i] = 1;
      for(int j = N; j >= i; j--) {
        if(A[i] > A[j]) {
          R[i] = Math.max(R[i], R[j] + 1);
        }
      }
      ans2 = Math.max(ans2, R[i]);
    }

    // 최대값 구하기
    for(int i = 1; i <= N; i++) {
      max = Math.max(DP[i] + R[i], max);
    }

    // 1을 뺀 결과값
    System.out.println(max-1);

  }

}

[백준/11722] 가장 긴 감소하는 부분 수열

작성일 2018-10-29 Edited on 2020-05-05 In 백준 Disqus:

Baekjoon Online Judge - 11722

Review

백준 11053 문제를 풀었다면, 부등호 하나만 고쳐서 풀 수 있는 문제이다.
그래서 그런지 정답률이 꽤 높다.

Code (JAVA)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

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());
    int[] A = new int[N + 1];
    int[] DP = new int[N + 1];
    int ans = 1;
    StringTokenizer st = new StringTokenizer(bf.readLine());
    
    for(int i = 1; i <= N; i++) {
      A[i] = Integer.parseInt(st.nextToken());
    }
    
    for(int i = 1; i <= N; i++ ) {
      DP[i] = 1;
      for(int j = 1; j <= i; j++) {
        if(A[i] < A[j]) {
          DP[i] = Math.max(DP[i], DP[j] + 1);
        }
      }
      ans = Math.max(ans, DP[i]);
    }
    
    System.out.println(ans);
    
  }
  
}

[백준/11053] 가장 긴 증가하는 부분 수열

작성일 2018-10-28 Edited on 2020-05-05 In 백준 Disqus:

Baekjoon Online Judge - 11053

Review

나무위키 최장 증가 부분 수열를 참고해서 풀었다.

Code (JAVA)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

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());
    int[] A = new int[N + 1];
    int[] DP = new int[N + 1];
    int ans = 1;
    StringTokenizer st = new StringTokenizer(bf.readLine());
    
    for(int i = 1; i <= N; i++) {
      A[i] = Integer.parseInt(st.nextToken());
    }
    
    for(int i = 1; i <= N; i++ ) {
      DP[i] = 1;
      for(int j = 1; j <= i; j++) {
        if(A[i] > A[j]) {
          DP[i] = Math.max(DP[i], DP[j] + 1);
        }
      }
      ans = Math.max(ans, DP[i]);
    }
    
    System.out.println(ans);
    
  }
  
}

[백준/9465] 스티커

작성일 2018-10-26 Edited on 2020-05-05 In 백준 Disqus:

Baekjoon Online Judge - 9465

Review

포도주 시식, 계단 오르기랑 비슷한 문제이다. 다른 점은 두 줄이라는 점.
따라서 첫 번째 줄은 sticker[0][i], 두 번째 줄은 sticker[1][i] 이런 식으로 표현을 할 수 있다.
규칙은 기준점에서 대각선에 있는 스티커의 점수만 더할 수 있다.
하지만 문제는 두 칸, 세 칸 뒤의 대각선으로도 이동을 할 수 있다는 건데, 결론적으로는 두 칸까지의 이동만 비교하면 된다. 왜냐면 세 칸 뒤의 대각선은 이전 점수를 통해서 오는 게 더 높은 점수를 받을 수 있기 때문이다.
따라서 경우는 총 두 가지
1. 기준점에서 한 칸 뒤의 대각선으로 이동하는 경우
2. 기준점에서 두 칸 뒤의 대각선으로 이동하는 경우
각각의 경우를 점화식으로 나타내면 다음과 같다.
1. dp[0][i] = Max(dp[1][i-1], dp[1][i-2]) + sticker[0][i]
2. dp[1][i] = Max(dp[0][i-1], dp[0][i-2]) + sticker[1][i]
첫 번째 줄에서 시작한 경우, 두 번째 줄에서 시작한 경우를 각각 구한 다음, 둘 중 큰 수를 출력하면 된다.
여기서 sticker 배열은 스티커의 점수, dp 배열은 점수의 최대값을 저장한 배열이다.
문제 푸는 것보다 입력 받는 게 더 까다로웠다.

Code (JAVA)

import java.io.*;

public class Main {
  
  public static void main(String args[]) throws IOException{
    BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
    int T = Integer.parseInt(bf.readLine());
    
    while(T-- > 0) {
      int n = Integer.parseInt(bf.readLine());
      
      // 배열 선언
      int[][] dp = new int[2][100001];
      int[][] sticker = new int[2][100001];
      String[] str;
      
      // 스티커에 값 집어넣기
      for(int i = 0; i <= 1; i++) {
        str = bf.readLine().split(" ");
        for(int j = 1; j <= n; j++) {
          sticker[i][j] = Integer.parseInt(str[j-1]);
        }
      }
      
      // 첫 번째 값 넣어주기
      // (이동이 없으니 sticker의 첫 번째 값을 dp 배열에 넣어줌)
      dp[0][1] = sticker[0][1];
      dp[1][1] = sticker[1][1];
      
      // 값 비교해서 각 배열에 넣어주기
      for(int i = 2; i <= n; i++) {
        dp[0][i] = Math.max(dp[1][i-1], dp[1][i-2]) + sticker[0][i];
        dp[1][i] = Math.max(dp[0][i-1], dp[0][i-2]) + sticker[1][i];
      }
      
      System.out.println(Math.max(dp[0][n], dp[1][n]));  
    }
    
  }
  
}

[백준/2579] 계단 오르기

작성일 2018-10-25 Edited on 2020-05-05 In 백준 Disqus:

Baekjoon Online Judge - 2579

Review

포도주 시식이랑 비슷한 문제.
포도주 시식이랑 다른 점은 무조건 마지막 칸을 밟아야 한다는 것이다.
경우는 총 두 가지 - 마지막 칸을 밟았을 때
1. 이전 계단을 밟지 않은 경우
2. 이전 계단을 밟을 경우
각각의 경우를 점화식으로 나타내면 다음과 같다.
1. dp[i] = dp[i-2] + stair[i]
2. dp[i] = dp[i-3] + stair[i] + stair[i-2]
여기서 dp[]는 점수의 최대값이 되고, stair[]는 계단의 점수다.

Code (JAVA)

import java.util.*;

public class Main {
  
  public static void main(String args[]) {
    Scanner sc = new Scanner(System.in);
    int N = sc.nextInt();
    
    int[] stair = new int[N + 1];
    int[] dp = new int[N + 1];
    
    for(int i = 1; i <= N; i++) {
      stair[i] = sc.nextInt();
    }
    
    // 초기화
    dp[0] = 0;
    dp[1] = stair[1];
    dp[2] = dp[1] + stair[2];
    
    // 최대값 찾기
    for(int i = 3; i <= N; i++) {
      dp[i] = Math.max(dp[i-2] + stair[i], dp[i-3] + stair[i-1] + stair[i]);
    }
    
    System.out.println(dp[N]);
    sc.close();
    
  }
  
}

[백준/2156] 포도주 시식

작성일 2018-10-24 Edited on 2020-05-05 In 백준 Disqus:

Baekjoon Online Judge - 2156

Review

경우는 총 세 가지
1. 현재 포도주는 마시지 않을 경우
2. 현재 포도주는 마시고 이전 포도주는 마시지 않은 경우
3. 현재 포도주와 이전의 포도주를 마신 경우
각각의 경우를 점화식으로 나타내면 다음과 같다.
1. dp[i - 1]
2. wine[i] + dp[i - 2]
3. wine[i] + wine[i - 1] + dp[i - 3]
여기서 dp[]는 포도주를 마신 최대값이 되고, wine[]은 포도주의 양이다.

Code (JAVA)

import java.util.*;

public class Main {
  
  public static int Max(int a, int b, int c) {
    if(b > c) {
      return a > b ? a : b;
    } else {
      if(a > c) {
        return a;
      } else {
        return c;
      }
    }
  }
  
  public static void main(String args[]) {
    Scanner sc = new Scanner(System.in);
    int N = sc.nextInt();
    
    int[] wine = new int[10001];
    int[] dp = new int[10001];
    
    // 배열 초기화
    for(int i = 1; i <= N; i++) {
      wine[i] = sc.nextInt();
    }

    dp[0] = 0;
    dp[1] = wine[1];
    dp[2] = dp[1] + wine[2];
    
    // 값 비교
    for(int i = 3; i <= N; i++) {
      dp[i] = Max(dp[i-1], wine[i] + dp[i-2], wine[i] + wine[i-1] + dp[i-3]);
    }
    
    System.out.println(dp[N]);
    sc.close();
    
  }
  
}

[React] Flux 개념 이해하기

작성일 2018-10-17 Edited on 2020-05-05 In React Disqus:

Flux 개념 정리

Flux 등장 배경

Flux는 MVC 패턴의 문제점을 보완하기 위해 만들어진 디자인 패턴이다. 그렇기 때문에 왜 등장했는지부터 짚고 넘어가면 좋다. 등장 배경에 대해 잘 설명된 문서가 있어서 링크로 대체한다.

요악하자면 MVC(Model-View-Controller) 패턴으로 개발하던 페이스북이 알림(notification)버그를 발견하고, 이를 근본적으로 해결하는 과정에서 Flux가 탄생하게 되었다는 얘기다. MVC 패턴은 작은 애플리케이션의 경우에는 별 문제가 없지만, 대규모 애플리케이션의 경우라면 엄청나게 복잡해진다는 단점을 가지고 있다.

MVC 패턴은 컨트롤러(Controller), 모델(Model), 뷰(View) 세 가지 개념으로 이루어져있다. 작은 애플리케이션의 경우 모델과 뷰가 적어서 MVC 패턴이 큰 문제없이 작동한다.

컨트롤러: 모델에 명령을 보내서 모델의 상태를 변경할 수 있음

모델: 모델의 상태에 변화가 있을 때 컨트롤러와 뷰에 통보
뷰: 모델로부터 정보를 얻어와 결과물로 반영함

하지만 대규모 애플리케이션은 모델과 뷰가 많아서 엄청나게 복잡해진다. 모델이 많아지면서 이를 표현하기 위한 뷰들이 많아지고, 뷰를 통해 입력된 값이 모델에 영향을 주면서 엄청나게 복잡해진다. 이를 타개하기 위해 flux 아키텍처가 만들어졌다.

Flux 패턴

Flux는 페이스북에서 MVC의 문제를 해결할 목적으로 고안한 애플리케이션 아키텍처이다. Flux 아키텍쳐의 가장 큰 특징은 단방향 데이터 흐름(unidirectional data flow)이다. 말 그대로 한 방향으로 데이터가 흐르는 것이다. 뷰를 통해 입력된 값은 디스패쳐를 통해 스토어로 전달되고, 스토어는 이 변경된 값을 다시 뷰에게 전달하는 역할을 한다. Flux 애플리케이션은 세 가지 주요 파트로 구성되는데, 각각 디스패처(Dispatcher), 스토어(Store), 뷰(View)이다.

액션 생성자(The action creator)

Flux 아키텍쳐의 주요 파트를 알아보기 전에 ‘액션 생성자(The action creator)’ 라는 개념을 알고 넘어가야 한다. 액션 생성자란 모든 변경사항과 사용자와의 상호작용이 거처가야 하는 액션의 생성을 담당하고 있다. 애플리케이션의 상태를 변경하거나 뷰를 업데이트하고 싶다면 액션을 생성해야만 한다.

액션 생성자가 하는 일은 마치 전보 기사가 알파벳을 모스 부호로 바꾸는 것처럼 특정 포맷에 맞게 메시지를 작성하는 것과 같다. 그리고 액션 생성자가 특정 액션이 적힌 메시지를 다 작성하면 바로 디스패쳐에게 넘겨준다.

Flux 아키텍쳐의 세 가지 주요 파트

앞서 말했듯, Flux 애플리케이션은 세 가지 주요 파트로 구성되어 있다.

1.디스패쳐(Dispatcher)

디스패쳐는 Flux 어플리케이션의 중앙 허브로 모든 데이터의 흐름을 관리한다. 스토어의 콜백함수들이 등록되어 있으며, 각각의 스토어를 직접 등록하고 콜백함수를 제공한다. 비유를 하자면 전화 교환수와도 같다. 액션 생성자한테서 액션을 받으면, 여러 스토어에게 그 액션을 보내는 역할을 한다.

2. 스토어(The stores)

애플리캐이션의 상태를 저장한다. 모든 상태 변경은 스토어에 의해서 결정되고, 상태 변경을 위한 요청을 스토어에 직접 보낼 수 없다. 무조건 액션 생성자->디스패처 흐름으로 액션을 보내야 상태 변경이 가능해진다. 스토어의 상태 변경이 될 때마다 스토어는 변경 이벤트를 내보내는데, 이 이벤트는 컨트롤러 뷰에게 상태가 변경되었다는 것을 알려주게 된다.

3. 컨트롤러 뷰(Controller view)와 뷰(View)

상태를 가져오고, 유저에게 입력받을 화면을 보여준다. 리액트에서는 즉 리액트 컴포넌트에 해당한다. 컨트롤러 뷰와 뷰의 차이는 리액트에서의 부모 컴포넌트와 자식 컴포넌트와도 같다. 스토어가 상태를 변경되었다고 컨트롤러 뷰에게 알려주면, 컨트롤러 뷰는 자신의 아래에 있는 모든 자식 뷰에게 새로운 상태를 넘겨준다.

Flux는 어떻게 동작할까?

준비 단계 (The setup)

스토어는 디스패쳐에게 액션이 들어오면 알려달라고 말해둔다.
컨트롤러 뷰는 스토어에게 최신 상태를 묻는다.
스토어가 컨트롤러 뷰에게 상태를 주면 렌더링하기 위해 모든 자식 뷰에게 상태를 넘겨준다.
컨트롤러 뷰는 스토어에게 상태가 바뀔 때 알려달라고 다시 부탁한다.

데이터의 흐름 (The data flow)

일단 액션으로 발생한 모든 데이터는 디스패쳐 -> 스토어 -> 뷰로 흘러간다.

뷰는 액션 생성자에게 액션을 준비하라고 말한다.
액션 생성자는 액션을 포맷에 맞게 만들어서 디스패쳐에게 넘겨준다.
디스패쳐는 들어온 순서에 따라 알맞은 스토어로 보낸다.
스토어는 상태가 변경되었기 때문에 컨트롤러 뷰에게 이 사실을 알린다.
컨트롤러 뷰는 자신의 아래에 있는 자식 뷰에게 모든 상태를 넘겨준다.

Reference

Wikipedia
Flux 한국어 번역 페이지
Flux로의 카툰 안내서