매일 Algorithm

백준 11724번 (그래프 이론)

import java.util.Scanner;

public class problem249 {

    static int n;
    static int m;
    static int[][] graph;
    static boolean visit[];

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        n = in.nextInt();
        m = in.nextInt();
        graph = new int[1001][1001]; // 범위 지정
        visit = new boolean[1001]; // 범위 지정

        int a, b;
        for (int i = 0; i < m; i++) {
            a = in.nextInt();
            b = in.nextInt();
            graph[a][b] = graph[b][a] = 1; // 간선 연결
        }

        int result = 0;

        // DFS 탐색
        for (int i = 1; i <= n; i++) {
            if (!visit[i]) {
                DFS(i);
                result++;
            }
        }
        System.out.println(result);

    }

    private static void DFS(int input) {
        // 방문한 노드일경우
        if (visit[input]) {
            return;
        }
        // 방문한 노드가 아닐경우
        else {
            visit[input] = true; // 방문처리
            for (int i = 1; i <= n; i++) {
                if (graph[input][i] == 1) {
                    // 연결된 노드가 있으면 노드 깊이까지 탐색
                    DFS(i);
                }
            }
        }
    }
}

백준 1920번 (이분 탐색)

import java.util.Arrays;
import java.util.Scanner;

public class problem250 {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);

        int n = in.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = in.nextInt();
        }
        // 이분 탐색을 위한 정렬
        Arrays.sort(arr);
        int m = in.nextInt();
        for (int j = 0; j < m; j++) {
            boolean flag = false; // 찾지 못한경우를 false로 정의
            int target = in.nextInt();
            int start = 0;
            int end = arr.length - 1;

            // 1 2 3 4 5
            while (start <= end) {
                int midIndex = (start + end) / 2; // 중간 인덱스 지정
                int midValue = arr[midIndex]; // 중간 값 지정
                if (midValue > target) {
                    end = midIndex - 1; // 중간 인덱스 - 1
                } else if (midValue < target) {
                    start = midIndex + 1; // 중간 인덱스 + 1
                } else {
                    flag = true;
                    break;
                }
            }
            if (flag) {
                System.out.println(1);
            } else {
                System.out.println(0);
            }
        }
    }
}

백준 1541번 (그리디)

import java.util.Scanner;

public class problem251 {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);

        String ex = in.nextLine();
        String[] arr = ex.split("-");

        int result = 0;
        for (int i = 0; i < arr.length; i++) {

            // "55" - "50 + 40"
            int total = mySum(arr[i]);
            // 맨 앞의 수일경우
            if (i == 0) {
                result += total;
            } else {
                result -= total;
            }
        }
        System.out.print(result);

    }

    // "-" 으로 나뉜 문자열을 +기준으로 누적합
    private static int mySum(String str) {
        int sum = 0;
        // []롤 하여 인식 되게한다.
        String[] temp = str.split("[+]");
        for (int i = 0; i < temp.length; i++) {
            // +로 나뉜 배열의 누적합
            sum += Integer.parseInt(temp[i]);
        }
        return sum;
    }
}