1. 문제 링크

 

www.acmicpc.net/problem/11053

 

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

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

www.acmicpc.net

 

 

2. 문제 설명

수열을 입력받은 후, 가장 긴 증가하는 부분 수열의 길이를 출력하는 문제입니다.

다이나믹 프로그래밍으로 풀 수 있는 문제입니다.

 

 

 

3. 소스코드

BOJ 11053번 가장 긴 증가하는 부분 수열 C++ 풀이입니다.

#include <iostream>
#include <algorithm>
using namespace std;
 
int d[1000];
int a[1000];
 
int main(void)
{
	ios::sync_with_stdio(0);
	cin.tie(0);
 
	int N;
	cin >> N;
	for (int i = 0; i < N; i++)
		cin >> a[i];
 
	d[0] = 1;
	for (int i = 1; i < N; i++) {
		d[i] = 1;
		for (int j = 0; j < i; j++) {
			if (a[j] < a[i])
				d[i] = max(d[i], d[j] + 1);
		}
	}
	cout << *max_element(d, d + N);
 
	return 0;
}

5번 라인 :  다이나믹 프로그래밍으로 문제를 풀기 위해 길이가 수열의 크기의 최댓값(1000)인 배열을 선언했습니다. d[i]에는 i번째 수열의 항을 마지막으로 포함하는 부분 수열의 길이의 최댓값을 저장합니다.

6번 라인 : 수열의 각 항의 값을 입력받기 길이가 1000인 배열을 선언했습니다.

16번 라인 : 수열의 각 항의 값을 입력받아 배열 a에 저장합니다.

18번 라인 : d[0]은 0번째 항을 마지막으로 포함하는 부분 수열의 길이의 최댓값이므로 {a[0]}을 의미합니다. 따라서 1을 저장합니다.

19번 라인 : i = 1부터 N - 1까지 for문을 돌 때

20번 라인 : d[i]의 최솟값은 {a[i]}로 길이가 1이므로 일단 1로 초기화합니다.

21번 라인 : d[i]는 i번째 항을 마지막으로 포함하는 부분 수열의 길이의 최댓값이므로 for문을 이용해 j = 0부터 j < i까지 돌면서,

22번 라인 : j번째 수열의 항이 i번째 수열의 항보다 작다면 (예를 들어, a = {10, 30, 20}이고 i = 2라면 j = 0일 때는 10(a[j]) < 20(a[i])이므로 증가하는 부분 수열이 성립하지만, j = 1일 때는 30(a[j]) < 20(a[i])가 성립하지 않으므로 증가하는 부분 수열이 될 수 없습니다.)

23번 라인 : d[i]는 현재까지 i번째 항을 마지막으로 포함하는 부분 수열의 길이의 최댓값(d[i])과, j번째 항을 마지막으로 포함하는 부분 수열의 길이의 최댓값(d[j])에 i번째 항을 추가한 값인 d[j] + 1 중에서 큰 값을 d[i]에 저장합니다.

26번 라인 : d[0] ~ d[N - 1]까지의 값 중에서 최댓값을 출력하면 되고, 이를 구하기 위해 max_element함수를 사용했습니다.

'Algorithm' 카테고리의 다른 글

[백준 2606번 C++] 바이러스  (0) 2021.01.20
[백준 1260번 C++] DFS와 BFS  (0) 2021.01.20
[백준 2579번 C++] 계단 오르기  (0) 2020.11.09
[백준 2580번 C++] 스도쿠  (0) 2020.10.13
[백준 9663번 C++] N-Queen  (0) 2020.10.13

1. 문제 링크

www.acmicpc.net/problem/2579

 

2579번: 계단 오르기

계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. <그림 1>과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점

www.acmicpc.net

 

 

2. 문제 설명

계단의 개수와 각 계단의 점수를 입력받아, 계단 오르기 게임에서 얻을 수 있는 총점수의 최댓값을 출력하는 문제입니다.

계단 오르기 게임의 규칙은 다음과 같습니다.

1. 계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음 다음 계단으로 오를 수 있다.

2. 연속된 세 개의 계단을 모두 밟아서는 안 된다. 단, 시작점은 계단에 포함되지 않는다.

3. 마지막 도착 계단은 반드시 밟아야 한다.

다이나믹 프로그래밍으로 풀 수 있는 문제입니다.

 

 

 

3. 소스코드

BOJ 2579번 계단 오르기 C++ 풀이입니다.

#include <iostream>
#include <algorithm>
using namespace std;
 
int d[300][2];
int step[300];
 
int main(void)
{
	ios::sync_with_stdio(0);
	cin.tie(0);
 
	int n;
	cin >> n;
	for (int i = 0; i < n; i++)
		cin >> step[i];
 
	d[0][0] = step[0];
	d[1][0] = step[1];
	d[1][1] = step[0] + step[1];
	for (int i = 2; i < n; i++) {
		d[i][0] = max(d[i - 2][0], d[i - 2][1]) + step[i];
		d[i][1] = d[i - 1][0] + step[i];
	}
	cout << max(d[n - 1][0], d[n - 1][1]);
 
	return 0;
}

5번 라인 : 다이나믹 프로그래밍으로 문제를 풀기 위해 계단의 개수의 최댓값인 300크기의 int형 배열을 선언합니다. 계단 오르기 게임의 규칙이 한 번에 한 계단씩 또는 두 계단씩 오를 수 있고, 연속된 세 개의 계단을 모두 밟아서는 안 되므로, 이 조건을 검사하기 위해 d[i][0]에는 계단을 연속해서 밟지 않는 경우(즉, i -2번째 계단을 밟은 후 i번째 계단을 밟는 경우)의 최대 점수값을 저장하고, d[i][1]에는 계단을 연속해서 밟는 경우(즉, i - 1번째 계단을 밟은 후, i번째 계단을 밟는 경우)의 최대 점수 값을 저장합니다.

6번 라인 : 각 계단의 점수를 저장할 step 배열을 선언합니다. 역시 계단의 개수의 최댓값이 300이므로 크기는 300으로 선언했습니다. d배열과 step배열 모두 0으로 초기화하기 위해 전역변수로 선언했습니다.

16번 라인 : 각 계단의 점수를 입력받아 step배열에 저장합니다. 문제에서는 1번째부터 시작하지만 편의를 위해 0번째부터 저장했습니다.

18번 라인 : 0번째 계단은 연속해서 밟을 수 없으므로 d[0][0]만 가능하므로 d[0][0]에 0번째 계단의 점수를 저장합니다.

19번 라인 : 1번째 계단은 연속해서 밟지 않는 경우 바로 1번째 계단을 밟는 것이기 때문에 d[1][0]에 1번째 계단의 점수를 저장합니다.

20번 라인 : 1번째 계단은 연속해서 밟는 경우, 0번째 계단, 1번째 계단을 밟는 것이기 때문에 d[1][1]에 0번째 계단의 점수와 1번째 계단의 점수의 합을 저장합니다.

21번 라인 : 2번째 계단부터 n - 1번째 계단까지 for문을 돌면서

22번 라인 : d[i][0]번째 계단에는 계단을 연속해서 밟지 않는 경우를 저장하기 때문에, i-2번째 계단을 밟은 후, i번째 계단을 밟는 경우입니다. 따라서 i-2번째 계단을 밟을 때 얻을 수 있는 점수인 d[i - 2][0]과 d[i - 2][1] 중에서 큰 값과 i번째 계단의 값을 더해서 저장합니다.

23번 라인 : d[i][1]번째 계단에는 계단을 연속해서 밟는 경우를 저장하기 때문에 i-1번째 계단을 밟은 후, i번째 계단을 밟는 경우입니다. 연속된 세 개의 계단을 밟을 수 없으므로 d[i - 1][1]을 선택할 수 없습니다. 따라서 d[i - 1][0]에 저장된 점수에 i번째 계단의 값을 더해서 저장합니다.

25번 라인 : 계단의 점수를 입력받을 때 0번째 부터 입력받았으므로, 최종적으로 n - 1번째 계단을 밟았을 때의 점수 중에서 큰 값을 출력합니다.

'Algorithm' 카테고리의 다른 글

[백준 1260번 C++] DFS와 BFS  (0) 2021.01.20
[백준 11053번 C++] 가장 긴 증가하는 부분 수열  (0) 2020.11.09
[백준 2580번 C++] 스도쿠  (0) 2020.10.13
[백준 9663번 C++] N-Queen  (0) 2020.10.13
[백준 14888번 C++] 연산자 끼워넣기  (0) 2020.10.07

1. 개선된 switch 문이란?

2020년 3월에 출시된 Java 14부터 개선된 switch 문을 지원합니다.

기존 switch문은 깔끔하지 못하고 가독성도 떨어지며, break문의 누락으로 인한 오류 가능성도 크기 때문에

화살표 case 라벨, 다중 case 라벨, switch 연산식, yield 예약어 등의 기능이 추가되었습니다.

 

예제에서 사용하는 열거 타입은 다음과 같습니다. 열거 타입을 사용하는 이유는 마지막에 설명드리겠습니다.

enum Day { MONDAY, TUESDAY, WEDNESDAY, THURSDAY, FRIDAY, SATURDAY, SUNDAY }

 

 

 

2. 화살표 case 라벨, 다중 case 라벨 (switch1, enhancedSwitch1)

switch (day) {
    case MONDAY:
    case FRIDAY:
    case SUNDAY:
        System.out.println(6);
        break;
    case TUESDAY:
        System.out.println(7);
        break;
    case THURSDAY:
    case SATURDAY:
        System.out.println(8);
        break;
    case WEDNESDAY:
        System.out.println(9);
        break;
}

day의 길이를 출력하는 기존 switch 문 예제입니다.

day가 MONDAY, FRIDAY, SUNDAY인 경우 fall through를 이용하여 6을 출력하는 것을 볼 수 있습니다.

이를 화살표 case 라벨과 다중 case 라벨을 사용한 개선된 switch문으로 바꾸면 아래와 같습니다.

switch (day) {
    case MONDAY, FRIDAY, SUNDAY	-> System.out.println(6);
    case TUESDAY				-> System.out.println(7);
    case THURSDAY, SATURDAY		-> System.out.println(8);
    case WEDNESDAY				-> System.out.println(9);
}

fall through를 사용하지 않고 다중 case 라벨(,)을 사용하여 case MONDAY, FRIDAY, SUNDAY라고 표현한 것이 훨씬 가독성이 좋습니다.

또, 화살표 case 라벨(->)을 사용하면 마지막에 break를 사용한 것과 동일합니다.

이때 주의해야 할 점은 case 라벨(:)을 사용할 때는 실행문이 여러 개여도 중괄호({})로 묶어줄 필요가 없었지만,

화살표 case 라벨(->)을 사용할 때 실행문이 여러 개(즉, 2줄 이상)일 때는 중괄호로 묶어줘야 합니다.

한마디로 화살표 case 라벨(->)을 사용할 때는 if 문이나 for 문처럼 실행문이 1줄일 때만 중괄호를 생략할 수 있습니다.

 

 

 

3. switch 연산식 (switch2, enhancedSwitch2)

int numLetters;
switch (day) {
    case MONDAY:
    case FRIDAY:
    case SUNDAY:
        numLetters = 6;
        break;
    case TUESDAY:
        numLetters = 7;
        break;
    case THURSDAY:
    case SATURDAY:
        numLetters = 8;
        break;
    case WEDNESDAY:
        numLetters = 9;
        break;
    default:
        numLetters = -1;
}

numLetters 변수에 day의 길이를 저장하는 기존 switch 문 예제입니다.

case 문에서 numLetters 변수에 값을 저장하는 방식을 사용해야 합니다.

이를 switch 연산식을 사용한 향상된 switch 문으로 바꾸면 아래와 같습니다.

int numLetters = switch (day) {
    case MONDAY, FRIDAY, SUNDAY	-> 6;
    case TUESDAY				-> 7;
    case THURSDAY, SATURDAY		-> 8;
    case WEDNESDAY				-> 9;
};

화살표 case 라벨(->) 뒤에 있는 값을 return하여 numLetters에 바로 대입할 수 있습니다.

만약 case TUESDAY -> 7;에서 7을 System.out.println(7)이나 "Seven" 등으로 바꾸면 int type이 아니므로 에러가 발생합니다.

numLetters의 type을 Object로 바꿔주면 "Seven"은 가능하지만,

System.out.println(7)은 return type이 void이므로 여전히 에러가 발생합니다.

즉, switch 연산식을 사용할 때 화살표 case 라벨(->) 뒤에 있는 값이 void type이면 에러가 발생합니다.

 

 

 

4. yield 예약어 사용 (enhancedSwitch3, enhancedSwitch4)

yield는 키워드가 아니라 제한된 식별자(restricted identifier)이기 때문에 var처럼 식별자로 사용할 수 있습니다.

방금 전에 본 switch 연산식에서 길이를 return하기 전에 특정 메시지를 출력하고 싶으면 아래와 같이 사용하면 됩니다.

int numLetters = switch (day) {
    case MONDAY, FRIDAY, SUNDAY	-> {
        System.out.print("Six ");
        yield 6;
    }
    case TUESDAY				-> 7;
    case THURSDAY, SATURDAY		-> 8;
    case WEDNESDAY				-> 9;
};

향상된 switch 문에서는 중괄호 안에서만 yield 예약어를 사용할 수 있습니다.

따라서 case TUESDAY -> yield 7; 이라고 하면 에러입니다. 

int numLetters = switch (day) {
    case MONDAY, FRIDAY, SUNDAY:
        System.out.print("Six ");
        yield 6;
    case TUESDAY:
        yield 7;
    case THURSDAY, SATURDAY:
        yield 8;
    case WEDNESDAY:
        yield 9;
};

yield 예약어는 case 라벨(:)에도 사용 가능합니다.

case 라벨(:)은 실행문이 여러 개일 때 중괄호를 사용하지 않아도 됩니다.

 

 

 

5. 열거 타입(enum)을 사용하는 이유

static int switchError(String s) {
    return switch (s) {
        case "MONDAY", "FRIDAY", "SUNDAY"	-> 6;
        case "TUESDAY"					-> 7;
        case "THURSDAY, SATURDAY"		-> 8;
        case "WEDNESDAY"				-> 9;
        default						-> -1;
    };
}

위의 메서드에서 default를 주석 처리하면 "'switch' expression does not cover all possible input values" 에러 메시지를 볼 수 있습니다.

가능한 모든 값에 대하여 일치하는 case 라벨이 하나라도 없으면 위와 같은 에러를 볼 수 있습니다.

위의 예제에서는 String type이므로 가능한 모든 값은 거의 무한대나 마찬가지입니다.

String대신 int type이고, default를 사용하지 않는다면 int 범위의 모든 값에 대하여 case를 사용해야 할 것입니다.

따라서 default를 사용하거나, 필요한 값들로 열거 타입(enum)을 만들어서 사용해야 합니다.

 

 

 

6. 전체 코드

예제에서 사용한 전체 코드입니다.

더보기 
public class SwitchTest {
 
    public static void main(String[] args) {
        switch1(Day.FRIDAY);                                // 6
        enhancedSwitch1(Day.FRIDAY);                        // 6
 
        System.out.println(switch2(Day.SATURDAY));          // 8
        System.out.println(enhancedSwitch2(Day.SATURDAY));  // 8
 
        System.out.println(enhancedSwitch3(Day.SUNDAY));    // Six 6
        System.out.println(enhancedSwitch4(Day.SUNDAY));    // Six 6
 
        switchError("ERROR");                            // -1
    }
 
    static void switch1(Day day) {
        switch (day) {
            case MONDAY:
            case FRIDAY:
            case SUNDAY:
                System.out.println(6);
                break;
            case TUESDAY:
                System.out.println(7);
                break;
            case THURSDAY:
            case SATURDAY:
                System.out.println(8);
                break;
            case WEDNESDAY:
                System.out.println(9);
                break;
        }
    }
 
    static void enhancedSwitch1(Day day) {
        switch (day) {
            case MONDAY, FRIDAY, SUNDAY -> System.out.println(6);
            case TUESDAY                -> System.out.println(7);
            case THURSDAY, SATURDAY     -> System.out.println(8);
            case WEDNESDAY              -> System.out.println(9);
        }
    }
 
    static int switch2(Day day) {
        int numLetters;
        switch (day) {
            case MONDAY:
            case FRIDAY:
            case SUNDAY:
                numLetters = 6;
                break;
            case TUESDAY:
                numLetters = 7;
                break;
            case THURSDAY:
            case SATURDAY:
                numLetters = 8;
                break;
            case WEDNESDAY:
                numLetters = 9;
                break;
            default:
                numLetters = -1;
        }
        return numLetters;
    }
 
    static int enhancedSwitch2(Day day) {
        // 변수를 선언하지 않고 바로 return하는 것도 가능
        return switch (day) {
            case MONDAY, FRIDAY, SUNDAY -> 6;
            case TUESDAY                -> 7;
            case THURSDAY, SATURDAY     -> 8;
            case WEDNESDAY              -> 9;
        };
 
//        int numLetters = switch (day) {
//            case MONDAY, FRIDAY, SUNDAY -> 6;
//            case TUESDAY                -> 7;
//            case THURSDAY, SATURDAY     -> 8;
//            case WEDNESDAY              -> 9;
//        };
//        return numLetters;
    }
 
    // return type이 Object인 경우 다양한 type 사용 가능
//    static Object enhancedSwitch2(Day day) {
//        return switch (day) {
//            case MONDAY, FRIDAY, SUNDAY -> 6;
//            case TUESDAY                -> "Seven";
//            case THURSDAY, SATURDAY     -> 8;
//            case WEDNESDAY              -> 9;
//        };
//    }
 
    static int enhancedSwitch3(Day day) {
        return switch (day) {
            case MONDAY, FRIDAY, SUNDAY -> {
                System.out.print("Six ");
                yield 6;
            }
            case TUESDAY -> 7;
            case THURSDAY, SATURDAY -> 8;
            case WEDNESDAY -> 9;
        };
    }
 
    static int enhancedSwitch4(Day day) {
        return switch (day) {
            case MONDAY, FRIDAY, SUNDAY:
                System.out.print("Six ");
                yield 6;
            case TUESDAY:
                yield 7;
            case THURSDAY, SATURDAY:
                yield 8;
            case WEDNESDAY:
                yield 9;
        };
    }
 
    static int switchError(String s) {
        return switch (s) {
            case "MONDAY", "FRIDAY", "SUNDAY"   -> 6;
            case "TUESDAY"                      -> 7;
            case "THURSDAY, SATURDAY"           -> 8;
            case "WEDNESDAY"                    -> 9;
            default                             -> -1;
        };
    }
 
    enum Day { MONDAY, TUESDAY, WEDNESDAY, THURSDAY, FRIDAY, SATURDAY, SUNDAY }
}

 

 

 

7. 참고한 사이트

 

JEP 361: Switch Expressions

JEP 361: Switch Expressions AuthorGavin BiermanOwnerJan LahodaTypeFeatureScopeSEStatusClosed / DeliveredRelease14Componentspecification / languageDiscussionamber dash dev at openjdk dot java dot netEffortSDurationMRelates toJEP 354: Switch Expressi

openjdk.java.net

 

'Java' 카테고리의 다른 글

[Java 10] 자바 var  (0) 2020.09.13

+ Recent posts

티스토리툴바