tose33

https://www.acmicpc.net/problem/2331 2331번: 반복수열 첫째 줄에 반복되는 부분을 제외했을 때, 수열에 남게 되는 수들의 개수를 출력한다. www.acmicpc.net 일단 풀긴 했는데 그래프? 스럽게 풀진 않은 것 같다. 문제에서 나온 수열 생성 방식에 따라 수열을 만들다 보면 반복되는 구간이 생기는데 이 반복되는 부분을 제외했을 때 남는 수들의 개수를 구하는 문제이다. nextnum 그렇다면 일단 제공된 수열 생성 방식에 따라 수열을 만들어야 한다. static int nextnum(int num, int p) { int sum = 0; int temp = num; while(temp != 0) { sum += Math.pow(temp % 10, p); temp /= ..

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 문제 그림만 봐도 11724. 연결 요소의 개수 문제와 상당히 비슷할 것처럼 보였다. 다른 점은 간선에 방향이 있다는 것? 그래서 그래프를 입력할 때 a [u]. add(v) a [v]. add(u) 이런 식으로 양방향을 입력할 필요 없다. int[] arr = new int[n + 1]; // arr에 삽입 for (int i..

https://www.acmicpc.net/problem/1707 1707번: 이분 그래프 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K(2≤K≤5)가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V(1≤V≤20,000)와 간선의 개수 www.acmicpc.net 그래프가 주어졌을 때 이분 그래프인지 아닌지 판별하는 문제. 일단 이분 그래프는 모든 정점들이 2개의 그룹으로 나뉘어 있고, 같은 그룹에 속해있는 정점끼리 이어져 있는 간선이 없는 그래프라고 한다. 그렇다면 모든 간선의 양 정점이 서로 다른 그룹에 속해있다는 것이다. DFS탐색을 하면 정점에서 간선으로 이어진 다음 정점으로 계속해서 이동한다. 그렇다면 탐색을 하면서 방문 여부를 기록하..

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 그래프가 주어지고 그 그래프가 연결돼 있는지 분리돼 있는지 판단하고 분리되어 있으면 몇 개로 분리되어 있는지 알아내는 문제. 일단 그래프가 분리되있는지 하나로 돼있는지 판단해야 하는데 DFS로 (BFS로 해도 될 것 같다) 첫 번째 정점에서부터 탐색을 시작한다. DFS로 탐색을 시작한다면 이어져있는 모든 정점을 방문하고 돌아올 것이..