목록백준 (183)
Study hard
https://www.acmicpc.net/problem/10451 10451번: 순열 사이클 문제 1부터 N까지 정수 N개로 이루어진 순열을 나타내는 방법은 여러 가지가 있다. 예를 들어, 8개의 수로 이루어진 순열 (3, 2, 7, 8, 1, 4, 5, 6)을 배열을 이용해 표현하면 \(\begin{pmatrix} 1 & 2 &3&4&5&6&7&8 www.acmicpc.net [풀이] bfs를 이용하여 풀었다. 이어진 정점을 방문하다가 처음 시작했던 정점이 나오면 순열 사이클이므로 개수를 갱신해 주었다. #include #include #include //memset using namespace std; int T, N; int P[1001];//순열 저장 bool check[1001];//방문한 정..
https://www.acmicpc.net/problem/1707 1707번: 이분 그래프 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K(2≤K≤5)가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V(1≤V≤20,000)와 간선의 개수 www.acmicpc.net [풀이] bfs와 dfs로 모든 정점을 돌면서 서로 이어진 정점들을 다른 그룹에 넣는 방식으로 풀었다. #include #include #include using namespace std; int K, V, E; vectorGraph[20001];//각 정점에 연결된 간선 저장 int Group[20001];//그룹 1, 그룹 2, 0이면 아직 방문X void init() { for ..
https://www.acmicpc.net/problem/11724 11724번: 연결 요소의 개수 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주�� www.acmicpc.net [풀이] 연결 요소 : 한 개 이상의 간선으로 연결된 정점들로 이루어진 그래프.(서로 아무 관련 없는 각각의 그래프) 연결 요소 조건 - 연결 요소에 속한 모든 정점을 잇는 경로가 존재해야 함. - 다른 연결 요소에 속하는 정점과 이어지는 경로가 있으면 안됨. 방문을 체크하는 배열을 만들어서 체크하지 않은 정점을 시작점으로 bfs를..
https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net dfs알고리즘, bfs알고리즘 #include #include #include //memset using namespace std; int N, M, V; int Graph[1001][1001];//이어진 정점들 1 표시 bool check[1001]; void dfs(int curV) { check[curV] = true; cout V; for (int i ..
https://www.acmicpc.net/problem/2004 2004번: 조합 0의 개수 첫째 줄에 정수 n, m(0≤m≤n≤2,000,000,000, n!=0)이 들어온다. www.acmicpc.net [풀이] nCm = n! / m!(n-m)!이므로 n!을 구할 때 나오는 2의 개수 - m!을 구할 때 나오는 2의 개수 - (n-m)!을 구할 때 나오는 2의 개수와, n!을 구할 때 나오는 5의 개수 - m!을 구할 때 나오는 5의 개수 - (n-m)!을 구할 때 나오는 5의 개수 중에 더 작은 수가 0의 개수가 된다. (2 * 5의 개수이기 때문!) 2020/06/18 - [백준/여러가지 문제들] - (c++)백준 1676번: 팩토리얼 0의 개수 (c++)백준 1676번: 팩토리얼 0의 개수 ..
https://www.acmicpc.net/problem/1676 1676번: 팩토리얼 0의 개수 N!에서 뒤에서부터 처음 0이 아닌 숫자가 나올 때까지 0의 개수를 구하는 프로그램을 작성하시오. www.acmicpc.net [풀이] 팩토리얼을 일일이 구하면 어느 순간 기하급수적으로 커지기 때문에 한계가 있다. 팩토리얼을 구하면서 10이 몇번 곱해지는 지를 구하면 된다. 1부터 N까지 for문을 돌리면서 각 수에 2와 5가 몇 개씩 포함되어 있는지 센다. 더 적은 개수가 2 * 5(10)의 개수이다. ex)12 1, 2, 3, 4(2 * 2), 5, 6(2 * 3), 7, 8(2 * 2 * 2) , 9, 10(2 * 5), 11, 12(2 * 2 * 3) 2 개수 : 10개 5 개수 : 2개 2 * 5(..