본문 바로가기

분류 전체보기76

[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.
[BOJ 5247] 불 https://www.acmicpc.net/problem/5427 5427번: 불 문제 상근이는 빈 공간과 벽으로 이루어진 건물에 갇혀있다. 건물의 일부에는 불이 났고, 상근이는 출구를 향해 뛰고 있다. 매 초마다, 불은 동서남북 방향으로 인접한 빈 공간으로 퍼져나간다. 벽에는 불이 붙지 않는다. 상근이는 동서남북 인접한 칸으로 이동할 수 있으며, 1초가 걸린다. 상근이는 벽을 통과할 수 없고, 불이 옮겨진 칸 또는 이제 불이 붙으려는 칸으로 이동할 수 없다. 상근이가 있는 칸에 불이 옮겨옴과 동시에 다른 칸으로 이동할 수 있다. 빌딩 www.acmicpc.net 위 문제는 여러 테스트 케이스가 주어지고, 맵의 크기도 1000이 되기 때문에 상근이가 이동할 때마다 불을 옮기면 시간초과가 날 수 있다. 그.. 2020. 4. 8.
[BOJ 2352] 반도체 설계 https://www.acmicpc.net/problem/2352 2352번: 반도체 설계 첫째 줄에 정수 n(1 ≤ n ≤ 40,000)이 주어진다. 다음 줄에는 차례로 1번 포트와 연결되어야 하는 포트 번호, 2번 포트와 연결되어야 하는 포트 번호, …, n번 포트와 연결되어야 하는 포트 번호가 주어진다. 이 수들은 1 이상 n 이하이며 서로 같은 수는 없다고 가정하자. www.acmicpc.net 위 그림에서 왼쪽의 포트가 연결된 오른쪽 포트의 번호를 A[i]라고 하고, 선택된 오른쪽 포트를 모아놓은 리스트를 L이라고 두면, 가장 많은 포트를 고르기 위해서는 리스트 L의 원소들이 정렬되어 있는 상태에서 크기가 가장 커야 한다. 예를 들어, 왼쪽 포트 1부터 차례대로 선택할 때, 오른쪽의 3번 포트가.. 2020. 4. 8.
[BOJ 14002] 가장 긴 증가하는 부분 수열 4 https://www.acmicpc.net/problem/14002 14002번: 가장 긴 증가하는 부분 수열 4 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다. www.acmicpc.net [BOJ 11053] 가장 긴 증가하는 부분 수열 과 똑같이 길이를 구한 뒤에 dp의 맨 끝부터 탐색을 하면서 가능한 최대 길이랑 같은지 다른지를 확인하면 된다. 같은 값이 나올 때마다 최대 길이를 1씩 줄여서 dp[i]에서 가능한 최대 길이를 구하면 된다. #include #include #de.. 2020. 4. 7.
[BOJ 12738] 가장 긴 증가하는 부분 수열 3 https://www.acmicpc.net/problem/12738 12738번: 가장 긴 증가하는 부분 수열 3 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (-1,000,000,000 ≤ Ai ≤ 1,000,000,000) www.acmicpc.net [BOJ 12015] 가장 긴 증가하는 부분 수열 2 과 풀이는 똑같다. 같은 코드로 통과가 된다. #include #include #include using namespace std; int n; int main() { scanf("%d", &n); vector dp; for (int i = 1; i dp.back()) dp.push_back(t); else { v.. 2020. 4. 7.
[BOJ 12015] 가장 긴 증가하는 부분 수열 2 https://www.acmicpc.net/problem/12015 12015번: 가장 긴 증가하는 부분 수열 2 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000) www.acmicpc.net 해당 문제 [BOJ 11053] 가장 긴 증가하는 부분 수열 문제와 거의 똑같다. 다만 배열의 크기가 1,000,000이기 때문에 위에서 쓴 O(N^2) 알고리즘으로는 못 푼다. 대신 O(N log N) 알고리즘을 이용하여 풀면 된다. 자세한 풀이는 LIS 에 있다. #include #include #include using namespace std; int n; int main() { scanf.. 2020. 4. 7.
가장 긴 증가하는 부분 수열, LIS(Longest Increasing Subsequence) LIS는 어떠한 수열에서 증가하는 부분 수열중 길이가 가장 긴 수열를 뜻합니다. LIS를 찾는 알고리즘은 다이나믹 프로그래밍을 이용한 O(N^2) 알고리즘과 이보다는 좀 더 복잡한 O(N log N) 알고리즘이 있습니다. 부분 수열이란 어떠한 수열에서 일부 숫자를 지워서 만들 수 있는 새로운 수열을 의미합니다. O(N^2) O(N^2) 알고리즘은 비교적 간단하게 구현할 수 있습니다. dp[i] = i 번째 원소를 마지막으로 하는 LIS의 길이 dp[i]를 구하는 법은 1 ~ (i - 1)까지의 원소들 중 i번째 원소보다 값이 작은 것들 중 dp의 값이 가장 큰 것에 1을 더하면 된다. 즉, j = 1 ~ (i - 1)을 순회할 때, a[i]보다 a[j]가 작다면, dp[i] = max(dp[i], dp[.. 2020. 4. 7.

티스토리툴바