Algorithm

    [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...

    [Java] 백준 2239 (스도쿠) Gold 4
    Algorithm/Baekjoon Online Judge

    [Java] 백준 2239 (스도쿠) Gold 4

    Problem : https://www.acmicpc.net/problem/2239 2239번: 스도쿠 스도쿠는 매우 간단한 숫자 퍼즐이다. 9×9 크기의 보드가 있을 때, 각 행과 각 열, 그리고 9개의 3×3 크기의 보드에 1부터 9까지의 숫자가 중복 없이 나타나도록 보드를 채우면 된다. 예를 들어 다 www.acmicpc.net Approach 유명한 스도쿠 게임을 구현하는 문제였다. 사용되는 알고리즘은 백트랙킹이다. 비어있는 칸을 백트랙킹을 하며, 스도쿠에서 중요한 가로, 세로, 3x3 영역을 검사하며 놓을 수 있는지를 판단한다. 3x3 영역 부분은 3x3 영역의 좌상위치를 구한 뒤, 거기서부터 x, y 좌표 + 3까지를 검사했다. Code import java.io.*; import java.u..

    [Java] 백준 2213 (트리의 독립집합) Gold 1
    Algorithm/Baekjoon Online Judge

    [Java] 백준 2213 (트리의 독립집합) Gold 1

    Problem : https://www.acmicpc.net/problem/2213 2213번: 트리의 독립집합 첫째 줄에 트리의 정점의 수 n이 주어진다. n은 10,000이하인 양의 정수이다. 1부터 n사이의 정수가 트리의 정점이라고 가정한다. 둘째 줄에는 n개의 정수 w1, w2, ..., wn이 주어지는데, wi는 정점 i의 www.acmicpc.net Approach 트리 DP 문제이다. 문제를 풀기 위해서는 다음 개념들을 알고 있어야 한다. 먼저 독립집합 이란, 그래프 이론에서, 어떤 두 꼭짓점도 서로 인접하지 않는 그래프에 있는 꼭짓점들의 집합을 이르는 말. 이라고 한다. 다시 말해 독립집합에 속해 있는 임의의 노드는 자신과 연결된 모든 노드와 인접해있지 않다.(연결되어 있지 않다는 뜻이다...

    [Java] 백준 2143 (두 배열의 합) Gold 3
    Algorithm/Baekjoon Online Judge

    [Java] 백준 2143 (두 배열의 합) Gold 3

    Problem : https://www.acmicpc.net/problem/2143 2143번: 두 배열의 합 첫째 줄에 T(-1,000,000,000 ≤ T ≤ 1,000,000,000)가 주어진다. 다음 줄에는 n(1 ≤ n ≤ 1,000)이 주어지고, 그 다음 줄에 n개의 정수로 A[1], …, A[n]이 주어진다. 다음 줄에는 m(1≤m≤1,000)이 주어지고, 그 다 www.acmicpc.net Approach 이분탐색 문제이다. 먼저 A 배열 과 B 배열의 요소들로 부 배열의 합들을 구하여 각각 aSum, bSum 에 저장한다. 그런 후, aSum에 있는 각 요소들에 대하여 더해서 T가 되는 요소를 bSum에서 구할 것이다. 그러기 위해 일단 bSum을 정렬한다. aSum의 각 요소들에 대해 ..

    [Java] 백준 2096 (내려가기) Gold 4
    Algorithm/Baekjoon Online Judge

    [Java] 백준 2096 (내려가기) Gold 4

    Problem : https://www.acmicpc.net/problem/2096 2096번: 내려가기 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다. www.acmicpc.net Approach 간단한 DP 문제로 생각하고 풀었다. DP의 점화식은 문제에서 알려주고 있기 때문에 따로 언급은 하지 않겠다. 최솟값 배열과 최댓값 배열을 따로 두어, 한 번 순회하며 두 값을 각각 갱신하였다. 마지막 줄을 검사하여 최종최댓값과 최종최솟값을 구하면 된다. Code import java.io.*; import java.util.StringTokenizer; /** * No.209..

    [Java] 백준 2056 (작업) Gold 4
    Algorithm/Baekjoon Online Judge

    [Java] 백준 2056 (작업) Gold 4

    Problem : https://www.acmicpc.net/problem/2042 2042번: 구간 합 구하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 합을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄 www.acmicpc.net Approach 기본적인 위상정렬 (Topological Sort) 문제였다. 위상 정렬에서는 선행되어야 하는 것들의 개수를 저장하는 inDegree 배열이 필요하다. 먼저 inDegree[a] 를 a작업이 수행되기까지 선행되어야 하는 작업의 수라고 정의한다. 그렇게 inDegree를 구성하고, inDegree가 0인 것..

티스토리툴바