더 이상 물러설 곳이 없다

www.acmicpc.net/problem/1912

문제

n개의 정수로 이루어진 임의의 수열이 주어진다. 우리는 이 중 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하려고 한다. 단, 수는 한 개 이상 선택해야 한다.

예를 들어서 10, -4, 3, 1, 5, 6, -35, 12, 21, -1 이라는 수열이 주어졌다고 하자. 여기서 정답은 12+21인 33이 정답이 된다.

입력

첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다.

출력

첫째 줄에 답을 출력한다.

예제 입력 1

10

10 -4 3 1 5 6 -35 12 21 -1

예제 출력 1

33

예제 입력 2

10

2 1 -4 3 4 -4 6 5 -5 1

예제 출력 2

14

예제 입력 3

5

-1 -2 -3 -4 -5

예제 출력 3

-1

풀이 .

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

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());
        StringTokenizer st = new StringTokenizer(br.readLine());
        int[] arr = new int[n];
        int[] dp = new int[n];
        for(int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        dp[0] = arr[0];
        for(int i = 1; i < n; i++) {
            dp[i] = Math.max(dp[i-1] + arr[i], arr[i]);
        }

        OptionalInt ans = Arrays.stream(dp).max();
        System.out.println(ans.getAsInt());
    }
}

DP문제 풀기 전 반드시 생각해볼 것

1. dp에 어떤 값을 담을 것인가?

2. dp에 들어갈 수 있는 경우의 수는?

3. 각 경우의 수가 가능하기 위한 조건은?

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

1. dp에 어떤 값을 담을 것인가?

-> dp[n] = arr[n]으로 끝나는 최대 부분합 

2. dp에 들어갈 수 있는 경우의 수는?

-> 이전 부분합을 이어나가는 경우, 새로운 부분합을 시작하는 경우 (어쨌든 arr[n]은 포함되어야 한다)

3. 각 경우의 수가 가능하기 위한 조건은?

-> 두 경우 중 더 큰 값을 선택해야 한다.

www.acmicpc.net/problem/11054

문제

수열 S가 어떤 수 Sk를 기준으로 S1 < S2 < ... Sk-1 < Sk > Sk+1 > ... SN-1 > SN을 만족한다면, 그 수열을 바이토닉 수열이라고 한다.

예를 들어, {10, 20, 30, 25, 20}과 {10, 20, 30, 40}, {50, 40, 25, 10} 은 바이토닉 수열이지만,  {1, 2, 3, 2, 1, 2, 3, 2, 1}과 {10, 20, 30, 40, 20, 30} 은 바이토닉 수열이 아니다.

수열 A가 주어졌을 때, 그 수열의 부분 수열 중 바이토닉 수열이면서 가장 긴 수열의 길이를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000)

출력

첫째 줄에 수열 A의 부분 수열 중에서 가장 긴 바이토닉 수열의 길이를 출력한다.

예제 입력 1

10

1 5 2 1 4 3 4 5 2 1

예제 출력 1

7

풀이 .

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 br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        int[] arr = new int[n];
        int[] dp1 = new int[n];  // 가장 긴 증가 부분수열
        int[] dp2 = new int[n];  // 가장 긴 감소 부분수열
        for(int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        dp1[0] = 1;
        for(int i = 1; i < n; i++) {
            dp1[i] = 1;
            for(int j = 0; j < i; j++) {
                if(arr[i] > arr[j] && dp1[j] + 1 > dp1[i]) {
                    dp1[i] = dp1[j] + 1;
                }
            }
        }

        dp2[n-1] = 1;
        for(int i = n-2; i >= 0; i--) {
            dp2[i] = 1;
            for(int j = i+1; j < n; j++) {
                if(arr[i] > arr[j] && dp2[j] + 1 > dp2[i]) {
                    dp2[i] = dp2[j] + 1;
                }
            }
        }

        int ans = 0;
        for(int i = 0; i < n; i++) {
            if(dp1[i] + dp2[i] > ans) {
                ans = dp1[i] + dp2[i];
            }
        }
        ans -= 1;
        System.out.println(ans);
    }
}

1. 가장 긴 증가하는 부분수열을 구한다.

2. 가장 긴 감소하는 부분수열을 구한다.

3. 가장 길게 이어붙일 수 있는 끝점을 찾는다.

기존에 "가장 긴 감소하는 부분수열" 문제를 풀었을때는 0번 인덱스부터 내림차순으로 구해서 풀었다.

그런데 이렇게 구하면 3번을 진행할 수가 없다.

[n-1]인덱스부터 거꾸로 가장 긴 증가하는 부분수열을 찾아서 가장 긴 감소하는 부분수열을 찾으면 3번을 진행할 수 있다.

www.acmicpc.net/problem/11722

문제

수열 A가 주어졌을 때, 가장 긴 감소하는 부분 수열을 구하는 프로그램을 작성하시오.

예를 들어, 수열 A = {10, 30, 10, 20, 20, 10} 인 경우에 가장 긴 감소하는 부분 수열은 A = {10, 30, 10, 20, 20, 10}  이고, 길이는 3이다.

입력

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다.

둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000)

출력

첫째 줄에 수열 A의 가장 긴 감소하는 부분 수열의 길이를 출력한다.

예제 입력 1

6

10 30 10 20 20 10

예제 출력 1

3

풀이 .

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

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());
        StringTokenizer st = new StringTokenizer(br.readLine());
        int[] arr = new int[n];
        int[] dp = new int[n];
        for(int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        dp[0] = 1;
        for(int i = 1; i < n; i++) {
            dp[i] = 1;
            for(int j = 0; j < i; j++) {
                if(arr[j] > arr[i] && dp[j] + 1 > dp[i]) {
                    dp[i] = dp[j] + 1;
                }
            }
        }

        OptionalInt ans = Arrays.stream(dp).max();
        System.out.println(ans.getAsInt());
    }
}

codeung.tistory.com/118?category=449370 와 비슷한 문제.

dp[n] = "n번째 수로 끝나는 부분수열 중 가장 긴 것의 길이"

n번째 수로 끝나는 부분수열에서는 n번째 수가 마지막 수이기 때문에 dp[n]을 구하기 위해선 dp[n-1] 까지만 살펴보면 된다.

감소하는 부분수열을 유지하려면 arr[n]로 끝나는 부분수열에서 arr[n] 앞에 올 수 있는 숫자는 반드시 arr[n]보다 커야 한다.

즉, [0]~[n-1] 중에서 arr[n] 보다 큰 숫자만 검사하면 된다.

arr[n]보다 큰 인덱스를 대상으로 dp[0]~dp[n-1]을 검사한다. arr[n]을 추가해서 arr[n]으로 끝나는 부분수열을 완성했을 때 최장길이가 되기 위해선 dp[n 이전의 인덱스] + 1 은 dp[n] 의 현재값보다 더 커야 한다. 

위 검사를 arr[0]~arr[n-1] 중 arr[n] 보다 큰 놈들에게만 수행하여 dp[n] 값을 갱신하면 된다.

www.acmicpc.net/problem/11055

문제

수열 A가 주어졌을 때, 그 수열의 증가 부분 수열 중에서 합이 가장 큰 것을 구하는 프로그램을 작성하시오.

예를 들어, 수열 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 인 경우에 합이 가장 큰 증가 부분 수열은 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 이고, 합은 113이다.

입력

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다.

둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000)

출력

첫째 줄에 수열 A의 합이 가장 큰 증가 부분 수열의 합을 출력한다.

예제 입력 1

10

1 100 2 50 60 3 5 6 7 8

예제 출력 1

113

풀이 .

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

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());
        StringTokenizer st = new StringTokenizer(br.readLine());
        int[] arr = new int[n];
        int[] dp = new int[n];
        for(int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        dp[0] = arr[0];
        for(int i = 1; i < n; i++) {
            dp[i] = arr[i];
            for(int j = 0; j < i; j++) {
                if(arr[i] > arr[j] && dp[j] + arr[i] > dp[i]) {
                    dp[i] = dp[j] + arr[i];
                }
            }
        }

        OptionalInt ans = Arrays.stream(dp).max();
        System.out.println(ans.getAsInt());
    }
}

codeung.tistory.com/118?category=449370 와 비슷한 문제이다

dp[n] = "arr[n]으로 끝나는 부분수열 중 가장 큰 합"

arr[n]으로 끝난다는 것은 arr[n]이 마지막 원소라는 것. 즉, [0]~[n-1] 까지만 검사하면 된다.

증가하는 부분수열이란 조건을 지키기 위해 [0]~[n-1] 중 arr[n]보다 작은 놈들에 대해서만 검사하면 된다.

dp[0]~dp[n-1] 에서 arr[n]을 더했을 때 현재의 dp[n] 값보다 커지는 놈이 있다면 dp[n] 값을 갱신해준다.

www.acmicpc.net/problem/11053

문제

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.

예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.

입력

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다.

둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000)

출력

첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다.

예제 입력 1

6 10 20 10 30 20 50

예제 출력 1

4

풀이 .

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

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());
        StringTokenizer st = new StringTokenizer(br.readLine());
        int[] arr = new int[n];
        int[] dp = new int[n];
        for(int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        dp[0] = 1;
        for(int i = 1; i < n; i++) {
            dp[i] = 1;
            for(int j = 0; j < i; j++) {
                if(arr[i] > arr[j] && dp[j] + 1 > dp[i]) {
                    dp[i] = dp[j] + 1;
                }
            }
        }

        OptionalInt ans = Arrays.stream(dp).max();
        System.out.println(ans.getAsInt());
    }
}

잘 알려진 LIS(Longest Increasing Subsequence) 문제이다.

dp[n] = "n번째 수로 끝나는 부분수열 중 가장 긴 것의 길이"

n번째 수로 끝나는 부분수열에서는 n번째 수가 마지막 수이기 때문에 dp[n]을 구하기 위해선 dp[n-1] 까지만 살펴보면 된다.

증가하는 부분수열을 유지하려면 arr[n]로 끝나는 부분수열에서 arr[n] 앞에 올 수 있는 숫자는 반드시 arr[n]보다 작아야 한다.

즉, [0]~[n-1] 중에서 arr[n] 보다 작은 숫자만 검사하면 된다.

arr[n]보다 작은 인덱스를 대상으로 dp[0]~dp[n-1]을 검사한다. arr[n]을 추가해서 arr[n]으로 끝나는 부분수열을 완성했을 때 최장길이가 되기 위해선 dp[n 이전의 인덱스] + 1 은 dp[n] 의 현재값보다 더 커야 한다. 

위 검사를 arr[0]~arr[n-1] 중 arr[n] 보다 작은 놈들에게만 수행하여 dp[n] 값을 갱신하면 된다.

www.acmicpc.net/problem/2156

문제

효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규칙이 있다.

1. 포도주 잔을 선택하면 그 잔에 들어있는 포도주는 모두 마셔야 하고, 마신 후에는 원래 위치에 다시 놓아야 한다.
2. 연속으로 놓여 있는 3잔을 모두 마실 수는 없다.

효주는 될 수 있는 대로 많은 양의 포도주를 맛보기 위해서 어떤 포도주 잔을 선택해야 할지 고민하고 있다. 1부터 n까지의 번호가 붙어 있는 n개의 포도주 잔이 순서대로 테이블 위에 놓여 있고, 각 포도주 잔에 들어있는 포도주의 양이 주어졌을 때, 효주를 도와 가장 많은 양의 포도주를 마실 수 있도록 하는 프로그램을 작성하시오. 

예를 들어 6개의 포도주 잔이 있고, 각각의 잔에 순서대로 6, 10, 13, 9, 8, 1 만큼의 포도주가 들어 있을 때, 첫 번째, 두 번째, 네 번째, 다섯 번째 포도주 잔을 선택하면 총 포도주 양이 33으로 최대로 마실 수 있다.

입력

첫째 줄에 포도주 잔의 개수 n이 주어진다. (1≤n≤10,000) 둘째 줄부터 n+1번째 줄까지 포도주 잔에 들어있는 포도주의 양이 순서대로 주어진다. 포도주의 양은 1,000 이하의 음이 아닌 정수이다.

출력

첫째 줄에 최대로 마실 수 있는 포도주의 양을 출력한다.

예제 입력 1

6

6

10

13

9

8

1

예제 출력 1

33

풀이 .

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

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());
        int[] arr = new int[n+1];
        int[][] dp = new int[n+1][3];
        for(int i = 1; i <= n; i++) {
            arr[i] = Integer.parseInt(br.readLine());
        }
        dp[1][0] = 0;
        dp[1][1] = arr[1];
        dp[1][2] = arr[1];

        for(int i = 2; i <= n; i++) {
            dp[i][0] = Math.max(dp[i-1][0], Math.max(dp[i-1][1], dp[i-1][2]));
            dp[i][1] = dp[i-1][0] + arr[i];
            dp[i][2] = dp[i-1][1] + arr[i];
        }

        int ans = Math.max(dp[n][0], Math.max(dp[n][1], dp[n][2]));
        System.out.println(ans);
    }
}

n번째 잔에서 할 수 있는 선택지는 3개 이다.

1. n번째 잔을 0번 연속 선택 (선택하지 않음) -> n-1번째에서 어떤 선택을 했든지 상관 없음

2. n번째 잔을 1번 연속 선택 -> n-1번째에서 0번 연속 선택을 했어야 함

3. n번째 잔을 2번 연속 선택 -> n-1번째에서 1번 연속 선택을 했어야 함

dp[i][j] = i 번째 잔을 j 번 연속 선택할 때 마실 수 있는 최대 포도주의 양

@Autowired 자동 주입은 객체의 '타입'으로 조회한 빈을 주입한다.

@Autowired
private DiscountPolicy discountPolicy
.
.
@Component
public class FixDiscountPolicy implements DiscountPolicy {
}
.
.
@Component
public class RateDiscountPolicy implements DiscountPolicy {
}

바람직한 설계는 인터페이스에 의존하는 것이다.

위와 같은 코드에서 discountPolicy에 주입할 빈들을 조회하면 해당 인터페이스를 구현한 모든 구현체들의 빈이 조회될 것이다.

그럼 그 여러 가지 빈들 중 어느것을 주입해야할까?

세 가지 방법이 존재한다.

1. 필드명 매칭

조회된 빈들 중에서 자동주입이 되어야 하는 필드 변수의 이름과 같은 이름의 빈이 있다면 이 빈을 우선적으로 등록한다.

@Component
public class OrderServiceImpl implements OrderService{

    private final MemberRepository memberRepository;
    private final DiscountPolicy discountPolicy;

    @Autowired  // 파라미터 변수명 rateDiscountPolicy
    public OrderServiceImpl(MemberRepository memberRepository, DiscountPolicy rateDiscountPolicy) {
        this.memberRepository = memberRepository;
        this.discountPolicy = rateDiscountPolicy;
    }
}

타입은 DiscountPolicy 이지만 생성자의 파라미터 이름은 rateDiscountPolicy 이다.

조회된 빈들(fixDiscountPolicy, rateDiscountPolicy) 중 필드명과 이름이 같은 빈인 rateDiscountPolicy 가 우선적으로 주입되게 된다.

(생성자 주입이 아닌 필드 주입을 사용하는 경우에도 동일하게 적용된다.)

2. @Qualifier

public class BlahBlah {
    private final DiscountPolicy discountPolicy
    
    @Autowired
    public BlahBlah(@Qualifier("mainDiscountPolicy") DiscountPolicy discountPolicy) {
        this.discountPolicy = discountPolicy;
    }
}
.
.
@Component
@Qualifier("fixDiscountPolicy")
public class FixDiscountPolicy implements DiscountPolicy {
}
.
.
@Component
@Qualifier("mainDiscountPolicy")
public class RateDiscountPolicy implements DiscountPolicy {
}

@Qualifier는 의존성 주입에 있어 추가적인 구분 방법일 뿐 빈 이름을 변경하는 것은 아니라는 것에 주의하자

(@Qualifier 역시 필드 주입에서도 사용 가능하다)

만약 @Qualifier("mainDiscountPolicy") 가 일치하는 빈을 찾지 못한다면 차선책으로 빈 이름이 mainDiscountPolicy인 빈을 찾는다.

(이 기능은 굳이 사용되게 하지 않도록 하는 것이 좋다)

@Qualifier 는 ComponentScan 이 아닌 @Bean 직접 등록할 때에도 달아넣을 수 있다.

(추가)

Lombok의 @RequiredArgsConstructor 을 사용해서 생성자를 만들 경우 @Qualifier를 사용하지 못한다.

@RequiredArgsConstructor 는 어노테이션까지 포함해 생성자를 만들 수 없다.

www.inflearn.com/questions/71872

위 링크에 @RequiredArgsConstructor과 @Qualifier를 같이 사용할 수 있는 방법이 나와있지만 귀찮으니 그냥 같이 쓰지는 말자

3. @Primary  (자주 사용함, 편하지만 한계점이 있다)

그냥 우선순위를 주고 싶은 빈의 클래스에 @Primary 를 달아주면 된다.

@Autowired
private DiscountPolicy discountPolicy
.
.
@Component
public class FixDiscountPolicy implements DiscountPolicy {
}
.
.
@Component
@Primary
public class RateDiscountPolicy implements DiscountPolicy {
}

만약 @Primary와 @Qualifier가 겹치는 상황이 발생한다면?

-> @Qualifier가 우선된다.

스프링은 항상 포괄적인 개념보다는 상세한 개념을 우선시 한다.

(수동등록 > 자동등록 처럼)

여러 가지 문제들에 의해 필드주입, setter주입은 사용을 지양하며 반드시 생성자 주입을 사용하는게 좋다.

생성자 주입은 필드변수에 final키워드 사용 가능, 테스트 코드에서 컴파일에러를 통해 실수한 부분을 바로 알 수 있음 등의 장점이 있다.

하지만 생성자 코드를 그때그때 전부 입력하는 것은 좀 귀찮을 수도 있다.

Lombok 라이브러리를 통해 이를 해결할 수 있다.

Lombok 라이브러리는 start.spring.io 에서 프로젝트 생성 시 Dependencies에서 검색하여 추가할 수 있다.

이 라이브러리를 사용하기 위해선

file -> settings -> build, execution, deployment -> compiler -> annotation processors 에서 enable annotation processing을 체크해주어야 한다.

(file -> settings -> plugins 에서 lombok 검색하여 설치는 반드시 해줘야 함)

Lombok 라이브러리를 사용하면 getter, setter, 생성자 등을 직접 만들지 않아도 된다.

클래스에 @Getter, @Setter를 다는 것만으로 라이브러리가 만들어주는 getter, setter를 사용할 수 있으며,

@RequiredArgsConstructor 를 통해 final이 붙은 필드변수들을 받는 생성자를 알아서 만들어준다

@Component
@RequiredArgsConstructor  // final이 붙은 필드변수들을 받는 생성자를 알아서 만들어준다
public class OrderServiceImpl implements OrderService{

    private final MemberRepository memberRepository;
    private final DiscountPolicy discountPolicy;

}

위 코드에서 눈에 보이는 생성자는 없지만 @RequiredArgsConstructor 에 의해 memberRepository, discountPolicy 두 객체를 받아서 주입해주는 생성자가 존재하게 된다.

생성자 주입의 이점과 코드의 간편화를 동시에 챙길 수 있다.

출처 : www.inflearn.com/course/%EC%8A%A4%ED%94%84%EB%A7%81-%ED%95%B5%EC%8B%AC-%EC%9B%90%EB%A6%AC-%EA%B8%B0%EB%B3%B8%ED%8E%B8/dashboard