Garbage Collection

java에서는 개발자가 코드로 메모리를 명시적으로 해제하지 않기 때문에 Garbage Collector가 더이상 필요없는 객체를 찾아 지우는 작업을 한다.

 

stop-the-world

GC를 실행하기 위해 JVM이 애플리케이션 실행을 멈추는것.

stop-the-world가 발생하면 GC를 실행하는 쓰레드를 제외한 나머지 쓰레드는 모두 작업을 멈춘다.

GC작업을 완료한 이후에야 중단했던 장업을 다시 시작한다.

어떤 GC알고리즘을 사용하더라도 stop-the-world는 발생한다.

대개의 경우 GC 튜닝이란 이 stop-the-world시간을 줄이는 것.

 

 

GC는 두가지 가정 하에 만들어졌다. : weak generational hypothesis

  • 대부분의 객체는 금방 접근 불가능 상태(unreachable)가 된다.
  • 오래된 객체에서 젊은 객체로의 참조는 아주 적게 존재한다.

 

이 가정의 장점을 최대한 살리기 위해 HotSpot VM에서는 크게 2개의 물리적 공간을 나누었다.(Young/Old)

  • Young Generation 영역

    새롭게 생성한 객체의 대부분이 여기에 위치한다.

    대부분의 객체가 금방 접근 불가능 상태가 되기 때문에 매우 많은 객체가 Young 영역에 생성되었다가 사라진다. 이 영역에서 객체가 사라질때 Minor GC가 발생한다고 말한다.

  • Old Generation 영역

    접근 불가능 상태로 되지 않아 Young영역에서 살아남은 객체가 여기로 복사된다. 대부분 Young 영역보다 크게 할당되며, 크기가 큰 만큼 Young 영역보다 GC는 적게 발생한다. 이 영역에서 객체가 사라질 때 Major GC(또는 Full GC)가 발생한다고 말한다.

     

 

  • Permanent Generation 영역(Method Area)

    객체나 억류(intern)된 문자열 정보를 저장하는 곳.

    Old영역에서 살아남은 객체가 영원히 남아있는 곳은 아니다. 이 영역에서 GC가 발생할 수도 있는데, 여기서 GC가 발생해도 Major GC 횟수에 포함된다.

 

Old 영역에 있는 개체가 Young 영역의 객체를 참조한다면?

Old 영역에는 512바이트의 덩어리(chunk)로 되어있는 card table이 존재한다.

card table에는 old 영역에 있는 객체가 young 영역의 객체를 참조할 때마다 정보가 표시된다. young영역의 GC를 실행할 때에는 old 영역에 있는 모든 객체의 참조를 확인하지 않고, 이 카드 테이블만 뒤져서 GC대상인지 식별한다.

카드 테이블은 write barrier를 사용하여 관리한다. write barrier은 Minor GC를 빠르게 할 수 있도록 하는 장치이다. wirte barrier 때문에 약간의 오버헤드는 발생하지만 전반적인 GC 시간은 줄어들게 된다.

 

 

Young Generation

  • Eden 영역
  • Survivor 영역 (2개)

 

  1. 새로 생성한 대부분의 객체는 Eden 영역에 위치한다.
  2. Eden 영역에서 GC가 한 번 발생한 후 살아남은 객체는 Survivor 영역 중 하나로 이동된다.
  3. Eden 영역에서 GC가 발생하면 이미 살아남은 객체가 존재하는 Survivor 영역으로 객체가 계속 쌓인다.
  4. 하나의 Survivor 영역이 가득 차게 되면 그 중에서 살아남은 객체를 다른 Survivor 영역으로 이동한다. 그리고 가득 찬 Survivor영역은 아무 데이터도 없는 상태로 된다.
  5. 이 과정을 반복하다가 계속해서 살아남아 있는 객체는 Old 영역으로 이동하게 된다.

 

 

HotSpot VM에서는 보다 빠른 메모리 할당을 위해 두가지 기술을 사용한다.

  • bump-the-point
  • TLABs(Thread-Local Allocation Buffers)

 

bump-the-point

Eden영역에 할당된 마지막 객체를 추적한다. 마지막 객체는 Eden 영역의 맨 위에 있다. 그리고 그 다음에 생성되는 객체가 있으면, 해당 객체의 크기가 Eden영역에 넣기 적당한지만 확인한다.

만약 해당 객체의 크기가 적당하다고 판정되면 Eden 영역에 넣게 되고, 새로 생성된 객체가 맨 위에 있게 된다. 따라서, 새로운 객체를 생성할 때 마지막에 추가된 객체만 점검하면 되므로 빠르게 메모리 할당이 이루어진다.

그러나, 멀티 스레드 환경에서 Thread-Safe하기 위해 만약 여러 스레드에서 사용하는 객체를 Eden영역에 저장하려면 lock이 발생할 수 밖에 없고, lock-contention때문에 성능은 매우 떨어질 것이다. 이를 해결한 것이 TLABs이다.

 

TLABs 각각의 스레드가 각각의 몫에 해당하는 Eden 영역의 작은 덩어리를 가질수 있도록 하는 것이다. 각 쓰레드에는 자기가 갖고 있는 TLAB에만 접근할 수 있기 때문에, bump-the-point라는 기술을 사용하더라도 아무런 락 없이 메모리 할당이 가능하다.

 

 

Old Generation

old 영역은 기본적으로 데이터가 가득 차면 GC를 실행한다.

(JDK 7기준)

  • Serial GC
  • Parallel GC
  • Parallel Old GC
  • Concurrent Mask & Sweep GC (CMS)
  • G1(Garbage First) GC

 

Serial GC (-XX:+UseSerialGC)

Old 영역에 살아있는 객체를 식별(Mask)한다. 그 다음에 heap의 앞 부분부터 확인하여 살아 있는 것만 남긴다(Sweep). 마지막 단계에서는 각 객체들이 연속되게 쌓이도록 힙의 가장 앞부분부터 채워서 객체가 존재하는 부분과 객체가 없는 부분으로 나눈다(Compaction).

Serail Gc는 적은 메모리와 CPU 코어 개수가 적을 때 적합한 방식이다.

Serial GC는 운영 서버에서 절대 사용하면 안되는 방식이다. 데스크톱의 CPU 코어가 하나만 있을 때 사용하기 위해 만든 방식으로, 애플리케이션의 성능이 많이 떨어질 수 있다.

 

Parallel GC (-XX:+UseParallelGC)

Serial GC와 기본적은 알고리즘은 같다. 그러나 Parallel GC는 GC를 처리하는 쓰레드가 여러 개이다. 그렇기 때문에 더 빠르게 객체를 처리할 수 있다. Parallel GC는 메모리가 충분하고 코어의 개수가 많을 때 유리하다.

 

Parallel Old GC (-XX:+UseParallelOldGC)

앞서 설명한 Parallel GC와 비교하여 Old 영역의 GC 알고리즘만 다르다. 이 방식은 Mark-Summary-Compaction 단계를 거친다. Summary 단계는 앞서 GC를 수행한 영역에 대해서 별도로 살아 있는 객체를 식별한다는 점에서 Mark-Sweep-Compaction 알고리즘의 Sweep 단계와 다르며, 약간 더 복잡한 단계를 거친다.

 

CMS GC (-XX:+UseConcMarkSweepGC)

초기의 Initial Mark 단계에서는 클래스 로더에서 가장 가까운 객체 중 살아 있는 개체만 찾는 것으로 끝낸다. 따라서, 멈추는 시간은 매우 짧다. 그리고 Concurrent Mark단계에서는 방금 살아있다고 확인한 객체에서 참조하고 있는 개체들을 따라가면서 확인한다. 이 단계의 특징은 다른 스레드가 실행 중인 상태에서 동시에 진행된다는 것이다.

그 다음 Remark 단계에서는 Concurrent Mark 단계에서 새로 추가되거나 참조가 끊긴 객체를 확인한다. 마지막으로 Concurrent Sweep 단계에서는 쓰레기를 정리하는 작업을 실행한다. 이 작업도 다른 스레드가 실행되고 있는 상황에서 진행한다.

이러한 단계로 진행되는 GC방식이기 때문에 stop-the-world 시간이 매우 짧다. 모든 애플리케이션의 응답 속도가 중요할 때, CMS GC를 사용하며, Low Latency GC라고도 부른다.

 

하지만, 단점도 존재한다.

  • 다른 GC방식보다 메모리와 CPU를 많이 사용
  • Compaction단계가 기본적으로 제공되지 않는다.

조각난 메모리가 많아 Compaction 작업을 실행하면 다른 GC 방식의 stop-the-world 시간보다 더 길기 때문에 Compaction 작업이 얼마나 자주,오랫동안 수행되는지 확인해야 한다.

 

 

G1(Garbage First) GC

G1 GC는 바둑판의 각 영역에 객체를 할당하고 GC를 실행한다. 그러다 해당 영역이 꽉 차면, 다른 영역에서 객체를 할당하고 GC를 실행한다. 즉, 지금까지 영역간 데이터가 이동하는 단계가 사라진 방식이다.

G1 GC의 가장 큰 장점은 성능이다. 지금까지 설명한 방식중 가장 빠르다.

JDK7부터 정식으로 G1 GC를 포함하여 제공하지만, 실 서비스에서 사용하려면 많은 검증기간이 필요할 것으로 보인다.

저작자표시 (새창열림)

'Computer Science > Languages' 카테고리의 다른 글

OOP 5대 원칙 : SOLID  (1) 2019.09.03
[javascript] Hoisting 호이스팅이란  (1) 2019.07.11
[java 예외처리]Try-with-resources  (2) 2019.07.11
java tip  (0) 2019.02.18
[java] 쓰레드(Thread)  (0) 2019.01.24

Try with resources

JDK1.7 에는 AutoCloseable 인터페이스가 추가됐다.

/**
 * @author Josh Bloch
 * @since 1.7
 */
public interface AutoCloseable {
    void close() throws Exception;
}

 

인터페이스 추가와 함께 try절에 ()가 들어갈 수 있게 됐다.

public static void main(String[] args) {
    try(FileInputStream fis = new FileInputStream("")){
         
    }catch(IOException e){

    }
}

이런식으로 try(){} 형태로 사용이 가능하며 ()안에 들어올 수 있는건 AutoCloseable 구현체 뿐이다.

이런 문법을 try with resources 라고 부른다.

 

장점은 다음과 같다.

  • try catch 절이 종료되면서 자동으로 close() 메서드를 호출해준다.
  • 코드의 길이를 현저히 줄이면서 가독성을 높인다.

 

try() 구문 안에서 자원을 생성하면, 알아서 close() 를 호출해준다.

저작자표시 (새창열림)

'Computer Science > Languages' 카테고리의 다른 글

OOP 5대 원칙 : SOLID  (1) 2019.09.03
[javascript] Hoisting 호이스팅이란  (1) 2019.07.11
java tip  (0) 2019.02.18
[java] 쓰레드(Thread)  (0) 2019.01.24
[java] 예외처리  (2) 2019.01.24

문제보기 >> [BOJ] 17144 : 미세먼지 안녕!



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
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;
 
//2019-06-20
//BOJ :: 17144 미세먼지안녕!
 
public class Main17144_미세먼지안녕 {
    private static int R, C, T;
    private static int[][] map, nmap;
    static int[] dy = { -1, 1, 0, 0 };
    static int[] dx = { 0, 0, -1, 1 };
 
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        R = Integer.parseInt(st.nextToken());
        C = Integer.parseInt(st.nextToken());
        T = Integer.parseInt(st.nextToken());
        map = new int[R][C];
        for (int i = 0; i < R; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            for (int j = 0; j < C; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        } //// input
 
        for (int t = 0; t < T; t++) {
            spreadDust();
        }
        
        int ans=0;
        for(int i=0;i<R;i++) {
            for(int j=0;j<C;j++) {
                if(map[i][j]>0) {
                    ans+=map[i][j];
                }
            }
        }
        
        System.out.println(ans);
 
    }
 
    public static void spreadDust() {
        ArrayList<pair> airCleanr = new ArrayList<>();
        nmap = new int[R][C];
        for (int i = 0; i < R; i++) {
            for (int j = 0; j < C; j++) {
                if (map[i][j] > 0) {// 먼지인 경우
                    int cnt = 0;
                    for (int d = 0; d < 4; d++) {
                        int ny = i + dy[d];
                        int nx = j + dx[d];
                        if (ny < 0 || ny > R - 1 || nx < 0 || nx > C - 1 || map[ny][nx] == -1)
                            continue;
 
                        nmap[ny][nx] += map[i][j] / 5;
                        cnt++;
                    }
                    nmap[i][j] += map[i][j] - (map[i][j] / 5) * cnt;
                } else if (map[i][j] == -1) {// 공기청정기 위치.
                    nmap[i][j] = -1;
                    airCleanr.add(new pair(i, j));
                }
            }
        }
 
        for (int i = 0; i < R; i++) {
            map[i] = Arrays.copyOf(nmap[i], C);
        }
 
        cleanAir(airCleanr.get(0), airCleanr.get(1));
 
    }
 
    public static void cleanAir(pair up, pair down) {
        // up : 반시계방향
        // down : 시계방향
 
        for (int i = 0; i < C - 1; i++) {
            if (nmap[up.y][i] == -1 || nmap[down.y][i] == -1) {
                map[up.y][i + 1] = 0;
                map[down.y][i + 1] = 0;
 
            } else {
                map[up.y][i + 1] = nmap[up.y][i];
                map[down.y][i + 1] = nmap[down.y][i];
            }
 
            map[0][i] = nmap[0][i + 1];
 
            map[R - 1][i] = nmap[R - 1][i + 1];
        }
 
        for (int j = 0; j < R - 1; j++) {
 
            if (j < up.y) {
                map[j + 1][0] = nmap[j][0]; // 위로
                map[j][C - 1] = nmap[j + 1][C - 1]; // 아래로
 
            } else if (j >= down.y) {
                map[j + 1][C - 1] = nmap[j][C - 1]; // 아래
                map[j][0] = nmap[j + 1][0]; // 위로
            }
        }
 
        map[up.y][up.x] = -1;
        map[down.y][down.x] = -1;
 
        //System.out.println();
    }
 
    static class pair {
        int y;
        int x;
 
        public pair(int y, int x) {
            this.y = y;
            this.x = x;
        }
 
    }
 
}
 
cs
저작자표시 (새창열림)

'Algorithm Problem Solving' 카테고리의 다른 글

[BOJ] 2146 : 다리 만들기  (1) 2019.06.05
[BOJ] 17281 :: ⚾ 야구  (2) 2019.06.05
[BOJ] 16236 : 아기상어  (0) 2019.06.05
[BOJ] 16235 : 나무재테크  (1) 2019.04.13
[BOJ] 15685. 드래곤 커브  (5) 2019.04.09


문제보기 >> [BOJ] 2146 : 다리 만들기


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
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class Main_2146_다리만들기 {
    static int N;
    static int[] dy = { -1, 1, 0, 0 };
    static int[] dx = { 0, 0, -1, 1 };
    static int[][] map;
    static int[][] boundary;
    private static boolean[][] visit;
 
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        map = new int[N][N];
        boundary = new int[N][N];
        visit = new boolean[N][N];
        for (int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
            for (int j = 0; j < N; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        } ////// input
 
        int chk = 1;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (visit[i][j] || map[i][j] == 0)
                    continue;
                bfs(i, j, chk);
                chk++;
            }
        }
        int min = Integer.MAX_VALUE;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (boundary[i][j] <1)
                    continue;
                int b = bridge(i, j, boundary[i][j]);
                min = min > b? b:min;
            }
        }
 
        System.out.println(min);
    }// end of main
 
    static void bfs(int y, int x, int chk) {
        Queue<pair> que = new LinkedList<>();
        que.add(new pair(y, x));
        visit[y][x] = true;
        boundary[y][x] = -1;
        while (!que.isEmpty()) {
            pair p = que.poll();
            int py = p.y;
            int px = p.x;
 
            for (int i = 0; i < 4; i++) {
                int ny = py + dy[i];
                int nx = px + dx[i];
                if (ny < 0 || ny > N - 1 || nx < 0 || nx > N - 1 || visit[ny][nx])
                    continue;
                if (map[ny][nx] == 1) {
                    que.add(new pair(ny, nx));
                    visit[ny][nx] = true;
                    boundary[ny][nx] = -1;
                }
                if (map[ny][nx] == 0) {
                    boundary[py][px] = chk;
                }
            }
        }
    }
 
    static int bridge(int y, int x, int me) {
        int[][] visit2 = new int[N][N];
        Queue<pair> que = new LinkedList<>();
        que.add(new pair(y, x));
        visit2[y][x] = 1;
        int len = 0;
        while (!que.isEmpty()) {
 
            len++;
            int qSize = que.size();
            for (int q = 0; q < qSize; q++) {
                pair p = que.poll();
                int py = p.y;
                int px = p.x;
 
                for (int i = 0; i < 4; i++) {
                    int ny = py + dy[i];
                    int nx = px + dx[i];
                    if (ny < 0 || ny > N - 1 || nx < 0 || nx > N - 1 || visit2[ny][nx] != 0 || boundary[ny][nx] == -1 || boundary[ny][nx]==me)
                        continue;
                    if (boundary[ny][nx] != 0 && boundary[ny][nx] != -1 && boundary[ny][nx] != me) {
                        //System.out.println("("+ny+","+nx+")");
                        return len-1;
                    }
 
                    if (boundary[ny][nx] ==0) {
                        que.add(new pair(ny, nx));
                        visit2[ny][nx] = len;
                    }
                }
            }
        }
        return len;
    }
 
    static class pair {
        int y;
        int x;
 
        public pair(int y, int x) {
            super();
            this.y = y;
            this.x = x;
        }
    }
}
 
cs


저작자표시 (새창열림)

'Algorithm Problem Solving' 카테고리의 다른 글

[BOJ] 17144 : 미세먼지 안녕!  (1) 2019.06.20
[BOJ] 17281 :: ⚾ 야구  (2) 2019.06.05
[BOJ] 16236 : 아기상어  (0) 2019.06.05
[BOJ] 16235 : 나무재테크  (1) 2019.04.13
[BOJ] 15685. 드래곤 커브  (5) 2019.04.09
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
package basic;
 
import java.util.ArrayList;
import java.util.Arrays;
 
public class NumberOfCases {
    static char[] arr = { 'a', 'b', 'c', 'd' };
    static int r = 2;
 
    public static void main(String[] args) {
 
        set = new char[r];
        // System.out.println("==조합==");
        // nCr(0,0);
        //comb(r,arr.length);
        // System.out.println("==중복조합==");
        // nHr(0,0);
        //System.out.println("==중복순열==");
        //nPir(0);
        setList = new ArrayList<>();
        //subset(0,0);
        
        visit = new boolean[arr.length];
        nPr(0);
    }
 
    static char[] set;
 
    public static void nCr(int len, int k) { // 조합
        if (len == r) {
            System.out.println(Arrays.toString(set));
            return;
        }
 
        for (int i = k; i < arr.length; i++) {
            set[len] = arr[i];
            nCr(len + 1, i + 1);
        }
    }
 
    public static void comb(int depth, int idx) {
        if (depth==0) {
            System.out.println(Arrays.toString(set));
        } else if (idx < depth) {
            return;
        } else {
            //System.out.println(depth + " " + idx );
            set[depth-1] = arr[idx-1];
 
            comb(depth - 1, idx - 1);
            comb(depth, idx-1);
        }
 
    }
 
    public static void nHr(int len, int k) { // 중복조합
        if (len == r) {
            System.out.println(Arrays.toString(set));
            return;
        }
 
        for (int i = k; i < arr.length; i++) {
            set[len] = arr[i];
            nHr(len + 1, i);
        }
    }
    static boolean[] visit;
    public static void nPr(int len) {// 순열
        if(len==r) {
            System.out.println(Arrays.toString(set));
            return;
        }
        
        for(int i=0;i<arr.length;i++) {
            if(!visit[i]) {
                set[len]=arr[i];
                visit[i]=true;
                nPr(len+1);
                visit[i]=false;
            }
        }
    }
 
    public static void nPir(int len) {// 중복순열
        if(len==r) {
            System.out.println(Arrays.toString(set));
            return;
        }
        
        for(int i=0;i<arr.length;i++) {
            set[len]=arr[i];
            nPir(len+1);
        }
    }
 
    static ArrayList<Character> setList;
    public static void subset(int len, int k) {// 부분집합
        System.out.println(setList);
        if(len==arr.length) {
            return;
        }
        for(int i=k;i<arr.length;i++) {
            setList.add(arr[i]);
            subset(len+1,i+1);
            setList.remove(setList.size()-1);
        }
    }
}
 
cs
저작자표시 (새창열림)

'Computer Science > Algorithms' 카테고리의 다른 글

[java] Dijkstra 다익스트라 알고리즘  (0) 2019.02.19
Kruskal 크루스칼 알고리즘  (0) 2019.02.18
DisjointSets  (0) 2019.02.18
[java] Insertion Sort 삽입정렬  (0) 2019.01.28
Permutation 순열  (0) 2019.01.17



문제보기 >> [BOJ] 17281 :: ⚾ 야구


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
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
 
//BOJ:: 17281 야구 
public class Main17281_야구 {
    static int N;
    static int[][] rst;
 
    public static void main(String[] args) throws Exception {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(bf.readLine()); // 이닝
        rst = new int[N][10];
        for (int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(bf.readLine());
            for (int j = 1; j < 10; j++) {
                rst[i][j] = Integer.parseInt(st.nextToken());
            }
        } //////// input
 
        visit = new boolean[10];
        player = new int[10];
        player[4] = 1;
        max = -1;
        perm(1);
        System.out.println(max);
    }// end of main
 
    static boolean[] visit;
    static int[] player;
    static int max;
    public static void perm(int len) { // 선수 배치하기
        if (len == 4) { // 4번째 타자는 1번.
            perm(len + 1);
            return;
        }
        if (len == 10) {
            // 선택완료
            int score = playGame();
            max = max<score? score:max;
            return;
        }
 
        for (int i = 2; i < 10; i++) {
            if (visit[i])
                continue;
            player[len] = i;
            visit[i] = true;
            perm(len + 1);
            visit[i] = false;
        }
    }
 
    public static int playGame() {
        int score = 0;
        int out;
        boolean[] roo = new boolean[4];
        int hitter = 1;
        
        for (int inning = 0; inning < N; inning++) {
            out = 0;
            Arrays.fill(roo, false);
            while(true) {
                int now = rst[inning][player[hitter]];
                if(hitter==9) hitter = 1;
                else hitter++;
                if (now == 1) { // 안타
                    if(roo[3]) {
                        score++;
                        roo[3]=false;
                    }
                    for(int r=2;r>=1;r--) {
                        if(roo[r]) {
                            roo[r]=false;
                            roo[r+1]=true;
                        }
                    }
                    roo[1]=true;
                } else if (now == 2) { // 2루타
                    if(roo[3]) {
                        score++;
                        roo[3]=false;
                    }
                    if(roo[2]) {
                        score++;
                        roo[2]=false;
                    }
                    if(roo[1]) {
                        roo[1]=false;
                        roo[3]=true;
                    }
                    roo[2]=true;
 
                } else if (now == 3) { // 3루타
                    for(int r=1;r<=3;r++) {
                        if(roo[r]) {
                            score++;
                            roo[r]=false;
                        }
                    }
                    roo[3] = true;
                } else if (now == 4) { // 홈런
                    for(int r=1;r<=3;r++) {
                        if(roo[r]) {
                            score++;
                            roo[r]=false;
                        }
                    }
                    score++; //타자도 홈으로.
                } else if (now == 0) { // 아웃
                    out++;
                    if (out == 3) {
                        break;
                    }
                }
            }
        }// end of for
        return score;
    } //end of playGame
}// end of class
 
 cs

 

Comment

정말 귀찮은 문제다~

 

순열로 타자를 뽑아준다. 여기서 1번 타자가 4번째 순서는 고정인 것에 주의해야 한다!

타자를 뽑은 후에는 주어진 조건대로 게임을 진행하고, 최대 점수를 갱신한다.

저작자표시 (새창열림)

'Algorithm Problem Solving' 카테고리의 다른 글

[BOJ] 17144 : 미세먼지 안녕!  (1) 2019.06.20
[BOJ] 2146 : 다리 만들기  (1) 2019.06.05
[BOJ] 16236 : 아기상어  (0) 2019.06.05
[BOJ] 16235 : 나무재테크  (1) 2019.04.13
[BOJ] 15685. 드래곤 커브  (5) 2019.04.09

 

 

문제보기>> [BOJ] 16236 : 아기상어

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
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
//2019-06-01
//BOJ 16236 아기상어
 
/*
 * 아기상어의 초기 크기 : 2
 * 자신보다 큰 물고기가 있는 칸은 지날 수 없다. 나머지 칸은 지날 수 있다.
 * 자신의 크기보다 작은 물고기만 먹을 수 있다. 
 * ==> 크기가 같은 물고기는 먹을수는 없지만, 지나갈 수는 있다.
 * 
 * 더 이상 먹을 수 있는 물고기가 공간에 없으면. 엄마 상어에게 도움을 요청한다.
 * 먹을수 있는 물고기가 1마리면 먹으러 간다.
 * 1마리보다 많으면,가장 가까운 물고기를 먹으러 간다 .
 *  지나야하는 칸의 개수의 최솟값.
 *  가까운 물고기가 많으면 : 가장위 -> 가장 왼쪽 
 *  이동과 동시에 물고기를 먹는다. 
 *  물고기를 먹으면, 그 칸은 빈칸이된다.
 *  
 *  자신의 크기와 같은 수의 물고기를 먹으면 크기가 1 증가.
 *  크기가 2인 아기 상어는 물고기를 2마리 먹으면 이됨.
 *  
 */
public class Main_16236_아기상어 {
    static int N, ans;
    static int[][] map;
    static int[] dy = { -1, 1, 0, 0 };
    static int[] dx = { 0, 0, -1, 1 };
 
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        map = new int[N][N];
        int sy = -1, sx = -1;
        for (int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int j = 0; j < N; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
                if (map[i][j] == 9) {
                    sy = i;
                    sx = j; // 아기상어 위치 
                }
            }
        } // input
        bfs(sy, sx);
        System.out.println(ans);
    }// end of main
    
    
    public static void bfs(int sy, int sx) {
        int sharksize = 2; //초기크기 
        int sharkeat = 0;
        Queue<pair> q = new LinkedList<>();
        ArrayList<pair> fish = new ArrayList<>();
        boolean[][] visit = new boolean[N][N];
        q.add(new pair(sy, sx)); // 아기상어의 초기위치
        visit[sy][sx]=true;
 
        int time = 0;
        while (!q.isEmpty()) {
            
            int qSize = q.size();
            int y=-1, x=-1;
            for (int s = 0; s < qSize; s++) { //1초 단위로 순회 
                
                pair p = q.poll();
                y = p.y;
                x = p.x;
                for (int i = 0; i < 4; i++) {
                    int ny = y + dy[i];
                    int nx = x + dx[i];
 
                    if (ny < 0 || ny > N - 1 || nx < 0 || nx > N - 1 || visit[ny][nx] || map[ny][nx]>sharksize)
                        continue;
                    
                    q.add(new pair(ny, nx)); //방문할 수 있는 모든 곳 (빈 곳, 상어 이하 크기의 물고기 )
                    visit[ny][nx] = true;
                    if(map[ny][nx]!=0 && map[ny][nx]<sharksize) { //그 중, 먹을 수 있는 물고기 
                        fish.add(new pair(ny,nx));
                    }
                }
            } // 1초
            time++;
            
            if(fish.size()!=0) { //먹을 물고기가 있다.
                Collections.sort(fish); //조건에 맞는 물고기 찾기. 
                pair meal = fish.get(0);
                fish.clear(); 
                sharkeat++;
                if(sharksize==sharkeat) {
                    sharksize++;
                    sharkeat=0;
                }
                
                map[sy][sx]=0; //이전 상어 위치 초기화 
                sy=meal.y;
                sx=meal.x; //상어 위치 변경 
                map[sy][sx] = 9; //이동후 상어의 위치 
                
                q.clear(); 
                q.add(meal); //이동 후 상어의 위치부터 다시 bfs 순회. 
                ans+=time; //****** 시간을 더해준다. ******
                time = 0; //시간 초기화 
                for(int i=0;i<N;i++) { //visit initialize
                    Arrays.fill(visit[i], false);
                }
                visit[meal.y][meal.x]=true;
            }
            
        } // end of while
    }// end of bfs
 
 
    static class pair implements Comparable<pair> {
        int y;
        int x;
 
        public pair(int y, int x) {
            super();
            this.y = y;
            this.x = x;
        }
 
        @Override
        public int compareTo(pair o) {
            if (this.y == o.y) {
                return this.x - o.x;
            } else {
                return this.y - o.y;
            }
        }
    }
}// end of class
 
 cs

 

< Comment >

5번만에 해결한 아기상어..

이 문제에서 주의해야할 부분은 "더 이상 먹을 수 있는 물고기가 공간에 없으면. 엄마 상어에게 도움을 요청한다." 이다.

 

더이상 먹을 수 있는 물고기가 있는지 없는지 어떻게 알 수 있을까?



나는 ans 와 time을 분리함으로서 해결했다.

상어를 직접 이동시켰을 때, 갈 수 있는곳을 모두 순회해보고 그제서야 먹을 수 있는 물고기가 없다는걸 깨닫는다면 답을 얻을 수 없다.

따라서 나는 물고기를 탐색할때 time을 증가시켜주고,

먹을 물고기를 찾아 먹을 때 ans+=time; time=0; 작업을 해줬다 !

저작자표시 (새창열림)

'Algorithm Problem Solving' 카테고리의 다른 글

[BOJ] 2146 : 다리 만들기  (1) 2019.06.05
[BOJ] 17281 :: ⚾ 야구  (2) 2019.06.05
[BOJ] 16235 : 나무재테크  (1) 2019.04.13
[BOJ] 15685. 드래곤 커브  (5) 2019.04.09
[BOJ] 1938 통나무 옮기기  (0) 2019.04.05

문제보기 >> [BOJ] 16235 : 나무재테크



Comment

문제 그대로 구현했다.

우선순위큐를 사용할때 팝하는 과정에서 내 의지와 다르게 팝될 수 있으므로 주의 ..**

우선순위큐 사이즈만큼 팝하고, 다시 애드 할때에는 새로운 큐에 담은 후 옮겨줘야한다

 

 

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
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
 
//BOJ :: 16235 나무재테크
//2019-04-13
 
public class Main16235_나무재테크 {
    private static int[][] A;
    private static int N,K;
    private static PriorityQueue<pair> trees;
    private static int[][] Y;
    private static int[] dy = {-1,-1,-1,0,0,1,1,1};
    private static int[] dx = {-1,0,1,-1,1,-1,0,1};
 
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
        A = new int[N + 1][N + 1];
        Y = new int[N + 1][N + 1];
 
        trees = new PriorityQueue<>();
        for (int i = 1; i <= N; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            for (int j = 1; j <= N; j++) {
                A[i][j] = Integer.parseInt(st.nextToken());
                Arrays.fill(Y[i], 5); // 양분 초기값
            }
        }
 
        for (int i = 0; i < M; i++) {// 나무정보
            st = new StringTokenizer(br.readLine(), " ");
            int y = Integer.parseInt(st.nextToken());
            int x = Integer.parseInt(st.nextToken());
            int z = Integer.parseInt(st.nextToken()); // 나무 나이
            trees.add(new pair(y, x, z));
        }
        //////// input
 
        treeInvestment();
        
        System.out.println(trees.size());
    }
 
    public static void treeInvestment() {
        ArrayList<pair> die = new ArrayList<>();
        ArrayList<pair> breed = new ArrayList<>();
        for (int year = 0; year < K; year++) {
            // 봄
            int tsize = trees.size();
            PriorityQueue<pair> newpq = new PriorityQueue<>();
            for (int i = 0; i < tsize; i++) {
            
                pair p = trees.poll();
                int py = p.y;
                int px = p.x;
 
                if (Y[py][px] < p.age) {// 양분이 내 나이보다 적으면 죽는다.
                    die.add(new pair(py,px,p.age));
                    continue;
                }
                
                Y[py][px] -= p.age; // 나이만큼 양분 먹기
                newpq.add(new pair(py, px, p.age+1));
                
                if((p.age+1)%5==0) {//나이가 5의 배수면 
                    breed.add(new pair(py,px,p.age+1));
                }
            }
            trees = new PriorityQueue<>(newpq);
 
            // 여름
            for(pair p : die) {
                int py = p.y;
                int px = p.x;
                
                Y[py][px] += p.age/2;
            }
            die.clear();
        
            //가을
            for(pair p : breed) {
                int py = p.y;
                int px=p.x;
                for(int i=0;i<8;i++) {
                    int ny = py+dy[i];
                    int nx = px+dx[i];
                    
                    if(ny<1 || ny>N || nx<1 || nx>N) continue;
                    
                    trees.add(new pair(ny,nx,1));
                }
            }
            breed.clear();
            
            //겨울 
            for(int i=1;i<=N;i++) {
                for(int j=1;j<=N;j++) {
                    Y[i][j] += A[i][j];
                }
            }
        
        }//year term 
    
        return;
 
    }
 
    static class pair implements Comparable<pair> {
        int y;
        int x;
        int age;
        public pair(int y, int x, int age) {
            super();
            this.y = y;
            this.x = x;
            this.age = age;
        }
        @Override
        public int compareTo(pair o) {
            return this.age - o.age;
        }
    }
}
 
 cs
저작자표시 (새창열림)

'Algorithm Problem Solving' 카테고리의 다른 글

[BOJ] 17281 :: ⚾ 야구  (2) 2019.06.05
[BOJ] 16236 : 아기상어  (0) 2019.06.05
[BOJ] 15685. 드래곤 커브  (5) 2019.04.09
[BOJ] 1938 통나무 옮기기  (0) 2019.04.05
[SWEA] 2383. 점심식사 시간  (5) 2019.04.04

+ Recent posts

티스토리툴바