어제 공부한 것들...(12월 13일)

 

어제 하루 동안은 거의 알고리즘 문제 하나 푸는데 시간을 거의 다 쏟아부은거 같다. 다른 공부나 해야 할 일들도 조금 한거 같지만.

1.

1931번: 회의실 배정 (acmicpc.net)

1931번: 회의실 배정

위 문제는 활동 선택 문제( activity selection problem )에 관한 것이다. 일정 시간동안 최대한 많은 활동을 선택하는 문제인데, 이 문제를 풀려면 그리디 접근법으로 풀어야 한다. 종료 시간이 빠를수록 최대한 많은 활동을 선택할 수 있다는 글로벌한 원칙이 적용된다. 그래서 우선 종료시간이 빠른 순으로 정렬을 하고, 종료 시간이 같다면 시작시간이 빠른 활동을 우선적으로 접근할 수 있도록 정렬하였다.

나 같은 경우, 처음에 이 문제를 bfs 같은 최단 경로 탐색 방식으로 그리디하게 접근하여 풀려고 시도하였으나 실패하였고 그 다음으로, DP(동적 계획법, 다이나믹 프로그래밍) 방식으로 접근하여 풀려고 했다. 아래는 시도했던 코드이다.

 

package backjoon;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.util.*;

public class _1931_dp_failed{
    public static void main(String[] args) throws FileNotFoundException {
        Scanner sc = new Scanner(new FileReader(args[0]));
        int N = sc.nextInt();
        HashMap<Integer, TreeSet<Integer>> times = new HashMap<>();
        TreeMap<Integer, Integer> dpTable = new TreeMap<>();
        for(int i = 0; i < N; i++){
            int temp = sc.nextInt();
            if(times.get(temp) == null){
                times.put(temp, new TreeSet<>());
            }
            dpTable.put(temp, 0);
            times.get(temp).add(sc.nextInt());
        }
        if(!dpTable.containsKey(Integer.MAX_VALUE)){
            dpTable.put(Integer.MAX_VALUE, 0);
        }

        List<Integer> keys = new ArrayList<>(times.keySet());
        Collections.sort(keys);
        for(int key : keys){
            for(int i : times.get(key)){
                if(i == key){
                    dpTable.put(key, dpTable.get(key) + 1);
                } else {
                    dpTable.put(dpTable.higherKey(i), Math.max(dpTable.get(dpTable.higherKey(i)), dpTable.get(key) + 1));
                }
            }
        }
        System.out.println(Collections.max(dpTable.values()));
    }
}

 

위의 코드로 제시된 입력 예제를 넣었을 시 일단 해당 문제의 정답인 출력 값과 같은 값이 나왔다. 그래서 제출하였으나 틀렸다는 결과가 나왔다. 어디가 문제인지 아직 발견하지 못하였으나 그리디한 접근 방식으로 봤을 때 문제가 될 부분이 있는지 다시 확인해봐야 할거 같다.

 

아래는 인터넷의 어느 블로그에서 확인한 그리디 접근법을 통해 푼 코드이다.

 

import java.util.*;

public class Main{
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int[][] table = new int[N][2];
        for(int i = 0; i < N; i++){
            int start = sc.nextInt();
            int end = sc.nextInt();
            table[i][0] = start;
            table[i][1] = end;
        }
        Arrays.sort(table, (a, b) -> {
            if(a[1] == b[1]){
                return a[0] - b[0];
            } else {
                return a[1] - b[1];
            }
        });

        int count = 0;
        int previousEnd = 0;
        for(int i = 0; i < N; i++){
            if(previousEnd <= table[i][0]){
                previousEnd = table[i][1];
                count++;
            }
        }
        System.out.println(count);
    }
}

 

 

 

2.

마지막으로 추가적으로 풀었던 문제는 색종이 만들기 란 문제이다. 재귀와 분할정복을 통해 문제를 어렵지 않게 풀 수 있을 것으로 생각된다. 하지만 나는 먼저 클래스를 생성하여 풀면 재밌을거 같단 생각이 들어서 한번 시도해봤다. 결과적으론 디버깅을 거듭하였으나 정답이 나오진 않았다. 일단 문제를 맞춘 뒤 다시 검토해봐야 할거 같다.

2630번: 색종이 만들기 (acmicpc.net)

2630번: 색종이 만들기

 

아래는 클래스를 활용하여 타이핑한 코드이다. 색다르게 접근하고 싶었던 바램이 커서 이렇게 작성하였지만 메모리 문제 등으로 단순 문제 풀이용으론 비효율적이라 판단된다. setter/getter 메소드도 설정하지 않았음을 감안해야 한다.

import java.io.FileNotFoundException;
import java.io.FileReader;
import java.util.*;

import java.util.*;

public class Main{
    public static void main(String[] args) throws FileNotFoundException {
        Scanner sc = new Scanner(new FileReader("./test.text"));
        int n = sc.nextInt();
        boolean[][] _2dArray = new boolean[n][n];
        int tempCount = 0;
        for(int i = 0; i < n; i++){
            for(int j= 0; j < n; j++){
                int temp = sc.nextInt();
                if(temp == 0){
                    _2dArray[i][j] = true;
                } else{
                    _2dArray[i][j] = false;
                }
            }
        }
        int[] result = new int[2];

        UntilIFoundYou uify = new UntilIFoundYou(n, _2dArray);
        uify.checkBlueAndWhite(n);
        result[0] = uify.resultWhite;
        result[1] = uify.resultBlue;
        System.out.println(result[0]);
        System.out.println(result[1]);
    }

}

class UntilIFoundYou {

    static boolean[][] _2dArray; // 0 is true, 1 is false
    int currentN;
    int startRow;
    int startCol;
    static int resultWhite;
    static int resultBlue;

    byte WhiteOrBlue; // 0 is white, 1 is blue
    UntilIFoundYou westNorth;
    UntilIFoundYou eastNorth;
    UntilIFoundYou westSouth;
    UntilIFoundYou eastSouth;

    public UntilIFoundYou(){

    }

    public UntilIFoundYou(int n, int startRow, int startCol){
        this.WhiteOrBlue = 2;
        this.currentN = n;
        this.startRow = startRow;
        this.startCol = startCol;
        if(n == 1){
            WhiteOrBlue = (byte)((_2dArray[startRow][startCol]) ? 0 : 1);
          westNorth = null;
          eastNorth = null;
          westSouth = null;
          eastSouth = null;
        
            return;
        } else{
        westNorth = new UntilIFoundYou(currentN / 2, startRow, startCol);
        eastNorth = new UntilIFoundYou(currentN / 2, startRow, startCol + currentN/2);
        westSouth = new UntilIFoundYou(currentN / 2, startRow + currentN/2, 0);
        eastSouth = new UntilIFoundYou(currentN / 2, startRow + currentN/2, startCol + currentN/2);
        }
    }

    public UntilIFoundYou(int n, boolean[][] _2dArray){
        this._2dArray = _2dArray;
        currentN = n;
        westNorth = new UntilIFoundYou(n / 2, 0, 0);
        eastNorth = new UntilIFoundYou(n / 2, 0, n/2);
        westSouth = new UntilIFoundYou(n / 2, n/2, 0);
        eastSouth = new UntilIFoundYou(n / 2 , n/2, n/2);
    }

    public byte checkBlueAndWhite(int n){
        if(n == 1){
            return WhiteOrBlue;
        } else{
            byte white = 0;
            byte blue = 0;
            byte[] result = new byte[4];
            byte resultCount = 0;
            result[0] = westNorth.checkBlueAndWhite(n / 2);
            result[1] = eastNorth.checkBlueAndWhite(n / 2);
            result[2] = westSouth.checkBlueAndWhite(n / 2);
            result[3] = eastSouth.checkBlueAndWhite(n / 2);

            for(byte b : result){
                if(b == 0){
                    white++;
                } else if(b == 1){
                    blue++;
                } else if(b == 2){
                    return  2;
                }
                resultCount += b;
            }
            if(resultCount == 4){
                WhiteOrBlue = 1;
                return WhiteOrBlue;
            } else if(resultCount == 0){
                WhiteOrBlue = 0;
                return WhiteOrBlue;
            } else{
                System.out.println("layer is " + n +" , white " + white + " , blue " + blue + " crashed where " + this.startRow + " " + this.startCol);
                this.resultWhite += white;
                this.resultBlue += blue;
                return 2; // 2 means null
            }
        }
    }
}