더 이상 물러설 곳이 없다

www.acmicpc.net/problem/1874

문제

스택 (stack)은 기본적인 자료구조 중 하나로, 컴퓨터 프로그램을 작성할 때 자주 이용되는 개념이다. 스택은 자료를 넣는 (push) 입구와 자료를 뽑는 (pop) 입구가 같아 제일 나중에 들어간 자료가 제일 먼저 나오는 (LIFO, Last in First out) 특성을 가지고 있다.

1부터 n까지의 수를 스택에 넣었다가 뽑아 늘어놓음으로써, 하나의 수열을 만들 수 있다. 이때, 스택에 push하는 순서는 반드시 오름차순을 지키도록 한다고 하자. 임의의 수열이 주어졌을 때 스택을 이용해 그 수열을 만들 수 있는지 없는지, 있다면 어떤 순서로 push와 pop 연산을 수행해야 하는지를 알아낼 수 있다. 이를 계산하는 프로그램을 작성하라.

입력

첫 줄에 n (1 ≤ n ≤ 100,000)이 주어진다. 둘째 줄부터 n개의 줄에는 수열을 이루는 1이상 n이하의 정수가 하나씩 순서대로 주어진다. 물론 같은 정수가 두 번 나오는 일은 없다.

출력

입력된 수열을 만들기 위해 필요한 연산을 한 줄에 한 개씩 출력한다. push연산은 +로, pop 연산은 -로 표현하도록 한다. 불가능한 경우 NO를 출력한다.

예제 입력 1

8 4 3 6 8 7 5 2 1

예제 출력 1

+ + + + - - + + - + + - - - - -

예제 입력 2

5 1 2 5 3 4

예제 출력 2

NO

풀이 .

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        Stack<Integer> stk = new Stack<>();
        int n = Integer.parseInt(br.readLine());

        int lastPush = 0;
        while(n-- > 0) {
            int target = Integer.parseInt(br.readLine());

            if(stk.isEmpty()) {
                int len = target - lastPush;
                for(int i = 0; i < len; i++) {
                    stk.push(++lastPush);
                    sb.append("+").append("\n");
                }
                stk.pop();
                sb.append("-").append("\n");
            }else {
                if(stk.peek() == target) {
                    stk.pop();
                    sb.append("-").append("\n");
                }else if(stk.peek() > target) {
                    System.out.println("NO");
                    return;
                }else if(stk.peek() < target) {
                    int len = target - lastPush;
                    for(int i = 0; i < len; i++) {
                        stk.push(++lastPush);
                        sb.append("+").append("\n");
                    }
                    stk.pop();
                    sb.append("-").append("\n");
                }
            }
        }
        System.out.println(sb.toString());
    }
}

무식하게 구현했다.

더 똑똑한 방법이 있을 거 같긴 하다.

값 타입의 실제 인스턴스를 그대로 공유하는 것은 매우 위험하다.

객체를 넘기면 값 자체를 넘기는 것이 아니라 참조값을 넘기기 때문에 이런 식으로 객체를 공유하면 한 엔티티의 속성을 변경했는데 객체를 공유하던 다른 엔티티의 속성까지 함께 변해버리는 문제가 발생할 수 있다.

만약 같은 값을 공유해야 하는 경우가 있다면 이러한 문제를 방지하기 위해 항상 값 타입의 실제 객체를 직접 공유하지 말고 값만 복사해서 사용해야 한다. 아래와 같은 모양처럼.

혹시라도 실수로 참조값을 공유하여 문제가 발생하는 것을 막기 위해서 항상 값 타입 객체는 불변 객체(immutable object)로 만들어야 한다.

뭐 대단한 건 아니고 그냥 setter를 만들지 않거나 private으로 만들어서 속성의 변경을 막아버리는 것이다.

그리고 만약 값을 공유하거나 혹은 일부 속성만 변경하고 싶은 경우에는 아래처럼 완전히 새로운 객체를 만들어서 갈아끼워넣는 방식이 바람직하다.

Address address = new Address("city", "street", "10000");
            
Member member = new Member();
member.setHomeAddress(address);
em.persist(member);
            
// city만 변경하고 싶더라도 객체 자체를 새로 갈아끼워넣는다
member.setHomeAddress(new Address("NewCity", address.getStreet(), address.getZipcode()));
            

JPA의 값 타입 중에는 임베디드 타입이란 것이 존재한다.

@Entity
public class Member {

    @Id @GeneratedValue
    @Column(name = "MEMBER_ID")
    private Long id;

    @ManyToOne
    @JoinColumn(name = "TEAM_ID")
    private Team team;
    
    private LocalDateTime startDate;
    private LocalDateTime endDate;
}

똑같은 날짜 타입으로 두 가지 컬럼이 존재한다.

'날짜'라는 공통점이 있기에 하나로 묶어 관리한다면 더 편하게 쓸 수 있을 듯 하다.

@Embeddable
public class Period {

    private LocalDateTime startDate;
    private LocalDateTime endDate;
}
.
.
.
@Entity
public class Member {

    @Id @GeneratedValue
    @Column(name = "MEMBER_ID")
    private Long id;

    @ManyToOne
    @JoinColumn(name = "TEAM_ID")
    private Team team;

    @Embedded
    private Period workPeriod;
}

날짜를 한 번에 관리하는 클래스를 만들고 그 클래스를 속성으로 가져올 수 있다.

임베디드 타입을 선언하는 클래스에는 @Embeddable, 사용하는 쪽에는 @Embedded를 달아주면 된다.

물론 임베디드 타입 클래스 내부에서도 @Column으로 특정 컬럼과 매핑해줄 수 있다. 기본적으로는 임베디드 클래스의 모든 멤버변수들이 컬럼으로 만들어진다.

또한, 임베디드 클래스 내부에 메서드를 생성하여 좀 더 객체지향스러운 사용도 가능하다.

JPA는 데이터 타입을 크게 둘로 분류한다.

1. 엔티티 타입

@Entity로 테이블에 매핑하는 객체

2. 값 타입

primitive type, wrapper class 등 식별자(PK)없이 값 자체만 존재하는 데이터

값 타입은 다시 셋을 분류된다.

1. 기본값 타입 (primitive type, wrapper class, String)

2. 임베디드 타입 (= 복합 값 타입)

3. 컬렉션 값 타입

기본적으로 엔티티 타입이 값 타입을 포함하는 형태가 구성되기 때문에 값 타입은 그 생명주기를 엔티티에 의존하게 된다.

(Cascade 영속성 전이)

RDB에서의 cascade 기능을 JPA에서도 사용할 수 있다.

Member와 Team은 N:1 관계이다. Team은 여러 Member를 가질 수 있는데, member 객체가 하나 생성될 때마다 일일히 em.persist(member) 해주기 귀찮을 수 있다.

굳이 귀찮음의 문제가 아니더라도 member 중심이 아닌 team 중심적 프로그래밍을 하고 싶을 수도 있다.

이때 cascade 속성을 사용해서 멤버들을 포함한 team 하나만 persist() 함으로써 모든 멤버들을 한 번에 persist() 할 수 있다.

@Entity
public class Member {

    @Id @GeneratedValue
    @Column(name = "MEMBER_ID")
    private Long id;

    @ManyToOne
    @JoinColumn(name = "TEAM_ID")
    private Team team;
}
.
.
.
@Entity
public class Team {

    @Id @GeneratedValue
    @Column(name = "TEAM_ID")
    private Long id;

    @OneToMany(mappedBy = "team", cascade = CascadeType.ALL)
    private List<Member> members = new ArrayList<>();
}

 이렇게 하면 연관관계의 주인인 team이 persist 될 때 cascade 하게 그 안의 모든 member들도 함께 처리된다.

보통 CascadeType.ALL, CascadeType.PERSIST 둘 중 하나를 선택하여 사용한다.

(완전히 같이 가도록 두든지 아님 삭제를 막기 위해 저장에 대해서만 허용하든지)

주의할 점은, Member처럼 Team이라는 단일 엔티티에만 종속된 경우에는 cascade로 함께 관리해도 무방하지만 만약 Member를 참조하는 다른 엔티티가 또 존재한다면 이 경우엔 cascade를 쓰지 않고 따로 관리하는 것이 좋다. 

(이 경우에도 cascade를 쓰면 운영이 너무 어려워진다.

예를 들어, Member를 가지는 다른 엔티티가 존재하는데 Team에서 Member에 CascadeType.ALL을 해놓으면? 

Team이 지워질 때 Member도 함께 지워지고, 그 Member를 참조하던 다른 엔티티에 문제가 생길 수 있다) 

(고아 객체)

부모와 참조관계를 형성한 자식 객체가 존재한다.

이 부모가 사라진다면 자식은 고아가 된다. 고아가 된 객체를 자동적으로 처리하는 CascadeType.REMOVE 와 같은 동작을 수행하도록 하는 옵션이 있다.

@OneToMany(mappedBy = "관계의 주인", orphanRemoval = true)

orphanRemoval도 Cascade와 같은 이유로 인해 단일 참조 관계일 경우에만 사용해야 한다.

cascade = CascadeType.ALL + orphanRemoval = true   ->  자식의 생명주기를 부모가 관리???

Member와 Team처럼 참조 관계로 엮여있을 경우 Member객체를 조회하면 조인 쿼리로 조회하여 Team객체까지 한 번에 찾아온다.

그런데 참조 관계로 엮여있기는 하지만 Team을 별로 사용하지 않는 비즈니스 로직일 경우에는 조인으로 Team까지 한 번에 가져오는 것이 낭비가 될 수 있다.

이를 막기 위해 프록시를 사용한 지연 로딩이 존재한다.

@Entity
public class Member {

    @Id @GeneratedValue
    @Column(name = "MEMBER_ID")
    private Long id;

    @ManyToOne(fetch =  FetchType.LAZY)
    private Team team;
}

참조 관계 매핑 어노테이션의 fetch 속성을 통해 이를 조작할 수 있다.

즉시 로딩의 경우엔 Member를 조회하면 조인 쿼리로 Team까지 함께 가져온다.

(@ManyToOne, @OneToOne은 디폴트가 FetchType.EAGER으로 즉시 로딩이다.)

FetchType.LAZY를 사용할 경우 지연 로딩 방식을 사용하는데, 이 경우 조인 쿼리를 사용하지 않고 오롯이 Member객체만 조회한다.

이때 Member객체 안에 있는 Team 객체는 Team을 상속한 프록시 객체가 대체하게 된다.

(@OneToMany, @ManyToMany는 디폴트가 지연 로딩)

그러다가 m.getTeam.getName() 등으로 team객체의 기능을 직접 사용해야 하는 순간이 왔을 때 DB에 Team의 조회 쿼리를 날려 프록시 객체를 초기화해준다.

가급적 지연 로딩만 사용하는 것이 좋다.

엔티티들이 관계가 복잡해져 조인이 얽히고 섥힐수록 조인을 통해 한 번에 모든 객체를 조회하기 위한 낭비가 커진다.

기본적으로 설정은 LAZY로 해놓고 참조 객체들이 한  번에 필요한 경우에는 JPQL fetch join, 엔티티 그래프 등을 사용해서 한 번에 가져오도록 명시해주는 것이 좋다.

www.acmicpc.net/problem/1943

문제

윤화와 준희는 솔선수범하여 쓰레기를 줍는 착한 일을 하였다. 원장선생님께서는 윤화와 준희를 칭찬하시고 과자나 사 먹으라고 하시며 동전 몇 개를 윤화와 준희에게 건네 주었다.

그런데 돈을 받은 윤화와 준희는 좋아하기보다 고민에 빠지고 말았다. 원장선생님께 받은 이 돈을 어떻게 나누어 할지 고민에 빠진 것이다. 두 사람 모두 상대방이 자기보다 1원이라도 더 받는 것은 도저히 인정할 수 없어 한다. 따라서 돈을 똑같이 둘로 나누어 가져야 두 사람이 모두 만족할 수 있게 된다.

하지만 두 사람에게 돈을 똑같이 나누는 것이 불가능한 경우도 있다. 예를 들어 500원짜리 1개와 50원짜리 1개를 받았다면, 이 돈을 두 사람이 똑같이 나누어 가질 수는 없다. 물론 동전을 반으로 잘라서 나누어 가질 수도 있겠지만 그러면 돈으로서의 가치를 잃기 때문에 그렇게 할 수는 없다.

이제 우리가 할 일은 다음과 같다. 원장 선생님께서 N가지 종류의 동전을 각각 몇 개씩 주셨을 때, 그 돈을 반으로 나눌 수 있는지 없는지 판단하는 것이다.

입력

세 개의 입력이 주어진다. 각 입력의 첫째 줄에 동전의 종류 N(1≤N≤100)이 주어진다. 각 입력의 둘째 줄부터 N+1째 줄까지 각각의 동전의 금액과 개수가 빈 칸을 사이에 두고 주어진다. 단, 원장선생님께서 주신 금액의 총 합은 100,000원을 넘지 않는다.

출력

첫째 줄부터 세 줄에 걸쳐, 각 입력에 대하여 반으로 나누는 것이 가능하면 1, 불가능하면 0을 출력한다.

예제 입력 1

2

500 1

50 1

3

100 2

50 1

10 5

3

1 1

2 1

3 1

예제 출력 1

0

1

1

풀이 .

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

class Coin {
    int value, quantity;
    Coin(int value, int quantity) {
        this.value = value;
        this.quantity = quantity;
    }
}

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;

        int T = 3;
        while(T-- > 0) {
            int n = Integer.parseInt(br.readLine());
            Coin[] coins = new Coin[n+1];  // 원장님이 주는 금액의 최대는 10만원
            boolean[] dp = new boolean[100001];  // i원 만들기 가능?

            int total = 0;
            for(int i = 1; i <= n; i++) {
                st = new StringTokenizer(br.readLine());
                int value = Integer.parseInt(st.nextToken());
                int quantity = Integer.parseInt(st.nextToken());
                coins[i] = new Coin(value, quantity);
                total += value * quantity;  // 받은 총 금액 구함
                for(int j = 1; j <= quantity; j++) {
                    dp[value * j] = true;  // 각 종류의 동전으로 만들 수 있는 액수 먼저 체크
                }
            }

            // 굳이 dp[] 다 안 채워도 되는 경우
            if(total % 2 == 1) {
                System.out.println(0);
                continue;
            }else if(dp[total / 2]) {
                System.out.println(1);
                continue;
            }

            // 주어진 동전으로 (total / 2)원을 만들 수 있는지 확인하면 될 듯?
            dp[0] = true;
            for(int i = 1; i <= n; i++) {
                int v = coins[i].value;
                int q = coins[i].quantity;

                for(int j = total/2; j >= v; j--) {
                    if(dp[j - v]) {  // dp[j-v]가 가능해야 거기에 동전 하나씩 더해서 다음 액수를 가능하게 만들지

                        // (j-v)원부터 동전 v를 하나씩 사용하는 것
                        for(int k = 1; k <= q; k++) {
                            if(j - v + v * k > total/2) break;  // dp[total/2] 이상으로는 어차피 채울 필요 없음
                            dp[j - v + v * k] = true;
                        }
//                        // 이게 이말임
//                        for(int k = 0; k < quantity; k++) {
//                            dp[j + value * k] = true;
//                        }
                    }
                }
            }
            System.out.println(dp[total / 2] ? 1 : 0);
        }
    }
}

DP로 푸는 냅색 문제.

동전을 하나씩 사용하여 total/2 ~ v에 대한 검사를 한다.

1. 0원까지 안 하고 v까지만 검사하는 이유? 

해당 동전을 1개만 사용해도 v-1원보다는 크니까

2. v~total/2가 아니라 total/2~v로 내려오면서 검사하는 이유?

냅색 문제에서 흔히 발생하는 오류를 피하기 위함.

오름차순으로 검사를 하면 이전에 이미 사용한 동전에 의해 true가 된 것을 가지고 동전을 또 사용해서 다음값을 true로 만든다.

결국 1원짜리 하나만 있어도 모든 dp[]가 true가 되어버린다.

이것을 막기 위해 큰 금액부터 검사.

3. if(dp[j - v]) 하는 이유?

v의 값을 가지는 동전 q개를 사용하려는 상황.

dp[j-v] 까지는 완성이 되어있어야 동전 1~q개를 사용하면서 dp[j], dp[j+v], ... , dp[j + (q-1)v]을 만들 수 있다.

dp 테이블에 대한 정의도 어려웠고 채우는 것도 어려웠다.

그냥 다 어려웠다..

www.acmicpc.net/problem/12865

문제

이 문제는 아주 평범한 배낭에 관한 문제이다.

한 달 후면 국가의 부름을 받게 되는 준서는 여행을 가려고 한다. 세상과의 단절을 슬퍼하며 최대한 즐기기 위한 여행이기 때문에, 가지고 다닐 배낭 또한 최대한 가치 있게 싸려고 한다.

준서가 여행에 필요하다고 생각하는 N개의 물건이 있다. 각 물건은 무게 W와 가치 V를 가지는데, 해당 물건을 배낭에 넣어서 가면 준서가 V만큼 즐길 수 있다. 아직 행군을 해본 적이 없는 준서는 최대 K만큼의 무게만을 넣을 수 있는 배낭만 들고 다닐 수 있다. 준서가 최대한 즐거운 여행을 하기 위해 배낭에 넣을 수 있는 물건들의 가치의 최댓값을 알려주자.

입력

첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000)가 주어진다.

입력으로 주어지는 모든 수는 정수이다.

출력

한 줄에 배낭에 넣을 수 있는 물건들의 가치합의 최댓값을 출력한다.

예제 입력 1

4 7

6 13

4 8

3 6

5 12

예제 출력 1

14

풀이 .

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());

        int[] W = new int[n+1];
        int[] V = new int[n+1];
        int[][] dp = new int[n+1][k+1];  // dp[n][k] = 1~N개의 물건으로 무게제한 K 범위에서 가능한 최대 V
        for(int i = 1; i <= n; i++) {
            st = new StringTokenizer(br.readLine());
            int w = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            W[i] = w;
            V[i] = v;
        }

        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= k; j++) {
                if(W[i] > j) {  // 무게 제한 j로 W[i]이 감당이 안 되는 경우
                    dp[i][j] = dp[i-1][j];
                }else {  // W[i]를 포함해서 새로운 조합을 만들 수 있는 경우 (= j가 W[i] 감당 가능)
                    dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j-W[i]] + V[i]);
                }
            }
        }
        System.out.println(dp[n][k]);
    }
}

유명한 DP 유형 중 하나인 냅색(Knapsack) 문제라고 한다.

입력 값에 대하여 weight, value 두 개의 값이 주어지는 경우를 말한다. 냅색 안에서도 여러 가지 종류로 나눠지는데 이 경우는 0-1 Knapsack이다.

입력 값을 더 작은 단위로 나눌 수 없다는 뜻인데 내 수준에서는 그냥 0-1냅색 유형 하나만 있다고 알고 있어도 되지 않을까 싶다.

두 개의 입력 값을 어떻게 처리해야 할지, DP배열의 값을 어떻게 정의해야할지 모든 게 낯설고 어색했다.

대표적인 유형이라고 그냥 수업 듣는 느낌으로 조금만 생각해보고 바로 풀이를 확인했다.

dp[n][k] = 1~n의 물건을 가지고 무게 제한 k 안에서 채울 수 있는 최대 value 이다.

O(n * k) = 10,000,000 (천 만)으로 충분히 시간 안에 들어올 수 있다.

i 반복이 새로 돌 때마다의 의미는 이렇게 표현할 수 있다.

i-1번째 물건까지 살펴보았고 배낭의 용량이 j-w[i] 였을 때의 값에, 새롭게 i번째 물건을 넣는 상황

(j-w[i]인 상황에서 넣는 이유는? -> 그래야 i번째 물건을 넣어서 무게가 j가 될 거니까. 무게 j를 채우는 경우를 찾는 건 아니지만 j 범위 안에서 최대 밸류를 찾는 것도 이런식으로 처리할 수 있다)

아.. 너무 어렵다... ㅋㅋ