피너클의 it공부방

https://www.acmicpc.net/problem/17143 17143번: 낚시왕 낚시왕이 상어 낚시를 하는 곳은 크기가 R×C인 격자판으로 나타낼 수 있다. 격자판의 각 칸은 (r, c)로 나타낼 수 있다. r은 행, c는 열이고, (R, C)는 아래 그림에서 가장 오른쪽 아래에 있는 칸이다. www.acmicpc.net 귀찮은 구현문제다. 하나라도 삐끗하면 지금까지 짠 모든 코드가 물거품이 되는 무서운 문제다. 위처럼 된다. 만약 계속해서 틀린다면 낚시 -> 상어 움직임 -> 상어 끼리 싸우기 순으로 했는지 확인해봐라 나는 상어 움직임 -> 상어 싸움 -> 낚시 순서로 여러번 돌려서 위처럼 되었다. int r, c, m; vector map[201][201]; vector map_chk; cl..

https://www.acmicpc.net/problem/1647 1647번: 도시 분할 계획 첫째 줄에 집의 개수 N, 길의 개수 M이 주어진다. N은 2이상 100,000이하인 정수이고, M은 1이상 1,000,000이하인 정수이다. 그 다음 줄부터 M줄에 걸쳐 길의 정보가 A B C 세 개의 정수로 주어지는데 A번 www.acmicpc.net 최소 스패닝 트리 문제다. 스패닝 트리를 돌린 뒤 마지막에 더한 cost를 빼줄것이다. int n, m; int parent[100001]; vector edges; 사용할 변수다. parent는 유니온 파인드에 사용할것이고 edges는 입력받을때와 스패닝 트리에서 사용할것이다. int find(int num) { if (parent[num] == num) r..

https://www.acmicpc.net/problem/4386 4386번: 별자리 만들기 도현이는 우주의 신이다. 이제 도현이는 아무렇게나 널브러져 있는 n개의 별들을 이어서 별자리를 하나 만들 것이다. 별자리의 조건은 다음과 같다. 별자리를 이루는 선은 서로 다른 두 별을 일 www.acmicpc.net 최소 스패닝 트리 문제다. int n; int parent[101]; vector v; vector edges; 사용할 변수다. int find(int num) { if (parent[num] == num) return num; else return parent[num] = find(parent[num]); } find함수다. num의 조상을 반환한다. void merge(int u, int v) ..

https://www.acmicpc.net/problem/16566 16566번: 카드 게임 첫째 줄에 세 개의 자연수 N, M, K가 주어진다. (1 ≤ M ≤ N ≤ 4,000,000, 1 ≤ K ≤ min(M, 10,000)) 다음 줄에 카드의 번호를 나타내는 M개의 자연수가 주어진다. 각각의 수들은 1 이상이고 N 이하이며 서로 www.acmicpc.net 이진탐색과 유니온 파인드를 이용한 문제다. 내가 낼 수 있는 카드중에서 민수를 이길수있는 가장 작은 카드를 내면 된다. int n, m, k; int parent[4000001]; vector v; vector ::iterator it; 사용할 변수다. parent는 조상을 담을것이고 it은 이진탐색에 사용할것이다. int find(int nu..

https://www.acmicpc.net/problem/2568 2568번: 전깃줄 - 2 첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100,000 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결 www.acmicpc.net lcs문제다. 아래그림을 위에 처럼 만들면 된다. 오른쪽을 보면 1, 4, 6, 7, 10으로 게속해서 증가하는걸 알수있다. 부분수열중 증가하는 부분수열을 찾으면 되는 문제다. int n; vector v; vector lis, back(100001, 0); vector ::iterator it; 사용하는 변수다. v는 입력받을때, lis는 수열을 담을 배열, back은 백트래킹 할때, it은..

https://www.acmicpc.net/problem/25311 25311번: UCPC에서 가장 쉬운 문제 번호는? 대회 참가자는 되도록 일찍 대회의 모든 문제를 한 번씩 읽어 보는 것이 권장됩니다. 이렇게 하면 대회의 전체적인 분위기를 느낄 수 있고, 종종 비교적 쉬운 문제를 빨리 발견해서 속도에서 우 www.acmicpc.net 구현문제다. 그냥 A출력하면 된다. #include #include using namespace std; string s; int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> s; cout

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