BOJ

    [Java] 백준 2146 (다리 만들기) Gold 3
    Algorithm/Baekjoon Online Judge

    [Java] 백준 2146 (다리 만들기) Gold 3

    Problem : https://www.acmicpc.net/problem/2146 2146번: 다리 만들기 여러 섬으로 이루어진 나라가 있다. 이 나라의 대통령은 섬을 잇는 다리를 만들겠다는 공약으로 인기몰이를 해 당선될 수 있었다. 하지만 막상 대통령에 취임하자, 다리를 놓는다는 것이 아깝다 www.acmicpc.net Approach BFS를 사용하여 풀이할 수 있는 문제이다. 여기서는 섬 인덱싱을 위한 BFS, 그리고 각 섬에서 수행되는 BFS 이렇게 두 가지의 BFS를 사용한다. 문제에서 요구하는 것은, 어떤 섬이든 길이가 최소가 되는 다리 하나를 놓는 것이다. 문제 풀이의 주요 순서는 다음과 같다. 섬 인덱싱을 수행한다. (BFS) 각각의 섬에서 가장 가까운 섬과의 거리를 구한다. (BFS) ..

    [Java] 벡준 16947 (서울 지하철 2호선) Gold 3
    Algorithm/Baekjoon Online Judge

    [Java] 벡준 16947 (서울 지하철 2호선) Gold 3

    Problem : https://www.acmicpc.net/problem/16947 16947번: 서울 지하철 2호선 첫째 줄에 역의 개수 N(3 ≤ N ≤ 3,000)이 주어진다. 둘째 줄부터 N개의 줄에는 역과 역을 연결하는 구간의 정보가 주어진다. 같은 구간이 여러 번 주어지는 경우는 없고, 역은 1번부터 N번까지 번호 www.acmicpc.net Approach 그래프 정보가 주어졌을 때, 사이클을 구하고, 그 사이클로부터 얼마나 멀리 떨어져 있는지를 구하는 문제였다. 먼저 주의할 점은, 노드의 개수가 N개이고, 간선의 개수도 N개이므로, 사이클(순환선)은 무조건 1개 존재한다는 것이다. 문제 풀이의 순서는 다음과 같다. 먼저 사이클 찾은 뒤, 사이클에 속하는 노드들을 표시한다. (cycle 배..

    [Java] 벡준 16929 (Two Dots) Gold 4
    Algorithm/Baekjoon Online Judge

    [Java] 벡준 16929 (Two Dots) Gold 4

    Problem : https://www.acmicpc.net/problem/16929 16929번: Two Dots 첫째 줄에 게임판의 크기 N, M이 주어진다. 둘째 줄부터 N개의 줄에 게임판의 상태가 주어진다. 게임판은 모두 점으로 가득차 있고, 게임판의 상태는 점의 색을 의미한다. 점의 색은 알파벳 대문 www.acmicpc.net Approach 행렬 정보가 주어졌을 때, 사이클이 존재하는지를 판단하는 문제였다. 사이클을 판별하는 방법은 여러가지가 있지만, 여기서는 DFS를 이용하였다. 모든 정점을 방문할 수 있도록, 방문하지 않은 모든 곳에서 DFS를 수행한다. 그 중에 사이클이 있다면, 더이상 진행할 필요가 없으므로 종료시켰다. 사이클을 판별하는 로직은 다음과 같다. 임의의 시작점에서 DFS를..

    [Java] 벡준 13023 (ABCDE) Gold 5
    Algorithm/Baekjoon Online Judge

    [Java] 벡준 13023 (ABCDE) Gold 5

    Problem : https://www.acmicpc.net/problem/13023 13023번: ABCDE 문제의 조건에 맞는 A, B, C, D, E가 존재하면 1을 없으면 0을 출력한다. www.acmicpc.net Approach DFS를 활용한 문제이다. 문제에서 요구하는게 이해가 어려울 수 있으나, 쉽게 얘기하자면 어느 하나의 노드에서 시작하여 깊이가 5이상인 그래프가 존재하는지를 판단하면 된다. 그래프의 최대 지름이 5 이상이면 1을 아니라면 0을 출력하면 된다. 그래프의 최대지름을 구하는 법은 다음과 같다. 임의의 노드에서 가장 먼(깊이가 가장 깊은) 노드를 찾는다. (DFS 로) 그 노드에서부터 다시 DFS를 진행하여 가장 먼 노드와의 길이를 측정한다. 두번의 DFS가 이루어져야 한다...

    [Java] 벡준 1248 (맞춰봐) Gold 3
    Algorithm/Baekjoon Online Judge

    [Java] 벡준 1248 (맞춰봐) Gold 3

    Problem : https://www.acmicpc.net/problem/1248 1248번: 맞춰봐 첫째 줄에 수열의 크기 N이 주어진다. N은 10보다 작거나 같은 자연수이다. 둘째 줄에는 N(N+1)/2 길이의 문자열이 주어진다. 처음 N개의 문자는 부호 배열의 첫 번째 줄에 해당하고, 다음 N-1개의 문 www.acmicpc.net Approach Backtracking을 이용하여 완전탐색(BruteForce)를 수행하는 문제이다. 이 문제에서 주의할 점을 좀 적어보겠다. 중복된 수로 수열을 만들 수 있다. 숫자 0 과 문자 '0'은 다르다. 수열을 완전히 만들고 검사하는 것이 아니라, 만드는 과정에서 검사가 이루어져야 한다. 먼저 주어진 문자열로 i ~ j까지의 합의 상태를 나타낸 s[i][j..

    [Java] 백준 1339 (단어 수학) Gold 4
    Algorithm/Baekjoon Online Judge

    [Java] 백준 1339 (단어 수학) Gold 4

    Problem : https://www.acmicpc.net/problem/1339 1339번: 단어 수학 첫째 줄에 단어의 개수 N(1 ≤ N ≤ 10)이 주어진다. 둘째 줄부터 N개의 줄에 단어가 한 줄에 하나씩 주어진다. 단어는 알파벳 대문자로만 이루어져있다. 모든 단어에 포함되어 있는 알파벳은 최대 www.acmicpc.net Approach 순열(Permutation) 을 이용한 완전탐색(BruteForce) 문제이다. 나는 입력에 따라 사용된 알파벳 개수를 세어, 조금이라도 시간을 단축시켜봤다. (사용된 알파벳 숫자가 10개면 말짱도루묵...) 주요 로직은 다음과 같다. 사용된 알파벳의 개수 A를 센다. (알파벳과 상수 값을 mapping 시킨다.) 9 ~ (9 - A)까지의 숫자를 가지고 순..

    [Java] 백준 17281 (⚾) Gold 4
    Algorithm/Baekjoon Online Judge

    [Java] 백준 17281 (⚾) Gold 4

    Problem : https://www.acmicpc.net/problem/17281 17281번: ⚾ ⚾는 9명으로 이루어진 두 팀이 공격과 수비를 번갈아 하는 게임이다. 하나의 이닝은 공격과 수비로 이루어져 있고, 총 N이닝 동안 게임을 진행해야 한다. 한 이닝에 3아웃이 발생하면 이닝이 종 www.acmicpc.net Approach BruteForce 문제이다. 순열(Permutation)을 활용하여 생길 수 있는 모든 경우의 수를 생각한다. 순열의 크기가 8이라서 가능한 일이다. 1번 타자 ~ 9번 타자까지 순서를 정해야한다. 하지만 4번 타자의 경우 이미 정해져있기 때문에 8명만 줄을 세우면 된다. 전체적인 로직은 다음과 같다. 1번타자 ~ 9번타자를 정한다. 야구게임을 시작한다. 주어진 이닝..

    [Java] 백준 17136 (색종이 붙이기) Gold 2
    Algorithm/Baekjoon Online Judge

    [Java] 백준 17136 (색종이 붙이기) Gold 2

    Problem : https://www.acmicpc.net/problem/17136 17136번: 색종이 붙이기 과 같이 정사각형 모양을 한 다섯 종류의 색종이가 있다. 색종이의 크기는 1×1, 2×2, 3×3, 4×4, 5×5로 총 다섯 종류가 있으며, 각 종류의 색종이는 5개씩 가지고 있다. 색종이를 크 www.acmicpc.net Approach BruteForce + DFS + Backtracking 문제이다. DP로도 풀 수 있을까 고민했지만, 색종이의 개수 제한도 있고 개수를 어떻게 세야할 지 감이 안와서 다른 방법을 생각했다. 색종이를 붙일 수 있는 모든 곳에 대해서 색종이 사이즈가 5, 4, 3, 2, 1인 색종이를 붙일 수 있는지 각각 검사한다. 현재 사용한 색종이의 개수가 최솟값보다 ..

    [Java] 백준 16637 (괄호 추가하기) Gold 3
    Algorithm/Baekjoon Online Judge

    [Java] 백준 16637 (괄호 추가하기) Gold 3

    Problem : https://www.acmicpc.net/problem/16637 16637번: 괄호 추가하기 첫째 줄에 수식의 길이 N(1 ≤ N ≤ 19)가 주어진다. 둘째 줄에는 수식이 주어진다. 수식에 포함된 정수는 모두 0보다 크거나 같고, 9보다 작거나 같다. 문자열은 정수로 시작하고, 연산자와 정수가 www.acmicpc.net Approach 입력값이 크지 않아, DFS + BruteForce로 풀이가 가능한 문제이다. 중첩된 괄호는 허용하지 않으므로, 주어진 식의 앞에서부터 괄호를 씌운 경우와 씌우지 않은 경우 두가지 경우를 모두 고려한다. 그렇게 가지를 치며 모든 경우를 조사한다.(BruteForce) 그중 가장 큰 결과값을 내는 값들을 ans에 갱신한다. Code import ja..

    [Java] 백준 2252 (줄 세우기) Gold 2
    Algorithm/Baekjoon Online Judge

    [Java] 백준 2252 (줄 세우기) Gold 2

    Problem : https://www.acmicpc.net/problem/2252 2252번: 줄 세우기 첫째 줄에 N(1≤N≤32,000), M(1≤M≤100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의미이 www.acmicpc.net Approach 위상정렬(Topological Sort) 을 활용하는 기본문제이다. 위상정렬을 구현할 줄 안다면 별다른 처리는 더 필요 없는 문제였다. 일반적인 위상정렬처럼 inDegree 배열을 구성하고, inDegree가 0인 노드들을 큐에 넣고 뽑고를 반복하며 진행한다. Code import java.io.*; import java.util...

티스토리툴바