본문 바로가기

분류 전체보기78

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

티스토리툴바