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

+ Recent posts

티스토리툴바