ブルトポス1.試し方
109878 ワード
4つの方法のうち1つ目は
1)試し方(主に繰り返しの文を指し、文に用いる)
2)シーケンスの使用
3)「在帰」コールを使用する(順序が分からない、ビットマスクも代替可能).
4)ビットマスクの使用
📌質問2309号7人の小人
9人中7人探し 9人中2人探し👍
-> 9C2
ジュニア数がNの場合、N(N-1)/2 x 1=O(N)²)
=メソッドの個数(9人中2人見つけた)x試行の複雑さ(残り7人のジュニアの身長の和)
残りの矮人の身長の和:O(N)
⏳ O(N²) x O(N) = O(N³)
残りの矮人の身長の和:O(1)
「背の低い人の身長は変わらない」で獲得
七人の小人の身長=すべての身長の和-偽の小人iとj
= sum - tall[i]- tall[j]
= O(1)
⏳ O(N²) x O(1) = O(N²)
System.exit(0);
mainメソッドを終了(main内部関数でも実際に呼び出す)
📌質問3085：キャンディゲーム
グリッド、 を選択します.キャンディ交換 等の色からなる最長連続部分行又は列 を選択する.
何種類の方法がありますか.
1つの格子を選択した後、周囲の4つの格子の中から1つを選択します:N²x4 = O(N²)
(実際には、左上から順に行うので、右上と下角から選択できます)
3-1. 不明なため、MxNのテーブル全体のどれが一番長いかを一つ一つチェックする必要があります.O(N²)
3-2. 3-1メソッドでは時間を短縮できます.これは、連続する部分がある場合、行と列のみをチェックすることを意味します.O(N)
💡 時間を減らす方法は、複数回繰り返される演算があるかどうかにかかっています.
3-1使用.O(N²) x O(N²) = O(N⁴)
3-2使用.O(N²) x O(N) = O(N³)
N≦50,50⁴=625万<1億で満足
三二四速
2番コードの「交換したキャンディの行と列のみ比較」を利用
2つ目は1つの方法を用いたが,ここでは2つの方法を用いた.
1)試し方(主に繰り返しの文を指し、文に用いる)
2)シーケンスの使用
3)「在帰」コールを使用する(順序が分からない、ビットマスクも代替可能).
4)ビットマスクの使用
📌質問2309号7人の小人
https://www.acmicpc.net/problem/2309
タイムアウト2秒
9人のジュニアのうち7人の本当のジュニアを探さなければならない.
ジュニアの身長と100
9人のジュニアの身長を手に入れたとき、白雪姫に7人のジュニアを探すプログラムを書いてください.
入力
9列の小人の身長.与えられた身長は100を超えない自然数で、9人のジュニアの身長はすべて異なっていて、可能な答えがたくさんあれば、勝手に出力することができます.
📄しゅつりょく
昇順に7人の小人の身長を出力する.7人の小人が見つからないことはない.
👀例
入力例1
20 7 23 19 10 15 25 8 13
サンプル出力1
7 8 10 13 19 20 23
質問に答える
メソッド数
-> 9C2
ジュニア数がNの場合、N(N-1)/2 x 1=O(N)²)
⑨7人の小人を救う時間の複雑さ
=メソッドの個数(9人中2人見つけた)x試行の複雑さ(残り7人のジュニアの身長の和)
残りの矮人の身長の和:O(N)
⏳ O(N²) x O(N) = O(N³)
残りの矮人の身長の和:O(1)
「背の低い人の身長は変わらない」で獲得
七人の小人の身長=すべての身長の和-偽の小人iとj
= sum - tall[i]- tall[j]
= O(1)
⏳ O(N²) x O(1) = O(N²)
🌴 Code
System.exit(0);
mainメソッドを終了(main内部関数でも実際に呼び出す)
1. O(N³)
import java.util.*;
public class Main {
public static void main(String args[]) {
Scanner sc = new Scanner(System.in);
int n = 9;
int[] a = new int[n];
for (int i=0; i<n; i++) {
a[i] = sc.nextInt();
}
Arrays.sort(a);
for (int i=0; i<n; i++) {
for (int j=i+1; j<n; j++) {
int sum = 0;
for (int k=0; k<n; k++) {
if (i == k || j == k) continue;
sum += a[k];
}
if (sum == 100) {
for (int k=0; k<n; k++) {
if (i == k || j == k) continue;
System.out.println(a[k]);
}
System.exit(0);
}
}
}
}
}2. O(N²)
import java.util.*;
public class Main {
public static void main(String args[]) {
Scanner sc = new Scanner(System.in);
int n = 9;
int[] a = new int[n];
int sum = 0;
for (int i=0; i<n; i++) {
a[i] = sc.nextInt();
sum += a[i];
}
Arrays.sort(a);
for (int i=0; i<n; i++) {
for (int j=i+1; j<n; j++) {
if (sum - a[i] - a[j] == 100) {
for (int k=0; k<n; k++) { // 7명의 진짜 난쟁이 출력
if (i == k || j == k) continue; //가짜이면 넘어감
System.out.println(a[k]);
}
System.exit(0); // main 메소드 종료 (main 내부 함수에서도 실제호출)
}
}
}
}
}3.私のコード
package brute_force.n2309_일곱난쟁이;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;
public class Main {
public static int MAX = 9;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
ArrayList<Integer> list = new ArrayList<>();
int sum =0;
for (int i=0;i<MAX;i++){
list.add(sc.nextInt());
sum += list.get(i);
}
hi:
for (int i=0;i<MAX-1;i++){
for (int j=i+1;j<MAX;j++){
if(sum-100 == list.get(i)+list.get(j)){
list.remove(j);
list.remove(i);
break hi;
}
}
}
Collections.sort(list);
for (int k : list) System.out.println(k);
}
}
package brute_force.n2309_일곱난쟁이;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;
public class Main {
public static int MAX = 9;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
ArrayList<Integer> list = new ArrayList<>();
int sum =0;
for (int i=0;i<MAX;i++){
list.add(sc.nextInt());
sum += list.get(i);
}
for (int i=0;i<MAX-1;i++){
for (int j=i+1;j<MAX;j++){
if(sum-100 == list.get(i)+list.get(j)){
list.remove(j);
list.remove(i);
Collections.sort(list);
for (int k : list) System.out.println(k);
System.exit(0)
}
}
}
}
}
📌質問3085：キャンディゲーム
https://www.acmicpc.net/problem/3085
タイムアウト1秒
最初はN×砂糖をnサイズのところに入れる.キャンディの色が違うかもしれません.上根は隣接するキャンディの色の異なる格子を2つ選んだ.それから均一な四角い格子の中のキャンディを交換します.今では、すべての人が同じ色からなる最長の連続部分(行または列、1行のみ)を選択し、すべてのキャンディを食べてしまいます.
あなたがあなたにあげた砂糖が満たされたとき、プログラムを書いて、あなたが食べられる砂糖の最大個数を求めます.
入力
最初の行は、プレートのサイズNを与える.(3 ≤ N ≤ 50)
次のN行は、板紙に充填されたキャンディの色を与える.赤はC、青はP、緑はZ、黄色はYです.
隣接する2つのキャンディ色の異なる格子が存在する入力のみが与えられる.
📄しゅつりょく
1行目は、食べられるキャンディの最大個数を出力します.
👀例
入力例1
5
YCPZY
CYZZP
CCPPP
YCYZC
CPPZZ
サンプル出力1
4
最大の隣接キャンディ数は4個で、以下の2列目にCが4個隣接していることがわかります.
YCPZY
YCZZP
CCPPP
YCYZC
CPPZZ
質問に答える
2つの隣接する
何種類の方法がありますか.
1.隣接する2つのグリッドを選択
1つの格子を選択した後、周囲の4つの格子の中から1つを選択します:N²x4 = O(N²)
(実際には、左上から順に行うので、右上と下角から選択できます)
2.交換後、同じ色で構成されていない場合は、返却し直します。
3.同じ色からなる最長連続部分を選択
3-1. 不明なため、MxNのテーブル全体のどれが一番長いかを一つ一つチェックする必要があります.O(N²)
3-2. 3-1メソッドでは時間を短縮できます.これは、連続する部分がある場合、行と列のみをチェックすることを意味します.O(N)
💡 時間を減らす方法は、複数回繰り返される演算があるかどうかにかかっています.
表の合計時間の複雑さ
3-1使用.O(N²) x O(N²) = O(N⁴)
3-2使用.O(N²) x O(N) = O(N³)
N≦50,50⁴=625万<1億で満足
🌴 Code
三二四速
1.時間複雑度O(N^4)
package brute_force.n3085_사탕게임;
import java.util.*;
//시간복잡도 O(N^4)
public class Main {
//가장 긴 연속부분을 찾는 메소드 O(N^2)
static int check(char[][] a) {
int n = a.length;
int ans = 1;
for (int i=0; i<n; i++) {
int cnt = 1; //인접한 사탕의 개수
for (int j=1; j<n; j++) { //열
if (a[i][j] == a[i][j-1]) { //i행에서 1열씩 증가하며 인접한 사탕 있는지 검사
cnt += 1;
} else {
cnt = 1;
}
if (ans < cnt) ans = cnt; //최대의 인접함 찾기
}
cnt = 1;
for (int j=1; j<n; j++) { //행
if (a[j][i] == a[j-1][i]) { //i열에서 1행씩 증가하며 인접한 사탕 있는지 검사
cnt += 1;
} else {
cnt = 1;
}
if (ans < cnt) ans = cnt;
}
}
return ans;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
char[][] a = new char[n][n];
for (int i=0; i<n; i++) {
a[i] = sc.next().toCharArray();
}
int ans = 0;
for (int i=0; i<n; i++) {
for (int j=0; j<n; j++) { //i행에서 1열씩 증가
if (j+1 < n) { //오른쪽
char t = a[i][j]; a[i][j] = a[i][j+1]; a[i][j+1] = t; //교환
int temp = check(a); //가장 긴 사탕 찾기
if (ans < temp) {
ans = temp;
// for (char [] k: a){
// for (char l :k) System.out.print(l);
// System.out.println();
// }
// System.out.println(ans);
}
t = a[i][j]; a[i][j] = a[i][j+1]; a[i][j+1] = t; //모든 경우를 검사해야 하기 때문에 교환한것 다시 원래대로
}
if (i+1 < n) { //아래
char t = a[i][j]; a[i][j] = a[i+1][j]; a[i+1][j] = t;
int temp = check(a);
if (ans < temp) {
ans = temp;
// for (char [] k: a){
// for (char l :k) System.out.print(l);
// System.out.println();
// }
// System.out.println(ans);
}
t = a[i][j]; a[i][j] = a[i+1][j]; a[i+1][j] = t;
}
}
}
System.out.println("ans : "+ans);
}
}
2.時間複雑度O(N^3)
package brute_force.n3085_사탕게임;
import java.util.*;
//시간복잡도 O(N^3)
public class Main2 {
//가장 긴 연속부분을 찾는 메소드 O(N)
//연속된 부분이 나타난 행과 열만 검사
static int check(char[][] a, int start_row, int end_row, int start_col, int end_col) {
int n = a.length;
int ans = 1;
//가로줄 연속부분
for (int i=start_row; i<=end_row; i++) {
int cnt = 1;
for (int j=1; j<n; j++) {
if (a[i][j] == a[i][j-1]) {
cnt += 1;
} else {
cnt = 1;
}
if (ans < cnt) ans = cnt;
}
}
//세로줄 연속부분
for (int i=start_col; i<=end_col; i++) {
int cnt = 1;
for (int j=1; j<n; j++) {
if (a[j][i] == a[j-1][i]) {
cnt += 1;
} else {
cnt = 1;
}
if (ans < cnt) ans = cnt;
}
}
return ans;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
char[][] a = new char[n][n];
for (int i=0; i<n; i++) {
a[i] = sc.next().toCharArray();
}
int ans = 0;
for (int i=0; i<n; i++) {
for (int j=0; j<n; j++) { //i행을 기준으로 한열씩 이동해서 검사
if (j+1 < n) {//오른쪽
char t = a[i][j]; a[i][j] = a[i][j+1]; a[i][j+1] = t; //교환
int temp = check(a, i, i, j, j+1);
if (ans < temp) ans = temp;
t = a[i][j]; a[i][j] = a[i][j+1]; a[i][j+1] = t;
}
if (i+1 < n) {//아래
char t = a[i][j]; a[i][j] = a[i+1][j]; a[i+1][j] = t;
int temp = check(a, i, i+1, j, j);
if (ans < temp) ans = temp;
t = a[i][j]; a[i][j] = a[i+1][j]; a[i+1][j] = t;
}
}
}
System.out.println(ans);
}
}3.符号化Oを見ない(N^4)
package brute_force.n3085_사탕게임;
import java.util.Scanner;
public class Prac1 {
//연결된 사탕갯수 검사
public static int max (char [][] arr){
int cnt = 0;
int ans = 1;
for (int i =0;i<arr.length;i++){
//가로 줄 검사
cnt = 1; // ❗
for (int j=1;j<arr.length;j++){
if(arr[i][j-1] == arr[i][j]) cnt++;
else cnt =1;
if(ans<cnt) ans = cnt;
}
//세로 줄 검사
cnt = 1; // ❗
for (int j=1;j<arr.length;j++){
if(arr[j-1][i]==arr[j][i]) cnt++;
else cnt = 1;
if(ans<cnt) ans = cnt;
}
}
return ans;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
char [][] candy = new char[n][n];
for (int i =0; i<n; i++){
candy[i] = sc.next().toCharArray(); //입력 받은 문자열을 char배열형태로 바꿈
}
int m = 1;
for(int i=0;i<n;i++){
for (int j=1;j<n;j++){
//오른쪽에 있는 사탕이랑 교환
char t = candy[i][j-1];
candy[i][j-1] = candy[i][j];
candy[i][j] = t;
//가장 긴지 검사..
if(m<max(candy)) {
m = max(candy);
// for (char [] k: candy){
// for (char l :k) System.out.print(l);
// System.out.println();
// }
// System.out.println("right : "+m);
}
t = candy[i][j-1];
candy[i][j-1] = candy[i][j];
candy[i][j] = t;
}
for (int j=1;j<n;j++){
//아래에 있는 사탕이랑 교환
char t = candy[j-1][i];
candy[j-1][i] = candy[j][i];
candy[j][i] = t;
if(m<max(candy)) {
m = max(candy);
// for (char [] k: candy){
// for (char l :k) System.out.print(l);
// System.out.println();
// }
// System.out.println("down: "+m);
}
t = candy[j-1][i];
candy[j-1][i] = candy[j][i];
candy[j][i] = t;
}
}
System.out.println(m);
}
}
4.符号化Oを見ない(N^3)
2番コードの「交換したキャンディの行と列のみ比較」を利用
2つ目は1つの方法を用いたが,ここでは2つの方法を用いた.
package brute_force.n3085_사탕게임;
import java.util.Scanner;
public class Prac2 {
public static int max_2column(char[][] candy,int row,int column){
int ans = 0;
//가로줄 1개 검사
int cnt = 1;
for (int i=1;i<candy.length;i++) {
if (candy[row][i - 1] == candy[row][i]) cnt++;
else cnt = 1;
if (ans < cnt) ans = cnt;
}
//세로줄 2개 검사
cnt = 1;
for (int i=1;i<candy.length;i++) {
if (candy[i - 1][column - 1] == candy[i][column - 1]) cnt++;
else cnt = 1;
if (ans < cnt) ans = cnt;
}
cnt=1;
for (int i=1;i<candy.length;i++){
if(candy[i-1][column]==candy[i][column]) cnt++;
else cnt = 1;
if(ans < cnt) ans = cnt;
}
return ans;
}
public static int max_2row(char[][] candy,int row,int column){
int ans = 0;
//세로줄 1개 검사
int cnt = 1;
for (int i=1;i<candy.length;i++) {
if (candy[i - 1][column] == candy[i][column]) cnt++;
else cnt = 1;
if (ans < cnt) ans = cnt;
}
//가로줄 2개 검사
cnt = 1;
for (int i=1;i<candy.length;i++) {
if (candy[row - 1][i - 1] == candy[row - 1][i]) cnt++;
else cnt = 1;
if (ans < cnt) ans = cnt;
}
cnt=1;
for (int i=1;i<candy.length;i++){
if(candy[row][i-1]==candy[row][i]) cnt++;
else cnt = 1;
if(ans < cnt) ans = cnt;
}
return ans;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
char [][] candy = new char[n][n];
for (int i=0;i<n;i++){
candy[i] = sc.next().toCharArray();
}
int m = 1;
for(int i=0;i<n;i++){
for (int j=1;j<n;j++){ //오른쪽
char t = candy[i][j-1];
candy[i][j-1] = candy[i][j];
candy[i][j] = t;
int tmp = max_2column(candy,i,j);
if(m<tmp) m = tmp;
t = candy[i][j-1];
candy[i][j-1] = candy[i][j];
candy[i][j] = t;
}
for (int j=1;j<n;j++){ //아래
char t = candy[j-1][i];
candy[j-1][i] = candy[j][i];
candy[j][i] = t;
int tmp = max_2row(candy,j,i);
if(m<tmp) m = tmp;
t = candy[j-1][i];
candy[j-1][i] = candy[j][i];
candy[j][i] = t;
}
}
System.out.println(m);
}
}
Reference
この問題について(ブルトポス1.試し方), 我々は、より多くの情報をここで見つけました https://velog.io/@ppnrn/브루트포스1.-다-해보는-방법テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol