땅지원의 A형 대비 기출 분석

• 문제 진짜 꼼꼼히 읽기
• 그리디로 이런걸로 생각이 안나면 무조껀 그냥 완탐으로 돌리면 된다
• 구현 문제는 배열돌리기, 여러 배열들 간의 index로 장난치기 유의하기
• 최대, 최소 구한다는 말 자체도 모든 경우를 본다음에 Math.min, max 돌리는 것
• 기출 분석 결과 완전탐색 + 추가 알고리즘, 구현 형식으로 많이 나오니까 너무 어렵게 생각하지말고 똑똑하게 풀기 

 

 

2383. [모의 SW 역량테스트] 점심 식사시간

SW Expert Academy

어려움

아직도 모르겠다

2382. [모의 SW 역량테스트] 미생물 격리

SW Expert Academy

백준 17143 낚시왕 (구현, 시뮬레이션)

 

1949. [모의 SW 역량테스트] 등산로 조성

SW Expert Academy

가장 높은 봉우리부터 시작해서 사방탐색을 하면서 dfs를 돌리면 된다.

문제는 k 깊이만큼 공사가 가능하다는 점인데

 

if 이동가능

    이동

else if 이동 불가능하고 공사를 아직 안했다

    for 1~k 만큼 공사 가능

        공사해서 이동

 

이런식으로 풀어나갈 수 있다.

 

 

1952. [모의 SW 역량테스트] 수영장

SW Expert Academy

SWEA 1952 수영장(DFS, DP)

 

1953. [모의 SW 역량테스트] 탈주범 검거

SW Expert Academy

SWEA 1953 탈주범 검거(BFS, 구현)

 

2112. [모의 SW 역량테스트] 보호 필름

SW Expert Academy

단면의 모든 세로방향에 대해서 동일한 특성의 셀들이 K개 이상 연속적으로 있는 경우에만 성능검사를 통과하게 된다.

행으로 약품을 넣어서 성능검사 통과하게 해야하는데 어떻게 하면 통과할지 모르겠는데? => 완탐

 

2115. [모의 SW 역량테스트] 벌꿀채취

SW Expert Academy

M개의 벌꿀통을 채취할 때 모든 가능한 경우에 따른 최대값을 구한다

이때 꿀의 양이 C를 넘으면 for 1 ~ M-1해서 가장 큰 거 찾으면 된다(N의 범위가 작기 때문에 가능)

 

2117. [모의 SW 역량테스트] 홈 방범 서비스

SW Expert Academy

SWEA 2117 홈 방문 서비스(BFS)

 

2105. [모의 SW 역량테스트] 디저트 카페

SW Expert Academy

어떤 지점에서 시작해서 어떤 방향으로 해야 최적의 정답이 될까? => DFS 완탐

특이점은 상하좌우가 아닌 대각선으로 움직이기 때문에 dfs를 호출할 때 boundary check로 먼저 거를 수 있다

2477. [모의 SW 역량테스트] 차량 정비소

SW Expert Academy

빡 시뮬레이션 문제

• 접수완료 처리
• 접수창구에 고객 배정
• 정비완료 처리
• 정비창구에 고객 배정

 

4008. [모의 SW 역량테스트] 숫자 만들기

SW Expert Academy

SWEA 4008 숫자만들기(DFS)

 

4012. [모의 SW 역량테스트] 요리사

SW Expert Academy

식재료 N개, A음식 : N/2개, B음식 : A가 고르지 않은 N/2개를 선택하기 위해 조합을 사용

A음식, B음식을 고른걸 가지고 2칸짜리 순열을 모두 만들어서(완탐) 최솟값 찾기

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Solution {

	static int N; // 음식 수
	static int[][] food; // 음식 배열
	static int S; // 시너지
	static int[] syn,isSelected; // 시너지의 합을 넣을 배열
	static int k;
	static int sum_temp;
	static int res = Integer.MAX_VALUE;

	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		int T = Integer.parseInt(st.nextToken());

		for (int tc = 1; tc <= T; tc++) {
			st = new StringTokenizer(br.readLine());
			N = Integer.parseInt(st.nextToken());
			food = new int[N][N];
			isSelected = new int [N/2];
			
			for (int i = 0; i < N; i++) {
				st = new StringTokenizer(br.readLine());
				for (int j = 0; j < N; j++) {
				
					food[i][j] = Integer.parseInt(st.nextToken());
				}
			}
			
			combi(0, 0);
			
			System.out.println("#"+tc+" "+res);
			res = Integer.MAX_VALUE;
			
		}

	}
	
	
	
	public static void combi(int depth, int start) {
		//기저조건
		if(depth==N/2) {
			
			int [] A = isSelected;
			int [] B = new int[N/2];
			boolean [] rev = new boolean [N];
			for(int idx : A) 
				rev[idx] = true;
			
			for (int i = 0,j=0; i < N; i++) {
				if (!rev[i]) {
					B[j++] = i;
				}
			}
			
			//System.out.println(Arrays.toString(A));
			//System.out.println(Arrays.toString(B));
			
			
			boolean[] visited = new boolean[N/2];
			int[] select_permu = new int[2];
			
			permu(0,A,visited,select_permu);
			int A_sum = sum_temp;
			//System.out.println(A_sum);
			sum_temp=0;
			
			permu(0,B,visited,select_permu);
			int B_sum = sum_temp;
			//System.out.println(B_sum);
			sum_temp=0;
			
			res = Math.min(res, Math.abs(A_sum-B_sum));
			
		return;
		}
		for(int i=start; i<N; i++) {
			isSelected[depth]=i;
			combi(depth+1, i+1);
		}
		
	}
	
	public static void permu(int depth,int[] data,boolean[] visited, int[] select_permu) {
		
		if (depth == 2) {
//			System.out.println(Arrays.toString(select_permu));
			sum_temp += food[select_permu[0]][select_permu[1]];
			return;
		}
		
		for (int i = 0; i < N/2; i++) {
			if (!visited[i]) {
				visited[i] = true;
				select_permu[depth] = data[i];
				permu(depth+1,data,visited, select_permu);
				visited[i] = false;
			}
				
		}
		
	}
	
	
}

 

4013. [모의 SW 역량테스트] 특이한 자석

SW Expert Academy

14891번: 톱니바퀴

규칙을 찾은 다음 배열돌리기 하면 되는 문제였다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.StringTokenizer;

public class Main {
	static List<Integer>[] data;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		data = new ArrayList[5];
		
		for (int i = 1; i <5; i++) 
			data[i] = new ArrayList<>();
		
		for (int i = 1; i < 5; i++) {
			String[] input = br.readLine().split("");
			for (int j = 0; j < 8; j++) 
				data[i].add(Integer.parseInt(input[j]));
		}

		
		//1(3) - 2(7)
		//2(3) - 3(7)   이 경우 살펴보면 될 듯
		//3(3) - 4(7)
		
		int n = Integer.parseInt(br.readLine());
		
		for (int i = 0; i < n; i++) {
			st = new StringTokenizer(br.readLine());
			int num = Integer.parseInt(st.nextToken());
			int direct = Integer.parseInt(st.nextToken());
			
			left_rotate(num-1,-direct);
			right_rotate(num+1,-direct);
			Collections.rotate(data[num], direct);			
		}
		
		int res = 0;
		
		for (int i = 0; i < 4; i++) { 
			res += data[i+1].get(0) * Math.pow(2, i);
		}
		System.out.println(res);
		
	}
	
	public static void left_rotate(int num, int direct) {
		if ((num<1))
			return;
		if (data[num].get(2) != data[num+1].get(6)) {
			left_rotate(num-1,-direct);
			Collections.rotate(data[num], direct);
		}
	}
	
	public static void right_rotate(int num, int direct) {
		if ((num>4))
			return;
		if (data[num-1].get(2) != data[num].get(6)) {
			right_rotate(num+1,-direct);
			Collections.rotate(data[num], direct);
		}
	}

}

 

4014. [모의 SW 역량테스트] 활주로 건설

SW Expert Academy

14890번: 경사로

Point: 경사로를 설치해서 높이를 일정하게 하라고 하는건 알겠는데 그럼 어느정도 높이를 맞춰야 활주로를 건설 할 수 있나?
=> 처음부터 끝까지 높이가 일정해지면 그떄 가능. 중간에 끊기면 아예 그 case는 포기해야됨

따라서 arr[0]부터 시작해서 +1, -1 차이나는 구간에 경사로를 설치할 수 있다는 뜻이니까 거기서
for x만큼 검사를 해주면서 return false를 판단하면 되는 구현 문제이다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Solution {
    static int N,X,res;
    static int[][] board;

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

        int T = Integer.parseInt(st.nextToken());
        for (int tc = 1; tc < T+1; tc++) {
            st = new StringTokenizer(br.readLine());

            N = Integer.parseInt(st.nextToken());
            X = Integer.parseInt(st.nextToken());

            board = new int[N][N];

            for (int i = 0; i < N; i++) {
                st = new StringTokenizer(br.readLine());
                for (int j = 0; j < N; j++) {
                    board[i][j] = Integer.parseInt(st.nextToken());
                }
            }


            res = 0;

            //행 검사
            for (int i = 0; i < N; i++) {
                if (check(board[i])){
                    res++;
                }
            }

            //열 검사
            for (int i = 0; i < N; i++) {
                int[] arr = new int[N];
                for (int j = 0; j < N; j++) {
                    arr[j] = board[j][i];
                }
                if (check(arr)){
                    res++;
                }
            }


            System.out.println("#"+tc+" "+res);

            
        }
    }

    public static boolean check(int[] arr){

        int std = arr[0];
        int cnt = 1; //for문을 1부터 시작하고 있기 때문
        for (int i = 1; i < N; i++) {
            if (arr[i] == std){
                cnt++;
                continue;
            }

            if (arr[i] == std+1){ //cnt에 담았던 개수만큼 판별하면됨, 다시 뒤로 for문 돌릴 필요가 없음
                if (cnt < X)
                    return false;

                std = arr[i];
                cnt = 1; //단순히 cnt로만 판별한 것이고 현재 지금 있는 위치는 std+1자리이니까 얘부터 cnt 고려를 해줘야되기 때문에
            }
            else if (arr[i] == std-1){ //앞으로 for x만큼 공간이 있는지 봐줘야함
                for (int j = 1; j < X; j++) {
                    if ((i+j)>=N || arr[i+j]!=std-1)
                        return false;
                }
                std = arr[i];
                cnt = 0; //for x까지 경사로를 설치했기 때문에 새로 0부터 시작해야됨
                i += X-1;
            }
            else{
                return false;
            }
        }
        return true;
    }

}

 

 

5644. [모의 SW 역량테스트] 무선 충전

SW Expert Academy

어려워 포기할래

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
import java.util.PriorityQueue;

public class Solution {
	static int[] dx = { 0, -1, 0, 1, 0 };
	static int[] dy = { 0, 0, 1, 0, -1 };
	static int[][] bc_data;
	static String[][] board;
	static int[] A, B;
	static int bc_cnt, A_x, A_y, B_x, B_y;
	static List<Integer> temp;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int t = Integer.parseInt(br.readLine());

		for (int tc = 1; tc < t + 1; tc++) {
			board = new String[10][10];

			String[] input = br.readLine().split(" ");
			int length = Integer.parseInt(input[0]);
			bc_cnt = Integer.parseInt(input[1]);

			temp = new ArrayList<>();
			A = new int[length + 1];
			B = new int[length + 1];

			input = br.readLine().split(" ");
			for (int i = 0; i < length; i++)
				A[i] = Integer.parseInt(input[i]);

			input = br.readLine().split(" ");
			for (int i = 0; i < length; i++)
				B[i] = Integer.parseInt(input[i]);

			bc_data = new int[bc_cnt][4];

			for (int i = 0; i < bc_cnt; i++) {
				input = br.readLine().split(" ");
				for (int j = 0; j < 4; j++) {
					bc_data[i][j] = Integer.parseInt(input[j]);
				}
			}
			board_init();
			bc_board_init();

			A_x = 0;
			A_y = 0;

			B_x = 9;
			B_y = 9;

			for (int i = 0; i < length + 1; i++) {
				String A_temp = board[A_x][A_y];
				String B_temp = board[B_x][B_y];

				if (!A_temp.equals(B_temp) && A_temp.length() == 1 && B_temp.length() == 1) {
					temp.add(bc_data[A_temp.charAt(0) - 'A'][3]);
					temp.add(bc_data[B_temp.charAt(0) - 'A'][3]);
				}

				else if (A_temp.equals(B_temp) && A_temp.length() == 1) {
					temp.add(bc_data[A_temp.charAt(0) - 'A'][3] / 2);
					temp.add(bc_data[B_temp.charAt(0) - 'A'][3] / 2);
				}

				else if (A_temp.equals("") && B_temp.length() == 1) {

					temp.add(bc_data[B_temp.charAt(0) - 'A'][3]);
				}

				else if (B_temp.equals("") && A_temp.length() == 1) {

					temp.add(bc_data[A_temp.charAt(0) - 'A'][3]);

				}

				else if (A_temp.length() > 1 && B_temp.equals("")) {

					int max = 0;
					for (int j = 0; j < A_temp.length(); j++) {
						max = Math.max(max, bc_data[A_temp.charAt(j) - 'A'][3]);
					}
					temp.add(max);

				}

				else if (B_temp.length() > 1 && A_temp.equals("")) {

					int max = 0;
					for (int j = 0; j < B_temp.length(); j++) {
						max = Math.max(max, bc_data[B_temp.charAt(j) - 'A'][3]);
					}
					temp.add(max);
				}

				else if (A_temp.length() > 1 && B_temp.length() == 1) {
					PriorityQueue<int[]> pq = new PriorityQueue<>((o1, o2) -> o2[2] - o1[2]);

					for (int j = 0; j < A_temp.length(); j++) {
						if (A_temp.charAt(j) == B_temp.charAt(0)) {
							pq.add(new int[] { j, 0, bc_data[A_temp.charAt(j) - 'A'][3] });
						} else {
							pq.add(new int[] { j, 0,
									bc_data[A_temp.charAt(j) - 'A'][3] + bc_data[B_temp.charAt(0) - 'A'][3] });
						}
					}
					int[] res = pq.poll();
					temp.add(res[2]);
				}

				else if (B_temp.length() > 1 && A_temp.length() == 1) {
					PriorityQueue<int[]> pq = new PriorityQueue<>((o1, o2) -> o2[2] - o1[2]);

					for (int j = 0; j < B_temp.length(); j++) {
						if (A_temp.charAt(0) == B_temp.charAt(j)) {
							pq.add(new int[] { j, 0, bc_data[B_temp.charAt(j) - 'A'][3] });
						} else {
							pq.add(new int[] { j, 0,
									bc_data[A_temp.charAt(0) - 'A'][3] + bc_data[B_temp.charAt(j) - 'A'][3] });
						}
					}
					int[] res = pq.poll();
					temp.add(res[2]);
				} else if (A_temp.length() > 1 && B_temp.length() > 1) {
					PriorityQueue<int[]> pq = new PriorityQueue<>((o1, o2) -> o2[2] - o1[2]);

					for (int j = 0; j < A_temp.length(); j++) {
						for (int q = 0; q < B_temp.length(); q++) {
							if (A_temp.charAt(j) == B_temp.charAt(q)) {
								pq.add(new int[] { j, q, bc_data[A_temp.charAt(j) - 'A'][3] });
							} else {
								pq.add(new int[] { j, q,
										(bc_data[A_temp.charAt(j) - 'A'][3] + bc_data[B_temp.charAt(q) - 'A'][3]) });
							}
						}

					}

					int[] res = pq.poll();
					temp.add(res[2]);

				}

				if (is_move(A_x, A_y, A[i])) {
					A_x += dx[A[i]];
					A_y += dy[A[i]];
				}
				if (is_move(B_x, B_y, B[i])) {
					B_x += dx[B[i]];
					B_y += dy[B[i]];
				}

			}

//			for (String[] row : board)
//				System.out.println(Arrays.toString(row));
//			System.out.println();
			int res = 0;

			for (int j = 0; j < temp.size(); j++) {
				res += temp.get(j);
			}

			System.out.println("#" + tc + " " + res);

		}

	}

	public static void bc_board_init() {
		for (int bc = 0; bc < bc_cnt; bc++) {
			int y = bc_data[bc][0] - 1;
			int x = bc_data[bc][1] - 1;
			int p = bc_data[bc][2];

			for (int i = 0; i < 10; i++) {
				for (int j = 0; j < 10; j++) {
					if (distance(i, j, x, y) <= p) {
						board[i][j] += Character.toString((char) ('A' + bc));
					}
				}
			}
		}
	}

	public static boolean is_move(int x, int y, int direct) {
		x += dx[direct];
		y += dy[direct];
		if ((0 <= x) && (0 <= y) && (x < 10) && (y < 10))
			return true;
		return false;
	}

	public static int distance(int x, int y, int x1, int y1) {
		return Math.abs(x - x1) + Math.abs(y - y1);
	}

	public static void board_init() {
		for (int i = 0; i < 10; i++) {
			for (int j = 0; j < 10; j++) {
				board[i][j] = "";
			}
		}
	}

}

 

 

5650. [모의 SW 역량테스트] 핀볼 게임

SW Expert Academy

단순 구현 문제

어떤 도형을 만났을 때 어떻게 이동하는지 dir 배열을 미리 잡아두고 관리해주면 빠르고 쉽게 풀 수 있다.

 

 

5648. [모의 SW 역량테스트] 원자 소멸 시뮬레이션

SW Expert Academy

보기에 쉬워보이는데 함정이 많은 문제. 

좌표를 먼저 양수로 바꿔준 후에 모든 원자들 하나씩 Queue에 넣어서 고려해주면 되는데 1초가 아닌 0.5초에 충돌이 일어날 수 있고 map을 List로 하나씩 관리했다간 터지고 만다.

 

5653. [모의 SW 역량테스트] 줄기세포배양

SW Expert Academy

BFS + 시뮬레이션 문제

 

문제를 잘 읽고 하나씩 구현하는거 밖엔 답이 없다.

k시간 만큼 걸린 후에 답을 구해야 하니까 Queue에 세포들을 모두 넣고 k번 만큼 bfs를 수행

5656. [모의 SW 역량테스트] 벽돌 깨기

SW Expert Academy

어디에 먼저 벽돌을 놓아야되는지 모르니까 dfs 완탐으로 모든 경우를 돌아보면서 연쇄작용으로 벽돌이 깨지는 부분은 bfs로 구현을 해주면 된다

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Solution {
    static int N,W,H,res;
    static int[][] board;
    static int[] dx = {1,-1,0,0};
    static int[] dy = {0,0,1,-1};

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

        int T = Integer.parseInt(st.nextToken());

        for (int tc = 1; tc < T+1; tc++) {
            st = new StringTokenizer(br.readLine());
            N = Integer.parseInt(st.nextToken());
            W = Integer.parseInt(st.nextToken());
            H = Integer.parseInt(st.nextToken());
            res = 0;


            board = new int[H][W];
            int data = 0;

            for (int i = 0; i < H; i++) {
                st = new StringTokenizer(br.readLine());
                for (int j = 0; j < W; j++) {
                    int temp = Integer.parseInt(st.nextToken());
                    if (temp != 0)
                        data++;
                    board[i][j] = temp;
                }
            }

            dfs(0,board,0);
            System.out.println("#"+tc+" "+(data-res));



        }


    }

    public static void dfs(int depth, int[][] board, int cnt){
        if (depth == N){
            res = Math.max(res, cnt);
            return;
        }


        for (int i = 0; i < W; i++) {
            int[][] copy_board = deepcopy(board);

            //1. 아래로 벽돌 만날때까지 내려감
            int x = 0;
            while (x<H && copy_board[x][i] == 0)
                x++;


            int crush_cnt = 0;
            if (x < H){
                //2. 벽돌 부수기
                crush_cnt = crush(x,i,copy_board);
                //3. 부순 벽돌 정렬하기
                sort_board(copy_board);

            }

            dfs(depth+1,copy_board,cnt+crush_cnt);



        }

    }

    public static int[][] deepcopy(int[][] board){
        int[][] copy_board = new int[H][W];
        for (int i = 0; i < H; i++) {
            for (int j = 0; j < W; j++) {
                copy_board[i][j] = board[i][j];
            }
        }
        return copy_board;
    }

    public static int crush(int r, int c, int[][] copy_board){
        Queue<int[]> queue = new ArrayDeque<>();
        queue.add(new int[]{r,c,copy_board[r][c]});
        copy_board[r][c] = 0;
        int cnt = 1;

        while (!queue.isEmpty()){
            int[] poll_data = queue.poll();
            int x = poll_data[0];
            int y = poll_data[1];
            int weight = poll_data[2];
            for (int i = 1; i < weight; i++) {
                for (int j = 0; j < 4; j++) {
                    int nx = x + dx[j]*i;
                    int ny = y + dy[j]*i;
                    if (nx<0 || ny <0 || nx>=H || ny>=W)
                        continue;
                    if (copy_board[nx][ny] != 0){
                        if (copy_board[nx][ny] != 1)
                            queue.add(new int[]{nx,ny,copy_board[nx][ny]});
                        cnt++;
                        copy_board[nx][ny] = 0;
                    }
                }
            }
        }
        return cnt;
    }


    public static void sort_board(int[][] copy_board){

        for (int i = 0; i < W; i++) {
            int idx = H-1;

            for (int j = H-1; j >= 0; j--) {
                if (copy_board[j][i] != 0){
                    if (idx != j){
                        int temp = copy_board[idx][i];
                        copy_board[idx][i] = copy_board[j][i];
                        copy_board[j][i] = temp;
                    }
                    idx--;
                }
            }

        }

    }

    public static void print(int[][] board){
        for (int[] ints : board) {
            for (int anInt : ints) {
                System.out.print(anInt+" ");
            }
            System.out.println();
        }
        System.out.println();
    }




}

 

5658. [모의 SW 역량테스트] 보물상자 비밀번호

SW Expert Academy

string을 4개의 substring으로 나누고 16진수로 바꾼다음 대소비교 해주면 끝나는 문제

Treeset으로 바로 하거나 List이용해서 list.contain(), Collections.sort()해도 된다