반응형

* 정답

 1. Thread

 11. 그림 참고 

 2. Daemon

 12. Controller, View, Model

 3. Memory leak(메모리 누수)

 13. O(2^n)

 4. Linker

 14. O(n^2)

 5. DNS

 15. O(1), O(n)

 6. UDP

 16. 1번 ( len(A)=N, len(B)=M일 때,  (N+M)logN < (N+M)logM )

 7. AJAX

 17. Stack

 8. Struck(구조체)

 18. Hash, Tree 

(참고 : https://en.wikipedia.org/wiki/Database_index#Index_implementations)

 9. Inheritance(상속)

 19. Queue

 10. Transaction(트렌잭션)

20. C,D,B,I,F

11.   

20.


* 문제 출처

http://tech.kakao.com/files//kakao-blind-recruitment.pdf

http://tech.kakao.com/2017/11/14/kakao-blind-recruitment-round-3/

반응형
반응형

* 핵심 개념

삽질을 상당히 많이한 문제다.

문제를 해석하면 한 방향으로 기울이면 끝까지 이동해야하고 두 구슬이 같은 위치인 경우도 처리가 필요하다.

4%에서 계속 틀렸다고 나왔는데 이유를 알고보니 개념의 실수였다.

구슬의 방문여부를 4차원 배열로 해결해야 하는데, 2차원배열 2개로 해결하려다 보니 당연히 틀릴수밖에 없었다.

이 둘의 차이는 명백하니 실수하지 말아야겠다.


문제 해결 순서는 

빨간 구슬을 한 방향 끝까지 이동 >> 파란 구슬을 한 방향 끝까지 이동 >> 둘이 같은 점이면 많이 움직인 구슬을 한칸 되돌림 >> 새로운 점 큐에 추가


* 문제

문제

스타트링크에서 판매하는 어린이용 장난감 중에서 가장 인기가 많은 제품은 구슬 탈출이다. 구슬 탈출은 직사각형 보드에 빨간 구슬과 파란 구슬을 하나씩 넣은 다음, 빨간 구슬을 구멍을 통해 빼내는 게임이다.

보드의 세로 크기는 N, 가로 크기는 M이고, 편의상 1×1크기의 칸으로 나누어져 있다. 가장 바깥 행과 열은 모두 막혀져 있고, 보드에는 구멍이 하나 있다. 빨간 구슬과 파란 구슬의 크기는 보드에서 1×1크기의 칸을 가득 채우는 사이즈이고, 각각 하나씩 들어가 있다. 게임의 목표는 빨간 구슬을 구멍을 통해서 빼내는 것이다. 이때, 파란 구슬이 구멍에 들어가면 안된다.

이때, 구슬을 손으로 건드릴 수는 없고, 중력을 이용해서 이리 저리 굴려야 한다. 왼쪽으로 기울이기, 오른쪽으로 기울이기, 위쪽으로 기울이기, 아래쪽으로 기울이기와 같은 네 가지 동작이 가능하다.

각각의 동작에서 공은 동시에 움직인다. 빨간 구슬이 구멍에 빠지면 성공이지만, 파란 구슬이 구멍에 빠지면 실패이다. 빨간 구슬과 파란 구슬이 동시에 구멍에 빠져도 실패이다. 빨간 구슬과 파란 구슬은 동시에 같은 칸에 있을 수 없다. 또, 빨간 구슬과 파란 구슬의 크기는 한 칸을 모두 차지한다. 기울이는 동작을 그만하는 것은 더 이상 구슬이 움직이지 않을 때 까지이다.

보드의 상태가 주어졌을 때, 최소 몇 번 만에 빨간 구슬을 구멍을 통해 빼낼 수 있는지 구하는 프로그램을 작성하시오.

입력

첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B' 로 이루어져 있다. '.'은 빈 칸을 의미하고, '#'은 공이 이동할 수 없는 장애물 또는 벽을 의미하며, 'O'는 구멍의 위치를 의미한다. 'R'은 빨간 구슬의 위치, 'B'는 파란 구슬의 위치이다.

입력되는 모든 보드의 가장자리에는 모두 '#'이 있다. 구멍의 개수는 한 개 이며, 빨간 구슬과 파란 구슬은 항상 1개가 주어진다.

출력

최소 몇 번 만에 빨간 구슬을 구멍을 통해 빼낼 수 있는지 출력한다. 만약, 10번 이하로 움직여서 빨간 구슬을 구멍을 통해 빼낼 수 없으면 -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
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
import java.io.*;
import java.util.*;
 
public class Main {
    public static StringTokenizer stk;
    public static StringBuilder sb = new StringBuilder();
    public static int[] dx = {1-100};
    public static int[] dy = {001-1};
    public static int n, m;
    public static int rx, ry, bx, by;
    public static int[][] map;
    public static boolean[][][][] visited;
    public static Queue<Pair> q = new LinkedList<>();
 
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        stk = new StringTokenizer(br.readLine());
        n = Integer.parseInt(stk.nextToken());
        m = Integer.parseInt(stk.nextToken());
        map = new int[n + 1][m + 1];
        visited = new boolean[n + 1][m + 1][n + 1][m + 1];
        for (int i = 1; i <= n; i++) {
            String s = br.readLine();
            for (int j = 1; j <= s.length(); j++) {
                int tmp = 0;
                switch (s.charAt(j - 1)) {
                    case '#':
                        tmp = -1;
                        break;
                    case '.':
                        tmp = 0;
                        break;
                    case 'R':
                        tmp = 1;
                        rx = i;
                        ry = j;
                        break;
                    case 'B':
                        tmp = 2;
                        bx = i;
                        by = j;
                        break;
                    case 'O':
                        tmp = 3;
                        break;
                }
                map[i][j] = tmp;
            }
        }
        System.out.println(bfs());
    }
 
    public static int bfs() {
        q.add(new Pair(rx, ry, bx, by, 0));
        visited[rx][ry][bx][by] = true;
        while (!q.isEmpty()) {
            Pair p = q.poll();
            if (p.cnt > 10continue;
            if (map[p.bx][p.by] == 3continue;
            if (map[p.rx][p.ry] == 3return p.cnt;
 
            for (int i = 0; i < 4; i++) {
                //빨간 구슬 상하좌우 끝까지 이동
                int next_rx = p.rx, next_ry = p.ry;
                while (true) {
                    //다음 지점이 벽이랑 구멍이 아니면
                    if (map[next_rx][next_ry] != -1 && map[next_rx][next_ry] != 3) {
                        next_rx += dx[i];
                        next_ry += dy[i];
                    } else {
                        //다음 지점이 벽이면
                        if (map[next_rx][next_ry] == -1) {
                            next_rx -= dx[i];
                            next_ry -= dy[i];
                        }
                        break;
                    }
                }
 
                //파란 구슬 상하좌우 끝까지 이동
                int next_bx = p.bx, next_by = p.by;
                while (true) {
                    //다음 지점이 벽이랑 구멍이 아니면
                    if (map[next_bx][next_by] != -1 && map[next_bx][next_by] != 3) {
                        next_bx += dx[i];
                        next_by += dy[i];
                    } else {
                        //다음 지점이 벽이면
                        if (map[next_bx][next_by] == -1) {
                            next_bx -= dx[i];
                            next_by -= dy[i];
                        }
                        break;
                    }
                }
 
                //구한 Red, Blue 의 점이 서로 같은데 'O'가 아닌 경우
                //더 움직인 구슬의 dx[i], dy[i]를 빼준다
                if (next_rx == next_bx && next_ry == next_by) {
                    if (map[next_rx][next_ry] != 3) {
                        int red_cost = Math.abs(next_rx - p.rx) + Math.abs(next_ry - p.ry);
                        int blue_cost = Math.abs(next_bx - p.bx) + Math.abs(next_by - p.by);
                        if (red_cost > blue_cost) {
                            next_rx -= dx[i];
                            next_ry -= dy[i];
                        } else {
                            next_bx -= dx[i];
                            next_by -= dy[i];
                        }
                    }
                }
 
                //next 점이 방문한적 없다면 큐에 추가
                if (!visited[next_rx][next_ry][next_bx][next_by]) {
                    visited[next_rx][next_ry][next_bx][next_by] = true;
                    q.add(new Pair(next_rx, next_ry, next_bx, next_by, p.cnt + 1));
                }
            }
        }
        return -1;
    }
 
    public static class Pair {
        int rx, ry, bx, by, cnt;
 
        public Pair(int rx, int ry, int bx, int by, int cnt) {
            this.rx = rx;
            this.ry = ry;
            this.bx = bx;
            this.by = by;
            this.cnt = cnt;
        }
    }
}
cs


반응형
반응형

* 핵심 개념

고려해야 할 사항은 크게 두가지다.

1. 물고기가 같은 거리에 있는 경우 위에 있고, 왼쪽에 있는 물고기를 먹는다. 

다른 방법도 존재하지만 우선순위 큐를 사용하여 처리하였다. (148ms)

먹이를 찾았을 때 큐에 남은 점들을 다시 확인해서 비교한다. (80ms)

2. 물고기를 먹고 나서 상어 크기가 증가하는 지 확인해야 한다.

하나 주의해야 할 점은 상어의 위치를 받고 map을 0으로 변경해주는 작업도 필요하다.


요약하면, 

상어 위치 확인  >> 물고기 탐색(BFS) >> 찾은 물고기 우선순위 큐에 저장 >> 우선순위 큐의 맨 앞 물고기 선택 >> 상어 위치 변경 및 상어 크기 증가여부 확인

상어 위치 확인 >> 물고기 탐색(BFS) >> 물고기 찾으면 남아있는 큐 탐색 >> 최적의 물고기 위치 확인 >> 상어 위치 변경 및 상어 크기 증가 여부 확인

위 순서대로 진행하며 BFS가 끝낫는데 큐의 크기가 0이라면 먹을 수 있는 물고기가 없다는 뜻이므로 움직인 거리를 출력하면 된다.

* 문제

문제

N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다.

아기 상어와 물고기는 모두 크기를 가지고 있고, 이 크기는 자연수이다. 가장 처음에 아기 상어의 크기는 2이고, 아기 상어는 1초에 상하좌우로 인접한 한 칸씩 이동한다.

아기 상어는 자신의 크기보다 큰 물고기가 있는 칸은 지나갈 수 없고, 나머지 칸은 모두 지나갈 수 있다. 아기 상어는 자신의 크기보다 작은 물고기만 먹을 수 있다. 따라서, 크기가 같은 물고기는 먹을 수 없지만, 그 물고기가 있는 칸은 지나갈 수 있다.

아기 상어가 어디로 이동할지 결정하는 방법은 아래와 같다.

  • 더 이상 먹을 수 있는 물고기가 공간에 없다면 아기 상어는 엄마 상어에게 도움을 요청한다.
  • 먹을 수 있는 물고기가 1마리라면, 그 물고기를 먹으러 간다.
  • 먹을 수 있는 물고기가 1마리보다 많다면, 거리가 가장 가까운 물고기를 먹으러 간다.
    • 거리는 아기 상어가 있는 칸에서 물고기가 있는 칸으로 이동할 때, 지나야하는 칸의 개수의 최소값이다.
    • 거리가 가까운 물고기가 많다면, 가장 위에 있는 물고기, 그러한 물고기가 여러마리라면, 가장 왼쪽에 있는 물고기를 먹는다.

아기 상어의 이동은 1초 걸리고, 물고기를 먹는데 걸리는 시간은 없다고 가정한다. 즉, 아기 상어가 먹을 수 있는 물고기가 있는 칸으로 이동했다면, 이동과 동시에 물고기를 먹는다. 물고기를 먹으면, 그 칸은 빈 칸이 된다.

아기 상어는 자신의 크기와 같은 수의 물고기를 먹을 때 마다 크기가 1 증가한다. 예를 들어, 크기가 2인 아기 상어는 물고기를 2마리 먹으면 크기가 3이 된다.

공간의 상태가 주어졌을 때, 아기 상어가 몇 초 동안 엄마 상어에게 도움을 요청하지 않고 물고기를 잡아먹을 수 있는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 공간의 크기 N(2 ≤ N ≤ 20)이 주어진다.

둘째 줄부터 N개의 줄에 공간의 상태가 주어진다. 공간의 상태는 0, 1, 2, 3, 4, 5, 6, 9로 이루어져 있고, 아래와 같은 의미를 가진다.

  • 0: 빈 칸
  • 1, 2, 3, 4, 5, 6: 칸에 있는 물고기의 크기
  • 9: 아기 상어의 위치

아기 상어는 공간에 한 마리 있다.

출력

첫째 줄에 아기 상어가 엄마 상어에게 도움을 요청하지 않고 물고기를 잡아먹을 수 있는 시간을 출력한다.

* 소스 코드

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
import java.io.*;
import java.util.*;
 
public class Main {
    public static StringTokenizer stk;
    public static StringBuilder sb = new StringBuilder();
    public static int[] dx = {-1001};
    public static int[] dy = {0-110};
    public static int n, eating = 0;
 
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        int[][] map = new int[n][n];
        Queue<Shark> q = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            stk = new StringTokenizer(br.readLine());
            for (int j = 0; j < n; j++) {
                map[i][j] = Integer.parseInt(stk.nextToken());
                if (map[i][j] == 9) {
                    q.add(new Shark(i, j, 20));
                    map[i][j] = 0;
                }
            }
        }
 
        int ans = 0;
        boolean[][] visited = new boolean[n][n];
        while (!q.isEmpty()) {
            Shark shark = q.poll();
            if (!visited[shark.x][shark.y]) {
                visited[shark.x][shark.y] = true;
                if (map[shark.x][shark.y] != 0 && map[shark.x][shark.y] < shark.power) {  //상어가 먹이를 찾으면
                    Shark curr = shark;
                    //거리 > 높이 > 왼쪽 순서로 먹기 위해 남은 Queue 탐색
                    while (!q.isEmpty()) {
                        shark = q.poll();
                        if (map[shark.x][shark.y] != 0 && map[shark.x][shark.y] < shark.power) {
                            if (curr.cost == shark.cost) {
                                if (curr.x > shark.x) {
                                    curr = shark;
                                } else if (curr.x == shark.x && curr.y > shark.y) {
                                    curr = shark;
                                }
                            } else if (curr.cost > shark.cost) {
                                curr = shark;
                            }
                        }
                    }
                    map[curr.x][curr.y] = 0;
                    eating++;
                    ans += curr.cost;
                    int flag = 0;
                    if (eating == curr.power) {        //상어가 성장할 수 있으면
                        flag = 1;
                        eating = 0;
                    }
                    q.clear();
                    q.add(new Shark(curr.x, curr.y, curr.power + flag, 0));
                    visited = new boolean[n][n];
                    continue;
                }
                for (int i = 0; i < 4; i++) {
                    int nx = shark.x + dx[i];
                    int ny = shark.y + dy[i];
                    if (nx >= 0 && nx < n && ny >= 0 && ny < n && map[nx][ny] <= shark.power && !visited[nx][ny]) {
                        q.add(new Shark(nx, ny, shark.power, shark.cost + 1));
                    }
                }
            }
        }
        System.out.println(ans);
    }
 
    public static class Shark {
        int x, y, power, cost;
 
        public Shark(int x, int y, int power, int cost) {
            this.x = x;
            this.y = y;
            this.power = power;
            this.cost = cost;
        }
    }
}
cs


반응형
반응형

* 핵심

우선순위 큐를 사용해서 끝나는 순서가 빠른 순서대로 정렬


* 문제

문제

한 개의 회의실이 있는데 이를 사용하고자 하는 N개의 회의들에 대하여 회의실 사용표를 만들려고 한다. 각 회의 I에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 최대수의 회의를 찾아라. 단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 회의의 시작시간과 끝나는 시간이 같을 수도 있다. 이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다.

입력

첫째 줄에 회의의 수 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N+1 줄까지 각 회의의 정보가 주어지는데 이것은 공백을 사이에 두고 회의의 시작시간과 끝나는 시간이 주어진다. 시작 시간과 끝나는 시간은 231-1보다 작거나 같은 자연수 또는 0이다.

출력

첫째 줄에 최대 사용할 수 있는 회의 수를 출력하여라.


* 소스 코드

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
import java.io.*;
import java.util.*;
 
public class Main {
    public static StringTokenizer stk;
    public static StringBuilder sb = new StringBuilder();
 
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        PriorityQueue<Info> pq = new PriorityQueue<>();
        for (int i = 0; i < n; i++) {
            stk = new StringTokenizer(br.readLine());
            pq.add(new Info(Integer.parseInt(stk.nextToken()), Integer.parseInt(stk.nextToken())));
        }
        int end = 0;
        int cnt = 0;
        for (int i = 0; i < n; i++) {
            Info o = pq.poll();
            if (o.start >= end) {   //이전 끝난 시간보다 새로 시작하는 회의 시간이 크거나 같으면
                end = o.end;
                cnt++;
            }
        }
        System.out.println(cnt);
    }
 
    public static class Info implements Comparable<Info> {
        int start, end;
 
        public Info(int start, int end) {
            this.start = start;
            this.end = end;
        }
 
        @Override
        public int compareTo(Info o) {
            if (end == o.end) return start - o.start;   //같은 시간에 끝나면 Start 오름 차순
            return end - o.end;     //끝나는 순서 오름차순 정렬
        }
    }
}
cs


반응형
반응형

* 핵심

어제 올린 백준/16985 :: Maaaaaaaaaze 와 비슷하지만 조금 쉬운 문제이다.

이 문제 또한 3단계로 나누어서 해결할 수 있다.

1. 입력받은 map에서 0인 좌표중에서 3개를 선택하는 함수 nCr >> 벽 3곳 선정

2. BFS를 통해서 바이러스 퍼트리기

3. 안전지역 비교 함수


* 문제 

문제

인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다.

연구소는 크기가 N×M인 직사각형으로 나타낼 수 있으며, 직사각형은 1×1 크기의 정사각형으로 나누어져 있다. 연구소는 빈 칸, 벽으로 이루어져 있으며, 벽은 칸 하나를 가득 차지한다. 

일부 칸은 바이러스가 존재하며, 이 바이러스는 상하좌우로 인접한 빈 칸으로 모두 퍼져나갈 수 있다. 새로 세울 수 있는 벽의 개수는 3개이며, 꼭 3개를 세워야 한다.

예를 들어, 아래와 같이 연구소가 생긴 경우를 살펴보자.

2 0 0 0 1 1 0
0 0 1 0 1 2 0
0 1 1 0 1 0 0
0 1 0 0 0 0 0
0 0 0 0 0 1 1
0 1 0 0 0 0 0
0 1 0 0 0 0 0

이때, 0은 빈 칸, 1은 벽, 2는 바이러스가 있는 곳이다. 아무런 벽을 세우지 않는다면, 바이러스는 모든 빈 칸으로 퍼져나갈 수 있다.

2행 1열, 1행 2열, 4행 6열에 벽을 세운다면 지도의 모양은 아래와 같아지게 된다.

2 1 0 0 1 1 0
1 0 1 0 1 2 0
0 1 1 0 1 0 0
0 1 0 0 0 1 0
0 0 0 0 0 1 1
0 1 0 0 0 0 0
0 1 0 0 0 0 0

바이러스가 퍼진 뒤의 모습은 아래와 같아진다.

2 1 0 0 1 1 2
1 0 1 0 1 2 2
0 1 1 0 1 2 2
0 1 0 0 0 1 2
0 0 0 0 0 1 1
0 1 0 0 0 0 0
0 1 0 0 0 0 0

벽을 3개 세운 뒤, 바이러스가 퍼질 수 없는 곳을 안전 영역이라고 한다. 위의 지도에서 안전 영역의 크기는 27이다.

연구소의 지도가 주어졌을 때 얻을 수 있는 안전 영역 크기의 최댓값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. (3 ≤ N, M ≤ 8)

둘째 줄부터 N개의 줄에 지도의 모양이 주어진다. 0은 빈 칸, 1은 벽, 2는 바이러스가 있는 위치이다. 2의 개수는 2보다 크거나 같고, 10보다 작거나 같은 자연수이다.

빈 칸의 개수는 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
import java.io.*;
import java.util.*;
 
public class Main {
    public static StringTokenizer stk;
    public static StringBuilder sb = new StringBuilder();
    public static int[][] map;
    public static ArrayList<Point> virusPos = new ArrayList<>();    //바이러스의 좌표를 저장하는 ArrayList
    public static int[] dx = {1-100};
    public static int[] dy = {001-1};
    public static int n, m;
    public static int ans = 0;
 
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        stk = new StringTokenizer(br.readLine());
        n = Integer.parseInt(stk.nextToken());
        m = Integer.parseInt(stk.nextToken());
        map = new int[n][m];
        for (int i = 0; i < n; i++) {
            stk = new StringTokenizer(br.readLine());
            for (int j = 0; j < m; j++) {
                map[i][j] = Integer.parseInt(stk.nextToken());
                if (map[i][j] == 2) virusPos.add(new Point(i, j));
            }
        }
 
        nCr(0new boolean[n][m]);
        System.out.println(ans);
    }
 
    //0의 개수들 중에서 3개의 점에 벽을 세우는 경우의 수
    public static void nCr(int cnt, boolean[][] visited) {
        if (cnt == 3) {
            int[][] nmap = new int[n][m];
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) {
                    if (!visited[i][j]) nmap[i][j] = map[i][j];
                    else nmap[i][j] = 1;
                }
            }
            bfs(nmap);
            return;
        }
        for (int x = 0; x < n; x++) {
            for (int y = 0; y < m; y++) {
                if (map[x][y] == 0 && !visited[x][y]) {
                    visited[x][y] = true;
                    nCr(cnt + 1, visited);
                    visited[x][y] = false;
                }
            }
        }
        return;
    }
 
    //bfs를 이용해서 바이러스가 주위로 퍼져나감
    public static void bfs(int[][] nmap) {
        Queue<Point> q = new LinkedList<>();
        boolean[][] visited = new boolean[n][m];
        for (int i = 0; i < virusPos.size(); i++) {
            q.add(virusPos.get(i));     //바이러스의 좌표들을 큐에 저장
        }
        while (!q.isEmpty()) {
            Point p = q.poll();
            if (!visited[p.x][p.y] && nmap[p.x][p.y] != 1) {
                visited[p.x][p.y] = true;
                nmap[p.x][p.y] = 2;
                for (int i = 0; i < 4; i++) {
                    int nx = p.x + dx[i];
                    int ny = p.y + dy[i];
                    if (check(nx, ny) && !visited[nx][ny] && nmap[nx][ny] != 1) {
                        q.add(new Point(nx, ny));
                    }
                }
            }
        }
        ans = Math.max(ans, getSafeCnt(nmap));
    }
 
    //안전지역 숫자를 세는 함수
    public static int getSafeCnt(int[][] nmap) {
        int cnt = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (nmap[i][j] == 0) cnt++;
            }
        }
        return cnt;
    }
 
    public static boolean check(int x, int y) {
        if (x >= 0 && x < n && y >= 0 && y < m) return true;
        return false;
    }
 
    public static class Point {
        int x, y;
 
        public Point(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
}
cs


반응형
반응형

* 핵심

문제를 하루종일 삽질하면서 풀었다.

첫번째 실수는 문제를 이해를 잘못해서 각 미로를 nCr로 조합한다는 경우를 생각하지 못했고, 

두번째 실수는 visited를 매번 초기화하지 않아서 한바퀴밖에 돌지않는 경우가 발생했다.


문제를 뜯어보면 3가지 역할로 분리할 수 있다.

1. nCr 함수 : 판을 쌓는 순서를 참가자가 자유롭게 정할 수 있으므로 5!의 경우의 수가 발생

2. Rotation(DFS) 함수 : 판을 돌리는 경우의 수는 총 4가지이므로 4^5(판의 개수) 의 경우의 수 발생 >> DFS로 경우의 수 찾기

3. BFS 함수 : Rotaion으로 받은 map을 가지고 0,0,0에서 4,4,4로 가는 경우의 수를 찾는 함수

문제를 위처럼 3단계로 나누고 실수없이 구현하면 금방 풀 수 있는 문제였다.

특히, 자바는 파라미터가 Call by Reference이기 때문에 DFS 함수를 호출하고 다시 값을 변경해주는 것 또한 잊지말아야 한다.


* 문제

문제

평화롭게 문제를 경작하며 생활하는 BOJ 마을 사람들은 더 이상 2차원 미로에 흥미를 느끼지 않는다. 2차원 미로는 너무나 쉽게 탈출이 가능하기 때문이다. 미로를 이 세상 그 누구보다 사랑하는 준현이는 이런 상황을 매우 안타깝게 여겨 아주 큰 상금을 걸고 BOJ 마을 사람들의 관심을 확 끌 수 있는 3차원 미로 탈출 대회를 개최하기로 했다.

대회의 규칙은 아래와 같다.

  • 5×5 크기의 판이 5개 주어진다. 이중 일부 칸은 참가자가 들어갈 수 있고 일부 칸은 참가자가 들어갈 수 없다. 그림에서 하얀 칸은 참가자가 들어갈 수 있는 칸을, 검은 칸은 참가자가 들어갈 수 없는 칸을 의미한다.

  • 참가자는 주어진 판들을 시계 방향, 혹은 반시계 방향으로 자유롭게 회전할 수 있다. 그러나 판을 뒤집을 수는 없다.

  • 회전을 완료한 후 참가자는 판 5개를 쌓는다. 판을 쌓는 순서는 참가자가 자유롭게 정할 수 있다. 이렇게 판 5개를 쌓아 만들어진 5×5×5 크기의 큐브가 바로 참가자를 위한 미로이다. 이 때 큐브의 입구는 정육면체에서 참가자가 임의로 선택한 꼭짓점에 위치한 칸이고 출구는 입구와 면을 공유하지 않는 꼭짓점에 위치한 칸이다.

  • 참가자는 현재 위치한 칸에서 면으로 인접한 칸이 참가자가 들어갈 수 있는 칸인 경우 그 칸으로 이동할 수 있다.
  • 참가자 중에서 본인이 설계한 미로를 가장 적은 이동 횟수로 탈출한 사람이 우승한다. 만약 미로의 입구 혹은 출구가 막혀있거나, 입구에서 출구에 도달할 수 있는 방법이 존재하지 않을 경우에는 탈출이 불가능한 것으로 간주한다.

이 대회에서 우승하기 위해서는 미로를 잘 빠져나올 수 있기 위한 담력 증진과 체력 훈련, 그리고 적절한 운이 제일 중요하지만, 가장 적은 이동 횟수로 출구에 도달할 수 있게끔 미로를 만드는 능력 또한 없어서는 안된다. 주어진 판에서 가장 적은 이동 횟수로 출구에 도달할 수 있게끔 미로를 만들었을 때 몇 번 이동을 해야하는지 구해보자. 

입력

첫째 줄부터 25줄에 걸쳐 판이 주어진다. 각 판은 5줄에 걸쳐 주어지며 각 줄에는 5개의 숫자가 빈칸을 사이에 두고 주어진다. 0은 참가자가 들어갈 수 없는 칸, 1은 참가자가 들어갈 수 있는 칸을 의미한다.

출력

첫째 줄에 주어진 판으로 설계된 미로를 탈출하는 가장 적은 이동 횟수를 출력한다. 단, 어떻게 설계하더라도 탈출이 불가능할 경우에는 -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
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
import java.io.*;
import java.util.*;
 
public class Main {
    public static StringTokenizer stk;
    public static StringBuilder sb = new StringBuilder();
    public static int[][][] map = new int[5][5][5];
    public static boolean[][][] visited = new boolean[5][5][5];
    public static int[] p = {00000};        //nCr로 순서를 정할 때 idx를 저장하는 배열
    public static int[] dx = {1-10000};
    public static int[] dy = {001-100};
    public static int[] dh = {00001-1};
    public static int ans = Integer.MAX_VALUE;
 
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        for (int i = 0; i < 5; i++) {                //높이
            for (int j = 0; j < 5; j++) {            //가로
                stk = new StringTokenizer(br.readLine());
                for (int k = 0; k < 5; k++) {        //세로
                    map[i][j][k] = Integer.parseInt(stk.nextToken());
                }
            }
        }
        nCr(0new boolean[5]);
        System.out.println(ans == Integer.MAX_VALUE ? -1 : ans);
    }
 
    //참가자가 5개의 판을 쌓는 5!의 경우의 수
    public static void nCr(int cnt, boolean[] visited) {
        if (cnt == 5) {        //경우의 수를 찾았을때마다 만든 배열을 가지고 Backtracking 함수 호출
            int[][][] nmap = new int[5][5][5];
            for (int i = 0; i < 5; i++) {
                int idx = p[i];
                for (int x = 0; x < 5; x++) {
                    for (int y = 0; y < 5; y++) {
                        nmap[i][x][y] = map[idx][x][y];
                    }
                }
            }
            Backtracking(0new int[5][5][5], nmap);
            return;
        }
        for (int i = 0; i < 5; i++) {
            if (!visited[i]) {
                visited[i] = true;
                p[i] = cnt;
                nCr(cnt + 1, visited);
                p[i] = 0;
                visited[i] = false;
            }
        }
        return;
    }
 
    //dfs를 이용하여 각 높이별 회전할 때의 저장배열
    public static void Backtracking(int height, int[][][] nmap, int[][][] map) {
        if (height == 5) {        //배치한 판을 회전시킨 경우의 수마다 bfs 
            if (nmap[0][0][0== 1 && nmap[4][4][4== 1) {
                int tmp = bfs(nmap);
                if (tmp != -1) ans = Math.min(ans, tmp);
            }
            return;
        }
        for (int cnt = 1; cnt <= 4; cnt++) {     //반시계 돌리는 횟수
            for (int i = 0; i < 5; i++) {
                for (int j = 0; j < 5; j++) {
                    if (map[height][i][j] == 1) {
                        switch (cnt) {
                            case 1:
                                nmap[height][j][4 - i] = 1;
                                break;
                            case 2:
                                nmap[height][4 - i][4 - j] = 1;
                                break;
                            case 3:
                                nmap[height][4 - j][i] = 1;
                                break;
                            case 4:
                                nmap[height][i][j] = 1;
                                break;
                        }
                    }
                }
            }
            Backtracking(height + 1, nmap, map);
            nmap[height] = new int[5][5];
        }
        return;
    }
 
    //bfs를 이용해서 저장된 nmap을 가지고 정점가능횟수 찾는 횟수
    public static int bfs(int[][][] nmap) {
        Queue<Point> q = new LinkedList<>();
        visited = new boolean[5][5][5];
        q.add(new Point(0000));
        while (!q.isEmpty()) {
            Point p = q.poll();
            if (p.height == 4 && p.x == 4 && p.y == 4return p.cnt;
            if (!visited[p.height][p.x][p.y]) {
                visited[p.height][p.x][p.y] = true;
                for (int k = 0; k < 6; k++) {
                    int nh = p.height + dh[k];
                    int nx = p.x + dx[k];
                    int ny = p.y + dy[k];
                    if (check(nh, nx, ny) && nmap[nh][nx][ny] == 1 && !visited[nh][nx][ny]) {
                        q.add(new Point(nh, nx, ny, p.cnt + 1));
                    }
                }
            }
        }
        return -1;
    }
 
    public static boolean check(int h, int x, int y) {
        if (h >= 0 && h < 5 && x >= 0 && x < 5 && y >= 0 && y < 5return true;
        return false;
    }
 
    public static class Point {
        int height, x, y, cnt;
 
        public Point(int height, int x, int y, int cnt) {
            this.height = height;
            this.x = x;
            this.y = y;
            this.cnt = cnt;
        }
    }
}
cs


반응형
반응형

AWS는 Amazon Web Services의 약자로 저렴한 클라우딩 서비스를 제공한다.

클라우딩 서비스의 개념부터 알아보자.


* 클라우딩 서비스란?

과거에 물리적으로 서버를 구매하면 시간적, 금전적 비용이 많이 소모되었다. 

또한, 물리적 서버를 구매하면 늘어나는/줄어드는 트래픽에 대해 유연한 대처가 불가능하다.

이러한 비효율성을 극복하고자 AWS가 탄생하게 되었다.


* AWS의 특징

초기 투자 비용이 들지 않는다. AWS 초기에는 스타트업에서 주로 사용하였다고 한다.

서버 증설 및 폐기가 용이하다.

사용한 만큼 비용을 지불하고 효율적인 관리가 가능하다(부하 분산, 오토 스케일링)


* 실습

1. console.aws.amazon.com 접속

2. ec2 클릭 후 인스턴스 생성

3. Amazon Linuz 2 AMI 선택

4. t2.micro 선택(예제용 이므로.. 프리티어 사용)

5. 네트워크, 서브넷, ip할당 선택

6. 스토리지 확인

7. 키 페어 저장 후 인스턴스 시작

(키페어를 분실시 마스터 키를 분실해서 집에 못 들어가는 상황 발생..)

8. 생성 후 1분 내외로 인스턴스 상태가 running으로 변경

9. 보안 그룹에서 인바운드 설정

(쉽게 인바운드 : 들어오는 트래픽 관리, 아웃바운드 : 나가는 트래픽 관리 정도로 이해)

10. 포트 임의 설정 및 내 IP로 설정

11. 등록된 인바운드 규칙 확인 


이렇게 간단하게 클릭 몇번만으로 EC2를 구축할 수 있었다.



반응형
반응형

* HTTP(HyperText Transfer Protocol)이란?

인터넷에서 데이터를 주고받을 수 있는 프로토콜로 웹 서버와 클라이언트간 통신하기 위한 규약


* HTTP의 특징

TCP/IP를 사용하는 응용 프로토콜이며 HTTP 메세지는 HTTP 서버와 HTTP 클라이언트가 해석한다.

HTTP는 연결 상태를 유지하지 않는 프로토콜이기 때문에 Request와 Response 방식으로 작동한다. 

크롬 개발자도구의 네트워크 탭의 정보를 해석해보자.

요청한 URL은 http://sophia2730.tistory.com 이며 200 코드로 성공적인 요청이였다는 결과를 받았다.

여기서 작동한 Method는 GET이며 POST, PUT(수정) 등의 메소드를 사용하여 클라이언트와 서버가 데이터를 주고받는다.

URI를 자원으로 보고 Method를 동사로 보는 개발 방식이 REST 방식이다.


* REST API란?

웹의 장점을 최대한 활용할 수 있는 아키텍처 스타일로, 자원을 표현으로 구분하여 해당 자원의 상태(정보)를 주고 받는 모든 것을 의미한다.

즉, URI를 통해 자원(Resource)을 명시하고, HTTP Method(POST, GET, PUT, DELETE)를 통해 해당 자원에 대한 CRUD Operation을 적용하는 것을 의미한다.

REST API는 두 가지 특징을 가진다.

  1. URI는 정보의 자원을 표현해야 한다.  ex) GET /members/delete/1 (X),  DELETE /members/1 (O)
  2. 자원에 대한 행위는 HTTP Method(GET, POST, PUT, DELETE)로 표현한다.

이러한 방식으로 확장성과 재사용성을 높여 유지보수 및 운용을 편리하게 할 수 있다.


## Cache와 Session

공통점 : 서버가 사용자에게 빠르게 결과를 제공할 수 있음

Cookie 의 저장 위치는 내 컴퓨터 브라우저에 저장되므로 보안성이 떨어진다.

Session은 서버쪽에 저장되는 쿠키이며 클라이언트가 서버에 Request를 보내면 서버는 클라이언트한테 세션 ID를 제공한다.

반응형

'∙Network' 카테고리의 다른 글

[정보처리기사]TCP/IP  (0) 2020.06.30
[Network] TCP/UDP란?  (0) 2019.03.22
[Network] OSI 7 Layer란?  (0) 2019.03.22
[Network] 주소창에 www.naver.com을 치면 일어나는 일  (0) 2018.12.13