컴퓨터하는 kimmessi

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 문제 해결 알고리즘 Union find 문제 parent 배열이 무조건 그 노드의 조상노드를 가리키는 게 아니기 때문에 조상 노드 비교 해줄 때는 find_parent 함수를 써줘야한다. 소스 코드 #include using namespace std; int n, m; int parent[1000001]; int find_parent(int x){ if(x..

https://www.acmicpc.net/problem/21757 21757번: 나누기 $N$개의 정수 수열 $A_1, A_2, \dots , A_N$이 주어진다. 수열을 각각이 연속된 네 부분으로 나누려고 한다. 단, 각 부분은 최소 하나의 수를 포함해야 한다. 또, 각 부분의 합은 모두 같아야 한다. 즉, 어 www.acmicpc.net 문제 해결 알고리즘 수열의 누적합 배열을 만들어 준 후에 수열의 총합을 구하고, 총합이 0인 경우와 아닌 경우 두 가지로 나눠서 풀어줘야한다. 0인 경우는 마지막 0빼고 나머지 0의 개수에서 3개를 뽑는 조합으로 개수를 구해주면된다. 0이 아닌 경우는 다이나믹 프로그래밍을 이용해서 풀어줄 수 있는데 총합에서 4를 나누면 공차가 나오고 그 공차대로 늘어나는 길이 4의..

https://www.acmicpc.net/problem/1865 1865번: 웜홀 첫 번째 줄에는 테스트케이스의 개수 TC(1 ≤ TC ≤ 5)가 주어진다. 그리고 두 번째 줄부터 TC개의 테스트케이스가 차례로 주어지는데 각 테스트케이스의 첫 번째 줄에는 지점의 수 N(1 ≤ N ≤ 500), www.acmicpc.net 문제 해결 알고리즘 벨만 포드 알고리즘 음의 사이클의 존재 여부를 판단하는 문제. 출발점이 어디든 음의 사이클 존재만 판단하면 되므로 한 번만 벨만 포드 알고리즘을 돌리면 된다. (굳이 모든 출발점에서 음의 사이클 존재 여부 판단할 필요 X, 시간 초과남) if(d[cur_node] != INF && d[next_node] > d[cur_node] + cost) 보통의 벨만 포드 알고..

https://www.acmicpc.net/problem/11657 11657번: 타임머신 첫째 줄에 도시의 개수 N (1 ≤ N ≤ 500), 버스 노선의 개수 M (1 ≤ M ≤ 6,000)이 주어진다. 둘째 줄부터 M개의 줄에는 버스 노선의 정보 A, B, C (1 ≤ A, B ≤ N, -10,000 ≤ C ≤ 10,000)가 주어진다. www.acmicpc.net 문제 해결 알고리즘 벨만 포드 알고리즘 INF값은 충분히 크게 잡아주어야한다. 오버 플로우가 나기 때문에 int 대신 long long 자료형을 써주어야한다. 소스 코드 #include #define ll long long using namespace std; const ll INF = 1e9; const int MAX = 6001; l..

https://www.acmicpc.net/problem/14428 14428번: 수열과 쿼리 16 길이가 N인 수열 A1, A2, ..., AN이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오. 1 i v : Ai를 v로 바꾼다. (1 ≤ i ≤ N, 1 ≤ v ≤ 109) 2 i j : Ai, Ai+1, ..., Aj에서 크기가 가장 작은 값의 www.acmicpc.net 문제 해결 알고리즘 세그먼트 트리에 인덱스 값을 넣는데 이 때, 인덱스에 해당하는 배열 값과 항상 비교해서 작은 배열 값의 인덱스 값을 리턴해준다. 소스 코드 #include using namespace std; const int MAX = 100000; int arr[MAX+1], tree[4*MAX+1]; int ..

https://www.acmicpc.net/problem/5569 5569번: 출근 경로 상근이가 사는 도시는 남북 방향으로 도로가 w개, 동서 방향으로 도로가 h개 있다. 남북 방향 도로는 서쪽부터 순서대로 번호가 1, 2, ..., w로 매겨져 있다. 또, 동서 방향 도로는 남쪽부터 순서대 www.acmicpc.net 문제 해결 알고리즘 방향 전환이 가능한지, 방향이 아래인지 오른쪽인지 이 네가지로 나눠서 다이나믹 프로그래밍을 진행주어야한다. 소스 코드 #include using namespace std; const int mod = 100000; int arr[101][101][2][2]; // 행, 열, 방향 전환 가능 여부, 방향 아래 0 오른 1 int main(){ int w, h; cin ..

https://www.acmicpc.net/problem/5557 5557번: 1학년 상근이가 1학년 때, 덧셈, 뺄셈을 매우 좋아했다. 상근이는 숫자가 줄 지어있는 것을 보기만 하면, 마지막 두 숫자 사이에 '='을 넣고, 나머지 숫자 사이에는 '+' 또는 '-'를 넣어 등식을 만들며 놀 www.acmicpc.net 문제 해결 알고리즘 다이나믹 프로그래밍을 활용해서 풀어주는 문제 배열에 0부터 20까지 두고 첫번 째 수부터 그 안에 속하는 등식이면 배열에서 그 해당하는 값의 개수를 더해주면서 동적계획을 해준다. 소스 코드 #include using namespace std; int N; long long arr[103], dp[21][103]; long long result = 0; int main()..

https://www.acmicpc.net/problem/1060 1060번: 좋은 수 정수 집합 S가 주어졌을때, 다음 조건을 만족하는 구간 [A, B]를 좋은 구간이라고 한다. A와 B는 양의 정수이고, A < B를 만족한다. A ≤ x ≤ B를 만족하는 모든 정수 x가 집합 S에 속하지 않는다. 정수 www.acmicpc.net 문제 해결 알고리즘 S에 속한 숫자들을 먼저 우선순위 큐에 넣고 (이 때, 들어오는 S의 원소들은 정렬되지 않았기 때문에 정렬을 꼭 해주어야한다.) 좋은 구간의 개수는 0이긴 하지만 1로 해주어야 나중에 2 1 3 3 같은 반례로부터 자유롭다. 우선순위 큐에 있는 수들은 작은 수가 먼저 나오게 정렬해준다. 그리고 큐에서 나온 수의 1 큰 수와 1 작은 수의 좋은 구간 개수를..

https://www.acmicpc.net/problem/2014 2014번: 소수의 곱 첫째 줄에 K(1 ≤ K ≤ 100), N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 K개의 소수가 오름차순으로 주어진다. 같은 소수가 여러 번 주어지는 경우는 없으며, 주어지는 소수는 모두 541보다 작거나 www.acmicpc.net 문제 해결 알고리즘 우선순위 큐를 이용하는 문제. 메모리 관리가 빡세다. 그냥 곱한 값들을 전부 우선순위 큐에 집어넣는 방식으로 하면 메모리 초과를 피할 수 없다. 우선순위 큐의 크기가 N보다 크고 최댓값보다 그 값이 크다면 건너뛰고 중복은 받지 않는 식으로 메모리 관리를 해주어야한다. 시행착오가 참 많았던 문제 소스 코드 #include #define ll long l..

https://www.acmicpc.net/problem/11505 11505번: 구간 곱 구하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 곱을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄 www.acmicpc.net 문제 해결 알고리즘 세그먼트 트리 문제인데, 곱이기 때문에 구간 합 구하기 문제와는 좀 다르게 update 함수를 아래부터 위로 다시 곱하는 방식으로 구해주어야한다. 왜냐면 0이 있기 때문 오버플로우가 날 수 있으므로 long long 자료형을 써야한다. 소스 코드 #include #define ll long long using nam..