더 이상 물러설 곳이 없다

1. 생성자 주입 (가장 많이 사용)

생성자에 @Autowired 를 사용해 주입한다.

클래스가 ComponentScan 범위에 들어오면 빈이 생성되면서 생성자가 호출된다. 이때 @Autowired를 통해 DI가 이루어진다.

생성자가 하나만 있을 경우 @Autowired는 생략이 가능하다.

생성자는 한 번만 호출되기 때문에 불변, 필수 의존성 주입에 사용하는 방식이다. (객체가 절대로 바뀔 일이 없고 반드시 null이 아니어야 하는 의존성)

2. setter 주입

setter에 @Autowired 를 사용해 주입한다.

setter는 계속해서 호출이 가능하기 때문에 선택, 변경의 가능성이 있는 의존성 주입에 사용하는 방식이다.

필수값인 객체는 생성자 주입을 사용하고 필수가 아닌 객체는 setter 주입을 따로 사용하는 방법도 있다.

3. 필드 주입 (그냥 쓰지 말자)

그냥 필드 변수 선언 시에 필드측에 @Autowired로 박아버린다.

생성자, setter 주입 방식은 테스트 코드에서 순수 자바코드로도 생성자 주입이 가능하지만 필드 주입은 오로지 스프링 컨테이너를 통해서만 의존성 주입이 가능함.

스프링 컨테이너를 띄우지 않고 순수 자바코드로 단위 테스트를 실행할 때 의존성을 주입할 수 있는 방법이 없어져 곤란해질 수 있다.

(규모가 큰 프로젝트에서 스프링 컨테이너를 띄우고 테스트하는 것은 속도가 느리기 때문에 순수 자바 코드만 사용하는 단위테스트를 사용하는 경우도 많다. 필드 주입은 이 상황에서 의존성을 주입할 수 없게 된다.)

굳이 필드주입을 사용하고 순수 자바 코드 테스트를 진행하려면 별도의 setter를 만들어서 의존성을 주입해주어야 한다.

(근데 이럴거면 그냥 생성자 주입 or setter 주입을 쓰고 말지..)

단, 애플리케이션 설계와 전혀 관계가 없는 테스트 코드 내에서는 필드 주입으로 빠르게 의존성을 주입하고 사용하는 게 더 좋을 수도 있다.

4. 일반 메서드 주입

그냥 일반 메서드에 @Autowired 달고 주입받는 방식

거의 쓰지 않는다. 쓰지 말자.

(옵션 처리 설정)

@Autowired로 의존성 주입을 실시할 때 자동주입할 객체가 없는 경우가 있을 수도 있다.

이때 아무런 조치를 취하지 않은 채로 그냥 @Autowired만 사용한다면 에러가 발생한다.

주입할 빈이 없어도 문제없이 동작하게 하기 위해선 다음과 같은 처리들을 해줄 수 있다.

1. required

@Autowired(required = false) 로 옵션 지정을 해준다.

required의 디폴트 값은 true이다.

false로 지정될 경우, 주입할 빈이 없으면 해당 메서드를 실행하지 않고 바로 넘어간다.

2. @Nullable

method(@Nullable Member member)

파라미터 앞에 @Nullable을 추가할 수 있다. 들어올 빈이 없어도 메서드 호출은 이루어지지만 null이 주입된다.

3. Optional

method(Optional<Member> member)

자바8의 Optional을 사용하는 방법이다. (Optional.empty 주입됨)

출처 : 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

www.acmicpc.net/problem/9465

문제

상근이의 여동생 상냥이는 문방구에서 스티커 2n개를 구매했다. 스티커는 그림 (a)와 같이 2행 n열로 배치되어 있다. 상냥이는 스티커를 이용해 책상을 꾸미려고 한다.

상냥이가 구매한 스티커의 품질은 매우 좋지 않다. 스티커 한 장을 떼면, 그 스티커와 변을 공유하는 스티커는 모두 찢어져서 사용할 수 없게 된다. 즉, 뗀 스티커의 왼쪽, 오른쪽, 위, 아래에 있는 스티커는 사용할 수 없게 된다.

모든 스티커를 붙일 수 없게된 상냥이는 각 스티커에 점수를 매기고, 점수의 합이 최대가 되게 스티커를 떼어내려고 한다. 먼저, 그림 (b)와 같이 각 스티커에 점수를 매겼다. 상냥이가 뗄 수 있는 스티커의 점수의 최댓값을 구하는 프로그램을 작성하시오. 즉, 2n개의 스티커 중에서 점수의 합이 최대가 되면서 서로 변을 공유 하지 않는 스티커 집합을 구해야 한다.

위의 그림의 경우에 점수가 50, 50, 100, 60인 스티커를 고르면, 점수는 260이 되고 이 것이 최대 점수이다. 가장 높은 점수를 가지는 두 스티커 (100과 70)은 변을 공유하기 때문에, 동시에 뗄 수 없다.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의 점수이다. 연속하는 두 정수 사이에는 빈 칸이 하나 있다. 점수는 0보다 크거나 같고, 100보다 작거나 같은 정수이다. 

출력

각 테스트 케이스 마다, 2n개의 스티커 중에서 두 변을 공유하지 않는 스티커 점수의 최댓값을 출력한다.

예제 입력 1

2

5

50 10 100 20 40

30 50 70 10 60

7

10 30 10 50 100 20 40

20 40 30 50 60 20 80

예제 출력 1

260

290

풀이 .

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 T = Integer.parseInt(br.readLine());

        while(T-- > 0) {
            int n = Integer.parseInt(br.readLine());
            int[][] arr = new int[3][n+1];
            StringTokenizer st1 = new StringTokenizer(br.readLine());
            StringTokenizer st2 = new StringTokenizer(br.readLine());

            // 0행은 무시. dp랑 행 라인 맞추려면 0행 있는 게 편함
            for(int i = 1; i <= n; i++) {
                arr[1][i] = Integer.parseInt(st1.nextToken());
                arr[2][i] = Integer.parseInt(st2.nextToken());
            }

            // n개의 열에서 선택안하기, 1행선택하기, 2행선택하기
            int[][] dp = new int[3][n+1];
            dp[0][1] = 0;
            dp[1][1] = arr[1][1];
            dp[2][1] = arr[2][1];

            // 2~n 열
            for(int i = 2; i <= n; i++) {
                dp[0][i] = Math.max(dp[0][i-1], Math.max(dp[1][i-1], dp[2][i-1]));
                dp[1][i] = Math.max(dp[0][i-1], dp[2][i-1]) + arr[1][i];
                dp[2][i] = Math.max(dp[0][i-1], dp[1][i-1]) + arr[2][i];
            }
            int ans = Math.max(dp[0][n], Math.max(dp[1][n], dp[2][n]));
            System.out.println(ans);
        }
    }
}

하나의 열에서 고를 수 있는 선택지는 3개다.

1. 아무것도 고르지 않기

2. 1행의 스티커 고르기

3. 2행의 스티커 고르기

1. 아무것도 고르지 않으려면?

-> 이전 열에서 어떤 선택을 하더라도 모두 가능

2. 1행을 고르려면?

-> 이전 열에서 아무것도 안 골랐거나 2행을 골랐어야 가능

3. 2행을 고르려면?

-> 이전 열에서 아무것도 안 골랐거나 1행을 골랐어야 가능

계산의 편의상 0행 0열은 빈 칸으로 두고 1, 2행  1~n열이 존재할 때,

dp[i][j] = "j 번째 열에서 i 행을 선택하는 경우 점수의 최대값" 이다. (i = 0 일 경우 아무 행도 선택하지 않는 것으로 한다)

즉,

dp[n][0] = (이전 열에서 아무것도 안 고르기, 1행 고르기, 2행 고르기 중 최대값)

dp[n][1] = (이전 열에서 아무것도 안 고르기, 2행 고르기 중 최대값) + n열 1행의 값

dp[n][2] = (이전 열에서 아무것도 안 고르기, 1행 고르기 중 최대값) + n열 2행의 값

dp, ans 모두 int 사용 가능한 이유?

한 칸의 최대 점수는 100, 가장 많이 고를 수 있는 칸은 n칸 (지그재그로 한 열당 하나씩 무조건 고르는 경우)

즉, 획득 가능한 점수의 상한은 100n = 100 * 100,000 = 천만

-> int 범위 내에 속한다.

www.acmicpc.net/problem/2193

문제

0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다.

1. 이친수는 0으로 시작하지 않는다.
2. 이친수에서는 1이 두 번 연속으로 나타나지 않는다. 즉, 11을 부분 문자열로 갖지 않는다.

예를 들면 1, 10, 100, 101, 1000, 1001 등이 이친수가 된다. 하지만 0010101이나 101101은 각각 1, 2번 규칙에 위배되므로 이친수가 아니다.

N(1 ≤ N ≤ 90)이 주어졌을 때, N자리 이친수의 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다.

출력

첫째 줄에 N자리 이친수의 개수를 출력한다.

예제 입력 1

3

예제 출력 1

2

풀이 .

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());
        long[][] dp = new long[n + 1][2];
        dp[1][0] = 0;
        dp[1][1] = 1;

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

        long ans = dp[n][0] + dp[n][1];
        System.out.println(ans);
    }
}

dp[i][j] = i 자리 이친수가 j 로 끝나는 경우의 수

1. i 번째 자리에 0이 올 수 있는 경우 : i-1번째가 0일때, 1일때 모두 가능

2. i 번째 자리에 1이 올 수 있는 경우 : i-1번째가 0일 경우만 가능

즉, dp[n][0] = dp[n-1][0] + dp[n-1][1], dp[n][1] = dp[n-1][0]

dp, ans에 long을 사용한 이유?

-> % 연산을 취하라는 별도의 조건 없이 무작정 더해나가기만 하면서 dp[n]을 구한다. 이런 경우는 덧셈을 거듭하면서 숫자가 얼마나 커질지 모르기 때문에 굳이 시간 아깝게 계산하지 말고 그냥 처음부터 long을 사용하자.

www.acmicpc.net/problem/11057

문제

오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다.

예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다.

수의 길이 N이 주어졌을 때, 오르막 수의 개수를 구하는 프로그램을 작성하시오. 수는 0으로 시작할 수 있다.

입력

첫째 줄에 N (1 ≤ N ≤ 1,000)이 주어진다.

출력

첫째 줄에 길이가 N인 오르막 수의 개수를 10,007로 나눈 나머지를 출력한다.

예제 입력 1

1

예제 출력 1

10

예제 입력 2

2

예제 출력 2

55

예제 입력 3

3

예제 출력 3

220

풀이 .

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[][] dp = new int[n + 1][10];
        for(int i = 0; i <= 9; i++) {
            dp[1][i] = 1;
        }

        for(int i = 2; i <= n; i++) {
            for(int j = 0; j <= 9; j++) {
                for(int k = 0; k <= j; k++) {
                    dp[i][j] += dp[i - 1][k];
                }
                dp[i][j] %= 10007;
            }
        }

        int ans = 0;
        for(int num : dp[n]) {
            ans += num;
        }
        ans %= 10007;
        System.out.println(ans);
    }
}

dp[i][j] = 길이가 i인 오르막수가 j로 끝나는 경우.

i번째 자리에 j가 오려면 i-1번째 자리는 0~j 만 올 수 있다.

n * 10 * 10 = 100,000번의 연산으로 처리 가능

dp, ans 모두 int로 처리 가능

(dp[n][0]~dp[n][9]의 총합은 10007 * 10 이하이므로)

www.acmicpc.net/problem/10844

문제

45656이란 수를 보자.

이 수는 인접한 모든 자리수의 차이가 1이 난다. 이런 수를 계단 수라고 한다.

세준이는 수의 길이가 N인 계단 수가 몇 개 있는지 궁금해졌다.

N이 주어질 때, 길이가 N인 계단 수가 총 몇 개 있는지 구하는 프로그램을 작성하시오. (0으로 시작하는 수는 없다.)

입력

첫째 줄에 N이 주어진다. N은 1보다 크거나 같고, 100보다 작거나 같은 자연수이다.

출력

첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다.

예제 입력 1

1

예제 출력 1

9

예제 입력 2

2

예제 출력 2

17

풀이 .

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());
        long[][] dp = new long[n + 1][10];
        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][j] = (dp[i - 1][j + 1]) % 1000000000;
                else if(j == 9) dp[i][j] = (dp[i - 1][j - 1]) % 1000000000;
                else dp[i][j] = (dp[i - 1][j - 1] + dp[i - 1][j + 1]) % 1000000000;
            }
        }

        long ans = 0;
        for(long num : dp[n]) {
            ans += num;
        }
        ans %= 1000000000;
        System.out.println(ans);
    }
}

dp[i][j] = 길이가 i 이고 j로 끝나는 계단수의 개수

% 10억한 것을 dp에 넣으면 dp는 int로 처리가 가능하다.

그런데 그 dp[n][0] ~ dp[n][9] 를 모두 더하면 int 범위가 넘어가기 때문에 ans는 long을 사용하고 다시 한 번 '%= 10억'을 해줘야 한다.

www.acmicpc.net/problem/9095

문제

정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다.

• 1+1+1+1
• 1+1+2
• 1+2+1
• 2+1+1
• 2+2
• 1+3
• 3+1

정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. n은 양수이며 11보다 작다.

출력

각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다.

예제 입력 1

3

4

7

10

예제 출력 1

7

44

274

풀이 1. (DP)

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 T = Integer.parseInt(br.readLine());
        int[] dp = new int[11];
        dp[0] = 1;
        dp[1] = 1;
        dp[2] = 2;

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

        for(int i = 0; i < T; i++) {
            int n = Integer.parseInt(br.readLine());
            System.out.println(dp[n]);
        }
    }
}

+1, +2, +3을 사용해 n을 만드는 경우는 총 3가지가 있다.

1. n-1  +1

2. n-2  +2

3. n-3  +3

풀이 2. (Brute Force)

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

public class Main {
    static BufferedReader br = null;
    static int ans;

    public static void dfs(int sum, int target) {
        if(sum >= target) {
            if(sum == target) {
                ans += 1;
            }
            return;
        }

        for(int i = 1; i <= 3; i++) {
            dfs(sum + i, target);
        }
    }

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

        while(T-- > 0) {
            int n = Integer.parseInt(br.readLine());
            ans = 0;
            dfs(0, n);
            System.out.println(ans);
        }
    }
}

DFS로도 풀 수 있다.

www.acmicpc.net/problem/11727

문제

2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오.

아래 그림은 2×17 직사각형을 채운 한가지 예이다.

입력

첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000)

출력

첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다.

예제 입력 1

2

예제 출력 1

3

예제 입력 2

8

예제 출력 2

171

예제 입력 3

12

예제 출력 3

2731

풀이 .

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[] dp = new int[n + 1];
        dp[0] = 1;
        dp[1] = 1;
        for(int i = 2; i <= n; i++) {
            dp[i] = (dp[i - 1] + dp[i - 2] * 2) % 10007;
        }
        System.out.println(dp[n]);
    }
}

'2×n 타일링' 문제에서 조금만 수정하여 해결했다.

n-2까지 채운 후 남아있는 4칸을 채우는 방법은 2x2 블록 하나를 놓는 방법과 2x1 가로블럭 두개를 놓는 방법, 총 2개가 존재하기 때문에 dp[n-2] * 2를 해주었다.

www.acmicpc.net/problem/11726

문제

2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오.

아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다.

입력

첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000)

출력

첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다.

예제 입력 1

2

예제 출력 1

2

예제 입력 2

9

예제 출력 2

55

풀이 .

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[] dp = new int[n + 1];
        dp[0] = 1;
        dp[1] = 1;
        for(int i = 2; i <= n; i++) {
            dp[i] = (dp[i - 1] + dp[i - 2]) % 10007;
        }
        System.out.println(dp[n]);
    }
}

n번째 칸을 채울 수 있는 경우는 두가지가 있다.

1. n-1번째까지 모두 채운 후 n번째에 세로블럭 하나를 놓는다.

2. n-2번째까지 모두 채운 후 n-1, n번째에 가로블럭 둘을 놓는다.

dp[n] = "n번째까지 타일을 채울 수 있는 모든 경우의 수" 라고 한다면

dp[n] = dp[n-1] + dp[n-2] 로 해결이 가능하다.

접근은 잘 했는데 초기화 문제 때문에 ArrayIndexOutOfBounds 런타임 에러로 애를 먹었다.

dp[0] = 0;

dp[1] = 1;

dp[2] = 2

로 초기화를 하고 i = 3부터 반복을 돌렸는데, 이렇게 하면 n = 1 일 때, dp[2] 에서 배열 범위 문제가 발생한다.

초기화 부분을 수정하여 정답처리 되었다.

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

n-2에서 세로블럭을 두 개 놓아서 채우는 경우를 고려하지 않는 이유?

-> 이건 이미 n-1에서 세로블럭 놓는 경우에 포함되어있음 (연속된 세로블럭을 놓는 것이므로)