알고리즘/Dynamic Programming

[알고리즘][백준][JAVA] 11053번 : 가장 긴 증가하는 부분 수열

2023. 2. 15. 18:13
728x90

문제 : https://www.acmicpc.net/problem/11053

 

11053번: 가장 긴 증가하는 부분 수열

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이

www.acmicpc.net

해당 문제는 수열 A 가 주어졌을때, 가장 긴 증가하는 부분 수열, LIS (Longest Increasing Subsequence) 의 길이를 구하는 문제이다.

 

다이나믹 프로그래밍에서 가장 중요한 것은 규칙을 찾거나, 일반식을 찾는 것이다.

 

 

먼저, arr[1] < arr[2] 이므로 dp[2] = dp[1] +1 을 대입한다.

  1 2
arr[i] 10 20
dp[i] 1 2

 

다음으로, arr[3]은 arr[1]과 arr[2] 보다 작으므로 dp 값은 1로 유지한다.
  1 2 3
arr[i] 10 20 10
dp[i] 1 2 1

 

arr[4]는 arr[2]보다 값도 크고, dp값도 2보다 작은 1이었으므로 dp[2] 값인 2에서 +1 해서 3을 넣는다.
  1 2 3 4
arr[i] 10 20 10 30
dp[i] 1 2 1 3

arr[5]도 같은 방법으로 진행한다.

  1 2 3 4 5
arr[i] 10 20 10 30 20
dp[i] 1 2 1 3 2

6번째까지 진행하면, dp값이 4가 최대임을 알 수 있다.

  1 2 3 4 5 6
arr[i] 10 20 10 30 20 50
dp[i] 1 2 1 3 2 4

 

import java.util.Scanner;

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];
        int [] dp = new int[N+1];
        int cnt=1;

        for (int i=0;i<N;i++){
            arr[i]=sc.nextInt();
            dp[i]=1;
        }

        for (int i=1;i<N;i++){
            // 0 ~ i 이전 원소들을 탐색
            for (int j=0;j<i;j++){
                // i번째 원소가 j번째 원소보다 크고, i번째 dp가 j번째 dp값보다 작거나 같을경우
                if (arr[i]>arr[j] && dp[i]<=dp[j]){
                    dp[i]=dp[j]+1;  // j번째 원소의 +1 값이 i번째 dp가 된다.
                }
            }
        }
        
        // 최댓값(최대 길이) 탐색
        int max =0;
        for (int i : dp){
            max = Math.max(max, i);
        }
        System.out.println(max);
    }
}

 

728x90
'알고리즘/Dynamic Programming' 카테고리의 다른 글
  • [알고리즘][백준][JAVA] 1003번 : 피보나치 함수 / 다이나믹 프로그래밍
  • [알고리즘][백준][JAVA] 9095번 : 1,2,3 더하기 / Dynamic Programming, 다이나믹 프로그래밍
그냥코딩
그냥코딩
개발자가 될 수 있을까 ..? 자바.파이썬.알고리즘.프로그래밍.백준.스프링.JAVA.
justcoding개발자가 될 수 있을까 ..? 자바.파이썬.알고리즘.프로그래밍.백준.스프링.JAVA.
그냥코딩
justcoding
그냥코딩
전체
오늘
어제
  • 분류 전체보기 (22)
    • 알고리즘 (16)
      • 기본(문자열 처리 등) (0)
      • 자료구조 (0)
      • 그래프, 트리 (0)
      • Dynamic Programming (3)
      • 완전 탐색(Brute Force) (0)
      • 그리디(Greedy Algorithm) (0)
    • Spring (6)
      • 스프링 입문 (0)
      • 스프링 핵심 원리 - 기본편 (0)

블로그 메뉴

  • 홈
  • 태그
  • 방명록

공지사항

인기 글

태그

  • 백엔드
  • DP
  • 알고리즘
  • 10950번
  • java
  • 스택
  • 소수
  • 다이나믹 프로그래밍
  • 1920번
  • 분해합
  • 소수찾기
  • 2751
  • 인텔리제이
  • key promoter x
  • IntelliJ
  • 솔브닷
  • 백준
  • 인프런
  • 에라토스테레스
  • 자바

최근 댓글

최근 글

hELLO · Designed By 정상우.
그냥코딩
[알고리즘][백준][JAVA] 11053번 : 가장 긴 증가하는 부분 수열
상단으로

티스토리툴바

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.