Problem Solving

Problem Solving

    [백준, BOJ 1799] 비숍 (java)
    Problem Solving/BOJ

    [백준, BOJ 1799] 비숍 (java)

    https://www.acmicpc.net/problem/1799메모리: 15,996 KB , 시간: 192 ms사용 알고리즘: 백트래킹일단 이 문제에서 내가 생각해 낸 아이디어는,체스판에서 왼쪽 위 -> 오른쪽 아래로 내려오는 라인들을 그었을 때, 각 라인 위에 위치한 비숍들은 다른 라인에 영향을 줄 수 없다.마찬가지로 오른쪽 위부터 왼쪽 아래로 내려오는 라인들을 그었을 때, 각 라인 위에 위치한 비숍들은 다른 라인에 영향을 줄 수 없다. 이 아이디어를 가지고 오른쪽 위 -> 왼쪽 아래로 내려오는 라인들을 해당 라인에서 비숍을 하나 고르고 다른 라인에서 비숍을 고르러 가는 방법으로 백트래킹 했다.(비숍을 하나 골랐을 때, 왼쪽 위 -> 오른쪽 아래 라인에 이미 비숍이 있으면 놓을 수 없다.)그런데 이 ..

    [백준, BOJ 6443] 애너그램 (java)
    Problem Solving/BOJ

    [백준, BOJ 6443] 애너그램 (java)

    https://www.acmicpc.net/problem/6443메모리: 34,256 KB , 시간: 496 ms사용 알고리즘: 백트래킹, 문자열입력받은 문자열에서 사용한 문자의 개수를 담는 visited 배열을 만들어,인덱스에 해당하는 문자가 몇 개 사용됐는지 체크해준다. combi 메소드에서 백트래킹을 통해 현재 사용할 수 있는 문자 중 사전 순으로 빠른 문자부터 스택에 담아주고,사용할 수 있는 문자 개수를 줄여주며 애너그램 조합을 구해주는 방식을 사용했다.import java.io.BufferedReader;import java.io.InputStreamReader;import java.util.Stack;public class Main { static char[] string; stat..

    [백준, BOJ 2211] 네트워크 복구 (java)
    Problem Solving/BOJ

    [백준, BOJ 2211] 네트워크 복구 (java)

    https://www.acmicpc.net/problem/2211메모리: 131,376 KB , 시간: 864 ms사용 알고리즘: 데이크스트라, 그래프 이론, 최단 경로이 문제에서 주의해야 할 점은 '슈퍼컴퓨터가 다른 컴퓨터들과 통신하는데 걸리는 최소 시간이, 원래의 네트워크에서 통신하는데 걸리는 최소 시간보다 커져서는 안 된다.'는 점이다.이 부분을 간과하고 호기롭게 크루스칼 알고리즘으로 풀었다가 틀리고 나서야 문제를 다시 보고 이 점을 알았다. 따라서 이 문제는 크루스칼 알고리즘이 아니라 다익스트라 알고리즘을 사용해야 하는데, 관건은 최단 거리에 사용한 회선 정보를 출력해야 하는 것이다.이 문제를 해결하기 위해 다익스트라에서 사용하는 우선순위 큐에 넣을 Route 클래스를 만들고 객체에 경로의 마지막..

    [백준, BOJ 1520] 내리막 길 (java)
    Problem Solving/BOJ

    [백준, BOJ 1520] 내리막 길 (java)

    https://www.acmicpc.net/problem/1520메모리: 34,424 KB , 시간: 396 ms사용 알고리즘: 깊이 우선 탐색, 다이나믹 프로그래밍, 그래프 이론, 그래프 탐색import java.io.BufferedReader;import java.io.InputStreamReader;import java.util.StringTokenizer;public class Main { static int M, N; static int[][] map; static int[][] can_move; static int[] dx = {-1, 1, 0, 0}; static int[] dy = {0, 0, -1, 1}; public static void main(Stri..

    [백준, BOJ 16432] 떡장수와 호랑이 (java)
    Problem Solving/BOJ

    [백준, BOJ 16432] 떡장수와 호랑이 (java)

    https://www.acmicpc.net/problem/16432메모리: 16,364 KB , 시간: 176 ms사용 알고리즘: 깊이 우선 탐색, 다이나믹 프로그래밍, 그래프 이론, 그래프 탐색import java.io.BufferedReader;import java.io.InputStreamReader;import java.util.StringTokenizer;public class Main { static int N; static boolean[][] rice_cake; static boolean[][] visited; static int[] pick; public static void main(String[] args) throws Exception{ Buf..

    [백준, BOJ 1092] 배 (java)
    Problem Solving/BOJ

    [백준, BOJ 1092] 배 (java)

    https://www.acmicpc.net/problem/1092메모리: 16,204 KB , 시간: 156 ms사용 알고리즘: 그리디 알고리즘, 정렬import java.io.BufferedReader;import java.io.InputStreamReader;import java.util.Arrays;import java.util.Collections;import java.util.StringTokenizer;public class Main { public static void main(String[] args) throws Exception{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); ..

    [백준, BOJ 2233] 함께 블록 쌓기 (java)
    Problem Solving/BOJ

    [백준, BOJ 2233] 함께 블록 쌓기 (java)

    https://www.acmicpc.net/problem/2233메모리: 16,156 KB , 시간: 156 ms사용 알고리즘: 자료구조, 그래프 이론, 최소 공통 조상, 스택, 트리import java.io.BufferedReader;import java.io.InputStreamReader;import java.util.Stack;import java.util.StringTokenizer;public class Main { public static void main(String[] args) throws Exception{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int N = I..

    [백준, BOJ 1062] 가르침 (java)
    Problem Solving/BOJ

    [백준, BOJ 1062] 가르침 (java)

    https://www.acmicpc.net/problem/1062메모리: 89,116 KB , 시간: 264 ms사용 알고리즘: 백트래킹, 브루트포스 알고리즘import java.io.BufferedReader;import java.io.InputStreamReader;import java.util.*;public class Main { static int K; static int[] count; static ArrayList> list; static boolean[] pick; static int result; public static void main(String[] args) throws Exception{ BufferedReader br = new Bu..

    [백준, BOJ 18427] 함께 블록 쌓기 (java)
    Problem Solving/BOJ

    [백준, BOJ 18427] 함께 블록 쌓기 (java)

    https://www.acmicpc.net/problem/18427메모리: 52,680 KB , 시간: 352 ms사용 알고리즘: 다이나믹 프로그래밍, 배낭 문제import java.io.BufferedReader;import java.io.InputStreamReader;import java.util.HashMap;import java.util.StringTokenizer;public class Main { private static final int MOD = 10_007; public static void main(String[] args) throws Exception{ BufferedReader br = new BufferedReader(new InputStreamRead..

    [백준, BOJ 2812] 크게 만들기 (java)
    Problem Solving/BOJ

    [백준, BOJ 2812] 크게 만들기 (java)

    https://www.acmicpc.net/problem/2812메모리: 40,472 KB , 시간: 392 ms사용 알고리즘: 자료 구조, 그리디 알고리즘, 스택import java.io.BufferedReader;import java.io.InputStreamReader;import java.util.Deque;import java.util.LinkedList;import java.util.StringTokenizer;public class Main { public static void main(String[] args) throws Exception{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in));..

티스토리툴바