2024/03/28(목)

이틀동안 알고리즘을 미루고 미뤘다

제에에에발 미루지 말자! 하나님이 능력주시면 무엇이 능치 못할까

마음을 다잡고 지혜를 구하면서 공부하자!!

 

Part. 알고리즘

 

백준 2589 - 보물섬

https://www.acmicpc.net/problem/2589

2589번: 보물섬

 

보물섬 문제를 다시 복습해보자!!

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {

    public static String[][] map;
    public static int N;
    public static int M;
    public static int res;
    public static int[][] visited;
    public static int[] dx = {0, 1, 0, -1};
    public static int[] dy = {-1, 0, 1, 0};

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        map = new String[N][M];

        for (int i = 0; i < N; i++) {
            map[i] = br.readLine().split("");
        }

        res = 0;

        visited = new int[N][M];

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if ("L".equals(map[i][j])) {
                    res = Math.max(res, bfs(i, j));
                    visited = new int[N][M];
                }
            }
        }

        bw.write(res + "\n");
        bw.flush();
        bw.close();
        br.close();
    }

    public static int bfs(int y, int x) { // 최단거리

        int answer = 0;

        visited[y][x] = 1;
        Node node = new Node(y, x);
        Queue<Node> queue = new LinkedList<>();
        queue.add(node);

        while (!queue.isEmpty()) {
            Node curNode = queue.poll();
            for (int i = 0; i < 4; i++) {
                int nx = curNode.x + dx[i];
                int ny = curNode.y + dy[i];

                if (nx < 0 || nx >= M || ny < 0 || ny >= N || visited[ny][nx] != 0 || "W".equals(map[ny][nx])) {
                    continue;
                }
                if (visited[ny][nx] == 0 && "L".equals(map[ny][nx])) {
                    visited[ny][nx] = visited[curNode.y][curNode.x] + 1;
                    answer = Math.max(answer, visited[ny][nx]);
                    queue.add(new Node(ny, nx));
                }
            }
        }

        return answer - 1;
    }

    public static class Node {
        int y;
        int x;

        public Node(int y, int x) {
            this.y = y;
            this.x = x;
        }
    }
}

 

정답!!

 

https://www.acmicpc.net/problem/16234

16234번: 인구 이동

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {

    public static int N;
    public static int L;
    public static int R;

    public static int[][] map;
    public static int[][] visited;
    public static int[] dx = {0, 1, 0, -1};
    public static int[] dy = {-1, 0, 1, 0};

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        N = Integer.parseInt(st.nextToken());
        L = Integer.parseInt(st.nextToken());
        R = Integer.parseInt(st.nextToken());

        map = new int[N][N];
        visited = new int[N][N];

        for (int i = 0; i < N; i++) {
            map[i] = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        }

        int result = 0;

        while (true) { // 인구 이동이 없을 때까지
            if (move() == 0) { // 이동이 없다면
                break;
            } else {
                result++;
            }
        }

        bw.write(result + "\n");
        bw.flush();
        bw.close();
        br.close();
    }

    public static int move() {
        int flag = 0;

        for (int y = 0; y < N; y++) {
            for (int x = 0; x < N; x++) {
                if (visited[y][x] == 0) {
                    Queue<Node> queue = new LinkedList<>();
                    ArrayList<Node> list = new ArrayList<>();

                    Node node = new Node(y, x);
                    queue.add(node);
                    list.add(node);

                    int sum = map[node.y][node.x]; // 합계
                    visited[node.y][node.x] = 1;

                    while (!queue.isEmpty()) {
                        Node cur = queue.poll();

                        for (int i = 0; i < 4; i++) {
                            int nx = cur.x + dx[i];
                            int ny = cur.y + dy[i];

                            if (nx < 0 || nx >= N || ny < 0 || ny >= N) {
                                continue;
                            }
                            if (visited[ny][nx] == 0) { // 방문 x
                                int gap = Math.abs(map[ny][nx] - map[cur.y][cur.x]);
                                if (gap >= L && gap <= R) {
                                    queue.add(new Node(ny, nx));
                                    list.add(new Node(ny, nx));
                                    visited[ny][nx] = 1;
                                    flag = 1;
                                    sum += map[ny][nx];
                                }
                            }
                        }
                    }

                    if (flag > 0) { // 분할이 된 경우
                        int average = sum / list.size();
                        for (int k = 0; k < list.size(); k++) {
                            Node cur = list.get(k);
                            map[cur.y][cur.x] = average;
                        }
                    }
                }
            }
        }

        visited = new int[N][N];
        return flag;
    }

    public static class Node {
        int y;
        int x;

        public Node(int y, int x) {
            this.y = y;
            this.x = x;
        }
    }
}

 

https://www.acmicpc.net/problem/1781

1781번: 컵라면

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {

    public static int N;
    public static List<Node> list;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        N = Integer.parseInt(br.readLine());

        list = new ArrayList<>();

        for (int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int deadline = Integer.parseInt(st.nextToken());
            int value = Integer.parseInt(st.nextToken());
            list.add(new Node(deadline, value));
        }

        // 구간 -> 라인 스위핑
        Collections.sort(list, new Comparator<Node>() {
            @Override
            public int compare(Node o1, Node o2) {
                return o1.deadline - o2.deadline;
            }
        }); // 정렬

        PriorityQueue<Node> pq = new PriorityQueue<>();

        int answer = 0;

        for (int i = 0; i < list.size(); i++) {
            Node node = list.get(i);
            answer += node.value;
            pq.add(node);
            if (pq.size() > node.deadline) {
                answer -= pq.poll().value;
            }
        }

        bw.write(answer + "\n");
        bw.flush();
        br.close();
        bw.close();
    }

    public static class Node implements Comparable<Node> {

        int deadline;
        int value;

        public Node(int deadline, int value) {
            this.deadline = deadline;
            this.value = value;
        }

        @Override
        public int compareTo(Node node) {
            return this.value - node.value;
        }
    }
}

 

복습 끝!

 

DP문제 풀기

https://www.acmicpc.net/problem/2098

2098번: 외판원 순회

 

음.. 모르겠다..!

풀이를 보면서 배워보자!

 

풀이에선 dp와 비트마스킹을 사용해서 풀어주었다.

 

비트마스킹을 사용하면 2^n의 상태값을 n bit로 표현

 O(n!)을 dp 메모제이션 기법을 사용하여 최적화

 

TSP는 한 정점에서 다른 모든 정점을 순회하여 다시 출발 정점으로 돌아오는 최적의 경로를 찾는 방식으로 풀 수 있다. 

n개의 정점 중 어느 정점에서 탐색을 시작해도 결과는 똑같다.

 

 

 

(1) N!의 중복 경로를 제거해주는 DP 메모제이션 기법 사용

(2) 메모리 사용량도 줄이고 성능 향상을 위해 2^N의 경우의 수를 Nbit로 표현할 수 있는 비트마스킹으로 사용한다.

 

비트마스킹 사용하기

비트 마스킹과 for문을 통해 각 도시(0~n-1번 도시)의 방문 상태를 업데이트해준다.

A |= (1<<k) : k를 새롭게 방문

for(int i = 0; i<n; i++){
	int next = check | (1<<i);
}

 

ex)

check = 1 (0001) -> 현재 1번 도시 방문

i = 3, check | (1<<3) = 9 (1001) -> 1,4(i+1)번 도시 방문

check = 3 (0011) -> 현재 1,2번 도시 방문

 

비트마스킹에 대해서 공부해보자!

 

비트마스킹

컴퓨터는 내부적으로 모든 자료를 이진수로 표현한다.

이와 같은 특성을 이용해 정수의 이진수 표현을 자료구조로 쓰는 기법을 비트 마스크라고 한다.

비트 마스크를 이용하면 더 빠른 수행 시간, 더 간결한 코드, 더 적은 메모리 사용이라는 효과를 얻을 수 있습니다.

 

비트 연산자

a & b	a의 모든 비트와 b의 모든 비트를 AND연산한다. 둘다 1이라면 1, 아니면 0	a = 4 = 100(2) b = 7 = 111(2) a & b = 100(2) = 4
a | b	a의 모든 비트와 b의 모든 비트를 OR연산한다.	a = 2 = 010(2) b = 5 = 101(2) a | b = 111(2) = 7
a ^ b	a의 모든 비트와 b의 모든 비트를 XOR연산한다. 둘이 다르다면 1, 아니면 0	a = 3 = 011(2) b = 5 = 101(2) a ^ b = 110(2) = 6
~a	a의 모든 비트에 NOT 연산을 한다. 0이면 1, 1이면 0	a = 3 = 011(2) ~a = 100(2) = 4
a << b	a를 b비트 만큼 왼쪽으로 시프트	a = 1 = 001(2) a << 2 = 100(2) = 4
a >> b	a를 b비트 만큼 오른쪽으로 시프트	a = 4 = 100(2) a >> 2 = 001(2) = 1

 

집합의 표현

비트 마스크를 이용하면 집합을 쉽게 표현할 수 있다. 집합에 원소를 추가, 삭제하는 등 다양한 연산을 굉장히 빠르게 수행할 수 있다.

원소의 개수가 N인 집합이 있다고 하면, 각각의 원소를 0번부터 (N-1)번 까지 번호를 부여하고, 번호에 해당하는 비트가 1이면 원소가 포함, 0이면 원소가 불포함이라고 한다면 집합을 비트를 이용해 표현한다.

 

원소추가

현재 상태 i일때, p번 원소를 추가한다고 해보자. 현재 상태 i에서 p번 비트를 1로 바꿔줘야 한다.

a | b 비트 연산자를 활용하면 쉽게 해결할 수 있다.

cur = cur | (1 << p)

1 << p를 통해서 p번 비트만 1, 나머지 비트는 0인 값을 만들고 | 연산을 진행한다면 i번의 p번 비트는 1로 바뀌게 되고, 나머지 비트는 원래 상태를 유지하게 된다.

 

원소삭제

현재 상태 i에서 p번 원소를 삭제한다고 한다면, p번 비트를 0으로 바꿔줘야한다.

cur = cur & ~(1 << p);

 

원소 토글

p번 비트가 1이면 0, 0이면 1로 바꾸는 토클 연산도 쉽게 구현하 수 있다.

현재 상태 i에서 p번 원소가 있다면 삭제하고, 없다면 추가해본다.

 

아.. 오늘은 알고리즘만 했다...

진짜 이러면 안되는데. 좀 더 분발해보자