소스 보러가기
문제 보러가기

사용한 알고리즘 및 자료구조
DFS/BFS, 그래프

풀이

간단한 DFS/BFS 문제이다. 문제를 푸는데 20분도 안 걸렸다. 이번에는 DFS를 이용해서 해당 문제를 풀었다. 이 문제를 읽고 생각을 했던 것은 2차원 배열에서 (n,n) 칸들을 기준으로 좌우 대칭이 된다는 것이다. 또한 각각의 값들이 연결관계를 표현했다. 따라서 처음에 탐색할 때는 1/2만 탐색을 하고 DFS 를 사용할 때는 연결관계를 기준으로 탐색을 하면 된다. 보통의 DFS 문제는 ‘상하좌우’로 움직이면서 문제를 해결했지만, 해당 문제는 배열의 값들이 내포하고 있는 연결관계를 이용해서 DFS 함수를 구현했다.

  1. 초기화
  2. 문제에 해당하는 조건( 배열의 값 : 1 && 아직 탐색하지 않은 칸) 찾기 ,조건을 찾을 때 마다 answer++
  3. 조건 찾고 나서 DFS 함수를 이용해 연결관계를 따라 영역표시하기
  4. 다시 2-3번 반복
  5. Answer 출력

간단한 DFS 문제이다. 실제로 삼성 시험을 봤던 사람들에게는 매우 쉬웠을 거라 생각한다. 다만 이것을 어떻게 해야 더 효율적으로 구현할 수 있을까 고민해보았다. 간단한 문제라 특별하게 적용할 것은 없었으나, 그래도 고민 해보면 좋을 것이다.

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
    public static int SIZE;
 
    // before test, have to delete 'static' keywords
    public static int solution(int n, int[][] computers) {
        int answer = 0;
        boolean[][] visited = new boolean[n][n];
        SIZE = n;
 
        for (int c_idx = 0; c_idx < n; c_idx++)
            for (int r_idx = c_idx; r_idx < n; r_idx++) {
 
                if ((computers[c_idx][r_idx] == 1) && (visited[c_idx][r_idx] == false)) {
                    visited[c_idx][r_idx] = true;
                    dfs(r_idx, visited, computers);
                    answer++;
 
                }
            }
 
        return answer;
    }
 
    public static void dfs(int idx, boolean[][] visited, int[][] computers) {
 
        for (int col = 0; col < SIZE; col++) {
 
            if ((computers[idx][col] == 1) && (visited[idx][col] == false)) {
 
                visited[idx][col] = true;
 
                dfs(col, visited, computers);
 
            }
 
        }
 
    }
 
 
cs

'알고리즘(추가예정) > 동적계획법' 카테고리의 다른 글

[프로그래머스] 124 나라의 숫자  (0) 2020.08.30
[프로그래머스] 2n 타일링  (0) 2020.08.23
백준 2315 가로등 끄기  (0) 2017.11.16
백준 1563 개근상  (0) 2017.11.14
백준 1495 기타리스트  (0) 2017.11.13

소스 보러가기
문제 보러가기

사용한 알고리즘 및 자료구조

DP , 피보나치

풀이

문제에 대한 접근 방향이 중요하다. 여러 접근에 대한 후보를 떠올리고 최적의 후보를 택하여 접근해보았다. 인덱스 순서대로 접근하려고 했으나, 이내 방향을 바꿔 가장 맨 뒤를 가정하고 접근했다.

내가 N일 때, N-1, N-2에 올 수 있는 모양에 대해서 생각해보면 된다.

  • N-1 일 때 : 블록을 세울 수 밖에 없다.

  • N-2 일 때 : 세로 블록 2개 , 가로 블록 2개인 경우로 나뉠 수 있다. 하지만 세로 블록 2개인 경우에 N-1인 경우와 같다. 따라서 가로 블록 2개인 경우만 카운팅 된다.

즉, N-1, N-2가 어떠한 블록이 오느냐에 따라서 자동으로 N번째까지 블록이 채워진다.

그러므로 N-1 + N-2 개수를 합하여 더 하면 된다.

N = (N-1)+(N-2) => 피보나치

규칙을 보면 피보나치 수열이 근간이 되어 풀리는 문제다. 자세한건 코드를 보면서 파악하기 바란다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
 
    public static int solution(int n) {
        int answer = 0;
        int s = 1000000007;
 
        int[] dp = new int[n + 1];
 
        dp[0] = 0;
        dp[1] = 1;
        dp[2] = 2;
 
        for (int idx = 3; idx <= n; idx++) {
 
            dp[idx] = (dp[idx - 2] + dp[idx - 1]) % s;
 
        }
 
        answer = dp[n];
 
        return answer;
    }
 
 
cs

'알고리즘(추가예정) > 동적계획법' 카테고리의 다른 글

[프로그래머스] 124 나라의 숫자  (0) 2020.08.30
[프로그래머스] 네트워크  (0) 2020.08.23
백준 2315 가로등 끄기  (0) 2017.11.16
백준 1563 개근상  (0) 2017.11.14
백준 1495 기타리스트  (0) 2017.11.13

문제보기


실제로 이 문제를 푸는 방법은 여러가지가 있더라 , 

하지만 배열을 다루는 것에 있어 미숙한점을 알고 있기때문에

조건을 배열로 바꾸어 5차원 배열로 풀어보았다. 

 

풀이는 간단하지만 복잡하다. 

경우를 충분히 나누면 풀 수 있다. 

다만 그 경우가 다른 쉬운 다이나믹 문제보다 조건이 많아 처음에는

힘들었다. 


조건의 예를 들어보자 

점화식을 설명해보자면 

D[현재몇일][오늘의 출결][어제의 출결][그제의 출결][지각횟수]

이다. 

오늘 출결했다고 하면 뭘해도 상관없다.  이런식으로 조건을 나열하여 풀면된다. 

처음에는 상당히 시간이 걸렸다.

D[i][0][prev][prev2][0] += D[i-1][prev][prev2][prev3][0];

D[i][0][prev][prev2][1] += D[i-1][prev][prev2][prev3][1];


그리고 안되는 조건을 살펴보자면 

now , prev , prev2가 다 결석이면 안된다. 연속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
package Problems;
 
/**
 * 
 * 
 * 백준 1563 개근상
 * 
 * 동적계획
 *
 */
import java.util.Scanner;
 
public class boj1563dp {
    public static int mod = 1000000;
 
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[][][][][] D = new int[1001][3][3][3][2];
 
        for (int now = 0; now < 3; now++) {
            for (int prev = 0; prev < 3; prev++) {
                for (int prev2 = 0; prev2 < 3; prev2++) {
 
                    // 결석 연속3번은 안
                    if (now == 1 && prev == 1 && prev2 == 1) {
                        continue;
                    }
 
                    // 지각 2번은 안됨
                    if ((now == 2 && prev == 2) || (now == 2 && prev2 == 2) || (prev == 2 && prev2 == 2)) {
                        continue;
                    }
 
                    if (now == 2 || prev == 2 || prev2 == 2) {
                        D[3][now][prev][prev2][1] = 1;
                    } else {
 
                        D[3][now][prev][prev2][0] = 1;
 
                    }
 
                }
            }
        }
 
        for (int i = 4; i <= n; i++) {
            for (int prev = 0; prev < 3; prev++) {
                for (int prev2 = 0; prev2 < 3; prev2++) {
                    for (int prev3 = 0; prev3 < 3; prev3++) {
 
                        // 출석했을
                        D[i][0][prev][prev2][0] += D[i - 1][prev][prev2][prev3][0];
                        D[i][0][prev][prev2][0] %= mod;
                        D[i][0][prev][prev2][1] += D[i - 1][prev][prev2][prev3][1];
                        D[i][0][prev][prev2][1] %= mod;
 
                        // 결석
 
                        if (prev == 1 && prev2 == 1) {
 
                        } else {
 
                            D[i][1][prev][prev2][0] += D[i - 1][prev][prev2][prev3][0];
                            D[i][1][prev][prev2][0] %= mod;
                            D[i][1][prev][prev2][1] += D[i - 1][prev][prev2][prev3][1];
                            D[i][1][prev][prev2][1] %= mod;
 
                        }
 
                        D[i][2][prev][prev2][1] += D[i - 1][prev][prev2][prev3][0];
                        D[i][2][prev][prev2][1] %= mod;
 
                    }
                }
            }
        }
        
        int ans = 0;
        
        for(int i = 0; i < 3; i++) {
            for(int j = 0; j < 3; j++){
                for(int k = 0; k < 3; k++) {
                    for(int l = 0; l < 2; l++) {
                        ans += D[n][i][j][k][l];
                        ans%=mod;
                    }
                }
            }
        }
        
        System.out.println(ans);
 
    }
 
}
 
cs


'알고리즘(추가예정) > 동적계획법' 카테고리의 다른 글

[프로그래머스] 2n 타일링  (0) 2020.08.23
백준 2315 가로등 끄기  (0) 2017.11.16
백준 1495 기타리스트  (0) 2017.11.13
백준 11048 이동하기  (0) 2017.11.08
백준 1912 연속합  (0) 2017.11.07

일단 나의 하반기 계획과는 다른 방향으로 흘러갔다.

조금은 자소서를 준비했지만, 결국엔 많은 서탈을 경험하였고,

많은 시험을 봤지만, 많은 탈락을 맛봤다. 

어느순간 멘탈이 흔들렸다. 그런데 그게 지금까지도 계속 흔들리는 것 같다. 

결정적인 계기는 00회사의 시험이였다. 나는 그 시험에서 정확도 체크를 계산하여 6개중 5개 푸는 것을 목표로 했고

5개를 풀었다. 완벽했다. 장담한다. 


하지만..


탈락했다. 비록 서류 + 시험 + @로 평가하는 단계였지만, 

엄청난 멘붕이 왔다. 그날 소식듣고 독서실에서 확인하자마자

집에 갔다. 

실제로 코딩시험을 통과한 곳들도 있었다. 

하지만 코딩 시험이든 그 다음 시험이든, 나는 멘탈 유지하는 것을 실패했다. 

왜그러는지 모르겠다. 

시험전에는 계속 화장실을 가고, 손이 떨린다. 

공부를 더 많이 해서 그런가...?

시험을 보는 내내 멘탈유지가 쉽지 않더라, 어렸을때부터 시험 시간동안 세웠던 계획이 틀어지면 

뭔가 초조해지고 그랬다. 

예를들어 이번에 어떤 시험을 보면서 분명 아는문제고 풀줄아는데, 오류가나고 중간에 잠깐 막히더라, 

시간이 너무나 빠르게 흘러갔고, 그때부터 땀이 나더라.. 이게 너무 반복되었다. 

실제로 끝내고 다시 문제를 보면 쉬웠다. 왜 못풀었는지 모르겠다. 

이렇게 나의 하반기가 점점 마무리가 되어간다. 

아직 일정이 더 남았지만, 주말부터 뭔가 

가슴 한 구석이 '쿵'했다.


그래도..


날 믿기로 했다. 시간이 좀 더 걸리더라도..

'좋은 개발자'가 되기 위해서..

 

LinkedList.java

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
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
 
public class LinkedList {
    private Node head;
    private Node tail;
    private int size = 0;
 
    private class Node {
 
        private Object data;
        private Node next;
 
        // 변수타입을 가지고 있어야함
        public Node(Object input) {
            this.data = input;
            this.next = null;
 
        }
 
        public String toString() {
 
            return String.valueOf(this.data);
        }
    }
 
    // 머리에다가 추
    public void addFirst(Object input) {
        Node newNode = new Node(input);
        newNode.next = head;
        head = newNode;// 방금 생성한 노드를 head로
        size++;
 
        // 다음노드가 존재하지 않는다는
        if (head.next == null) {
            tail = head;
        }
 
    }
 
    public void addLast(Object input) {
        Node newNode = new Node(input);
        if (size == 0) {
            addFirst(input);
        } else {
            tail.next = newNode;
            tail = newNode;
            size++;
        }
 
    }
 
    // 내부적으로 사용할것 (test를 위해 public)
    Node node(int index) {
        // 첫번째 노드를 찾아오는 것이고 그게 헤드이다.
        Node x = head;
 
        // 다음 노드들을 가지고 오기 위해서 next를 인덱스만큼 반복
        for (int i = 0; i < index; i++) {
            x = x.next;
        }
        return x;
    }
 
    public void add(int k, Object input) {
        if (k == 0) {
            addFirst(input);
        } else {
            // 추가시키지 이전 노드를 알고있어야함
            Node temp1 = node(k - 1);
            // 밀어질 노드에 대한 정보
            Node temp2 = temp1.next;
            Node newNode = new Node(input);
            temp1.next = newNode;
            newNode.next = temp2;
            size++;
            // 뒤에 널이면 테일로 바준닷.
            if (newNode.next == null) {
                tail = newNode;
            }
        }
    }
 
    public String toString() {
        if (head == null) {
            return "[]";
        }
        Node temp = head;
        String str = "[";
 
        while (temp.next != null) {
            str += temp.data + ",";
            temp = temp.next;
        }
        str += temp.data;
 
        return str + "]";
 
    }
 
    // 자바에서는 컬렉션 프레임웍은 삭제된 노드의 값을 리턴해주게된다.
    public Object removeFirst() {
        Node temp = head;
        head = head.next;
        Object returnData = temp.data;
        temp = null;
        size--;
        return returnData;
    }
 
    // 노드 삭제하기
    public Object remove(int k) {
        if (k == 0) {
            return removeFirst();
        }
        Node temp = node(k - 1);
        Node todoDeleted = temp.next;
        temp.next = temp.next.next;
        Object returnData = todoDeleted.data;
        if (todoDeleted == tail) {
            tail = temp;
        }
        todoDeleted = null;
        size--;
        return returnData;
    }
 
    // 마지막 노드 삭제 테일만 지우면 이것저것 효과가 없어진닷;
    public Object removeLast() {
        return remove(size - 1);
    }
 
    // 사이즈 호출하기
    public int size() {
        return size;
    }
 
    // 특정한 위치의 데이터 가져오기
    public Object get(int k) {
        Node temp = node(k);
        return temp.data;
    }
 
    public int indexOf(Object data) {
        Node temp = head;
        int index = 0;
        while (temp.data != data) {
            temp = temp.next;
            index++;
            if (temp == null) {
                return -1;
            }
 
        }
        return index;
    }
 
    public ListIterator listIterator() {
        return new ListIterator();
    }
 
    public class ListIterator {
        private Node next;
        private Node lastReturned;
        // 몇번째 있는가 알필요가 있고, hasNext할때 필
        private int nextIndex;
 
        ListIterator() {
            next = head;
        }
 
        public Object next() {
            lastReturned = next;
            next = next.next;
            nextIndex++;
            return lastReturned.data;
 
        }
 
        public boolean hasNext() {
            return nextIndex < size();
        }
 
        public void add(Object input) {
            Node newNode = new Node(input);
 
            if (lastReturned == null) {
                head = newNode;
                newNode.next = next;
            } else {
 
                lastReturned.next = newNode;
                newNode.next = next;
            }
            
            lastReturned = newNode;
            nextIndex++;
            size++;
 
        }
        
        public void remove() {
            if(nextIndex == 0) {
                throw new IllegalStateException();
            }
            //비효율적이다. 노드를 찾았는데또 찾음!;
            LinkedList.this.remove(nextIndex-1);
            nextIndex--;
        }
    }
 
}
 
cs

Main.java


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
 
public class Main {
 
    public static void main(String[] args) {
        LinkedList numbers = new LinkedList();
//        numbers.addFirst(30);
//        numbers.addFirst(20);
//        numbers.addFirst(10);
//        
        numbers.addLast(10);
        numbers.addLast(20);
        numbers.addLast(30);
//        numbers.add(1, 15);
//        numbers.removeFirst();
        //특정한위치에
//        numbers.add(2,25);// 20은 뒤로밀린다.
//        System.out.println(numbers);
        
        //head삭
//        System.out.println(numbers.removeFirst());
//        System.out.println(numbers);
//        System.out.println(numbers.remove(0));
//        System.out.println(numbers.size());
//        System.out.println(numbers.get(2));
//        System.out.println(numbers.indexOf(30));
        LinkedList.ListIterator i = numbers.listIterator();
//        System.out.println(i.next());
//        System.out.println(i.hasNext());
        //        System.out.println(numbers.node(2));
 
        //hasNext호출을 위한 메소드 
//        while(i.hasNext()) {
//            System.out.println(i.next());
//    }
        
        //head에 노드 추가하
//        i.add(5);
//        i.next();
//        중간에 노드 추가하기 
//        i.add(15);
//        System.out.print(numbers);
    
        i.next();
        i.remove();
    
    }
        
 
}
 
cs

출처 : 생활코딩

'개발이야기 > Java' 카테고리의 다른 글

Java9 발표에 대한 요약  (0) 2017.11.06
GC(가비지 콜렉션)에 대한 공부  (0) 2017.11.03

문제 보기


* 몸이 안좋아서 , 짧게 하겠습니다.


4가지 풀이가 있습니다. 


solve1 은 현재칸을 기준으로 전 단계가 될 수 있는 칸들을 계산합니다.


solve2 는 현재칸을 기준으로 현재칸이 갈 수 있는 3가지의 경로를 계산합니다.


solve3는 solve1을 봤을때 대각선으로 바로 이동하는 수는 다른 방법으로 오는 수들 보다 작을 수 밖에 없습니다. 

이유는 모두 0보다 크기때문입니다. 그러기 때문에 수가 줄어들일이 없습니다. solve1 - 대각선 이라고 생각하시면 될 것 같습니다.


solve4는 재귀로 풀어봤습니다. 딱히 어려운건 없습니다.


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
package Problems;
 
/**
 * 
 * 
 * 백준 11048 이동하기 
 *  
 *
 */
import java.util.Scanner;
 
public class Boj11048dp {
 
    public static int n, m;
 
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        n = in.nextInt();
        m = in.nextInt();
 
        int[][] arr = new int[n + 1][m + 1];
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                arr[i][j] = in.nextInt();
            }
        }
        int[][] solve4 = new int[n + 1][m + 1];
        
        solve1(arr);
        solve2(arr);
        solve3(arr);
        int temp = solve4(arr,solve4,n,m);
        System.out.println(temp);
 
    }
 
    public static void solve1(int[][] arr) {
 
        int[][] dp = new int[n + 1][m + 1];
 
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                dp[i][j] = Math.max(dp[i - 1][j], Math.max(dp[i - 1][j - 1], dp[i][j - 1])) + arr[i][j];
                System.out.println("arr" + arr[i][j] + "    :   dp"  + dp[i][j]);
            }
        }
 
        System.out.println(dp[n][m]);
 
    }
 
    public static void solve2(int[][] arr) {
        int[][] dp = new int[n + 1][m + 1];
 
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
 
                if ( j + 1 <=m && dp[i][j + 1] < dp[i][j] + arr[i][j + 1]) {
                    dp[i][j + 1] = dp[i][j] + arr[i][j + 1];
                }
 
                if (i + 1 <= n && j + 1 <= m && dp[i + 1][j + 1] < dp[i][j] + arr[i + 1][j + 1]) {
                    dp[i+1][j + 1] = dp[i][j] + arr[i + 1][j + 1];
                }
 
                if (i + 1 <=n && dp[i + 1][j] < dp[i][j] + arr[i + 1][j]) {
                    dp[i+1][j] = dp[i][j] + arr[i + 1][j];
                }
            }
        }
 
        System.out.println(dp[n][m]);
    }
 
    public static void solve3(int[][] arr) {
 
        int[][] dp = new int[n + 1][m + 1];
 
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]) + arr[i][j];
            }
        }
 
        System.out.println(dp[n][m]);
 
    }
 
    public static int solve4(int[][] arr, int[][] dp, int x, int y) {
 
        if (x == 1 && y == 1) {
            return arr[1][1];
        }
        if (x < 1 || y < 1) {
            return 0;
        }
 
        if (dp[x][y] > 0) {
            return dp[x][y];
        }
 
        dp[x][y] = solve4(arr, dp, x - 1, y) + arr[x][y];
        int temp = solve4(arr, dp, x, y - 1) + arr[x][y];
 
        if (dp[x][y] < temp) {
 
            dp[x][y] = temp;
        }
 
        return dp[x][y];
 
    }
 
}
 
cs


'알고리즘(추가예정) > 동적계획법' 카테고리의 다른 글

백준 1563 개근상  (0) 2017.11.14
백준 1495 기타리스트  (0) 2017.11.13
백준 1912 연속합  (0) 2017.11.07
백준 11055 가장 큰 증가하는 부분수열  (0) 2017.11.07
백준 11053 가장 긴 증가하는 부분수열  (0) 2017.11.07

문제보기 


연속합을 구할때 유의할점은 

음수를 포함해도 답이 될때가 있다는 것이다. 

예를 들어 10 -1 11 일때, 음수를 포함하지 않으면 답이 나오질 않는다. 음수를 포함해서 10 + (-1) + 11 이 되어야만 가장 큰 연속합이된다.


D[i]는 A[i]로 끝나는 최대 연속합을 저장하는 배열이다. 


1. A[i-1]로 끝나는 연속합에 , A[i]가 포함된다. 

2. 1번의 경우보다 A[i]가 큰 경우이다. 


이 두개의 경우로 식을 세우면 된다.


D[i] = Math.max(A[i],D[i-1]+A[i])


시간복잡도는 O(N)이다. N번의 횟수와 계산식2개면 되니까! 


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
package Problems;
/**
 * 
 * 백준 1912 연속합 
 * 
 * 동적 계획
 * 
 */
import java.util.Scanner;
 
public class Boj1912dp {
    
    public static int n,arr[],dp[];
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        n = in.nextInt();
        arr = new int[n+1];
        dp = new int[n+1];
        
        for(int i = 1; i < n+1; i++) {
            arr[i] = in.nextInt();
        }
        
        for(int i = 1; i < n+1; i++) {
            
            dp[i] = Math.max(arr[i], dp[i-1]+arr[i]);
            
        }
        
        int ans = dp[1];
        
        for(int i = 1; i < n+1; i++) {
            
            if(ans < dp[i]) {
                ans = dp[i];
            }
        }
        
        System.out.println(ans);
        
    }
 
}
 
cs


'알고리즘(추가예정) > 동적계획법' 카테고리의 다른 글

백준 1495 기타리스트  (0) 2017.11.13
백준 11048 이동하기  (0) 2017.11.08
백준 11055 가장 큰 증가하는 부분수열  (0) 2017.11.07
백준 11053 가장 긴 증가하는 부분수열  (0) 2017.11.07
백준 2579 계단오르기  (0) 2017.11.07

문제보기


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


을 참고하면 된다.


달라진 것은 하나다. 


D[i] < D[j]+1

일때 +1 의 의미는 수열의 길이가 1증가 한다는 것이다. 

여기서 +1 -> A[i]로 바꿔준다면 값들을 더하면서 증가하는 수열이 될것이다. 


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
package Problems;
 
/**
 * 
 * 백준 11055 LIS
 * 
 * 
 */
 
import java.util.Scanner;
 
public class Boj11055dp {
    public static int n, arr[], d[];
 
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
 
        n = in.nextInt();
        
        arr = new int[n];
        d = new int[n];
 
        for (int i = 0; i < n; i++) {
            arr[i] = in.nextInt();
        }
 
        for (int i = 0; i < n; i++) {
            d[i] = arr[i];
 
            for (int j = 0; j < i; j++) {
                if (arr[j] < arr[i] && d[i] < d[j] +arr[i]) {
 
                    d[i] = d[j] + arr[i];
 
                }
            }
 
 
        }
        
        int max = d[0];
        
        for(int i = 0; i < n; i++) {
            if(max < d[i]) {
                max = d[i];
            }
        }
        
        System.out.println(max);
 
    }
 
}
 
cs


'알고리즘(추가예정) > 동적계획법' 카테고리의 다른 글

백준 11048 이동하기  (0) 2017.11.08
백준 1912 연속합  (0) 2017.11.07
백준 11053 가장 긴 증가하는 부분수열  (0) 2017.11.07
백준 2579 계단오르기  (0) 2017.11.07
백준 1463 1로 만들기  (0) 2017.11.03

문제보기


부분수열 문제이다. 


그리고 동적계획법이지만 이것은 LIS풀이가 적용되었다. 

'수열 A가 주어졌을때, 가장 긴 증가하는 부분수열을 구하라'  이다.

즉, 수열마다 이게 몇번째 수열인지 최대값으로 체크한다. 

수열이 존재할때 각각의 위치의 해석은 

A[i]를 마지막으로 하는 가장 긴 증가하는 부분수열의 길이이다.


조건은 이러하다


A[i]가 있을때, i 보다 작은 index들(ex. 0~j)의 값들을 A[i]와 비교한다. 그리고 A[i]가 A[j]가 '증가하는 수열'이므로 길이를 비교한다.

조건 : j<i , A[j] < A[i] 

또 하나의 조건이 더 있다. 만약 D[i]가 4인데, D[j]가 2이면 A[j]와 A[i]가 부분수열이여도 길이를 바꿔줄 필요가 없다. 

그래서 이러한 조건이 붙는다. 


D[i] < D[j]+1


끝이다. 코드를 보면 이해가 될 것이다. 


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
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
package Problems;
 
/**
 * 
 * 백준 11053 LIS
 * 
 * 
 */
 
import java.util.Scanner;
 
public class Boj11053dp {
    public static int n, arr[], d[], max = 0;
 
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
 
        n = in.nextInt();
 
        arr = new int[n];
        d = new int[n];
 
        for (int i = 0; i < n; i++) {
            arr[i] = in.nextInt();
        }
 
        for (int i = 0; i < n; i++) {
            d[i] = 1;
 
            for (int j = 0; j < i; j++) {
                if (arr[j] < arr[i] && d[i] < d[j] + 1) {
 
                    d[i] = d[j] + 1;
 
                }
            }
 
            if (max < d[i]) {
 
                max = d[i];
            }
 
        }
        
        System.out.println(max);
 
    }
 
}
 
cs
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39



 

'알고리즘(추가예정) > 동적계획법' 카테고리의 다른 글

백준 1912 연속합  (0) 2017.11.07
백준 11055 가장 큰 증가하는 부분수열  (0) 2017.11.07
백준 2579 계단오르기  (0) 2017.11.07
백준 1463 1로 만들기  (0) 2017.11.03
백준 11726,11727 2xN타일링 , 2xN타일링2  (0) 2017.11.03


문제보기


문제를 살펴보면 이러하다.


1. 한번에 1~2계단 갈 수 있다. 

2. 연속3개는 밟을 수 없다. 

3. 그리고 밟았을때, 포도주 문제와 달리 선택/미선택의 결정을 할 수 없다. 


경우를 나눠보자 


첫 번째, 1개 연속 밟았을 경우 

i 번째 일때 , i-1을 밟지 못한다. 그리고 i-2번째를 밟고 올라온다 

-- > D[i-2]+A[i]


두 번째, 2개 연속 밟았을 경우 

i번째 일때, i-1을 밟아야한다. 하지만 i-2번을 밟으면 규칙에 위배되므로 밟지 않는다. 

그리고 D[i-3]을 더한다.(여기는 뭘해도 상관없다. 규칙에 영향을 안받음)


점화식은 아래와 같다. 

 dp[i] = Math.max(dp[i-2]+arr[i], dp[i-3]+arr[i-1]+arr[i]);

2차원 배열의 경우 점화식 : D[i][1] = Math.max(D[i-2][2],D[i-2][1])+A[i]

D[i][2] = D[i-1][1] + A[i]

Math.max(D[N][1],D[N][2])

<전체코드>

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
package Problems;
/**
 * 
 * 백준 2579 계단오르기 
 * 
 * 동적계획법 
 * 
 * 
 */
import java.util.Scanner;
public class Boj2579dp {
    public static int n,arr[],dp[];
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        n = in.nextInt();
        arr = new int[n+1];
        dp = new int[n+1];
        
        for(int i = 1; i <=n; i++) {
            
            arr[i] = in.nextInt();
        }
        
        dp[1] = arr[1];
        dp[2] = arr[1] + arr[2];
        for(int i = 3; i <=n; i++) {
            
            dp[i] = Math.max(dp[i-2]+arr[i], dp[i-3]+arr[i-1]+arr[i]);
            
        }
        
        System.out.println(dp[n]);
    }
}
 
cs


'알고리즘(추가예정) > 동적계획법' 카테고리의 다른 글

백준 11055 가장 큰 증가하는 부분수열  (0) 2017.11.07
백준 11053 가장 긴 증가하는 부분수열  (0) 2017.11.07
백준 1463 1로 만들기  (0) 2017.11.03
백준 11726,11727 2xN타일링 , 2xN타일링2  (0) 2017.11.03
백준 1699 제곱수의 합  (0) 2017.11.02

+ Recent posts

티스토리툴바