본문 바로가기

알고리즘22

[BOJ 2143] 두 배열의 합 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)이 주어지고, 그 다음 줄에 m개의 정수로 B[1], …, B[m]이 주어진다. 각각의 배열 원소는 절댓값이 1,000,000을 넘지 않는 정수이다. www.acmicpc.net n과 m의 값이 크지 않기 때문에 각 배열의 합을 구하는 것은 가능하다. 이를 이용하여 A배열과 B배열의 연속합을 저장해둔 배열을 만들고, 이를 정렬한 뒤 각 합을 따로 합쳐보면서 개수를 세면 .. 2020. 4. 20.
[BOJ 2623] 음악프로그램 https://www.acmicpc.net/problem/2623 2623번: 음악프로그램 첫째 줄에는 가수의 수 N과 보조 PD의 수 M이 주어진다. 가수는 번호 1, 2,…,N 으로 표시한다. 둘째 줄부터 각 보조 PD가 정한 순서들이 한 줄에 하나씩 나온다. 각 줄의 맨 앞에는 보조 PD가 담당한 가수의 수가 나오고, 그 뒤로는 그 가수들의 순서가 나온다. N은 1이상 1,000이하의 정수이고, M은 1이상 100이하의 정수이다. www.acmicpc.net 위 문제도 위상 정렬을 해서 차례대로 출력을 하면 되는 문제이지만, 순서를 모를 경우를 예외처리해주어야 한다. 배열에 순서대로 위상정렬의 결과를 저장할 때 배열의 길이와 전체 가수의 개수가 맞지 않는다면 제대로 된 순서를 모르는 것이기 때문에 .. 2020. 4. 20.
[BOJ 2252] 줄 세우기 https://www.acmicpc.net/problem/2252 2252번: 줄 세우기 첫째 줄에 N(1≤N≤32,000), M(1≤M≤100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의미이다. 학생들의 번호는 1번부터 N번이다. www.acmicpc.net 위 문제는 전형적인 위상 정렬문제이다. 위상 정렬 알고리즘대로 풀면 쉽게 풀 수 있는 문제이다. #include #include #include #define max(a, b) ((a) > (b) ? (a) :(b)) using namespace std; int n, m; int indgree[100001]; int main(.. 2020. 4. 20.
[BOJ 1005] ACM Craft https://www.acmicpc.net/problem/1005 1005번: ACM Craft 첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N 과 건물간의 건설순서규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부터 N번까지 존재한다) 둘째 줄에는 각 건물당 건설에 걸리는 시간 D가 공백을 사이로 주어진다. 셋째 줄부터 K+2줄까지 건설순서 X Y가 주어진다. (이는 건물 X를 지은 다음에 건물 Y를 짓는 것이 가능하다는 의미이다) 마지막 줄에는 백준이가 승리하기 위해 건 www.acmicpc.net 위 문제는 [BOJ 1516] 게임 개발 와 거의 유사한 문제이다. 똑같이 위상정렬을 통해 건물이 지어지는 시간을 갱신하여 출력하면.. 2020. 4. 20.
[BOJ 1516] 게임 개발 https://www.acmicpc.net/problem/1516 1516번: 게임 개발 첫째 줄에 건물의 종류 수 N(1 ≤ N ≤ 500)이 주어진다. 다음 N개의 줄에는 각 건물을 짓는데 걸리는 시간과 그 건물을 짓기 위해 먼저 지어져야 하는 건물들의 번호가 주어진다. 건물의 번호는 1부터 N까지로 하고, 각 줄은 -1로 끝난다고 하자. 각 건물을 짓는데 걸리는 시간은 100,000보다 작거나 같은 자연수이다. www.acmicpc.net 위 문제는 위상 정렬을 이용하여 푸는 문제이다. 위상 정렬이란 그래프에서 진입 차수가 0인 노드를 차례대로 제거해나가는 형식의 정렬이다. 진입 차수가 0이 되는 순서대로 출력을 하는것이다. 위 문제에 대입해보자면, 어떤 건물을 짓기 위해 지어야하는 건물들의 관계를.. 2020. 4. 20.
[BOJ 1806] 부분합 https://www.acmicpc.net/problem/1806 1806번: 부분합 문제 10,000 이하의 자연수로 이루어진 길이 N짜리 수열이 주어진다. 이 수열에서 연속된 수들의 부분합 중에 그 합이 S 이상이 되는 것 중, 가장 짧은 것의 길이를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. 출력 첫째 줄에 구하고자 하는 최소의 길 www.acmicpc.net 위 문제를 전체 탐색을 하면 O(N^2)으로 N이 100000이어서 시간초과가 난다. 투 포인터 알고리즘을 이용하여 풀 수 있다. 배열에 .. 2020. 4. 17.
[BOJ 13398] 연속합 2 https://www.acmicpc.net/problem/13398 13398번: 연속합 2 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 위 문제는 연속합을 구하는 문제를 조금 바꾸어서 풀 수 있다. dp배열을 한 개를 제거했을 때, 제거하지 않았을 때로 나누어서 문제를 풀면 된다. dp[i][0] = 한 개를 제거하지 않고 i번째까지의 가장 큰 연속합 dp[i][1] = 한 개를 제거하고 i번째까지의 가장 큰 연속합 이렇게 나누어서 풀면된다. 제거하지 않고 구하는 건 max(0, dp[i - 1][0]) + a[i] (a[i]는 i번.. 2020. 4. 17.
유니온-파인드(Union-Find), 서로소 집합(Disjoint Set) Union Find와 Disjoint Set은 동일한 의미를 가지며, 여러 서로소 집합의 정보를 저장하고 있는 자료구조를 의미합니다. 트리 형태로 구현되며, 보통 자신의 root 노드를 집합을 구분하는 ID처럼 사용된다. 이 자료구조는 두 가지 연산을 지원한다. 1. find(p): p의 root 노드의 값을 가져옴 2. union(p, q): p와 q의 집합을 합친다. (코드 구성 시에는 union이라는 예약어가 있어 merge로 대체) 맨 처음에는 모든 노드가 자기 스스로를 root 노드로 가지게 된다. find 함수는 현재 자기의 parent 노드가 자신이면 자기를 반환하고, 아니면 자신의 parent 노드의 parent노드를 반환한다. 이러한 방식으로 자신의 root 노드를 찾게 된다. union.. 2020. 4. 14.
[BOJ 1717] 집합의 표현 https://www.acmicpc.net/problem/1717 1717번: 집합의 표현 첫째 줄에 n(1≤n≤1,000,000), m(1≤m≤100,000)이 주어진다. m은 입력으로 주어지는 연산의 개수이다. 다음 m개의 줄에는 각각의 연산이 주어진다. 합집합은 0 a b의 형태로 입력이 주어진다. 이는 a가 포함되어 있는 집합과, b가 포함되어 있는 집합을 합친다는 의미이다. 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산은 1 a b의 형태로 입력이 주어진다. 이는 a와 b가 같은 집합에 포함되어 있는지를 확인하는 연산이다. a www.acmicpc.net 위 문제는 n + 1개의 집합을 서로 합치고, 특정 원소가 같은 집합인지를 확인하는 문제이다. 이는 Union-Find 구조를 이용하.. 2020. 4. 8.

티스토리툴바