BOJ

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

    [Java] 백준 1987 (알파벳) Gold 4
    Algorithm/Baekjoon Online Judge

    [Java] 백준 1987 (알파벳) Gold 4

    Problem : https://www.acmicpc.net/problem/1987 1987번: 알파벳 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으 www.acmicpc.net Approach 이미 지나온 알파벳은 지날 수 없는 DFS 문제이다. 이미 지나온 알파벳은 지날 수 없다는 것을 확인하기 위해 visited 배열과 더불어 alpha 배열을 따로 두었다. 풀이 방법은 다음과 같다. 좌측 상단(0, 0)에서 시작하여 DFS를 수행한다. DFS 를 수행하며 지나온 알파벳을 기록한다. 이미 지나온 알파벳이라면 그 칸으로는 더이상 탐색하지 않는다..

    [Java] 백준 1967 (여행 가자) Gold 4
    Algorithm/Baekjoon Online Judge

    [Java] 백준 1967 (여행 가자) Gold 4

    Problem : https://www.acmicpc.net/problem/1976 1976번: 여행 가자 동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인 www.acmicpc.net Approach 유니온 파인드(Union-Find) 를 활용한 문제였다. 플로이드 와샬 알고리즘으로도 풀이가 가능하다고 한다. (여기서는 다루지 않는다.) 주어진 여행 경로가 어떤 형식으로든 서로 연결되어 길이 존재한다면 가능한 여행경로라고 볼 수 있다. 따라서 입력데이터를 받아 도시 사이에 길이 있다면 같은 집합으로 묶는 작업을 진행한다. 그런 뒤에 여행경로에 있는 모든 도시들..

    [Java] 백준 1967 (트리의 지름) Gold 4
    Algorithm/Baekjoon Online Judge

    [Java] 백준 1967 (트리의 지름) Gold 4

    Problem : https://www.acmicpc.net/problem/1967 1967번: 트리의 지름 파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 둘째 줄부터 n-1개의 줄에 각 간선에 대한 정보가 들어온다. 간선에 대한 정보는 세 개의 정수로 이루어져 있다. 첫 번째 정수는 간선이 연 www.acmicpc.net Approach 트리를 가장한 DFS/BFS문제이다. 트리의 지름은 가장 먼 두 노드 사이의 길이를 구하면 된다. 가장 먼 두 노드 사이의 길이는 다음과 같이 구할 수 있다. 임의의 점에서 가장 먼 노드 A를 구한다. A에서 가장 먼 노드 B를 구한다. A - B 사이의 길이가 가장 먼 두 노드 사이의 길이가 된다. 머릿속에서나 잠깐 생각해보면 쉽게 이해가 갈..

    [Java] 백준 1918 (후위 표기식) Gold 4
    Algorithm/Baekjoon Online Judge

    [Java] 백준 1918 (후위 표기식) Gold 4

    Problem : https://www.acmicpc.net/problem/1918 1918번: 후위 표기식 첫째 줄에 중위 표기식이 주어진다. 단 이 수식의 피연산자는 A~Z의 문자로 이루어지며 수식에서 한 번씩만 등장한다. 그리고 -A+B와 같이 -가 가장 앞에 오거나 AB와 같이 *가 생략되는 등의 수식 www.acmicpc.net Approach Stack을 이용하여 풀이하는 문제이다. 입력으로 주어진 문자열을 하나씩 읽으면서 각 문자에 대해 우선순위를 매겨서 하나씩 뽑는 형태이다. 다음과 같이 4개의 경우가 발생한다. 참고로 스택엔 여는괄호와 연산자만 들어가게끔 구현한다. 스택의 문자들은 각각 우선순위가 매겨져 있으며, (가 0, +-가 1, */가 2로 숫자가 높을수록 우선이 된다. stack..

    [Java] 백준 1937 (욕심쟁이 판다) Gold 3
    Algorithm/Baekjoon Online Judge

    [Java] 백준 1937 (욕심쟁이 판다) Gold 3

    Problem : https://www.acmicpc.net/problem/1937 1937번: 욕심쟁이 판다 n*n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에서 www.acmicpc.net Approach 어느 한 지점으로부터 시작하여 최대 몇개의 지점을 방문할 수 있는지를 판단하는 DFS문제이다. DFS는 인접행렬의 경우 O(n^2)의 시간복잡도를 가지고 있어, n의 크기가 크다면 모든 지점을 시작지점으로 하여 DFS하기에는 시간초과가 뜰 것이다. (O(n^2 * n^2)) 따라서 위와 같이 시간초과를 피하기 위하여, 모든 점을 시작지점으로 DFS를 수행..

티스토리툴바