반응형

14494번 다이나믹이 뭐예요?

https://www.acmicpc.net/problem/14494

 

14494번: 다이나믹이 뭐예요?

(1, 1)에서 (n, m)에 도달하는 경우의 수를 구하여라. 단, 경우의 수가 엄청 커질 수 있으므로 경우의 수를 1,000,000,007(=109+7)로 나눈 나머지를 출력한다.

www.acmicpc.net

Comment

DP문제의 기초격 문제

DP는 기초라고해도 왜이리 생각하기 어려운지 모르겠다..

hint

dp배열의 저장값 : 해당 지점에 도달하는 경우의 수

점화식 : 우측, 하단, 우하단 세가지 경우의 수를 활용

Solution

DP의 기초격 문제라 그런가 DP를 조금 맛본 상태에서 접했더니 점화식이 생각났던 얼마안되는 문제

먼저 dp배열을 만들고 해당 dp배열의 상단(우측으로만 진행하는 경우의 수) 하단(아래로만 진행하는 경우의 수)의 값은 도달하는 방법이 한가지 뿐이다. 때문에 먼저 초기화해서 쭉 1로 채워준 후에 해당 값을 가지고 남은 dp배열 모두를 채워나가면 되는데, 점화식은 위에 hint에 적었던 우측, 하단, 우하단 을 받는 이전dp배열을 가져오면 된다.

즉, dp[i][j] = dp[i - 1][j] + dp[i][j-1] + dp[i-1][j-1]; 로 해결이 된다

그림예시

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
import java.io.*;
import java.util.*;
 
/**
 * dp 다차원배열 도달할 수 있는 경우의 수
 */
public class Main {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
        int n, m;
 
        StringTokenizer st =new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
 
        int[][] dp = new int[1001][1001];
 
        for(int i = 1; i <= n; i++){
            dp[i][1] = 1;
        }
 
        for(int i = 1; i <= m; i++){
            dp[1][i] = 1;
        }
        //값 초기화 끝
 
        for(int i = 2; i <= n; i++){
            for(int j = 2; j <= m; j++){
                dp[i][j] = (((dp[i-1][j] + dp[i][j-1]) % 1000000007) + dp[i-1][j-1]) % 1000000007;
            }
        }
 
        System.out.println(dp[n][m]);
        
    }
}
cs

 

반응형
저작자표시 비영리 변경금지

'공부 > Algorithm' 카테고리의 다른 글

백준 2310번 어드벤처 게임 자바로 풀어 본 짧은 글  (0) 2023.11.28
백준 12755번 수면 장애 자바로 풀어 본 짧은 글  (0) 2023.11.21
백준 1680번 쓰레기 수거 자바로 풀어 본 짧은 글  (0) 2023.09.07
백준 1417번 국회의원 선거 자바로 풀어 본 짧은 글  (0) 2023.08.17
백준 골드5 달성!  (0) 2023.08.11
반응형

이번 프로젝트에서 리더보드를 구현하는 부분을 맡게 되었다.

리더보드에서는 해당 유저의 엔티티를 통해 하나의 값을 기준으로 내림차순으로 나열하는 방식이였는데, 때문에 JPA를 통해서 findAll로 받고 java에서 Arrays.sort형식으로 구현하려 했었는데 막상 구현하려고 하니 DB에서 데이터를 findAll로 받아서 Java로 구현한다면

"자바를 통해 다시한번 해당 데이터를 처리해야하기에 메모리에 손해가 있지 않을까?"

라는 의문을 시작으로 그렇다면 DB를 사용해서 정렬을 활용하면 더 빠를까?라는 생각을 통해 기본적으로 pk값인 id는 인덱스가 걸려있어서 속도걱정을 안해도 되겠지만 다른 특정한 값에 인덱스를 넣지 않고 orderByDesc를 해야하는 상황이였기에 이게 빠른지 저게 빠른지 모르는 상태였다.

현재는 프로젝트가 대규모 데이터를 갖고있지는 않기에 얼마나 성능적인 면에서 차이가 있을지는 모르겠어서 내가 할 수 있는 최대한의 방법인 검색을 통해 데이터를 수집해 보았고, 정리를 해 보았다.

  • 해당 데이터가 DB측에서 정리가 가능게 되어있는 가공된 데이터들 orderByDesc, Asc 등등 예외사항이 나올 수 없는 경우에 일반적으로 DB에서 처리하는 것이 빠르고 안정적
  • 위에서 언급했던 자바에서 해당 데이터를 한번 더 처리해야하기에 O(2n)의 시간복잡도를 가지게 될 것이라 생각한다.

 

GPT를 통한 답변도 비슷하게 나왔다.

JPA로 정렬하고 가져오는 것과 JPA의 findAll을 통해서 리스트를 가져온 다음 Java로 메서드를 작성해서 정렬하는것 어느게 더 빨라?
JPA
(Java Persistence API
)를 이용한 데이터베이스 쿼리와 Java의 메서드를 이용한 데이터 정렬은 각각 장단점이 있습니다
다음은 주요 차이점과 고려사항입니다

JPA로 정렬하고 가져오는 방법:
성능 : 데이터베이스에서 최적화된 정렬 알고리즘을 이용하기 때문에 대체로 빠릅니다
네트워크 부하 : 필요한 데이터만 가져올 수 있어서 네트워크 트래픽이 줄어듭니다
메모리 사용량 : 필요한 데이터만 메모리에 로드되므로 효율적입니다

Java로 메서드를 작성해서 정렬하는 방법
성능 : Java에서 처리하는 정렬은 데이터베이스의 최적화된 알고리즘보다 일반적으로 느립니다
네트워크 부하 : 모든 데이터를 가져와야 하므로 네트워크 트래픽이 증가할 수 있습니다
메모리 사용량 : 모든 데이터를 메모리에 로드해야 하므로 메모리 사용량이 늘어납니다

이러한 차이점을 고려하면 일반적으로는 JPA를 이용해서 데이터베이스에서 정렬하고 가져오는 것이 더 효율적입니다
그러나 상황에 따라 다를 수 있으므로
성능 테스트를 통해 가장 적합한 방법을 선택하는 것이 좋습니다

결론은 데이터를 추가로 가공할 것이 아니면 자바에서 findAll로 받아올 필요가 없을 것이라 정리가 되었다.

다음에 정렬할 일이 있다면 더 신중하고 정확하게 어느걸 고를지 판단할 수 있을듯 한 느낌😊

반응형
저작자표시 비영리 변경금지

'호기심 천국 > Spring' 카테고리의 다른 글

스프링 시큐리티 1 (인증)  (0) 2023.09.26
스프링부트 final로 클래스 생성자주입  (0) 2023.07.27
반응형

1680번 쓰레기 수거

https://www.acmicpc.net/problem/1680

 

1680번: 쓰레기 수거

쓰레기장에서 출발한 쓰레기차가 여러 지점들을 방문하며 쓰레기를 모으고 있다. 쓰레기차는 쓰레기장에서 가까운 지점부터 방문하며, 쓰레기를 모으다가 다음과 같은 경우에 쓰레기장으로 돌

www.acmicpc.net

Comment

일반 시뮬레이션 구현문제라서 평소처럼 풀까하다가 자바스럽게 풀어보고싶어서 객체지향(?)적으로 설계를 하기 위해 노력하면서 구현해보았다.

알고리즘을 풀 때 클래스를 잘 활용하지 않아서 생각보다 많이 오래걸렸던 문제

hint

문제를 잘 읽고 테스트케이스 또한 해당 지문에 맞춰서 잘 이해해야한다.

Solution

메모리나 시간이나 상관없이 구현만 잘하면 되는 문제였다. 때문에 클래스를 만들어서 써보기에 더 좋았던 것 같다.

일단 해당 문제의 1, 2, 3번 조건을 항상 잘 생각해서 염두에 두고 조건을 넣는다면 쉽게 풀리는 문제일 것이다.

1번의 시점은 다음 지점으로 이동하기 전이고, 2번의 시점은 쓰레기를 싣기 전, 3번은 가장 마지막. 이렇게 해당 분기를 잘 확인해서 조건처리만 잘 해준다면 문제 해결은 쉽게 될 것이다.

클래스 활용해서 구현하면 속도가 안나온다....

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
import java.io.*;
import java.util.*;
 
public class p1680 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
        int t = Integer.parseInt(br.readLine());
        int weight, point;
        StringTokenizer st;
        StringBuilder sb = new StringBuilder();
 
        while (t-- > 0) {
            st = new StringTokenizer(br.readLine());
            weight = Integer.parseInt(st.nextToken());
            point = Integer.parseInt(st.nextToken());
            p1680TrashCar garbageTruck = new p1680TrashCar(weight, 0);
 
            for (int i = 0; i < point; i++) {
                st = new StringTokenizer(br.readLine());
                int pointDistance = Integer.parseInt(st.nextToken());   //해당 위치의 거리값(원점기준)
                int pointWeight = Integer.parseInt(st.nextToken());     //해당 위치의 쓰레기양
 
                garbageTruck.movePoint(pointDistance); // 해당 포인트로 이동
 
                while (pointWeight > 0) {
 
                    if (!garbageTruck.possibleCollect(pointWeight)) { //용량을 넘게될때
                        garbageTruck.movePoint(0);
                        garbageTruck.movePoint(pointDistance);
                    }
 
                    if (garbageTruck.possibleCollect(pointWeight)) { // 용량이 넘지않으면 True반환
                        pointWeight = garbageTruck.collectTrash(pointWeight); // 쓰레기 수집 -> 해당 위치의 쓰레기는 0이됨
                    }
 
                    if (garbageTruck.isFull() && i != point - 1) { // 마지막 지점이 아닐 때 쓰레기가 꽉차면 수거장에 가서 비우고 와야함
                        garbageTruck.movePoint(0);
                        garbageTruck.movePoint(pointDistance);
                    }
                }
                if (i == point - 1) {
                    garbageTruck.movePoint(0);
                }
            }
            sb.append(garbageTruck.getMeter()).append("\n");
            System.out.println(garbageTruck.getPoints()); // 쓰레기를 담기위해 문제제출할 땐 주석처리해야함
        }
        System.out.println(sb);
    }
}
 
/**
 * 기본 차 인터페이스
 * recentDestination : 목적지에 이동할 때 이동한 거리를 매 순간 담음
 */
interface p1680Car {
 
    public int getMeter();
 
    public void movePoint(int distance);
 
    ArrayList<Integer> recentDestination = new ArrayList<>();
 
    default public void pointAdd(int n) {
        recentDestination.add(n);
    }
 
    default public ArrayList<Integer> getPoints() {
        return recentDestination;
    }
 
    default public void resetDestList() {
        recentDestination.clear();
    }
 
}
 
/**
 * TrashCar는 p15979Car의 상속을 받아 Meter와 movePoint를 반드시 사용해야한다.
 * 추가로 쓰레기를 담을 capacity, 쓰레기의 용량상태확인이 필요한 trashWeight이 필요
 */
class p1680TrashCar implements p1680Car {
    private int capacity;
    private int trashWeight;
    private int meter;
    private int nowLocation;
 
    public p1680TrashCar(int capacity, int nowLocation) {
        this.capacity = capacity;
        this.nowLocation = nowLocation;
        resetDestList();
    }
 
    @Override
    public int getMeter() {
        return meter;
    }
 
    @Override
    public void movePoint(int point) {
        if (point == 0) {
            pointAdd(nowLocation);
            meter += nowLocation;
            nowLocation = 0;
            trashWeight = 0;
            return;
        }
        pointAdd(point - nowLocation);
        meter += point - nowLocation;
        nowLocation += point - nowLocation;
 
    }
 
    public boolean possibleCollect(int weight) {
        if (capacity < trashWeight + weight) {
            return false;
        }
        return true;
    }
 
    public boolean isFull() { // 비었을 때는 꽉차는지 체크
        if (trashWeight >= capacity) {
            return true;
        }
        return false;
    }
 
    public int collectTrash(int weight) {
        trashWeight += weight;
        return 0;
    }
}
cs
반응형
저작자표시 비영리 변경금지

'공부 > Algorithm' 카테고리의 다른 글

백준 12755번 수면 장애 자바로 풀어 본 짧은 글  (0) 2023.11.21
백준 14494번 다이나믹이 뭐예요? 자바로 풀어 본 짧은 글  (0) 2023.09.15
백준 1417번 국회의원 선거 자바로 풀어 본 짧은 글  (0) 2023.08.17
백준 골드5 달성!  (0) 2023.08.11
백준 2644번 촌수 계산 자바(BFS,DFS)로 풀어 본 짧은 글  (0) 2023.08.03

+ Recent posts

티스토리툴바