📙[Algo] 24.03.01 알고리즘

알고리즘 문제) BOJ 1018. 체스판 다시 칠하기

• 링크 : https://www.acmicpc.net/problem/1018

문제 요약

• M*N 크기 보드
• 검정색 또는 흰색 칸으로 칠해져 있다
• 이 보드를 잘라서 8*8 크기의 체스판을 만들려고 함
• 체스판은 검,흰이 번갈아 칠해져야 함
  • 즉, 변을 공유하는 두 개의 사각형은 다른 색으로 칠해져야 함
  • 체스판을 칠하는 경우는 총 두 종류 → 맨 왼쪽 위가 흰 또는 검
• 8*8크기의 체스판으로 잘라낸 후 몇 개의 정사각형을 다시 칠해서 체스판을 만들려고 할 때 칠해야할 정사각형 최소 개수 구하라

시간 제한

• 1초

입력

• N M
  • 8≤N,M≤50
• N개의 줄에는 보드의 각 행의 상태가 주어진다
  • B: 검은색
  • W: 흰색

출력

• 다시 칠해야 하는 정사각형 개수 최솟값?

접근법

1. 완전 탐색으로 생각하기
   • (0,0)부터 8*8크기 체스판을 돌면서 맨위왼쪽이 W일 경우 B일경우 두 가지 케이스일 때 칠해야할 정사각형 개수를 카운트 한다.
   • 보드 크기가 최대 50*50이 가능하므로 만들 수 있는 모든 체스판을 본다고 할 때 (0,0)~(42,42)까지 총 42개의 경우를 보고 매 케이스마다 맨위왼쪾 구석이 W, B일 경우인 2가지 경우를 봐야한다. 또 그때마다 64개칸을 도니,,,
   • 42264 개 정도의 시간복잡도가걸린다. ⇒ 완탐 돌려도 됨
2. 체스판 개수 세기
   • 색은 (짝수, 짝수) , (홀수, 홀수) / (짝수, 홀수) (홀수, 짝수)로 나뉘어서 같은 색이 칠해진다.
   • 처음 시작하는 칸의 row 값이 짝수일 경우 → 해당 칸의 색상은 (짝,짝) 과 (홀,홀)인 곳에만 칠해져야함
   • 홀수일 경우는 (짝,홀)(홀,짝)

코드

import java.io.*;
import java.util.*;

public class Main {
    static int N, M;
    static char[][] boards;
    static int cnt;
    static int answer = Integer.MAX_VALUE;

    static int onPaint(int row, int col, char color) {
        cnt = 0;
        if (row % 2 == 0) {
            for (int i = row; i < row + 8; i++) {
                for (int j = col; j < col + 8; j++) {
                    if ((i % 2 == 0 && j % 2 == 0) || (i % 2 == 1 && j % 2 == 1)) {
                        if (boards[i][j] != color) cnt++;
                    } else {
                        if (boards[i][j] == color) cnt++;
                    }
                }
            }
        } else {
            for (int i = row; i < row + 8; i++) {
                for (int j = col; j < col + 8; j++) {
                    if ((i % 2 == 0 && j % 2 == 1) || (i % 2 == 1 && j % 2 == 0)) {
                        if (boards[i][j] != color) cnt++;
                    } else {
                        if (boards[i][j] == color) cnt++;
                    }
                }
            }
        }

        return cnt;
    }

    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;

        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        boards = new char[N][M];
        String str;
        for (int i = 0; i < N; i++) {
            str = br.readLine();
            for (int j = 0; j < M; j++) {
                boards[i][j] = str.charAt(j);
            }
        }

        for (int i = 0; i <= N - 8; i++) {
            for (int j = 0; j <= M - 8; j++) {
                // 시작 포인트 설정 (i,j)

                answer = Math.min(answer, Math.min(onPaint(i, j, 'B'), onPaint(i, j, 'W')));
            }
        }

        bw.write(String.valueOf(answer));
        bw.flush();
        bw.close();
        br.close();
    }
}

 

알고리즘 문제) BOJ 10866. 덱

• 링크 : https://www.acmicpc.net/problem/10866

문제 요약

• 덱 구현하기
  • push_front X : 정수 X를 덱의 앞에 넣는다.
  • push_back X : 정수 X를 덱의 뒤에 넣는다
  • pop_front : 덱의 가장 앞에 있는 수를 빼서 출력, 없다면 -1 출력
  • pop_back : 덱의 가장 뒤에 있는 수를 빼서 출력, 없다면 -1 출력
  • size : 덱에 들어있는 정수 개수 출력
  • empty : 비어있으면 1, 없으면 0 출력
  • front : 덱의 가장 앞에 있는 정수 출력, 없다면 -1 출력
  • back : 덱의 가장 뒤에 있는 정수 출력, 없다면 -1 출력

시간 제한

• 0.5초

입력

• 명령의 수 N
  • 1~10,000
• 명령이 하나씩 주어진다.
  • 같이 주어지는 정수는 1~10만이하

출력

• 명령이 주어질 때마다 결과값 출력

접근법

• 명령어가 최대 1만개까지 가능하니까 넉넉하게 2만개 배열을 만들어두고 구현

코드

import java.io.*;
import java.util.*;

public class Main {
    static int[] deque = new int[20010];
    static int size = 0;

    static void pushFront(int x) {
        int tmp1 = deque[0];
        int tmp2;
        size++;
        for (int i = 0; i < size - 1; i++) {
            tmp2 = deque[i + 1];
            deque[i + 1] = tmp1;
            tmp1 = tmp2;
        }

        deque[0] = x;
    }

    static void pushBack(int x) {
        deque[size] = x;
        size++;
    }

    static int popFront() {
        if (size == 0) {
            return -1;
        } else {
            int num = deque[0];

            for (int i = 0; i < size - 1; i++) {
                deque[i] = deque[i + 1];
            }

            size--;
            return num;
        }
    }

    static int popBack() {
        if (size == 0) {
            return -1;
        } else {
            int num = deque[size - 1];
            size--;
            return num;
        }
    }

    static int getSize() {
        return size;
    }

    static int isEmpty() {
        if (size == 0) return 1;
        else return 0;
    }

    static int getFront() {
        if (size == 0) {
            return -1;
        } else {
            return deque[0];
        }
    }

    static int getBack() {
        if (size == 0) {
            return -1;
        } else {
            return deque[size - 1];
        }
    }

    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;
        StringBuilder sb = new StringBuilder();

        int N = Integer.parseInt(br.readLine());
        int x;
        String cmd;
        while (N-- > 0) {
            st = new StringTokenizer(br.readLine());
            cmd = st.nextToken();

            if (cmd.equals("push_front")) {
                x = Integer.parseInt(st.nextToken());
                pushFront(x);
            } else if (cmd.equals("push_back")) {
                x = Integer.parseInt(st.nextToken());
                pushBack(x);
            } else if (cmd.equals("pop_front")) {
                sb.append(popFront() + "\\n");
            } else if (cmd.equals("pop_back")) {
                sb.append(popBack() + "\\n");
            } else if (cmd.equals("size")) {
                sb.append(getSize() + "\\n");
            } else if (cmd.equals("empty")) {
                sb.append(isEmpty() + "\\n");
            } else if (cmd.equals("front")) {
                sb.append(getFront() + "\\n");
            } else if (cmd.equals("back")) {
                sb.append(getBack() + "\\n");
            }

        }

        bw.write(String.valueOf(sb));
        bw.flush();
        bw.close();
        br.close();
    }
}

 

알고리즘 문제) BOJ 11866. 요세푸스 문제 0

• 링크 : https://www.acmicpc.net/problem/11866

문제 요약

• 1번부터 N번까지 N명의 사람이 원을 이루면서 앉아 있다
• 양의 정수 K(≤N)이 주어졌을 때, 순서대로 K번째 사람을 제거한다.
• 이 과정을 N명의 사람이 모두 제거될 때까지 한다.
• (N,K)-요세푸스 순열 : 원에서 제거되는 순서
  • (7, 3)-요세푸스 순열은 <3, 6, 2, 7, 5, 1, 4>
• (N,K)-요세푸스 순열을 구해라!

시간 제한

• 2초

입력

• N K
  • 1≤K≤N≤1,000

출력

• 요세푸스 순열 출력

접근법

• N=7, K=3일 때
  3 4 5 6 7 1 2
  6 7 1 2 4 5
  2 4 5 7 1
  …
• 큐에 3번째 전까지 빼고 뒤로 담고 3번쨰 되는 애는 출력 후 제거

코드

import java.io.*;
import java.util.*;

public class Main {

    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;
        StringBuilder sb = new StringBuilder();
        sb.append("<");

        st  = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());

        Queue<Integer> q = new LinkedList<>();
        for (int i = 1; i <= N; i++) {
            q.offer(i);
        }

        int nth = 0;
        while (!q.isEmpty()) {
            nth++;
            if (nth == K) {
                sb.append(q.poll());
                if (q.size() > 0) {
                    sb.append(", ");
                }
                nth = 0;
            } else {
                q.offer(q.poll());
            }
        }

        sb.append(">");
        bw.write(String.valueOf(sb));
        bw.flush();
        bw.close();
        br.close();
    }
}

 

알고리즘 문제) BOJ 11050. 이항 계수 1

• 링크 : https://www.acmicpc.net/problem/11050

문제 요약

• 자연수 N, K가 주어졌을 때 이항계수 출력하는 프로그램 작성

시간 제한

• 1초

입력

• N K
  • 1≤N≤10
  • 0≤K≤N

출력

• 이항계수 출력

코드

import java.io.*;
import java.sql.SQLOutput;
import java.util.*;

public class Main {

    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;

        st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());

        int top = N;
        int bottom = K;
        while (K-- > 1) {
            top *= --N;
            bottom *= K;
        }

        bw.write(K == -1 ? "1" : String.valueOf(top / bottom));
        bw.flush();
        bw.close();
        br.close();
    }
}