더 이상 물러설 곳이 없다

www.acmicpc.net/problem/1463

문제

정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.

1. X가 3으로 나누어 떨어지면, 3으로 나눈다.
2. X가 2로 나누어 떨어지면, 2로 나눈다.
3. 1을 뺀다.

정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.

입력

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

출력

첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다.

예제 입력 1

2

예제 출력 1

1

예제 입력 2

10

예제 출력 2

3

풀이 .

import java.util.*;
import java.io.*;

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] = 0;
        dp[1] = 0;

        for(int i = 2; i <= n; i++) {
            int temp = n;
            if(i % 3 == 0) temp = Math.min(temp, dp[i / 3]);
            if(i % 2 == 0) temp = Math.min(temp, dp[i / 2]);
            temp = Math.min(temp, dp[i - 1]);
            dp[i] = temp + 1;
        }
        System.out.println(dp[n]);
    }
}

전형적인 DP 문제이다.

문제는 n을 1로 만들 것을 요구하지만 1을 n으로 만드는 식으로 풀어냈다.

(dp[n] = 1에서 n으로 도달하기 위한 최소 연산 회수)

만약 n에 1, 2, 3 모든 연산을 사용할 수 있는 수라면, n으로 올 수 있는 숫자의 경우의 수는 총 셋이다.

1. (n / 3) * 3

2. (n / 2) * 2

3. (n - 1) + 1

다시 말하면 n/3, n/2, n-1에서 한 번의 연산만 더 수행하면 n이 될 수 있는 것.

즉, dp[n / 3], dp[n / 2], dp[n - 1] 중 최솟값 + 1이 dp[n]이 될 것이다.

그럼 dp[n / 3], dp[n / 2], dp[n - 1] 은 또 어떻게 구하나?

n에서 했던 것처럼 각자 자신에게 올 수 있는 연산들에 대한 경우를 모두 따져보면 된다.

탑 다운, 바텀 업 모두 가능하지만 바텀 업 방식으로 구현했다.

@Component("등록될 빈 이름")을 통해 빈의 이름을 직접 설정할 수 있다. (디폴트는 클래스명에서 앞글자만 소문자로 바꾼 이름)

만약 각각 다른 클래스에 똑같은 이름으로 설정해 놓는다면?

ex) 둘 다 service로 이름 설정 됨

@Component("service")
public class MemberServiceImpl implements MemberService {
}
.
.
@Component("service")
public class OrderServiceImpl implements OrderService {
}

-> ConflictingBeanDefinitionException 예외 발생

위처럼 자동vs자동이 아닌 수동vs자동인 경우 수동빈이 우선권을 가진다. 자동빈을 수동빈이 덮어버림

-> 이를 의도하여 사용할 수도 있겠지만 현실은 의도적이기 보다는 실수로 이런 현상을 많이 초래한다. 에러가 나는 상황인데 에러가 나지 않으니 잡기도 어렵다. 그래서 최근 스프링 부트에서 수동 빈 등록과 자동 빈 등록이 충돌하면 오류가 발생하도록 기본값을 변경하였다.

@ComponentScan 을 통해 빈 등록을 위한 컴포넌트 스캔을 조작할 수 있다.

basePackages 옵션을 통해 컴포넌트 스캔을 시작할 패키지의 위치를 직접 설정할 수 있으나 디폴트는 일단 @Component 가 있는 클래스가 속한 패키지를 시작으로 그 하위를 모두 스캔한다.

일반적이고 바람직한 방식은 스캔 시작 패키지를 따로 지정하기 보다는 설정 정보 클래스(AppConfig)를 프로젝트 최상단에 두는 것이다.

프로젝트의 구조가 다음과 같다면,

com.hello

com.hello.service

com.hello.repository

AppConfig를 com.hello 하위에 만들고 @ComponentScan을 다는 것이다. 그럼 service, repository 모든 패키지를 스캔할 수 있다.

컴포넌트 스캔을 시작하면 스캔 범위에 해당하는 모든 클래스를 검사하여 @Component 가 붙은 모든 클래스의 빈을 등록한다. 

(@Configuration, @Controller, @Service, @Repository 등은 모두 내부에 @Component를 포함하고 있다.)

스프링 부트를 사용할 때는 @SpringBootApplication 을 프로젝트 시작 루트 위치에 두는 것이 일반적이다.

(@SpringBootApplication은 내부적으로 @Component를 포함한다.)

또한 굳이 AppConfig 내부에서 @Bean을 통해 의존성 주입을 수동으로 해주지 않아도 @Autowired를 통해 자동으로 의존성 주입을 해줄 수 있다.

@Component
public class MemberServiceImpl implements MemberService {

    private final MemberRepository memberRepository;

    @Autowired
    public MemberServiceImpl(MemberRepository memberRepository) {
        this.memberRepository = memberRepository;
    }
    
}

이렇게 생성자에 @Autowired를 달아 의존성 생성자 주입을 자동으로 해줄 수 있다.

(@Autowired 를 찾으면 해당 함수의 파라미터의 타입으로 주입할 빈을 찾는다.)

(필드주입에도 @Autowired 사용 가능함)

이때, 만약 등록할 빈의 클래스에 @Component가 붙어있지 않거나 스캔의 범위에서 벗어나있어 빈 등록이 되지 않았을 경우 에러가 발생한다.

또한, 해당 빈의 타입으로 여러 가지 빈이 존재할 수 있는데 이 경우에는 @Qualifier 를 통해 어떤 타입의 빈을 주입할 것인지 명시할 수 있다.

@Component
public class MemberServiceImpl implements MemberService {

    private final MemberRepository memberRepository;

    @Autowired
    public MemberServiceImpl(@Qualifier("memory") MemberRepository memberRepository) {
        this.memberRepository = memberRepository;
    }
    
}

.
.
.

@Repository("memory")
public class MemoryMemberRepository implements MemberRepository {
    ...
}

의존성 주입에서 우선순위를 두고 싶은 빈의 이름을 @Qualifier에 담아 어노테이션을 달아놓으면 해당 빈을 우선적으로 찾아 주입한다.

(codeung.tistory.com/116 에서 좀 더 자세히 설명)

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

문제

예제를 보고 규칙을 유추한 뒤에 별을 찍어 보세요.

입력

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

출력

첫째 줄부터 N번째 줄까지 차례대로 별을 출력한다.

예제 입력 1

1

예제 출력 1

*

예제 입력 2

2

예제 출력 2

 *

***

예제 입력 3

3

예제 출력 3

  *

 * *

*****

예제 입력 4

4

예제 출력 4

   *

  * *

 * * *

******

풀이 .

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();

        int n = Integer.parseInt(br.readLine());
        int[] starArr = new int[n + 1];
        int[] spaceArr = new int[n + 1];
        int cnt = 3;
        for(int i = 2; i <= n; i++) {
            starArr[i] = cnt;
            spaceArr[i] = cnt - 2;
            cnt += 2;
        }

        // 첫번째 줄
        for(int i = 1; i <= n - 1; i++) sb.append(" ");
        sb.append("*\n");
        // (2 ~ n-1)번째 줄
        for(int i = 2; i <= n - 1; i++) {
            // 먼저 공백 쭉
            for(int j = n - i; j >= 1; j--) sb.append(" ");
            // "* 공백 쭉 *"
            sb.append("*");
            for(int j = 1; j <= spaceArr[i]; j++) sb.append(" ");
            sb.append("*\n");
        }
        // n번째 줄
        for(int i = 1; i <= starArr[n]; i++) sb.append("*");

        bw.write(sb.toString());
        br.close();
        bw.flush();
        bw.close();
    }
}

예시들을 보고 반복문의 역할을 어떻게 나눌 것인지가 중요

세 개의 큰 반복문으로 나누었다.

1. 첫번째 줄을 찍는 반복문

2. 2~n-1번째 줄을 찍는 반복문

3. n번째 줄을 찍는 반복문

n이 1, 2일 때는 별 사이에 연속적인 공백이 들어가는 줄이 없다.

그래서 두 특수케이스 n=1일때 3으로만 처리, n=2일때 1, 3으로만 처리하도록 하고 나머지는 1, 2, 3으로 해결하도록 했다.

2~n-1번째 줄들에서 별 사이에 들어가는 공백의 수는 1부터 시작해 2개씩 늘어나는 규칙을 이용했다.

www.acmicpc.net/problem/10991

문제

예제를 보고 규칙을 유추한 뒤에 별을 찍어 보세요.

입력

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

출력

첫째 줄부터 N번째 줄까지 차례대로 별을 출력한다.

예제 입력 1

1

예제 출력 1

*

예제 입력 2

2

예제 출력 2

 *

* *

예제 입력 3

3

예제 출력 3

  *

 * *

* * *

예제 입력 4

4

예제 출력 4

   *

  * *

 * * *

* * * *

풀이 .

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();

        int n = Integer.parseInt(br.readLine());
        int[] arr = new int[n + 1];
        int cnt = 1;
        for(int i = 1; i <= n; i++) {
            arr[i] = cnt;
            cnt += 2;
        }

        for(int i = 1; i <= n; i++) {
            for(int j = n - i; j >= 1; j--) sb.append(" ");
            for(int j = 1; j <= arr[i]; j++) {
                if(j % 2 == 1) sb.append("*");
                else sb.append(" ");
            }
            sb.append("\n");
        }

        bw.write(sb.toString());
        br.close();
        bw.flush();
        bw.close();
    }
}

www.acmicpc.net/problem/2522

문제

예제를 보고 규칙을 유추한 뒤에 별을 찍어 보세요.

입력

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

출력

첫째 줄부터 2×N-1번째 줄까지 차례대로 별을 출력한다.

예제 입력 1

3

예제 출력 1

  *

 **

***

 **

  *

풀이 .

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();

        int n = Integer.parseInt(br.readLine());
        for(int i = 1; i <= n; i++) {
            for(int j = n - i; j >= 1; j--) sb.append(" ");
            for(int j = 1; j <= i; j++) sb.append("*");
            sb.append("\n");
        }
        for(int i = n - 1; i >= 1; i--) {
            for(int j = 1; j <= n - i; j++) sb.append(" ");
            for(int j = i; j >= 1; j--) sb.append("*");
            sb.append("\n");
        }

        bw.write(sb.toString());
        br.close();
        bw.flush();
        bw.close();
    }
}

www.acmicpc.net/problem/2446

문제

예제를 보고 규칙을 유추한 뒤에 별을 찍어 보세요.

입력

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

출력

첫째 줄부터 2×N-1번째 줄까지 차례대로 별을 출력한다.

예제 입력 1

5

예제 출력 1

*********

 *******

  *****

   ***

    *

   ***

  *****

 *******

*********

풀이 .

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();

        int n = Integer.parseInt(br.readLine());
        int[] arr = new int[n + 1];
        int cnt = 1;
        for(int i = 1; i <= n; i++) {
            arr[i] = cnt;
            cnt += 2;
        }

        for(int i = n; i >= 1; i--) {
            for(int j = n - i; j >= 1; j--) sb.append(" ");
            for(int k = 0; k < arr[i]; k++) sb.append("*");
            sb.append("\n");
        }
        for(int i = 2; i <= n; i++) {
            for(int j = n - i; j >= 1; j--) sb.append(" ");
            for(int k = 0; k < arr[i]; k++) sb.append("*");
            sb.append("\n");
        }

        bw.write(sb.toString());
        br.close();
        bw.flush();
        bw.close();
    }
}

www.acmicpc.net/problem/2445

문제

예제를 보고 규칙을 유추한 뒤에 별을 찍어 보세요.

입력

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

출력

첫째 줄부터 2×N-1번째 줄까지 차례대로 별을 출력한다.

예제 입력 1

5

예제 출력 1

*        *

**      **

***    ***

****  ****

**********

****  ****

***    ***

**      **

*        *

풀이 .

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();
        int n = Integer.parseInt(br.readLine());

        for(int i = 1; i <= n; i++) {
            // "*", " ", "*"
            for(int j = 1; j <= i; j++) sb.append("*");
            for(int j = (n - i) * 2; j >= 1; j--) sb.append(" ");
            for(int j = 1; j <= i; j++) sb.append("*");
            sb.append("\n");
        }
        for(int i = n - 1; i >= 1; i--) {
            // "*", " ", "*"
            for(int j = 1; j <= i; j++) sb.append("*");
            for(int j = 1; j <= (n - i) * 2; j++) sb.append(" ");
            for(int j = 1; j <= i; j++) sb.append("*");
            sb.append("\n");
        }

        bw.write(sb.toString());
        br.close();
        bw.flush();
        bw.close();
    }
}