<stdio.han>

https://www.acmicpc.net/problem/10815

[난이도]

- Silver 5

[알고리즘]

- 이분탐색

[코드]

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

public class Main {
    static int N, M;
    static int[] sangArr;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        N = Integer.parseInt(br.readLine());
        sangArr = new int[N];
        st = new StringTokenizer(br.readLine(), " ");
        for (int i = 0; i < N; i++) {
            sangArr[i] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(sangArr); // 오름차순 정렬

        M = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine(), " ");
        for (int i = 0; i < M; i++) {
            int num = Integer.parseInt(st.nextToken());
            if (binarySearch(num)) {
                bw.write("1 ");
            } else {
                bw.write("0 ");
            }
        }
        bw.flush();
        bw.close();
        br.close();
    }

    static boolean binarySearch(int num) {
        int leftIndex = 0;
        int rightIndex = N - 1;
        while (leftIndex <= rightIndex) {
            int midIndex = (leftIndex + rightIndex) / 2;
            int mid = sangArr[midIndex];

            if (num < mid) { // 찾으려는 숫자가 더 작을경우 rightIndex를 mid-1 로 설정
                rightIndex = midIndex - 1;
            } else if (num > mid) { // 찾으려는 숫자가 더 클경우 leftIndex mid+1 로 설정
                leftIndex = midIndex + 1;
            } else { // 숫자가 있을 경우
                return true;
            }
        }
        return false; // 숫자가 없을 경우
    }
}

[풀이]

일반적인 이분탐색 문제이다. midIndex와 mid값이 다르기 때문에 탐색은 인덱스 기준으로하고 찾는 숫자는 arr[midIndex]로 찾는다.

https://school.programmers.co.kr/learn/courses/30/lessons/1844

[난이도]

- level 2

[알고리즘]

- BFS

[코드]

import java.util.*;

class Solution {
    static int answer = -1; // 우측하단에 도착하지못할경우 -1출력
    public int solution(int[][] maps) {
        bfs(maps);
        
        return answer;
    }
    static void bfs(int[][] maps){
        int n = maps.length;
        int m = maps[0].length;
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{0, 0, 1});
        boolean[][] visited = new boolean[n][m];
        visited[0][0] = true;
        int[] dx = {-1, 1, 0, 0}; // 4방탐색
        int[] dy = {0, 0, -1, 1};
        while(!queue.isEmpty()){
            int[] tmp = queue.poll();
            int x = tmp[0];
            int y = tmp[1];
            int count = tmp[2];
            if(x == n-1 && y == m-1){ // 우측하단에 도착했을 경우
                answer = count;
                return;
            }
            for(int i=0;i<4;i++) { // 4방탐색
                int nx = x + dx[i];
                int ny = y + dy[i];
                if(nx>=0&&nx<n&&ny>=0&&ny<m){ // 지도 내에 있을 경우
                    if(!visited[nx][ny] && maps[nx][ny] == 1){ // 방문한 적 없고, 벽이 아닐경우
                        queue.offer(new int[]{nx, ny, count+1});
                        visited[nx][ny] = true;
                    }
                }
            }
        }
        return;
    }
}

[풀이]

일반적인 미로찾기 BFS 알고리즘이다. 

큐에 x좌표, y좌표, 밟은블럭의 수를 담아준다.

queue.offer(new int[]{x, y, count});

https://school.programmers.co.kr/learn/courses/30/lessons/159993

[난이도]

- level 2

[알고리즘]

- BFS

[코드]

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

class Solution {
    static char[][] graph;
    static int n, m, answer = 0;
    static boolean[][] visited;
    static Queue<int[]> queue = new LinkedList<>();
    static int[] dx = {-1, 1, 0, 0}; // 상, 하
    static int[] dy = {0, 0, -1, 1}; // 좌, 우 4방탐색
    static boolean lever = false;
    public int solution(String[] maps) {
        n = maps.length;
        m = maps[0].length();
        visited = new boolean[n][m];
        graph = new char[n][m];
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                graph[i][j] = maps[i].charAt(j);
                if(graph[i][j] == 'S'){
                    queue.offer(new int[]{i, j, 0});
                    visited[i][j] = true;
                }
            }
        }
        bfs();
    
        return answer;
    }
    static void bfs(){
        while(!queue.isEmpty()){
            int[] tmp = queue.poll();
            int x = tmp[0];
            int y = tmp[1];
            int count = tmp[2];
            if(!lever&&graph[x][y] == 'L') { // 레버에 도착했을 경우, 레버를 아직 안켰을경우
                visited = new boolean[n][m];
                queue.clear();
                queue.offer(new int[]{x, y, count});
                visited[x][y] = true;
                lever = true;
            } else if(lever && graph[x][y] == 'E'){ // 레버를 켠 후 출구에 도착했을 경우
                answer = count;
                return;
            }
            for(int i=0;i<4;i++){
                int nx = x + dx[i];
                int ny = y + dy[i];
                if(nx>=0&&nx<n&&ny>=0&&ny<m){ // 맵 범위 내에 있을 경우
                    if(!visited[nx][ny] && graph[nx][ny] != 'X'){ // 방문한 적이 없고 벽이 아닐경우
                        queue.offer(new int[]{nx, ny, count+1});
                        visited[nx][ny] = true;
                    }
                }
            }
        }
        answer = -1;
        return;
    }
}

[풀이]

일반적인 BFS와 같지만 두 가지의 조건을 추가했다.

레버에 처음 도착했을경우 visited 배열을 다시 초기화해준다. 이유는 레버를 켠 후부터는 방문했던칸을 다시 방문해도 되기 때문이다.

queue를 queue.clear()메서드로 모두 비워준다. 레버에 도착한 순간 큐에담겨있던 데이터들은 쓸모없는 데이터들이기 때문이다.

레버를 켰다는 표시인 lever = true; 해준다.

if(!lever&&graph[x][y] == 'L') { // 레버에 도착했을 경우, 레버를 아직 안켰을경우
                visited = new boolean[n][m];
                queue.clear();
                queue.offer(new int[]{x, y, count});
                visited[x][y] = true;
                lever = true;
            }

lever를 켜서 lever = true로 된상태이면서 출구('E')에 도착했을 경우 answer = count; 해준 후 return으로 종료해준다.

else if(lever && graph[x][y] == 'E'){ // 레버를 켠 후 출구에 도착했을 경우
                answer = count;
                return;
            }

https://school.programmers.co.kr/learn/courses/30/lessons/169199

[난이도]

- level 2

[알고리즘]

- BFS

[코드]

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

class Solution {
    public int solution(String[] board) {
        int answer = 0;
        int[] dx = {-1, 1, 0, 0};
        int[] dy = {0, 0, -1, 1};
        boolean[][] visited = new boolean[board.length][board[0].length()];
        Queue<int[]> queue = new LinkedList<>();
        for(int i=0;i<board.length;i++){
            for(int j=0;j<board[0].length();j++){
                if(board[i].charAt(j) == 'R')
                { // 시작위치 저장
                    queue.offer(new int[]{i, j, 0});
                    visited[i][j] = true;
                }   
            }
        }
        
        while(!queue.isEmpty()){
            int[] tmp = queue.poll();
            int x = tmp[0];
            int y = tmp[1];
            int count = tmp[2];
            if(board[x].charAt(y) == 'G'){
                answer = count;
                return answer;
            }
            for(int i=0;i<4;i++){
                int nx = x;
                int ny = y;
                while(nx>=0&&nx<board.length&&ny>=0&&ny<board[0].length()&&board[nx].charAt(ny) != 'D'){ // 범위내에 있거나, 장애물 'D' 를 만날때 까지 계속 이동
                    nx += dx[i];
                    ny += dy[i];
                }
                // 범위 벗어나거나 장애물 만나기 직전으로 수정
                nx -= dx[i];
                ny -= dy[i];
                
                if(visited[nx][ny] || (x == nx && y == ny)){ // 방문한 적이 없고 같은 위치가 아닐경우
                    continue;
                    
                }
                    visited[nx][ny] = true;
                    queue.offer(new int[]{nx, ny, count+1});
                }
            }
        answer = -1;
        return answer;
    }
}

[풀이]

일반적인 bfs, 4방탐색 알고리즘을 활용한 문제이다.

다른점이 있다면 4방탐색 시 한 칸만 움직이는게 아닌 장애물을 만나거나 범위를 벗어나기전까지 계속 움직여야 한다는점이다.

                while(nx>=0&&nx<board.length&&ny>=0&&ny<board[0].length()&&board[nx].charAt(ny) != 'D'){ // 범위내에 있거나, 장애물 'D' 를 만날때 까지 계속 이동
                    nx += dx[i];
                    ny += dy[i];
                }
                // 범위 벗어나거나 장애물 만나기 직전으로 수정
                nx -= dx[i];
                ny -= dy[i];

https://www.acmicpc.net/problem/14889

[난이도]

- Silver 1

[알고리즘]

- DFS

- 완전탐색

- 백트래킹

[코드]

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

public class Main {
    static int N, answer = Integer.MAX_VALUE;
    static int[][] players;
    static boolean[] selected;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        N = Integer.parseInt(br.readLine());
        players = new int[N][N];
        selected = new boolean[N];

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

        solve(0, 0);
        System.out.println(answer);
        br.close();

    }
    static void solve(int depth, int index) {
        if (depth == N/2) {
            int startTeam = 0;
            int linkTeam = 0;

            for (int i = 0; i < N - 1; i++) {
                for (int j = i + 1; j < N; j++) {
                    if (selected[i] && selected[j]) {
                        startTeam += players[i][j];
                        startTeam += players[j][i];
                    } else if (!selected[i] && !selected[j]) {
                        linkTeam += players[i][j];
                        linkTeam += players[j][i];
                    }
                }
            }

            int diff = Math.abs(startTeam - linkTeam);
            answer = Math.min(answer, diff);
            return;
        }
        for (int i = index; i < N; i++) {
            if (!selected[i]) {
                selected[i] = true;
                solve(depth + 1, i + 1);
                selected[i] = false;
            }
        }
    }
}

[풀이]

boolean 배열로 선택한 선수와 선택하지 않은선수를 나눠계산한다.

            for (int i = 0; i < N - 1; i++) {
                for (int j = i + 1; j < N; j++) {
                    if (selected[i] && selected[j]) {
                        startTeam += players[i][j];
                        startTeam += players[j][i];
                    } else if (!selected[i] && !selected[j]) {
                        linkTeam += players[i][j];
                        linkTeam += players[j][i];
                    }
                }
            }

solve의 매개변수로 depth와 index를 주었다.

        for (int i = index; i < N; i++) {
            if (!selected[i]) {
                selected[i] = true;
                solve(depth + 1, i + 1);
                selected[i] = false;
            }
        }

for문을 돌며 선수를 선택할 때 i를 index로주고 선수를 선택했다면 매개변수를 건네줄때 i + 1로 주어 중복탐색을 줄여 시간초과를 방지할 수 있다.

https://www.acmicpc.net/problem/2961

[난이도]

- Silver 2

[알고리즘]

- 완전탐색

- DFS

- 백트래킹

[코드]

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

public class Main {
    static int N, answer = Integer.MAX_VALUE;
    static int[][] ingredient;
    static boolean[] selected;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        N = Integer.parseInt(br.readLine());
        ingredient = new int[N][2];
        selected = new boolean[N];
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            ingredient[i][0] = Integer.parseInt(st.nextToken());
            ingredient[i][1] = Integer.parseInt(st.nextToken());
        }
        solve(0, 1, 0, 0);
        System.out.println(answer);
    }

    // 트리의 깊이, 신맛, 쓴맛, 선택한 음식 개수
    static void solve(int depth, int sour, int bitter, int selectedCount) {
        if (depth == N) {
            if (selectedCount != 0) { // 1개 이상의 재료를 선택
                if (Math.abs(sour - bitter) < answer) { // 최솟값으로 갱신
                    answer = Math.abs(sour - bitter);
                }
            }
            return;
        }

        // 완전탐색을 위해 선택한경우와 선택하지 않은 경우를 나누어 진행
        solve(depth + 1, sour * ingredient[depth][0], bitter + ingredient[depth][1], selectedCount + 1); // 선택
        solve(depth + 1, sour, bitter, selectedCount); // 비선택
    }
}

[풀이]

부분집합을 구하는 방식을 활용해 완전탐색을 해야한다.

1. 재료를 선택한 경우와 선택하지 않은 경우 모두를 고려해서 재귀함수를 진행한다.

2. 트리의 깊이가 N이 될때까지 반복한다.

3. 트리의 깊이가 N이면서 1개 이상의 재료를 선택했으며 현재 알고있는 최소값보다 새로구한 값이 더 작을 때 answer를 갱신해준다.

https://www.acmicpc.net/problem/10971

[난이도]

- Silver 2

[알고리즘]

- 백트래킹

[코드]

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

public class Main {
    static int N, answer = Integer.MAX_VALUE;
    static int[][] map;
    static boolean[] visited;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

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

        for (int i = 0; i < N; i++) {
            visited[i] = true;
            backTracking(i, i, 0, 0);
        }
        System.out.println(answer);
    }

    /**
     * @param start : 메서드 실행 전 위에서 정해줌
     * @param now : 현재 내가 위치한 도시
     * @param sum : 현재위치한 도시까지 사용한 비용
     * @param depth
     */
    static void backTracking(int start, int now, int sum, int depth) {
        if (depth == N - 1) { // 모든 도시를 모두 방문한 경우, N-1인 이유는 백트래킹 메서드를 실행하기 전에 이미 방문함
            if (map[now][start] != 0) { // 마지막 도시에서 처음 도시로 가는 비용 더하기
                sum += map[now][start];
                answer = Math.min(answer, sum); // 최종적으로 나온 비용
            }
            return;
        }
        for (int i = 0; i < N; i++) {
            if (!visited[i]) { // 방문하지 않은 도시일경우
                if (map[now][i] != 0) { // 갈수 있는 도시일경우
                    visited[i] = true; // 방문했다면 true
                    backTracking(start, i, sum + map[now][i], depth + 1);
                    visited[i] = false; // 방문이 끝나면 false
                }
            }
        }
    }
}

[풀이]

시작하는 도시가 1번도시로 고정이 아닌 어느도시에서 시작하든 최소비용을 찾는것이기 때문에 N번 반복한다.

        for (int i = 0; i < N; i++) {
            visited[i] = true;
            backTracking(i, i, 0, 0);
        }

백트래킹 메서드의 매개변수 start 는 순회를 시작한 도시의 위치로 메서드를 실행할 때 정해진다.

매개변수 now는 현재 내가 위치한 도시의 위치를 뜻한다. 

매개변수 sum은 현재 내가 now에 올때까지 사용한 비용을 뜻한다.

매개변수 depth는 모든도시를 순회했는지 체크한다.

for문을 돌며 방문하지 않은 도시이며 map[i][j]가 0이 아닌도시(방문할 수 있는 도시) 라면 백트래킹을 재귀적으로 수행한다.

이때 넣어주어야 하는 매개변수들은 순회를 시작한 도시 start, 다음 방문할 도시 i, 현재까지 사용한 비용(sum) + 현재 위치에서 i까지 가는 비용(map[now][i]), depth + 1이다.

        for (int i = 0; i < N; i++) {
            if (!visited[i]) { // 방문하지 않은 도시일경우
                if (map[now][i] != 0) { // 갈수 있는 도시일경우
                    visited[i] = true; // 방문했다면 true
                    backTracking(start, i, sum + map[now][i], depth + 1);
                    visited[i] = false; // 방문이 끝나면 false
                }
            }
        }

depth 가 N-1이 되면 모든도시를 방문한 것이다. depth가 N이아닌 N-1인 이유는 순회를 시작한 도시는 메서드 실행전 체크하기 때문이다.

depth가 N-1이 되었다면 마지막 도착한 도시에서 순회를 시작한 도시로 돌아와야하기 때문에 map[now][start] != 0 이라면

sum += map[now][start]를 해주어 마지막 비용을 추가해준다.

        if (depth == N - 1) { // 모든 도시를 모두 방문한 경우, N-1인 이유는 백트래킹 메서드를 실행하기 전에 이미 방문함
            if (map[now][start] != 0) { // 마지막 도시에서 처음 도시로 가는 비용 더하기
                sum += map[now][start];
                answer = Math.min(answer, sum); // 최종적으로 나온 비용
            }
            return;
        }

https://www.acmicpc.net/problem/6603

[난이도]

- Silver 2

[알고리즘]

- 백트래킹

[코드]

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

public class Main {
    static int k;
    static int[] arr, list;
    static boolean[] checked;
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        while (true) {
            st = new StringTokenizer(br.readLine(), " ");
            k = Integer.parseInt(st.nextToken());
            if (k == 0) { // 0일경우 종료
                break;
            }
            arr = new int[k];
            list = new int[6];
            checked = new boolean[k];
            for (int i = 0; i < k; i++) {
                arr[i] = Integer.parseInt(st.nextToken());
            }
            backTracking(0, 0);
            bw.write("\n");
        }
        bw.flush();
        bw.close();
        br.close();
    }

    static void backTracking(int depth, int start) throws Exception{
        if (depth == 6) {
            for (int i : list) {
                bw.write(i + " ");
            }
            bw.write("\n");
            return;
        }
        for (int i = start; i < k; i++) { // i 는 start부터 시작
            if (!checked[i]) { // 사용하지 않은 숫자만 허용
                checked[i] = true;
                list[depth] = arr[i];
                backTracking(depth + 1, i + 1); // i+1을 해주어 중복을 막음
                checked[i] = false;
            }
        }
    }
}

[풀이]

1. 입력을 받는다. k가 0일경우 종료한다. 입력받은숫자는 arr 배열에 저장한다.

2. 백트래킹 알고리즘을 수행한다. 매개변수로 depth, start를 받는다. 0, 0부터 시작.

3. for문을 돌며 arr에 담긴 숫자를 list에 담아준다. for문은 i = start부터 시작.

4. 숫자를 list배열에 담아준 후 depth+1, i+1로 재귀적으로 호출해준다.

5. depth가 6일경우 list배열에 담겨있는 숫자를 출력해준다.