[Java] 백준 1717 (집합의 표현) Gold 4

Problem : https://www.acmicpc.net/problem/1717 1717번: 집합의 표현 첫째 줄에 n(1 ≤ n ≤ 1,000,000), m(1 ≤ m ≤ 100,000)이 주어진다. m은 입력으로 주어지는 연산의 개수이다. 다음 m개의 줄에는 각각의 연산이 주어진다. 합집합은 0 a b의 형태로 입력이 주어진다. 이는 www.acmicpc.net Approach Union-Find(Disjoint Set) 알고리즘을 사용한 기본 문제이다. 유니온파인드를 구현이 다인 문제이다. 입력의 처음이 0 인 경우, union 메소드를 적용하여 하나의 집합으로 묶는다. 입력의 처음이 1 인 경우, 두 숫자의 부모를 검사하여 같은 집합인지를 판단한다. Code import java.io.*; i..

→2021.04.04

Algorithm/Baekjoon Online Judge

[Java] 백준 1647 (도시 분할 계획) Gold 4

Problme : https://www.acmicpc.net/problem/1647 1647번: 도시 분할 계획 첫째 줄에 집의 개수N, 길의 개수M이 주어진다. N은 2이상 100,000이하인 정수이고, M은 1이상 1,000,000이하인 정수이다. 그 다음 줄부터 M줄에 걸쳐 길의 정보가 A B C 세 개의 정수로 주어지는데 A번 집 www.acmicpc.net Approach MST(Minimum Spanning Tree) 의 개념을 응용한 문제이다. MST를 적용한 그래프는 임의의 두 점 사이를 연결하는 경로는 유일하다. 따라서, 그 중 하나의 간선을 제거하면 MST 가 2개로 분리된다. (분리된 각 그래프도 MST이다.) 먼저 MST를 적용한다. (Prim or Kruskal 을 사용하면 된다...

→2021.04.04

Algorithm/Baekjoon Online Judge

[Java] 백준 9527 (1의 개수 세기) Gold 2

Problem : https://www.acmicpc.net/problem/9527 9527번: 1의 개수 세기 두 자연수 A, B가 주어졌을 때, A ≤ x ≤ B를 만족하는 모든 x에 대해 x를 이진수로 표현했을 때 1의 개수의 합을 구하는 프로그램을 작성하시오. 즉, f(x) = x를 이진수로 표현 했을 때 1의 개수라 www.acmicpc.net Approach Java에는 Integer.bitCount() 이라는 내장 라이브러리 함수가 있다. 인자로 받은 숫자를 이진수로 나타냈을 때, 1의 개수를 리턴해준다. 이 문제에서는 시간초과가 나서 사용할 수 없지만, 이런 함수도 있긴 하다. 이 문제는 은근히 찾기 힘든 규칙이 존재한다. bit[i]를 i번째 비트까지 모두0인 숫자(0)부터 i번째 비트까..

→2021.04.03

Algorithm/Baekjoon Online Judge

[Java] 백준 1600 (말이 되고픈 원숭이) Gold 5

Problem : https://www.acmicpc.net/problem/1600 1600번: 말이 되고픈 원숭이 첫째 줄에 정수 K가 주어진다. 둘째 줄에 격자판의 가로길이 W, 세로길이 H가 주어진다. 그 다음 H줄에 걸쳐 W개의 숫자가 주어지는데, 0은 아무것도 없는 평지, 1은 장애물을 뜻한다. 장애물이 있 www.acmicpc.net Approach BFS 문제이다. 일반적인 BFS 에 이동할 수 있는 추가적인 방향과 이 추가적인 방향을 사용하는데에 있어 제한을 두는 약간의 제약이 추가되었다. 문제에서 언급하는 말 이동은 횟수제한이 있으므로, 해당 지점에 말 이동을 몇 번 사용하여 최소 이동으로 도착하였는지를 저장하여야 한다. (이 때문에 visited 배열을 3차원으로 선언하였다.) 그 이외..

→2021.04.02

Algorithm/Baekjoon Online Judge

[Java] 백준 1517 (버블 소트) Gold 1

Problem : https://www.acmicpc.net/problem/1517 1517번: 버블 소트 첫째 줄에 N(1≤N≤500,000)이 주어진다. 다음 줄에는 N개의 정수로 A[1], A[2], …, A[N]이 주어진다. 각각의 A[i]는 0≤|A[i]|≤1,000,000,000의 범위에 들어있다. www.acmicpc.net Approach 버블 소트를 가장한 머지 소트 문제이다. Merge Sort를 구현하면서 Bubble Sort를 했을 때와 Swap의 관계를 찾아야 한다. 4 5 1 2 를 머지소트를 한다고 가정하자. left = 0, right = 3, mid = 1, [4, 5]의 인덱스 i = 0, [1, 2]의 인덱스 j = 0 이라 할 때, [1 2 4 5] 를 만드려면 4회의..

→2021.04.02

Algorithm/Baekjoon Online Judge

[Java] 백준 1516 (게임 개발) Gold 3

Problem : https://www.acmicpc.net/problem/1516 1516번: 게임 개발 첫째 줄에 건물의 종류 수 N(1 ≤ N ≤ 500)이 주어진다. 다음 N개의 줄에는 각 건물을 짓는데 걸리는 시간과 그 건물을 짓기 위해 먼저 지어져야 하는 건물들의 번호가 주어진다. 건물의 번호는 1부 www.acmicpc.net Approach 어떤 작업을 해야할 때 선행되야 하는 작업이 있다면, 위상정렬도 한번 생각해 보는 것이 좋다. 대개 위와 같은 문제 유형이면, 위상정렬을 사용하는 문제인 것들이 많았다.(개인적인 생각) 이 문제도 마찬가지로 위상정렬로 풀이하였다. 위상정렬의 개념은 설명하지 않겠다. 위상정렬의 기본 구조를 크게 벗어나지 않았고, 응용하는 부분도 없기에 조금의 코드설명만 ..

→2021.03.31

Algorithm/Baekjoon Online Judge

[Java] 백준 1261 (알고스팟) Gold 4

Problem : https://www.acmicpc.net/problem/1261 1261번: 알고스팟 첫째 줄에 미로의 크기를 나타내는 가로 크기 M, 세로 크기 N (1 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 미로의 상태를 나타내는 숫자 0과 1이 주어진다. 0은 빈 방을 의미하고, 1은 벽을 의미 www.acmicpc.net Approach 이 문제의 기본 접근법은 갈 수 있는 곳 중 벽이 아닌 곳이 있으면 우선 그 쪽으로 가고, 갈 수 있는 곳이 벽인 곳밖에 없다면 벽을 뚫는다.이다. 이를 구현하는 데에는 여러 방법이 있겠지만, 나는 Deque+BFS, PriorityQueue+BFS 두 가지 방법으로 풀이를 해봤다. 두 방법 모두 풀이가 가능하다. 주의할 점은, 큐에 동일한 ..

→2021.03.31

Algorithm/Baekjoon Online Judge

[Java] 백준 1238 (파티) Gold 3

Problem : https://www.acmicpc.net/problem/1238 1238번: 파티 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어 www.acmicpc.net Approach 단방향 그래프에서 자신에서 출발하여 자신으로 돌아오는 최단거리를 구하는 문제이다. 모든 정점에서의 최단거리를 구하여야 하므로 플로이드-와샬이 쉽게 떠오르겠지만, 이 문제의 입력 최대 크기가 1000이므로 시간복잡도가 O(N^3) 인 플로이드-와샬 알고리즘은 시간초과가 난다. 그래서 다익스트라를 응용하여 문제를 풀이하였다. 마을이 1 ..

→2021.03.30

Algorithm/Baekjoon Online Judge

[Java] 백준 1197 (최소 스패닝 트리) Gold 4

Problem : https://www.acmicpc.net/problem/1197 1197번: 최소 스패닝 트리 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 www.acmicpc.net Approach MST(Minimum Spanning Tree) 를 구하는 데에는 크게 Prim과 Kruskal알고리즘이 있다. 이 문제는 간단하게 위 두 알고리즘 중 하나를 택하여 구현만 하면 되는 문제였다. 간단한 로직만 설명하고, 자세한 내용은 다루지 않겠다. Prim알고리즘은 간선 중심 알고리즘이다. 간선을 오름차순으로 정렬한..

→2021.03.30

Algorithm/Baekjoon Online Judge

[Java] 백준 1167 (트리의 지름) Gold 3

Problem : https://www.acmicpc.net/problem/1167 1167번: 트리의 지름 트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지 www.acmicpc.net Approach BFS 나 DFS 를 사용하여 풀 수 있는 문제이다. 상식으로 접근하여 생각하면 쉽게 풀리는 문제였다. BFS나 DFS를 두번 수행하면 풀이가 가능한 문제이다. (나는 BFS를 사용했다.) 아무 정점을 시작으로 BFS를 수행하여 시작 정점으로부터 가장 먼 정점을 구한다. 그 정점을 기준으로 다시 BFS를 수행하여 가장 먼 정점까지의 거리가 트리의 ..

→2021.03.29

티스토리툴바