알고리즘 특강 2일차 : Simulation

simulation이란? : 문제가 시키는 규칙을 원하는 대로 그대로 실현하는 것

 

완전탐색

 

모든 경우의 수를 탐색하는 방법(ex : 자물쇠의 비밀번호를 알기 위해 000 부터 999까지 다 해본다.)

 

• 문제를 풀 수 있는 가장 확실한 방법.
• 시간이 오래걸린다는 단점이 있다.

import java.io.*;
import java.util.*;
import java.math.*;


public class Main {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());
        int[][] arr = new int[n][n];


        StringTokenizer st;

        for(int i = 0;i<n;i++){ //배열 입력받기
            st = new StringTokenizer(br.readLine());
            for(int j = 0;j<n;j++){
                arr[i][j] = Integer.parseInt(st.nextToken());

            }
        }

        int ans = 0;

        for(int i = 0;i<n-2;i++){
            for(int j = 0;j<n-2;j++){ //i와 j는 3*3배열의 왼쪽 위의 것
                int cnt = 0;

                for(int k = 0;k<3;k++){ //격자 내의 1의 값 세기
                    for(int m = 0;m<3;m++){
                        if(arr[i+k][j+m] == 1){
                            cnt++;
                        }
                    }
                }

                ans = Math.max(ans, cnt); //최댓값 갱신
            

            }
        }

        System.out.println(ans);
    }
}

이 코드는 입력받은 배열에서 3*3 격자 안에 들어갈 수 있는 1의 갯수의 최댓값을 완전탐색으로 구하는 코드이다.

 

 

배열 회전시키기

 

for(int i = 0;i<m;i++){
            int temp = arr[2*n-1];
            for(int j = 2*n-1; j>=1;j--){
                arr[j] = arr[j-1];
            }
            arr[0] = temp;
        }

이렇게 배열의 가장 끝에 있는 수는 temp변수에 넣어두고, 나머지 배열들은 한 칸씩 땡긴다. 그리고 남은 자리에 아까 넣어두었던 수를 대입해준다.

위의 경우에는 오른쪽으로 미는 경우이니까 가장 오른 쪽에 있는 수를 변수에 저장하고 나머지 배열들을 arr[j] = arr[j-1]을 이용해서 밀어준 후에 변수에 저장되어있던 수를 arr[0]에 넣어주었다.

 

 

격자 안에서 떨어지고 터지는 경우

 

 

1	1
		1

 

1	1	1

 이 경우와 같이 위에 있던 요소들이 중력에 의해 떨어지듯이 모두 아래로 내려오도록 프로그래밍하는 것이다.

 

 

기존 배열을 두고 새 배열을 만든 후 아래서부터 차례로 탐색하면서  순차적으로 새 배열에 수를 옮겨주는 방법

row는 기존 배열에서 탐색하고 있는 줄을 나타내는 변수이고, tempRow는 새로운 배열에 넣어야 할 줄을 나타내는 변수이다.

 

https://ethereal-coder.tistory.com/71

코드트리 [자바 java] 1차원젠가

이를 참고해서 문제를 풀어보았다.

 

격자 안에서 여러 객체를 이동

 

격자 안에 여러 객체들이 주어지고 이들을 조건에 따라 움직여야 하는 문제 역시 같은 크기의 빈 배열을 만들고 조건에 맞게 하나씩 옮긴 후 이를 다시 원래 배열에 clone해주는 방법을 사용한다.

 

예시문제이다.

https://ethereal-coder.tistory.com/72

코드트리 [자바 java] 숫자가 가장 큰 인접한 곳으로 동시에 이동

 

 

새로운 배열을 만들어서 문제를 푸는 것은 시간낭비와, 메모리 낭비가 크다고 생각했는데 막상 풀어보니까 괜찮아서 앞으로 이 방법을 많이 사용해야겠다.