피너클의 it공부방

https://www.acmicpc.net/problem/1766 1766번: 문제집 첫째 줄에 문제의 수 N(1 ≤ N ≤ 32,000)과 먼저 푸는 것이 좋은 문제에 대한 정보의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 둘째 줄부터 M개의 줄에 걸쳐 두 정수의 순서쌍 A,B가 빈칸을 사이에 두고 주 www.acmicpc.net 위상정렬 문제다. 이번에는 priority_queue를 사용하는 위상정렬 알고리즘을 사용한다. int n, m; vector adj[32001]; int inDegree[32001]; 사용할 변수다. adj는 문제끼리의 순서가 들어가고 inDegree는 해당 문제가 어떤 문제 다음으로 풀려야 하는지를 확인한다. 현재 예제 상태를 그래프로 표현하면 위와 같다. 위를 보..

https://www.acmicpc.net/problem/25416 25416번: 빠른 숫자 탐색 5 x 5 크기의 보드가 주어진다. 보드는 1 x 1 크기의 정사각형 격자로 이루어져 있다. 보드의 격자에는 -1, 0, 1중 하나의 숫자가 적혀 있다. 격자의 위치는 (r, c)로 표시한다. r은 행 번호, c는 열 번호 www.acmicpc.net bfs문제다. for (int i = 0; i > map[i][j]; visited[i][j] = false; } cin >> r >> c; cout

https://www.acmicpc.net/problem/2623 2623번: 음악프로그램 첫째 줄에는 가수의 수 N과 보조 PD의 수 M이 주어진다. 가수는 번호 1, 2,…,N 으로 표시한다. 둘째 줄부터 각 보조 PD가 정한 순서들이 한 줄에 하나씩 나온다. 각 줄의 맨 앞에는 보조 PD가 담당한 www.acmicpc.net 위상정렬 문제다. 여러가지 방법이 있지만 여기선 dfs를 이용한 위상정렬을 할것이다. int n, m; bool visited[1001]; vector v[1001], order; int adj[1001][1001]; 사용할 변수다. adj는 위상정렬에 사용할것이고 v는 입력받을때 order에는 정답을 넣을것이다. cin >> n >> m; memset(visited, fals..

https://www.acmicpc.net/problem/2166 2166번: 다각형의 면적 첫째 줄에 N이 주어진다. 다음 N개의 줄에는 다각형을 이루는 순서대로 N개의 점의 x, y좌표가 주어진다. 좌표값은 절댓값이 100,000을 넘지 않는 정수이다. www.acmicpc.net 기하학문제다. 다각형을 삼각형으로 쪼개서 문제를 풀것이다. 삼각형의 넓이를 구할때는 학원에서 자주 들었던 신발끈 공식을 이용할것이다. 신발끈 공식은 삼각형의 꼭짓점의 좌표를 알면 넓이를 구할수 있는 공식이다. 인터넷에 치면 많이 나온다. 한글로 만들었다. x, y는 각각 삼각형 꼭짓점의 좌표를 의미한다. cin >> n; for (int i = 0; i > a >> b; v...

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