피너클의 it공부방

https://www.acmicpc.net/problem/2902 2902번: KMP는 왜 KMP일까? 입력은 한 줄로 이루어져 있고, 최대 100글자의 영어 알파벳 대문자, 소문자, 그리고 하이픈 ('-', 아스키코드 45)로만 이루어져 있다. 첫 번째 글자는 항상 대문자이다. 그리고, 하이픈 뒤에는 반드 www.acmicpc.net 간단한 구현 문제다. #include #include using namespace std; string str; int main() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin >> str; cout

https://www.acmicpc.net/problem/10974 10974번: 모든 순열 N이 주어졌을 때, 1부터 N까지의 수로 이루어진 순열을 사전순으로 출력하는 프로그램을 작성하시오. www.acmicpc.net dfs로 풀었다. void solve(int idx, vector v) { if (idx == n) { for (int i = 0; i < n; i++) cout

https://www.acmicpc.net/problem/1707 1707번: 이분 그래프 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V와 간선의 개수 E가 빈 칸을 사이에 www.acmicpc.net bfs를 이용해 풀었다. 이분 그래프란 무엇인가 위와 같은 그래프다. 이웃한 정점끼리는 색이 절대로 같지 않다. 위의 그래프는 1과 2가 이웃하지만 서로 색이 같으니 이분 그래프가 아니다. int v, e; int color[20001]; vector graph[20001]; 사용할 변수들이다. color[i]는 i번째 정점에 들어있는 색이고 graph[i]는 i에 이웃한 정점을을 저장한다. in..

https://www.acmicpc.net/problem/10819 10819번: 차이를 최대로 첫째 줄에 N (3 ≤ N ≤ 8)이 주어진다. 둘째 줄에는 배열 A에 들어있는 정수가 주어진다. 배열에 들어있는 정수는 -100보다 크거나 같고, 100보다 작거나 같다. www.acmicpc.net 백트래킹 문제다. cin >> n; for (int i = 0; i > arr[i]; memset(visited, false, sizeof(visited)); int ans = solve(vector()); cout n; for (int i = 0; i > arr[i]; memset(visited, false, sizeof(visited)); int ans ..

https://www.acmicpc.net/problem/2003 2003번: 수들의 합 2 첫째 줄에 N(1 ≤ N ≤ 10,000), M(1 ≤ M ≤ 300,000,000)이 주어진다. 다음 줄에는 A[1], A[2], …, A[N]이 공백으로 분리되어 주어진다. 각각의 A[x]는 30,000을 넘지 않는 자연수이다. www.acmicpc.net 투 포인터 문제다. int n, m; int arr[10001]; 사용할 변수다. cin >> n >> m; for (int i = 0; i > arr[i]; int ans = 0, sum = 0; int start = 0, end = 0; 값들을 입력받는다. start와 end는 투 포인터에서 사용할것이다. while (end ..

https://www.acmicpc.net/problem/2644 2644번: 촌수계산 사람들은 1, 2, 3, …, n (1 ≤ n ≤ 100)의 연속된 번호로 각각 표시된다. 입력 파일의 첫째 줄에는 전체 사람의 수 n이 주어지고, 둘째 줄에는 촌수를 계산해야 하는 서로 다른 두 사람의 번호가 주어 www.acmicpc.net 브루트포스를 이용해 풀었다. int n, m; int a, b; bool visited[101]; vector v[101]; 사용할 변수다. cin >> n; cin >> a >> b; cin >> m; memset(visited, false, sizeof(visited)); for (int i = 0; i > a >> b; v[..

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 유니온 파인드 문제다. int n, m; int parent[1000001]; 사용할 변수다. parent[5] = 10이라면 5의 조상이 10이라는 의미다. parent[i] = j이라면 i의 조상이 j이라는 의미다. int find(int u) { if (u == parent[u]) return u; return parent[u] = find(paren..

https://www.acmicpc.net/problem/1028 1028번: 다이아몬드 광산 첫째 줄에 R과 C가 주어진다. R과 C는 750보다 작거나 같은 자연수이다. 둘째 줄부터 R개의 줄에는 다이아몬드 광산의 모양이 주어진다. www.acmicpc.net 완전탐색과 다이나믹을 응용해 풀었다. int r, c; string map[751]; int up_left[751][751]; int up_right[751][751]; int down_left[751][751]; int down_right[751][751]; 사용할 변수다. up_left는 왼쪽 위로 1이 얼마나 있는지다. 위의 그래프에서 up_left[3][3] = 2다. 그 외 up_right나 down_left도 이름과 맞는 의미를 같는..

https://www.acmicpc.net/problem/2522 2522번: 별 찍기 - 12 첫째 줄부터 2×N-1번째 줄까지 차례대로 별을 출력한다. www.acmicpc.net 구현문제다. #include using namespace std; int n; int main() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin >> n; for (int i = 1; i

https://www.acmicpc.net/problem/3053 3053번: 택시 기하학 첫째 줄에는 유클리드 기하학에서 반지름이 R인 원의 넓이를, 둘째 줄에는 택시 기하학에서 반지름이 R인 원의 넓이를 출력한다. 정답과의 오차는 0.0001까지 허용한다. www.acmicpc.net 구현문제다. 왼쪽이 유클리드 기하학에서의 원의 넓이, 오른쪽이 택시 기하학에서의 원의 넓이다. #include using namespace std; const double PI = 3.1415926535897932; int r; int main() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin >> r; cout