📙[Algo] 24.03.21 알고리즘

알고리즘 문제) BOJ 5585. 거스름돈

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

문제 요약

• 500엔. 100엔, 50엔, 10엔, 5엔, 1엔
• 1000엔을 냈을 때 거스름돈 개수를 최대한 적게 주려고 함 이때 잔돈 개수 구하기

시간 제한

• 1초

입력

• 지불할 돈 (1~1000미만 정수)

출력

• 잔돈에 포함된 매수

접근법

• 큰 단위부터 주기

코드

import java.io.*;
//import java.util.StringTokenizer;

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;

        int remain = 1000 - Integer.parseInt(br.readLine());
        int[] money = {500, 100, 50, 10, 5, 1};

        int cnt = 0, idx = 0;
        while (remain > 0) {
            cnt += remain / money[idx];
            remain %= money[idx];
            idx++;
        }

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

 

알고리즘 문제) BOJ 2606. 바이러스

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

문제 요약

• 1번 컴퓨터가 바이러스에 걸림
• 컴퓨터와 서로 연결되어 있는 정보가 주어졌을 때, 1번 컴퓨터를 통해 바이러스에 걸리게 되는 컴퓨터 수 구하기

시간 제한

• 1초

입력

• 컴퓨터 수(100이하 자연수) - 컴퓨터 번호는 1번부터 차례대로 매겨짐
• 네트워크상 직접 연결되어 있는 쌍의 수
• 쌍의 수만큼 한 줄 씩 연결 정보 번호 쌍이 주어짐

출력

• 1번 컴퓨터가 바이러스에 걸렸을 때, 1번 컴퓨터를 통해 걸리게 되는 컴퓨터 수?

접근법

• 인접행렬로 연결 관계 구현하기
  • DFS로 연결된 곳 방문하며 카운팅
• 인접리스트

코드

• 인접행렬로 구현

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

public class Main {
    static int N, E;
    static int[][] arr;
    static boolean[] visited;
    static int cnt;

    static void dfs(int node) {
        visited[node] = true;

        for (int i = 1; i <= N; i++) {

            if (visited[i]) continue;

            if (arr[node][i] == 1 && arr[i][node] == 1) {
                cnt++;
                dfs(i);
            }
        }
    }

    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;

        N = Integer.parseInt(br.readLine());
        E = Integer.parseInt(br.readLine());

        arr = new int[N + 10][N + 10];
        int node1, node2;
        for (int i = 0; i < E; i++) {
            st = new StringTokenizer(br.readLine());
            node1 = Integer.parseInt(st.nextToken());
            node2 = Integer.parseInt(st.nextToken());

            arr[node1][node2] = 1;
            arr[node2][node1] = 1;
        }

        visited = new boolean[N + 1];

        dfs(1);

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

 

알고리즘 문제) BOJ 11724. 연결 요소의 개수

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

문제 요약

• 무방향 그래프 → 연결요소 개수 구하기

시간 제한

• 3초

입력

• 정점의 개수 N, 간선의 개수 M
  • 1≤N≤1000
  • 0≤M≤N*(N-1)/2

출력

• 연결요소 개수 출력

접근법

• dfs로 방문하지 않은 노드 하나를 방문해서 끝까지 연결된 요소 방문하기 ⇒ 반복

코드

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

public class Main {
    static int N, E;
    static int[][] arr;

    static int cnt;
    static boolean[] visited;

    static void dfs(int node) {
        visited[node] = true;

        for (int i = 1; i <= N; i++) {
            if (visited[i] || arr[node][i] == 0) continue;

            dfs(i);
        }
    }

    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());
        E = Integer.parseInt(st.nextToken());

        arr = new int[N + 1][N + 1];
        int node1, node2;
        for (int i = 0; i < E; i++) {
            st = new StringTokenizer(br.readLine());
            node1 = Integer.parseInt(st.nextToken());
            node2 = Integer.parseInt(st.nextToken());

            arr[node1][node2] = 1;
            arr[node2][node1] = 1;
        }

        visited = new boolean[N + 1];

        for (int i = 1; i <= N; i++) {

            if (visited[i]) continue;
            dfs(i);
            cnt++;
        }

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

 

알고리즘 문제) BOJ 2667. 단지번호붙이기

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

문제 요약

• 1: 집 있는곳, 0: 집 없는 곳
• 단지 : 지도끼리 연결된 집의 모임(상하좌우로 붙어있는 경우)
• 단지 수를 출력하고, 그 단지에 속하는 집의 수를 오름차순으로 정렬하여 출력

시간 제한

• 1초

입력

• 지도 크기 N
  • 5≤N≤25
• N개의 줄에 지도가 주어짐
  • 0 : 집X, 1: 집O

출력

• 총 단지 수 출력
• 각 단지 내 집의 수 오름차순 출력

접근법

• 연결요소의 개수 구하기
• 각 연결요소 구하면서 방문하는 노드 수 카운트

코드

import java.io.*;
import java.util.ArrayList;
import java.util.Collections;

public class Main {
    static int N;
    static int[][] map;
    static boolean[][] visited;
    static int[] delR = {-1, 1, 0, 0};
    static int[] delC = {0, 0, -1, 1};
    static int cnt;
    static int danji;
    static ArrayList<Integer> list = new ArrayList<>();

    static boolean binaryCheck(int row, int col) {
        return 0 <= row && 0 <= col && row < N && col < N;
    }

    static void dfs(int row, int col) {
        cnt++;
        visited[row][col] = true;

        int mrow, mcol;
        for (int dir = 0; dir < 4; dir++) {
            mrow = row + delR[dir];
            mcol = col + delC[dir];

            if (!binaryCheck(mrow,mcol) || visited[mrow][mcol] || map[mrow][mcol] == 0) continue;

            dfs(mrow, mcol);
        }

    }

    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());

        map = new int[N][N];
        String input;
        for (int i = 0; i < N; i++) {
            input = br.readLine();
            for (int j = 0; j < N; j++) {
                map[i][j] = input.charAt(j) - '0';
            }
        }

        visited = new boolean[N][N];

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (visited[i][j] || map[i][j] == 0) continue;

                danji++;
                cnt = 0;
                dfs(i, j);
                list.add(cnt);
            }
        }

        Collections.sort(list);

        StringBuilder sb = new StringBuilder();
        sb.append(danji + "\\n");
        for (int i = 0; i < list.size(); i++) {
            sb.append(list.get(i) + "\\n");
        }

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