피너클의 it공부방

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 최소 스패닝 트리 문제다. 최소 스패팅 트리는 그래프의 모든 정점을 연결하는데 필요한 가중치중 가장 작은 가중치를 구하는 알고리즘이다. 인터넷에 치면 많이 나오는 알고리즘이니 따로 설명은 안하겠다. 여기선 크루스칼을 사용할것이다. int v, e; vector adj[10001]; vector parent(10001); vector rnk(10001,..

https://www.acmicpc.net/problem/20040 20040번: 사이클 게임 사이클 게임은 두 명의 플레이어가 차례대로 돌아가며 진행하는 게임으로, 선 플레이어가 홀수 번째 차례를, 후 플레이어가 짝수 번째 차례를 진행한다. 게임 시작 시 0 부터 n − 1 까지 고유한 www.acmicpc.net 유니온 파인드를 이용한 문제다. 두 점을 입력받은뒤 둘의 부모가 같다면 순서를 출력한다. int n, m; int uni[500001]; 사용할 변수들이다. uni가 점의 부모를 의미한다. int find(int num) { if (uni[num] == num) return num; else return uni[num] = find(uni[num]); } find함수는 정수 num의 조상을 ..

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)이 주어지고, 그 www.acmicpc.net 이진탐색을 이용하는 문제다. 각 배열의 부 배열을 만들고 그들을 이용해 이진탐색으로 답을 구한다. int t, n, m; int a[1001], b[1001]; vector as, bs; vector ::iterator f, s; 선언하는 변수다. as, bs는 부배열이 들어갈것이고 f, s는 이진탐색에 이용할것이다...

https://www.acmicpc.net/problem/1208 1208번: 부분수열의 합 2 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 40, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net 이진탐색 문제다. 현재 n이 40이니 모든 부분수열을 구하면 2 ^ 40 = 1,099,511,627,776만큼의 수열을 구해야한다. 그런 2 ^ 20짜리 부분수열 2개를 구할것이다. long long n, s; long long arr[41]; vector first, second; vector ::iterator a, b; 선언한 변수들이다. first와..

https://www.acmicpc.net/problem/2473 2473번: 세 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 3 이상 5,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 www.acmicpc.net 투 포인터 문제다. cin >> n; for (int i = 0; i > a; v.push_back(a); } sort(v.begin(), v.end()); 값을 입력받은 뒤 정렬한다. long long ans[3] = { 0, 0, 0 }; long long m = 9876543210; ans에는 세 용액이 들어가고 m에는 세 용액..

https://www.acmicpc.net/problem/12100 12100번: 2048 (Easy) 첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2 www.acmicpc.net 귀찮은 구현 문제다. int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n; for (int i = 0; i > map[i][j]; cout = 0; k--) { if (map[k][i] == 0) { map[k][i]..

https://www.acmicpc.net/problem/25372 25372번: 성택이의 은밀한 비밀번호 부산사이버대학교 학생 성택이는 엄마의 의뢰를 받아 주어진 문자열이 현관문 비밀번호에 사용 가능한지 알아내야 한다. 성택이는 공부해야 하므로 우리가 도와주자! 사용할 수 있는 비밀번호 www.acmicpc.net 간단한 구현 문제다. #include #include using namespace std; int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n; string s; cin >> n; for (int i = 0; i > s; if (6

https://www.acmicpc.net/problem/14003 14003번: 가장 긴 증가하는 부분 수열 5 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (-1,000,000,000 ≤ Ai ≤ 1,000,000,000) www.acmicpc.net 부분 수열의 길이를 구하는데 이진탐색을 사용할 것이고 부분 수열을 구하는데 백트래킹을 사용할것이다. int n; int arr[1000001]; int back[1000001]; vector v; vector::iterator it; 사용할 변수다. arr은 입력받을때, back은 백트래킹할때 v, it은 부분 수열을 구할 때 사용할 것이다. cin >> n; int..

https://www.acmicpc.net/problem/12852 12852번: 1로 만들기 2 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 자연수 N이 주어진다. www.acmicpc.net bfs문제다. 1로 만드는것 뿐만 아니라 1로 만드는 방법을 출력해야한다. int n; bool visited[1000001]; vector v[1000001]; 사용할 변수다. v[i]는 i로 가는 방법을 나타낸다. cin >> n; queue q; q.push(n); memset(visited, false, sizeof(visited)); visited[n] = true; v[n].push_back(n); 기본 준비를 한다. v[n]은 처음 시작이니 n을 넣어준다. while (!q.empty())..

https://www.acmicpc.net/problem/2239 2239번: 스도쿠 스도쿠는 매우 간단한 숫자 퍼즐이다. 9×9 크기의 보드가 있을 때, 각 행과 각 열, 그리고 9개의 3×3 크기의 보드에 1부터 9까지의 숫자가 중복 없이 나타나도록 보드를 채우면 된다. 예를 들어 다 www.acmicpc.net 구현문제다. int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); for (int i = 0; i > sudoku[i]; solve(0, 0); } string으로 입력받는다. void solve(int y, int x) { if (sudoku[y][x] == '0') { solve함수다. solve함수는 ..