최대 증가 부분 수열(난이도: 하)

2022. 9. 29. 11:30·알고리즘 (with JAVA)/동적 계획법

1. 문제 설명

(1) 부분 순열에 포함된 숫자들이 순 증가(strictly increasing)하면 이 부분 수열을 증가 부분 수열이라고 부른다.

* 순 증가란, 두 인접한 숫자 중 앞의 것이 항상 더 작을 때 수열이 순증가한다고 한다.

* 단조 증가(monotonically increasing)란, 두 인접한 숫자가 같은 경우를 말한다.

 

(2) 예를 들어, 수열 S가 '1 3 4 2 4' 라고 하면 '1 2 4'는 S의 증가 부분 수열이지만 '1 4 4'는 아니다.

 

(3) 이때 주어진 수열에서 얻을 수 있는 증가 부분 수열 중 가장 긴 것을 찾는 프로그램을 작성하여라.

* 이 문제를 최대 증가 부분 수열(LIS, Longest Increasing Subsequence)라고 부른다.

 

 

 

 

2. 입출력 조건 및 예제

입력 조건

(1) 입력의 첫 줄에는 테스트 케이스의 수 C(1<=C<=50)

(2) 그 후 두 번째 줄에 수열의 크기 N(1<=N<=100)

(3) 그 후 세 번째 줄에 수열의 원소들 S(1<=S<=100)

 

출력 조건

(1) 증가 부분 수열 중 가장 긴 것의 크기

 

 

입력 예제

2
8
3 2 1 7 5 4 2 6
8
3 2 1 7 3 4 2 6

 

출력 예제

3

4

 

 

 

3. 제약 조건

X

 

 

 

 

4. 가정법

X

 

 

 

 

5. 기저 사례

X

 

 

 

 

6. 코드

: 두 가지 코드가 존재한다.

 

(1)은 동적 계획법 프로그래밍을 해결하는 기본적인 코드이다.

 

 

 

(1) 동적 계획법 프로그래밍

public class LIS1 {
    private static BufferedReader sc = new BufferedReader(new InputStreamReader(System.in));
    private static StringBuilder sb = new StringBuilder();

    private static int N;
    private static int[] S;

    private static int[] cache;

    public static void main(String[] args) throws IOException {
        StringTokenizer st;
        int C = Integer.parseInt(sc.readLine());

        for(int i=0; i<C; i++) {
            cache = new int[101];
            N = Integer.parseInt(sc.readLine());
            S = new int[N];

            st = new StringTokenizer(sc.readLine());
            for(int y=0; y<N; y++) {
                S[y] = Integer.parseInt(st.nextToken());
            }

            int max=1;
            for(int y=0; y<N; y++) {
                max = Math.max(max, solve(y));
            }

            sb.append(max +"\n");
        }
        System.out.println(sb);
    }

    private static int solve(int start) {
        if(cache[start]!=0) return cache[start];

        // ret을 1로 설정하는 이유는 자기 자신을 포함한 부분 수열은 
        // 순증가에서 최소 1의 크기를 가지기 때문
        int ret =1;
        for(int next=start+1; next<N; next++) {
            if(S[start]<S[next]) {
                ret = Math.max(ret, solve(next)+1);
            }
        }
        return cache[start] = ret;
    }
}

 

 

 

(2)는 (1)에서 호출하는 부분을 간단하게 하기 위해서 -1을 사용해 수정한 코드이다.

 

 

 

(2)

public class LIS2 {
    private static BufferedReader sc = new BufferedReader(new InputStreamReader(System.in));
    private static StringBuilder sb = new StringBuilder();

    private static int N;
    private static int[] S;

    private static int[] cache;

    public static void main(String[] args) throws IOException {
        StringTokenizer st;
        int C = Integer.parseInt(sc.readLine());

        for(int i=0; i<C; i++) {
            cache = new int[101];
            N = Integer.parseInt(sc.readLine());
            S = new int[N];

            st = new StringTokenizer(sc.readLine());
            for(int y=0; y<N; y++) {
                S[y] = Integer.parseInt(st.nextToken());
            }
            sb.append(solve(-1) +"\n");
        }
        System.out.println(sb);
    }

    private static int solve(int start) {
        if(cache[start+1]!=0) return cache[start+1];

        int ret =0;
        for(int next=start+1; next<N; next++) {
            if(start==-1 || S[start]<S[next]) {
                ret = Math.max(ret, solve(next)+1);
            }
        }
        return cache[start+1] = ret;
    }
}
저작자표시 (새창열림)

'알고리즘 (with JAVA) > 동적 계획법' 카테고리의 다른 글

원주율 외우기 (난이도: 하)  (0) 2022.10.01
합친 LIS (난이도: 하)  (0) 2022.09.29
삼각형 위의 최대 경로 (난이도: 하)  (0) 2022.09.28
와일드 카드 (난이도: 중)  (0) 2022.09.27
외발 뛰기 (난이도: 하)  (0) 2022.09.27
'알고리즘 (with JAVA)/동적 계획법' 카테고리의 다른 글
  • 원주율 외우기 (난이도: 하)
  • 합친 LIS (난이도: 하)
  • 삼각형 위의 최대 경로 (난이도: 하)
  • 와일드 카드 (난이도: 중)
백_곰
백_곰
  • 백_곰
    친절한 코딩
    백_곰
  • 전체
    오늘
    어제
    • 분류 전체보기
      • 알고리즘 (with JAVA)
        • 기본 알고리즘
        • 완전 탐색
        • 분할 정복 알고리즘
        • 동적 계획법
        • 탐욕법
        • 코딩 테스트 기출 문제
        • 코드트리 조별과제
      • 백준 (with JAVA)
        • 완전 탐색
        • 분할 정복
        • 그 외
      • 자바
        • 개발 환경 구축하기
        • 팁
        • 기본적인 개념
        • 컬렉션 프레임워크
        • 프로세스와 쓰레드
        • 지네릭스
        • 람다식
        • 스트림
        • 입출력 IO
        • 네트워킹
        • 열거형(enums)
        • java.lang 패키지
        • java.time 패키지
        • 유용한 클래스들
        • 형식화 클래스들
      • 안드로이드 with 자바
        • 응용 문제들
        • 자잘한 문제들
        • 오류 보고서
  • 블로그 메뉴

    • 링크

    • 공지사항

    • 인기 글

    • 태그

      map()
      outputstream
      코딩테스트
      선택 정렬
      코드트리
      java.lang패키지
      스트림
      중간연산
      자바 개념
      TCP 소켓 프로그래밍
      snail
      serializable
      유용한 클래스
      Collections Framework
      역직렬화
      InputStream
      Arrays
      다형성
      안정 정렬
      코딩트리조별과제
      소켓 프로그래밍
      불안정 정렬
      java.time 패키지
      file
      ServerSocket
      제자리 정렬
      문자 기반 스트림
      람다식
      알고스팟
      안드로이드 스튜디오
    • 최근 댓글

    • 최근 글

    • hELLO· Designed By정상우.v4.10.3
    백_곰
    최대 증가 부분 수열(난이도: 하)
    상단으로

    티스토리툴바