localStorage

로컬에 영구적으로 저장하는 저장소입니다. html5에 추가된 저장소라고 합니다.

 

  • localStorage.setItem(key, value) : value를 key의 이름으로 저장합니다.
  • localStorage.getItem(key) : key로 저장되어있는 value를 가져옵니다.
  • localStorage.removeItem(key) : key로 저장되어있는 데이터를 삭제합니다.
  • localStorage.clear() : 모든 데이터를 삭제합니다.
  • localStorage.key(idx) : idx에 해당하는 key를 가져옵니다.
  • localStorage.length : 저장된 항목의 갯수를 가져옵니다.

일반적인 데이터는 위의 메소드를 이용하여 저장, 호출이 가능합니다.

 

하지만 Object배열의 경우는 다릅니다.

Object배열을 String으로 변환하여 저장한 다음 Object배열로 다시 변환하여 가져와야합니다.

 

[데이터 저장]

localStorage.setItem('emps', JSON.stringify(emp));

 => JSON.stringify를 통해 문자열로 변환한 후 'emps'라는 key로 저장합니다.

 

[데이터 호출]

JSON.parse(localStorage.getItem('emps'));

 => JSON.parse를 통해 문자열로 변환했던 'emps'를 다시 Object배열로 변환 후 가져옵니다.

'Etc' 카테고리의 다른 글

TypeScript 설치  (0) 2021.08.30
Windows 10 에서 WSL을 이용한 우분투 설치  (0) 2021.08.29
C++ cout 소수점 고정  (0) 2021.08.05
Java 문자열이 정수인지 확인  (0) 2021.06.01
Java 소수점 자리출력  (0) 2021.03.03

www.acmicpc.net/problem/17143

 

17143번: 낚시왕

낚시왕이 상어 낚시를 하는 곳은 크기가 R×C인 격자판으로 나타낼 수 있다. 격자판의 각 칸은 (r, c)로 나타낼 수 있다. r은 행, c는 열이고, (R, C)는 아래 그림에서 가장 오른쪽 아래에 있는 칸이다.

www.acmicpc.net

낚시왕은 1번 열부터 N번 열까지 1초에 한칸씩 움직이며 차례대로 낚시를 합니다.

1초동안 일어나는 일은

1. 낚시왕이 오른쪽으로 한 칸 이동합니다.

2. 낚시왕이 있는 열에 있는 상어 중에서 땅과 제일 가까운 상어를 잡습니다.

3. 상어가 이동합니다.

 

상어에 대한 정보는 좌표(x, y), 속력(s), 이동 방향(d), 크기(z)가 주어지며, 이동 방향에 맞춰서 속력만큼 이동합니다.

이동 중에 맵 밖으로 나가려고 하는 경우에는 방향을 반대로 바꿔준 후에 그대로 이동합니다.

 

상어가 이동을 마쳤을 때 같은 칸에 여러마리의 상어가 있을 수 있는데 이 경우에는 크기가 가장 큰 상어만 살아남습니다.

 

이 조건들을 모두 고려하여 시뮬레이션을 돌렸을 때 낚시왕이 잡은 상어의 크기 합을 구하는 문제입니다.

 

 

저는 두가지 방법으로 해결해보았습니다.

1. 배열의 모든 칸을 클래스화해서 관리하는 방법

2. 배열에는 상어의 번호만 유지하는 방법

 

먼저 첫 번째 방법입니다.

저는 모든 칸을 클래스화해서 관리하였습니다. (속력, 방향, 크기)

상어가 없는 칸은 (0, 0, 0)이 채워져있을 것이고, 상어가 있는 칸은 (speed, d, size)가 채워져 있습니다.

 

먼저 낚시왕이 상어를 잡고, 상어를 이동시켜줍니다.

이동을 완료한 상어들이 같은 좌표에 있으면 제거를 해야하기 때문에 상어들의 새로운 위치를 구별해주기 위한 새로운 배열(tmp)을 사용하였습니다.

 

우선 속력만큼 이동을 모두 시켜준다면 시간초과가 뜰것 같아서 mod를 사용하였습니다.

상어가 가로로 이동 중이라면 %((M - 1) * 2), 세로로 이동 중이라면 %((N - 1) * 2)만큼만 이동하였습니다.

 

tmp[nx][ny].size가 0이면 상어가 없으므로 상어를 넣어줍니다.

tmp[nx][ny].size가 0이 아니면 이미 다른 상어가 도착한 상태이므로 크기가 큰 상어로 갱신합니다.

 

이 과정을 낚시왕이 맵밖으로 나갈때까지 반복한 후에 크기 합을 출력해줍니다.

 

 

 

 

두 번째 방법입니다.

shark라는 클래스 배열을 이용하여 상어들의 정보를 담아놓습니다. (번호, 좌표(x, y), 속력, 방향, 크기, 죽었는지 여부)

그리고 list배열에는 각 칸에 들어있는 상어의 번호를 저장합니다. (상어가 없으면 0)

 

로직은 첫 번째 방법과 같지만 다른 점은

1번 방법은 N * M을 돌면서 상어가 있는 칸에만 이동을 시키고, 상어의 모든 정보를 이동시켜야하므로 새로운 클래스배열을 선언하였지만

2번 방법은 상어의 수만큼만 반복하면 되고, 인덱스만 이동시키면 되기때문에 새로운 int배열을 선언하였다는 차이입니다.

 

1번 방법
2번 방법
2번 방법에서 mod를 사용하지 않음

시간은 비슷하지만 1번 방법의 메모리가 2번에 비해 엄청 많이 차지하였습니다.

그리고 상어를 움직일 때 mod를 사용하지 않고 돌려보니 시간 차이가 많이 나는것을 알 수 있습니다.

 

 

[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
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;
 
public class Main {
    static class Pair {
        int speed;
        int d;
        int size;
 
        public Pair(int speed, int d, int size) {
            this.speed = speed;
            this.d = d;
            this.size = size;
        }
    }
 
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static ArrayList<Pair> shark = new ArrayList<>();
    static Pair list[][] = new Pair[101][101];
    static int direct[][] = { { -1, 0 }, { 1, 0 }, { 0, 1 }, { 0, -1 } };
    static int N, M, sharkCnt, ans;
 
    static Pair[][] moveShark() {
        Pair tmp[][] = new Pair[101][101];
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= M; j++) {
                tmp[i][j] = new Pair(0, 0, 0);
            }
        }
 
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= M; j++) {
                if (list[i][j].size > 0) {
                    int dis = list[i][j].speed;
                    int d = list[i][j].d;
                    int size = list[i][j].size;
 
                    if (d > 1)
                        dis %= ((M - 1) * 2);
                    else
                        dis %= ((N - 1) * 2);
 
                    int nx = i;
                    int ny = j;
                    for (int k = 0; k < dis; k++) {
                        if (nx == 1 && d == 0)
                            d = 1;
                        else if (nx == N && d == 1)
                            d = 0;
                        else if (ny == 1 && d == 3)
                            d = 2;
                        else if (ny == M && d == 2)
                            d = 3;
 
                        nx += direct[d][0];
                        ny += direct[d][1];
                    }
 
                    if (tmp[nx][ny].size == 0) {
                        tmp[nx][ny].speed = list[i][j].speed;
                        tmp[nx][ny].d = d;
                        tmp[nx][ny].size = size;
                    } else {
                        if (tmp[nx][ny].size < size) {
                            tmp[nx][ny].speed = list[i][j].speed;
                            tmp[nx][ny].d = d;
                            tmp[nx][ny].size = size;
                        }
                    }
                }
            }
        }
 
        return tmp;
    }
 
    static void func() {
        for (int j = 1; j <= M; j++) {
            for (int i = 1; i <= N; i++) {
                if (list[i][j].size > 0) {
                    ans += list[i][j].size;
                    list[i][j].speed = 0;
                    list[i][j].d = 0;
                    list[i][j].size = 0;
                    break;
                }
            }
            if (j == M)
                break;
 
            list = moveShark();
        }
 
        System.out.println(ans);
    }
 
    static void init() {
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= M; j++)
                list[i][j] = new Pair(0, 0, 0);
        }
    }
 
    static void input() throws Exception {
        int x, y, s, d, z;
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        sharkCnt = Integer.parseInt(st.nextToken());
        init();
        for (int i = 0; i < sharkCnt; i++) {
            st = new StringTokenizer(br.readLine());
            x = Integer.parseInt(st.nextToken());
            y = Integer.parseInt(st.nextToken());
            s = Integer.parseInt(st.nextToken());
            d = Integer.parseInt(st.nextToken());
            z = Integer.parseInt(st.nextToken());
 
            list[x][y].speed = s;
            list[x][y].d = d - 1;
            list[x][y].size = z;
        }
    }
 
    public static void main(String[] args) throws Exception {
        input();
        func();
    }
}
 cs

 

 

[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
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
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;
 
public class Main {
    static class Pair {
        int idx;
        int x;
        int y;
        int speed;
        int d;
        int size;
        boolean die;
 
        public Pair(int idx, int x, int y, int speed, int d, int size) {
            this.idx = idx;
            this.x = x;
            this.y = y;
            this.speed = speed;
            this.d = d;
            this.size = size;
            this.die = false;
        }
    }
 
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static int newlist[][] = new int[101][101];
    static int list[][] = new int[101][101];
    static Pair shark[] = new Pair[10001];
    static int direct[][] = { { -1, 0 }, { 1, 0 }, { 0, 1 }, { 0, -1 } };
    static int N, M, sharkCnt, ans;
 
    static void moveShark() {
        for (int i = 1; i <= N; i++)
            Arrays.fill(newlist[i], 0);
 
        for (int i = 1; i <= sharkCnt; i++) {
            int x = shark[i].x;
            int y = shark[i].y;
            int speed = shark[i].speed;
            int d = shark[i].d;
            int size = shark[i].size;
            boolean die = shark[i].die;
 
            if (die)
                continue;
 
            if (d > 1)
                speed %= ((M - 1) * 2);
            else
                speed %= ((N - 1) * 2);
 
            int nx = x;
            int ny = y;
            for (int k = 0; k < speed; k++) {
                if (nx == 1 && d == 0)
                    d = 1;
                else if (nx == N && d == 1)
                    d = 0;
                else if (ny == 1 && d == 3)
                    d = 2;
                else if (ny == M && d == 2)
                    d = 3;
 
                nx += direct[d][0];
                ny += direct[d][1];
            }
            shark[i].d = d;
 
            if (newlist[nx][ny] == 0) {
                newlist[nx][ny] = i;
                shark[i].x = nx;
                shark[i].y = ny;
            } else {
                int idx = newlist[nx][ny];
                int presize = shark[idx].size;
                if (presize < size) {
                    shark[idx].die = true;
                    newlist[nx][ny] = i;
                    shark[i].x = nx;
                    shark[i].y = ny;
                } else {
                    shark[i].die = true;
                }
            }
        }
    }
 
    static void func() {
        for (int j = 1; j <= M; j++) {
            for (int i = 1; i <= N; i++) {
                if (list[i][j] > 0) {
                    int idx = list[i][j];
                    ans += shark[idx].size;
                    shark[idx].die = true;
                    list[i][j] = 0;
                    break;
                }
            }
            if (j == M)
                break;
 
            moveShark();
            for (int x = 1; x <= N; x++)
                for (int y = 1; y <= M; y++)
                    list[x][y] = newlist[x][y];
        }
 
        System.out.println(ans);
    }
 
    static void input() throws Exception {
        int x, y, s, d, z;
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        sharkCnt = Integer.parseInt(st.nextToken());
 
        for (int i = 1; i <= sharkCnt; i++) {
            st = new StringTokenizer(br.readLine());
            x = Integer.parseInt(st.nextToken());
            y = Integer.parseInt(st.nextToken());
            s = Integer.parseInt(st.nextToken());
            d = Integer.parseInt(st.nextToken());
            z = Integer.parseInt(st.nextToken());
 
            shark[i] = new Pair(i, x, y, s, d - 1, z);
            list[x][y] = i;
        }
    }
 
    public static void main(String[] args) throws Exception {
        input();
        func();
    }
}
 cs

'algorithm > Implementation' 카테고리의 다른 글

boj 1756 피자 굽기  (0) 2024.08.08
boj 3758 KCPC  (0) 2024.06.09
boj 20207 달력  (0) 2021.04.22
boj 17144 미세먼지 안녕!  (0) 2021.04.14
boj 2564 경비원  (0) 2021.04.13

www.acmicpc.net/problem/20207

 

20207번: 달력

 수현이는 일년의 날짜가 1일부터 365일로 표시되어있는 달력을 가지고있다. 수현이는 너무나도 계획적인 사람이라 올 해 일정을 모두 계획해서 달력에 표시해놨다.  여름이 거의 끝나가자 장

www.acmicpc.net

시간정보를 입력받으면서 l ~ r시간의 등장횟수를 1씩 증가시킵니다.

 

이제 연속된 구간에서의 최댓값을 갱신하면서, list[i] = 0이 되는 시점에서 지금까지 연속으로 등장했던 시간 * 최댓값을 계속 더해주시면 됩니다.

이후에는 다음 구간을 구하기 위해 con과 max를 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
43
44
45
46
47
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static int list[] = new int[366];
    static int N, ans;
 
    static void func() {
        int max = 0;
        int con = 0;
        for (int i = 1; i <= 365; i++) {
            if (list[i] > 0) {
                con++;
                max = Math.max(max, list[i]);
            } else {
                ans += (con * max);
                con = 0;
                max = 0;
            }
        }
 
        ans += (con * max);
        System.out.println(ans);
    }
 
    static void input() throws Exception {
        int l, r;
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            l = Integer.parseInt(st.nextToken());
            r = Integer.parseInt(st.nextToken());
 
            for (int j = l; j <= r; j++)
                list[j]++;
        }
    }
 
    public static void main(String[] args) throws Exception {
        input();
        func();
    }
}
 cs

'algorithm > Implementation' 카테고리의 다른 글

boj 3758 KCPC  (0) 2024.06.09
boj 17143 낚시왕  (0) 2021.04.23
boj 17144 미세먼지 안녕!  (0) 2021.04.14
boj 2564 경비원  (0) 2021.04.13
boj 16719 ZOAC  (0) 2021.03.15

www.acmicpc.net/problem/19236

 

19236번: 청소년 상어

첫째 줄부터 4개의 줄에 각 칸의 들어있는 물고기의 정보가 1번 행부터 순서대로 주어진다. 물고기의 정보는 두 정수 ai, bi로 이루어져 있고, ai는 물고기의 번호, bi는 방향을 의미한다. 방향 bi는

www.acmicpc.net

이 문제는 고려해야할 부분이 많습니다.

 

상어와 물고기는 8방향 이동을 할 수 있습니다.

순서는 (1)상어가 물고기를 먹고 (2)물고기들이 이동합니다.

상어가 처음에는 (0, 0)에 있는 물고기를 먹으며 먹은 물고기의 방향을 갖게되고, 이후에는 주어진 방향으로만 이동합니다.

 

상어는 한 번에 여러 칸을 이동할 수 있고, 물고기가 있는 칸으로만 이동할 수 있습니다.

따라서 이동경로에 있는 물고기 후보 중 하나를 골라 먹습니다.

 

물고기는 맵 밖이나 상어가 있는 칸으로 이동할 수 없으며 이동할 때 번호가 작은 물고기부터 순서대로 이동합니다. (1번 ~ 16번)

(만약, 해당 번호의 물고기가 먹힌상태면 다음 번호가 이동하면 됩니다.)

물고기는 주어진 방향으로만 1칸 이동하며, 그 칸에 물고기가 있으면 서로의 자리를 바꿉니다.

만약 물고기가 이동할 수 없는 경우에는 이동할 수 있을 때까지 방향을 45도 반시계 방향으로 회전한 후 이동합니다.

 

 

이제 제 로직을 설명하겠습니다.

 

저는 입력을 받으면서 (0, 0)에 상어를 미리 놓고, (1)물고기들 이동, (2)상어 이동 순서대로 구현하였습니다.

func함수의 파라미터에 (현재 배열의 상태(arr), 물고기의 상태(f), 상어의 좌표(X, Y), 상어의 방향(D), 현재 먹은 물고기들의 번호합(S))

을 넘겨주는 재귀함수로 구성하였습니다.

 

함수가 돌 때마다 최대 합을 갱신해주었고, 물고기 이동부터 시작합니다.

먹히지 않은 물고기들만 이동하는 방식이며, 물고기가 이동할 수 있을 때까지 방향을 45도씩 반시계방향으로 회전시키며 반복문을 돌렸습니다.

물고기가 이동하고나면 break를 합니다.

 

이제 상어가 이동합니다.

상어는 한 방향으로만 움직일 수 있지만 여러 칸 이동이 가능하므로 맵 밖으로 나갈 때까지 반복문을 돌려줍니다.

물고기가 없는 칸은 갈 수 없으므로 continue를 하였고, 물고기가 있는 칸은 먹은 후의 상태를 다음 재귀로 넘겨주었습니다. (이는 백트래킹으로 구현하였습니다.)

 

상어와 물고기의 모든 이동이 끝나면 계속 갱신해주었던 답을 출력해줍니다.

 

 

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
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main {
    static class Pair {
        int x, y, d;
 
        public Pair(int x, int y, int d) {
            this.x = x;
            this.y = y;
            this.d = d;
        }
    }
 
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static int direct[][] = { { -1, 0 }, { -1, -1 }, { 0, -1 }, { 1, -1 }, { 1, 0 }, { 1, 1 }, { 0, 1 }, { -1, 1 } };
    static boolean eat[] = new boolean[17];
    static int ans;
 
    static void func(int[][] arr, Pair[] f, int X, int Y, int D, int S) {
        ans = Math.max(ans, S);
        for (int i = 1; i <= 16; i++) {
            if (eat[i])
                continue;
 
            int x = f[i].x;
            int y = f[i].y;
 
            int nx = x;
            int ny = y;
 
            while (true) {
                nx = x + direct[f[i].d][0];
                ny = y + direct[f[i].d][1];
 
                if (nx < 0 || ny < 0 || nx >= 4 || ny >= 4) {
                    f[i].d = (f[i].d + 1) % 8;
                    continue;
                }
                if (arr[nx][ny] == -1) {
                    f[i].d = (f[i].d + 1) % 8;
                    continue;
                }
 
                if (arr[nx][ny] == 0) {
                    f[i].x = nx;
                    f[i].y = ny;
                    arr[nx][ny] = arr[x][y];
                    arr[x][y] = 0;
                } else {
                    int tmp = arr[x][y];
                    f[arr[nx][ny]].x = x;
                    f[arr[nx][ny]].y = y;
                    f[i].x = nx;
                    f[i].y = ny;
                    arr[x][y] = arr[nx][ny];
                    arr[nx][ny] = tmp;
                }
                break;
            }
        }
 
        int nx = X;
        int ny = Y;
        while (true) {
            nx = nx + direct[D][0];
            ny = ny + direct[D][1];
 
            if (nx < 0 || ny < 0 || nx >= 4 || ny >= 4)
                break;
            if (arr[nx][ny] == 0)
                continue;
 
            int tmp = arr[nx][ny];
            arr[nx][ny] = -1;
            arr[X][Y] = 0;
            eat[tmp] = true;
            int arr2[][] = new int[4][4];
            for (int i = 0; i < 4; i++)
                arr2[i] = arr[i].clone();
            Pair f2[] = new Pair[17];
            for (int i = 1; i <= 16; i++)
                f2[i] = new Pair(f[i].x, f[i].y, f[i].d);
            func(arr2, f2, nx, ny, f[tmp].d, S + tmp);
            eat[tmp] = false;
            arr[nx][ny] = tmp;
            arr[X][Y] = -1;
        }
    }
 
    public static void main(String[] args) throws Exception {
        int list[][] = new int[4][4];
        Pair fish[] = new Pair[17];
 
        int nowx = 0, nowy = 0, nowd = 0, sum = 0;
        int x, d;
        for (int i = 0; i < 4; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < 4; j++) {
 
                x = Integer.parseInt(st.nextToken());
                d = Integer.parseInt(st.nextToken()) - 1;
 
                list[i][j] = x;
                fish[x] = new Pair(i, j, d);
                if (i == 0 && j == 0) {
                    list[i][j] = -1;
                    eat[x] = true;
                    nowx = i;
                    nowy = j;
                    nowd = d;
                    sum += x;
                }
            }
        }
        func(list, fish, nowx, nowy, nowd, sum);
        System.out.println(ans);
    }
}
 cs

'algorithm > dfs' 카테고리의 다른 글

boj 30893 트리 게임  (0) 2024.07.19
boj 19542 전단지 돌리기  (0) 2024.06.19
boj 2239 스도쿠  (0) 2021.04.16
boj 2458 키 순서  (0) 2021.04.13
boj 14889 스타트와 링크  (0) 2021.03.17

www.acmicpc.net/problem/1194

 

1194번: 달이 차오른다, 가자.

첫째 줄에 미로의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 50) 둘째 줄부터 N개의 줄에 미로의 모양이 주어진다. 같은 타입의 열쇠가 여러 개 있을 수 있고, 문도 마찬가지이다. 그리고,

www.acmicpc.net

기본적인 bfs에 비트마스킹이 더해진 문제입니다.

 

visit[x][y][key] : (x, y)에 도달했을 때 갖고있는 열쇠 종류

문을 열기 위해서는 열쇠를 갖고있어야 하므로 얻은 열쇠를 비트마스킹을 이용하여 관리합니다.

 

로직은 다른 bfs와 똑같이 돌아가며, 확인해야할 조건은

1. 맵 밖으로 나갈 경우

2. 문을 만났을 경우

3. 열쇠를 만났을 경우

4. 해당 좌표를 이미 방문한 경우

5. 벽을 만난 경우

 

1, 4, 5인 경우에는 continue를 해주시면 되고,

2인 경우에는 열쇠가 없는 경우에만 continue를 해주시면 됩니다.

3인 경우에는 열쇠를 추가합니다.

 

탈출에 성공하였으면 현재 시간을 출력해주시고, 큐가 비었는데도 탈출하지 못했으면 -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
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.StringTokenizer;
 
public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static Deque<int[]> dq = new ArrayDeque<>();
    static char list[][] = new char[51][51];
    static boolean visit[][][] = new boolean[51][51][64];
    static int direct[][] = { { 0, 1 }, { 1, 0 }, { 0, -1 }, { -1, 0 } };
    static int N, M;
 
    static void bfs() {
        for (int t = 0; !dq.isEmpty(); t++) {
            int size = dq.size();
            while (size-- > 0) {
                int x = dq.peek()[0];
                int y = dq.peek()[1];
                int key = dq.poll()[2];
 
                if (list[x][y] == '1') {
                    System.out.println(t);
                    return;
                }
                for (int i = 0; i < 4; i++) {
                    int nx = x + direct[i][0];
                    int ny = y + direct[i][1];
                    int nextKey = key;
 
                    if (nx < 0 || ny < 0 || nx >= N || ny >= M)
                        continue;
                    if ('A' <= list[nx][ny] && list[nx][ny] <= 'F') {
                        int door = list[nx][ny] - 'A';
 
                        if ((key & (1 << door)) == 0)
                            continue;
                    }
                    if ('a' <= list[nx][ny] && list[nx][ny] <= 'f') {
                        nextKey = nextKey | (1 << (list[nx][ny] - 'a'));
                    }
 
                    if (visit[nx][ny][nextKey] || list[nx][ny] == '#')
                        continue;
                    dq.add(new int[] { nx, ny, nextKey });
                    visit[nx][ny][nextKey] = true;
                }
            }
        }
        
        System.out.println(-1);
    }
 
    static void input() throws Exception {
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            list[i] = st.nextToken().toCharArray();
            for (int j = 0; j < M; j++) {
                if (list[i][j] == '0') {
                    dq.add(new int[] { i, j, 0 });
                    visit[i][j][0] = true;
                }
            }
        }
    }
 
    public static void main(String[] args) throws Exception {
        input();
        bfs();
    }
}
 cs

'algorithm > bfs' 카테고리의 다른 글

boj 16932 모양 만들기  (0) 2022.05.14
boj 17244 아맞다우산  (0) 2021.11.25
boj 17471 게리맨더링  (0) 2021.04.16
boj 2573 빙산  (0) 2021.04.05
boj 14923 미로 탈출  (0) 2021.03.29

www.acmicpc.net/problem/2273

 

2273번: 줄 서기

첫째 줄에 N(1≤N≤256), M(1≤M≤100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의미이다.

www.acmicpc.net

키를 비교한 두 학생의 번호 u, v가 주어집니다.

d[u][v] : u가 v보다 앞에서야하는 경우

이는 방향그래프이며 인접행렬을 만들어주고 플로이드로 상대적인 키 정보를 구합니다.

 

그리고 이중for를 돌리면서 d[i][j] = true이고, d[j][i] = true인 것을 찾아줍니다.

d[i][j]=true이면 i가 j보다 앞에 있어야한다는 뜻인데

d[j][i]=true이면 j가 i보다 앞에 있어야한다는 뜻이므로 둘다 true면 모순입니다. 이때는 -1을 출력하고 리턴합니다.

 

확인이 끝났으면 왼쪽 경계 값(l = 1), 오른쪽 경계 값(r = N)으로 두고 1번학생부터 확인합니다.

d[i][j]=true이면 i보다 뒤에 있어야하는 학생이 1명 추가됩니다. => r--;

d[j][i]=true이면 i보다 앞에 있어야하는 학생이 1명 추가됩니다. => l++;

 

모든 학생을 확인하고 l r 을 출력합니다.

 

 

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
#include <iostream>
using namespace std;
 
bool d[257][257];
int N, M;
 
void func() {
    for (int k = 1; k <= N; k++) {
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= N; j++) {
                if (d[i][k] && d[k][j]) d[i][j] = true;
            }
        }
    }
 
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            if (d[i][j] && d[j][i]) {
                cout << "-1\n";
                return;
            }
        }
    }
 
    for (int i = 1; i <= N; i++) {
        int l = 1;
        int r = N;
        for (int j = 1; j <= N; j++) {
            if (d[i][j]) r--;
            else if (d[j][i]) l++;
        }
 
        cout << l << ' ' << r << '\n';
    }
}
 
void input() {
    int u, v;
    cin >> N >> M;
    while (M--) {
        cin >> u >> v;
        d[u][v] = true;
    }
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    input();
    func();
 
    return 0;
}
 cs

'algorithm > Floyd' 카테고리의 다른 글

boj 14938 서강그라운드  (0) 2021.03.24

www.acmicpc.net/problem/17471

 

17471번: 게리맨더링

선거구를 [1, 4], [2, 3, 5, 6]으로 나누면 각 선거구의 인구는 9, 8이 된다. 인구 차이는 1이고, 이 값보다 더 작은 값으로 선거구를 나눌 수는 없다.

www.acmicpc.net

선거구를 두 구간으로 나누는데 나눠진 구간끼리 연결되어 있어야합니다.

 

dfs기반의 부분집합으로 나눌 수 있는 모든 구간을 확인합니다.

두 구간을 div1, div2라는 리스트를 사용하였고, 구역들끼리 연결되어있는지 bfs를 통해 확인합니다.

구간의 모든 구역끼리 연결되어 있으면 구역들의 합의 최솟값을 갱신합니다.

두 선거구로 나눌 수 없는 경우가 입력으로 주어질 수 있으니 그 때는 -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
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Deque;
import java.util.StringTokenizer;
 
public class Main {
    static ArrayList<Integer> graph[] = new ArrayList[11];
    static ArrayList<Integer> div1 = new ArrayList<>();
    static ArrayList<Integer> div2 = new ArrayList<>();
    static int list[] = new int[11];
    static boolean pick[] = new boolean[11];
    static boolean visit[] = new boolean[11];
    static int N, ans = 2147483647;
 
    static boolean bfs(ArrayList<Integer> div, int size, boolean t) {
        Arrays.fill(visit, false);
        Deque<Integer> dq = new ArrayDeque<>();
        dq.add(div.get(0));
        visit[div.get(0)] = true;
        int cnt = 0;
        while (!dq.isEmpty()) {
            int x = dq.poll();
            cnt++;
            for (int i = 0; i < graph[x].size(); i++) {
                int next = graph[x].get(i);
 
                if (visit[next] || pick[next] != t)
                    continue;
 
                visit[next] = true;
                dq.add(next);
            }
        }
 
        if (cnt == size)
            return true;
        else
            return false;
    }
 
    static void func(int idx) {
        if (!div1.isEmpty()) {
            for (int i = 1; i <= N; i++) {
                if (!pick[i])
                    div2.add(i);
            }
            
            if(!div2.isEmpty()) {
                if (bfs(div1, div1.size(), true)) {
                    if (bfs(div2, div2.size(), false)) {
                        int sum = 0;
                        for (int i = 0; i < div1.size(); i++) {
                            sum += list[div1.get(i)];
                        }
 
                        for (int i = 0; i < div2.size(); i++) {
                            sum -= list[div2.get(i)];
                        }
 
                        ans = Math.min(ans, Math.abs(sum));
                    }
                }
                div2.clear();
            }
        }
 
        for (int i = idx; i <= N; i++) {
            div1.add(i);
            pick[i] = true;
            func(i + 1);
            pick[i] = false;
            div1.remove(div1.size() - 1);
        }
    }
 
    static void input() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
 
        st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= N; i++) {
            list[i] = Integer.parseInt(st.nextToken());
        }
 
        int K, v;
        for (int i = 1; i <= N; i++) {
            st = new StringTokenizer(br.readLine());
            K = Integer.parseInt(st.nextToken());
            graph[i] = new ArrayList<>();
            while (K-- > 0) {
                v = Integer.parseInt(st.nextToken());
                graph[i].add(v);
            }
        }
    }
 
    static void print() {
        if (ans == 2147483647)
            System.out.println(-1);
        else
            System.out.println(ans);
    }
 
    public static void main(String[] args) throws Exception {
        input();
        func(1);
        print();
    }
}
 cs

'algorithm > bfs' 카테고리의 다른 글

boj 17244 아맞다우산  (0) 2021.11.25
boj 1194 달이 차오른다, 가자.  (0) 2021.04.21
boj 2573 빙산  (0) 2021.04.05
boj 14923 미로 탈출  (0) 2021.03.29
boj 17836 공주님을 구해라!  (0) 2021.03.26

www.acmicpc.net/problem/2239

 

2239번: 스도쿠

스도쿠는 매우 간단한 숫자 퍼즐이다. 9×9 크기의 보드가 있을 때, 각 행과 각 열, 그리고 9개의 3×3 크기의 보드에 1부터 9까지의 숫자가 중복 없이 나타나도록 보드를 채우면 된다. 예를 들어 다

www.acmicpc.net

백트래킹 기본문제 중 하나입니다.

우선 스도쿠는 9 * 9 배열이 있을 때 각 행, 열, 3 * 3구간에서 1 ~ 9가 한 번씩만 나오게 하는 문제입니다.

 

그럼 각 행, 열, 구간을 중복체크하는 배열을 세개 사용합니다.

(0, 0)부터 (8, 8)까지 한 칸씩 확인하며, list[x][y] != 0이면 수를 넣을 필요가 없으므로 바로 다음좌표를 탐색합니다.

list[x][y] == 0이면 1 ~ 9까지 넣을 수 있는지 확인합니다.

(x, y)에서 숫자 i가 x행에서 사용되었는지, y열에서 사용되었는지, 같은 구간에서 사용되었는지 각각 확인해줍니다.

세 구간 모두 사용되지 않은 숫자만 list[x][y]에 넣어주고 다음좌표로 넘겨줍니다.

모든 좌표를 탐색하였으면 답을 출력하고 리턴합니다.

 

 

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
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main {
    static char div[][] = { { 'a', 'a', 'a', 'b', 'b', 'b', 'c', 'c', 'c' },
            { 'a', 'a', 'a', 'b', 'b', 'b', 'c', 'c', 'c' }, { 'a', 'a', 'a', 'b', 'b', 'b', 'c', 'c', 'c' },
            { 'd', 'd', 'd', 'e', 'e', 'e', 'f', 'f', 'f' }, { 'd', 'd', 'd', 'e', 'e', 'e', 'f', 'f', 'f' },
            { 'd', 'd', 'd', 'e', 'e', 'e', 'f', 'f', 'f' }, { 'g', 'g', 'g', 'h', 'h', 'h', 'i', 'i', 'i' },
            { 'g', 'g', 'g', 'h', 'h', 'h', 'i', 'i', 'i' }, { 'g', 'g', 'g', 'h', 'h', 'h', 'i', 'i', 'i' }, };
    static boolean rowsChk[][] = new boolean[10][10];
    static boolean colsChk[][] = new boolean[10][10];
    static boolean divChk[][] = new boolean[10][10];
    static int list[][] = new int[10][10];
 
    static boolean func(int x, int y) {
        if (x == 9) {
            StringBuffer sb = new StringBuffer();
            for (int i = 0; i < 9; i++) {
                for (int j = 0; j < 9; j++) {
                    sb.append(list[i][j]);
                }
                sb.append("\n");
            }
            System.out.println(sb.toString());
            return true;
        }
 
        int nx = x;
        int ny = y + 1;
        if (ny == 9) {
            nx++;
            ny = 0;
        }
 
        if (list[x][y] != 0)
            return func(nx, ny);
        else {
            for (int i = 1; i <= 9; i++) {
                if (rowsChk[x][i] || colsChk[y][i] || divChk[div[x][y] - 'a'][i])
                    continue;
 
                rowsChk[x][i] = true;
                colsChk[y][i] = true;
                divChk[div[x][y] - 'a'][i] = true;
                list[x][y] = i;
                boolean chk = func(nx, ny);
                if (chk)
                    return true;
                list[x][y] = 0;
                divChk[div[x][y] - 'a'][i] = false;
                colsChk[y][i] = false;
                rowsChk[x][i] = false;
            }
        }
 
        return false;
    }
 
    static void input() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        char ch[];
        for (int i = 0; i < 9; i++) {
            st = new StringTokenizer(br.readLine());
            ch = st.nextToken().toCharArray();
            for (int j = 0; j < 9; j++) {
                list[i][j] = ch[j] - '0';
                if (list[i][j] != 0) {
                    rowsChk[i][list[i][j]] = true;
                    colsChk[j][list[i][j]] = true;
                    divChk[div[i][j] - 'a'][list[i][j]] = true;
                }
            }
        }
    }
 
    public static void main(String[] args) throws Exception {
        input();
        func(0, 0);
    }
}
 cs

'algorithm > dfs' 카테고리의 다른 글

boj 19542 전단지 돌리기  (0) 2024.06.19
boj 19236 청소년 상어  (0) 2021.04.22
boj 2458 키 순서  (0) 2021.04.13
boj 14889 스타트와 링크  (0) 2021.03.17
boj 2023 신기한 소수  (0) 2021.03.16

정렬 알고리즘은 N개의 숫자를 기준에 맞게 오름차순 or 내림차순으로 정렬하는 알고리즘입니다.

종류가 다양하게 있지만 이 글에서는 선택, 버블, 삽입, 병합, 퀵 정렬만 정리하려고 합니다.

그리고 오름차순 정렬만 정리하였습니다.

 

1. 선택 정렬 (Selection Sort)

선택 정렬은 현재 위치에 들어갈 수를 찾으면서 정렬하는 알고리즘입니다.

 

1. 선택한 인덱스부터 N까지 가장 작은 값을 찾습니다.

2. 가장 작은 값과 선택한 값을 서로 바꿉니다.

3. 이 과정을 N - 1번 반복합니다.

 

이 알고리즘의 시간복잡도는 최선, 최악 : O(N^2)이고, 공간복잡도는 O(N)입니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
void selectionSort() {
    for (int i = 0; i < N - 1; i++) {
        int minidx = i;
        for (int j = i + 1; j < N; j++) {
            if (list[minidx] > list[j]) {
                minidx = j;
            }
        }
        int tmp = list[minidx];
        list[minidx] = list[i];
        list[i] = tmp;
    }
}
 cs

 

 

2. 버블 정렬 (Bubble Sort)

버블 정렬은 연속된 2개의 수를 비교하여 정렬하는 알고리즘입니다.

정렬 과정에서 가장 큰수를 맨뒤로 보내는 방식입니다.

 

1. 두 번째 인덱스부터 바로 이전의 인덱스와 값을 비교합니다. (list[idx], list[idx - 1])

2. list[idx - 1] > list[idx]이면 두 수를 바꿉니다.

3. 아니면 다음 인덱스를 확인합니다.

4. 이 과정을 N번 반복합니다.

 

이 알고리즘의 시간복잡도는 최선, 최악 : O(N^2)이고, 공간복잡도는 O(N)입니다.

 

선택 정렬은 앞에서부터 작은 수가 결정되는 방식이지만

버블 정렬은 뒤에서부터 큰 수가 결정되는 방식입니다.

1
2
3
4
5
6
7
8
9
10
11
void bubbleSort() {
    for (int i = 0; i < N; i++) {
        for (int j = 1; j < N - i; j++) {
            if (list[j - 1] > list[j]) {
                int tmp = list[j];
                list[j] = list[j - 1];
                list[j - 1] = tmp;
            }
        }
    }
}
 cs

 

 

3. 삽입 정렬 (Insertion Sort)

삽입 정렬은 현재 위치에서 이전의 값들을 비교하여 자신이 들어갈 위치를 찾아들어가는 정렬 알고리즘입니다.

 

1. 현재 인덱스에서 왼쪽으로 이동하면서 값을 비교합니다.

2. tmp보다 작은 수가 나올 때까지 수들을 한칸 옮겨줍니다.

3. tmp보다 작은 수가 나오면 그 다음 자리에 tmp를 넣어줍니다.

4. 이 과정을 N - 1번 반복합니다.

 

이 알고리즘의 시간복잡도는 최선 : O(N), 최악 : O(N^2)이고, 공간복잡도는 O(N)입니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void insertionSort() {
    for (int i = 1; i < N; i++) {
        int tmp = list[i];
        int j = i - 1;
        for (; j >= 0; j--) {
            if (list[j] > tmp) {
                list[j + 1] = list[j];
            }
            else
                break;
        }
        list[j + 1] = tmp;
    }
}
 cs

 

 

4. 병합 정렬 (Merge Sort)

병합 정렬은 배열을 반씩 분할해가면서 정렬하는 알고리즘입니다.

시간적으로는 효율적이나 메모리를 배열의 2배 사용해야하는 단점이 있습니다.

 

1. 배열을 가장 작은크기까지 분할합니다.

2. 분할된 배열끼리 정렬합니다.

3. 분할된 배열을 다시 합쳐서 합친 배열을 다시 정렬합니다.

4. 이 과정을 반복합니다.

 

과정 예시)
 
list[] = {4, 5, 8, 2, 6, 1, 7, 3}


[배열을 분할합니다.]
N = 8    {4, 5, 8, 2, 6, 1, 7, 3}
    

N = 4    {4, 5, 8, 2}    {6, 1, 7, 3}


N = 2    {4, 5}    {8, 2}    {6, 1}    {7, 3}


N = 1    {4}    {5}    {8}    {2}    {6}    {1}    {7}    {3}


[배열을 병합하는 과정에서 정렬합니다.]
N = 1    {4}    {5}    {8}    {2}    {6}    {1}    {7}    {3}


N = 2    {4, 5}    {2, 8}    {1, 6}    {3, 7}


N = 4    {2, 4, 5, 8}    {1, 3, 6, 7}


N = 8    {1, 2, 3, 4, 5, 6, 7, 8}

 

정렬로직 설명)
 
분할된 두 개의 배열에서 가장 작은 값들끼리 비교하여 작은 값을 새로운 배열에 넣습니다.
arr1: {2, 4, 5, 8}    arr2: {1, 3, 6, 7}    sorted: {}
arr1 or arr2의 숫자를 모두 고를때까지 반복합니다.


arr1: {2, 4, 5, 8}    arr2: {1, 3, 6, 7}    sorted: {}
arr1[i] = 2
arr2[j] = 1


arr1: {2, 4, 5, 8}    arr2: {3, 6, 7}    sorted: {1}
arr1[i] = 2
arr2[j] = 3


arr1: {4, 5, 8}    arr2: {3, 6, 7}    sorted: {1, 2}
arr1[i] = 4
arr2[j] = 3


arr1: {4, 5, 8}    arr2: {6, 7}    sorted: {1, 2, 3}
arr1[i] = 4
arr2[j] = 6


arr1: {5, 8}    arr2: {6, 7}    sorted: {1, 2, 3, 4}
arr1[i] = 5
arr2[j] = 6


arr1: {8}    arr2: {6, 7}    sorted: {1, 2, 3, 4, 5}
arr1[i] = 8
arr2[j] = 6


arr1: {8}    arr2: {7}    sorted: {1, 2, 3, 4, 5, 6}
arr1[i] = 8
arr2[j] = 7


arr1: {8}    arr2: {}    sorted: {1, 2, 3, 4, 5, 6, 7}
여기서 arr2의 숫자를 모두 골랐으니 arr1의 남은 숫자를 sorted의 뒤에 붙여주면 됩니다.


arr1: {}    arr2: {}    sorted: {1, 2, 3, 4, 5, 6, 7, 8}

 

이 알고리즘의 시간복잡도는 최선, 최악 : O(NlogN)이고, 공간복잡도는 O(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
void merge(int l, int m, int r) {
    int i = l;
    int j = m + 1;
    int k = l;
 
    while (i <= m && j <= r) {
        if (list[i] < list[j])
            sorted[k++] = list[i++];
        else
            sorted[k++] = list[j++];
    }
 
    if (i > m) {
        for (int t = j; t <= r; t++, k++) {
            sorted[k] = list[t];
        }
    } else {
        for (int t = i; t <= m; t++, k++) {
            sorted[k] = list[t];
        }
    }
 
    for (int t = l; t <= r; t++)
        list[t] = sorted[t];
}
 
void mergeSort(int l, int r) {
    if (l < r) {
        int m = (l + r) / 2;
        mergeSort(l, m);
        mergeSort(m + 1, r);
        merge(l, m, r);
    }
}
 cs

 

 

 

5. 퀵 정렬 (Quick Sort)

배열에서 피봇을 선택해 피봇보다 작은 원소를 왼쪽에, 큰 원소를 오른쪽에 옮겨지고

피봇을 기준으로 피봇을 제외한 왼쪽, 오른쪽 원소들을 다시 정렬해나가는 알고리즘입니다.

 

과정 예시)
 
list[] = {4, 5, 8, 2, 6, 1, 7, 3}
피봇은 배열의 첫번째 요소로 지정합니다.


list[] = {4, 5, 8, 2, 6, 1, 7, 3}
pivot = 0
i = 1
j = 0


list[] = {4, 2, 8, 5, 6, 1, 7, 3}
pivot = 0
i = 3
j = 1


list[] = {4, 2, 1, 5, 6, 8, 7, 3}
pivot = 0
i = 5
j = 2


list[] = {4, 2, 1, 3, 6, 8, 7, 5}
pivot = 0
i = 7
j = 3


list[] = {3, 2, 1, 4(fix), 6, 8, 7, 5}


이후에 피봇 기준 왼쪽 오른쪽 배열{3, 2, 1}과    {6, 8, 7, 5}도 똑같은 로직을 반복합니다.

 

정렬로직 설명)
 
list[] = {4, 5, 8, 2, 6, 1, 7, 3}
pivot : 0
i = 1
j = 0


list[i]와 list[pivot]을 비교합니다.
list[i] < list[pivot]이면 j를 1증가하고, list[i]와 list[j]를 바꿉니다.
이를 i = 1부터 끝까지 반복합니다.


그럼 최종적으로
list[] = {4, 2, 1, 3, 6, 8, 7, 5} 라는 배열이 만들어집니다.
여기서 pivot은 여전히 0이고
j는 3입니다.


그럼 list[pivot]과 list[j]를 바꿉니다.
=> list[] = {3, 2, 1, 4(fix), 6, 8, 7, 5}
이제 4의 위치는 정해졌으며 이를 기준으로 왼쪽 배열과 오른쪽 배열도 같은 로직을 반복합니다.

 

이 알고리즘의 시간복잡도는 최선 : O(NlogN), 최악 : O(N^2)이고, 공간복잡도는 O(N)입니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int partition(int pivot, int l, int r) {
    int j = pivot;
    for (int i = pivot + 1; i <= r; i++) {
        if (list[pivot] > list[i]) {
            swap(list[++j], list[i]);
        }
    }
    swap(list[pivot], list[j]);
    
    return j;
}
 
void quickSort(int l, int r) {
    if (l < r) {
        int pivot = partition(l, l, r);
        quickSort(l, pivot - 1);
        quickSort(pivot + 1, r);
    }
}
 cs

 

'algorithm > Theory' 카테고리의 다른 글

좌표 압축 (Coordinate Compression)  (2) 2022.08.24

www.acmicpc.net/problem/17144

 

17144번: 미세먼지 안녕!

미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사

www.acmicpc.net

1초 동안 다음과 같은 일이 일어납니다.

1. 미세먼지가 확산되며 미세먼지가 있는 모든 칸에서 동시에 일어납니다.

 - 인접한 4방향으로 확산됩니다.

 - 인접한 방향이 맵 밖이거나 공기청정기가 있는 곳이라면 확산이 일어나지 않습니다.

 - 확산되는 양은 list[i][j] / 5입니다. (소수점 버림)

 - (i, j)에 남은 미세먼지 양은 list[i][j] - (list[i][j] / 5) * (확산된 방향의 갯수)입니다.

2. 공기청정기가 작동됩니다.

 - 위쪽 공기청정기의 바람은 반시계방향으로 순환, 아래쪽 공기청정기의 바람은 시계방향으로 순환합니다.

 - 미세먼지가 바람의 방향대로 한 칸씩 이동합니다.

 - 공기청정기로 들어가는 미세먼지는 정화됩니다.

 

위의 모든것을 직접 구현해야합니다.

 

우선 2중for문을 돌면서 미세먼지를 확산시킵니다. 이 때 확산이 동시에 일어나야하므로 nextlist라는 변수를 사용하였습니다.

그 다음 공기청정기를 작동시켜 위쪽에는 반시계방향으로, 아래쪽에는 시계방향으로 값을 회전시켜줍니다.

이 과정을 T번 반복하여 T초 후 남아있는 미세먼지 양을 출력합니다.

 

 

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
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
 
public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static int list[][] = new int[51][51];
    static int nextlist[][] = new int[51][51];
    static int direct[][] = { { 0, 1 }, { 1, 0 }, { 0, -1 }, { -1, 0 } };
    static int cleaner[][] = new int[2][2];
    static int N, M, T;
 
    static void clear() {
        int x = cleaner[0][0];
        int y = cleaner[0][1];
 
        x--;
        int d = 3;
        while (true) {
            int nx = x + direct[d][0];
            int ny = y + direct[d][1];
 
            if (nx <= 0 || ny <= 0 || nx > cleaner[0][0] || ny > M) {
                d = (d + 1) % 4;
                continue;
            }
            list[x][y] = 0;
            if (list[nx][ny] == -1)
                break;
 
            list[x][y] = list[nx][ny];
            x = nx;
            y = ny;
        }
 
        x = cleaner[1][0];
        y = cleaner[1][1];
 
        x++;
        d = 1;
        while (true) {
            int nx = x + direct[d][0];
            int ny = y + direct[d][1];
 
            if (nx < cleaner[1][0] || ny <= 0 || nx > N || ny > M) {
                d = (d + 3) % 4;
                continue;
            }
            list[x][y] = 0;
            if (list[nx][ny] == -1)
                break;
 
            list[x][y] = list[nx][ny];
            x = nx;
            y = ny;
        }
    }
    
    static void spread() {
        for (int i = 1; i <= N; i++)
            Arrays.fill(nextlist[i], 0);
 
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= M; j++) {
                if (list[i][j] > 0) {
                    int diff = list[i][j] / 5;
                    int cnt = 0;
                    for (int d = 0; d < 4; d++) {
                        int nx = i + direct[d][0];
                        int ny = j + direct[d][1];
 
                        if (nx <= 0 || ny <= 0 || nx > N || ny > M)
                            continue;
                        if (list[nx][ny] == -1)
                            continue;
 
                        nextlist[nx][ny] += diff;
                        cnt++;
                    }
 
                    nextlist[i][j] += (list[i][j] - diff * cnt);
                }
            }
        }
        
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= M; j++) {
                if (list[i][j] == -1)
                    continue;
                list[i][j] = nextlist[i][j];
            }
        }
    }
 
    static void func() {
        for (int t = 1; t <= T; t++) {
            spread();
            clear();
        }
    }
 
    static void print() {
        int ans = 0;
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= M; j++) {
                if (list[i][j] > 0)
                    ans += list[i][j];
            }
        }
 
        System.out.println(ans);
    }
 
    static void input() throws Exception {
        int t = 0;
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        T = Integer.parseInt(st.nextToken());
        for (int i = 1; i <= N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 1; j <= M; j++) {
                list[i][j] = Integer.parseInt(st.nextToken());
                if (list[i][j] == -1) {
                    cleaner[t][0] = i;
                    cleaner[t++][1] = j;
                }
            }
        }
    }
 
    public static void main(String[] args) throws Exception {
        input();
        func();
        print();
    }
}
 cs

'algorithm > Implementation' 카테고리의 다른 글

boj 17143 낚시왕  (0) 2021.04.23
boj 20207 달력  (0) 2021.04.22
boj 2564 경비원  (0) 2021.04.13
boj 16719 ZOAC  (0) 2021.03.15
boj 3085 사탕 게임  (0) 2021.02.26

www.acmicpc.net/problem/2110

 

2110번: 공유기 설치

첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가

www.acmicpc.net

M개의 공유기를 놓을 수 있는 최대한의 간격을 구하는 문제입니다.

최대한의 간격은 최적화된 정답을 구하는 것이므로 파라매트릭 서치로 해결합니다.

 

우선 이분탐색을 쓰기 위해 입력받은 위치정보를 정렬합니다.

탐색 범위는 간격이며, (1 ~ list[N] - list[1])의 범위에서 탐색합니다.

 

간격 m에서 공유기를 M개 이상 놓을 수 있는지 확인합니다.

놓을 수 있으면 true, 아니면 false를 리턴합니다.

 

solve함수의 리턴 값이 true면 ans에 현재 간격을 저장하고 (m + 1 ~ r) 범위를 탐색합니다.

solve함수의 리턴 값이 false면 (s ~ m - 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
#include <iostream>
#include <algorithm>
using namespace std;
 
int list[200001];
int N, M;
 
bool solve(int length) {
    int pre = list[1];
    int cnt = 1;
    for (int i = 2; i <= N; i++) {
        if (list[i] - pre >= length) {
            cnt++;
            pre = list[i];
        }
    }
 
    if (cnt >= M) return true;
    else return false;
}
 
int binarySearch(int l, int r) {
    int ans = 0;
 
    while (l <= r) {
        int m = (l + r) / 2;
        if (solve(m)) {
            ans = m;
            l = m + 1;
        }
        else r = m - 1;
    }
 
    return ans;
}
 
void input() {
    cin >> N >> M;
    for (int i = 1; i <= N; i++) {
        cin >> list[i];
    }
    sort(list + 1, list + 1 + N);
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    input();
    cout << binarySearch(1, list[N] - list[1]) << '\n';
 
    return 0;
}
 cs

'algorithm > binarysearch' 카테고리의 다른 글

boj 18113 그르다 김가놈  (0) 2022.10.09
boj 2295 세 수의 합  (0) 2022.06.28
boj 7453 합이 0인 네 정수  (0) 2021.01.22
boj 2143 두 배열의 합  (0) 2021.01.22
boj 2805 나무 자르기  (0) 2021.01.22

www.acmicpc.net/problem/2458

 

2458번: 키 순서

1번부터 N번까지 번호가 붙여져 있는 학생들에 대하여 두 학생끼리 키를 비교한 결과의 일부가 주어져 있다. 단, N명의 학생들의 키는 모두 다르다고 가정한다. 예를 들어, 6명의 학생들에 대하여

www.acmicpc.net

 

처음에 이 그림을 보았을 때 위상정렬을 쓰는건가 하고 생각했었지만 순서 중 하나를 출력하는 것이 아닌 자신의 정확한 순서를 알고있는 학생의 수를 출력하는 문제였습니다.

 

저는 두 가지 방법으로 해결하였습니다.

먼저 dfs 방법입니다.

 

저는 2개의 벡터를 사용하였습니다. (자신보다 키가 큰 학생을 저장하는 벡터(f), 작은 학생을 저장하는 벡터(s))

한 학생을 시작으로 두번의 dfs를 수행합니다.

i번 학생보다 키가 큰 학생들을 dfs로 순회하고, 작은 학생들도 똑같이 dfs로 순회합니다.

순회하면서 next의 갯수만큼 cnt를 1씩 늘려줍니다.

 

두 번의 dfs가 끝나고 cnt가 N - 1이면 자신의 정확한 순서를 알 수 있습니다.

 

 

그 다음은 플로이드 방법입니다.

 

d[i][j] : i번 학생의 키 < j번 학생의 키 인 경우

 

플로이드로 자신보다 키가 큰 학생들을 모두 구합니다.

그 다음 i번 학생과 j번 학생의 관계를 확인합니다.

d[i][j] (i번이 j번보다 작은 경우) || d[j][i] (i번이 j번보다 큰 경우)

 

위의 조건을 만족한 횟수가 N - 1이면 자신의 정확한 순서를 알 수 있습니다.

 

dfs
플로이드

 

아무래도 플로이드가  N^3이라 dfs에 비해 속도가 느린 편입니다.

 

 

[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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
 
vector<int> f[501], s[501];
bool visit[501];
int N, M, cnt;
 
void dfs(vector<int> t[], int v) {
    visit[v] = true;
 
    for (int i = 0; i < t[v].size(); i++) {
        int next = t[v][i];
 
        if (visit[next]) continue;
 
        cnt++;
        dfs(t, next);
    }
}
 
void func() {
    int ans = 0;
    for (int i = 1; i <= N; i++) {
        memset(visit, false, sizeof(visit));
        dfs(f, i);
        memset(visit, false, sizeof(visit));
        dfs(s, i);
 
        if (cnt == N - 1) ans++;
        cnt = 0;
    }
 
    cout << ans << '\n';
}
 
void input() {
    int u, v;
    cin >> N >> M;
    while (M--) {
        cin >> u >> v;
        f[u].push_back(v);
        s[v].push_back(u);
    }
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    input();
    func();
 
    return 0;
}
 cs

 

 

[플로이드]

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
#include <iostream>
#define INF 1000000000
using namespace std;
 
bool d[501][501];
int N, M, ans;
 
void solve() {
    for (int i = 1; i <= N; i++) {
        int cnt = 0;
        for (int j = 1; j <= N; j++) {
            if (d[i][j] || d[j][i]) cnt++;
        }
 
        if (cnt == N - 1) ans++;
    }
 
    cout << ans << '\n';
}
 
void func() {
    for (int k = 1; k <= N; k++) {
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= N; j++) {
                if (d[i][k] && d[k][j]) {
                    d[i][j] = true;
                }
            }
        }
    }
}
 
void input() {
    int u, v;
    cin >> N >> M;
    while (M--) {
        cin >> u >> v;
        d[u][v] = true;
    }
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    input();
    func();
    solve();
 
 
    return 0;
}
 cs

'algorithm > dfs' 카테고리의 다른 글

boj 19236 청소년 상어  (0) 2021.04.22
boj 2239 스도쿠  (0) 2021.04.16
boj 14889 스타트와 링크  (0) 2021.03.17
boj 2023 신기한 소수  (0) 2021.03.16
boj 14500 테트로미노  (0) 2021.03.15

+ Recent posts

티스토리툴바