☌

[CSBASEBALL] 각본 없는 야구

개발이야기/알고스팟2022. 1. 5. 09:49

Java 로 풀어보는 알고리즘입니다. 📖
코딩테스트를 대비하여 JAVA1.8 부터 제공되는 함수형 API 는 사용하지 않았습니다.

문제 : https://www.algospot.com/judge/problem/read/CSBASEBALL

 

algospot.com :: CSBASEBALL

각본 없는 야구 문제 정보 문제 현재 CS 야구팀과 화나 핀토스(Hwana Pintos)팀의 야구 경기가 진행 중이다. 지금은 CS 야구팀의 공격 상황. 주자는 아무도 없지만 이들은 계속 안타(1루타)를 치기 시

www.algospot.com


풀이입니다. 🤔

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
import java.util.*;
 
public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
 
        int cases = scanner.nextInt();
        while (cases-- > 0) {
            int a = scanner.nextInt(), b = scanner.nextInt();
            int diff = b - a;
            System.out.println(diff >= 0 ? 4 + diff : 0);
        }
    }
}
 cs

 


이 포스트를 읽어주셔서 감사합니다. 🙇🏻‍♂️

반응형

'개발이야기 > 알고스팟' 카테고리의 다른 글

[DECODE] Decoding  (0) 2022.01.05
[FIX] 문제 순서는 난이도 순이 아닙니다  (0) 2022.01.05
[TSP1] Traveling Salesman Problem 1  (0) 2022.01.04
[NQUEEN] N-Queen  (0) 2022.01.04
[FIXPAREN] Mismatched Parenthesis  (0) 2022.01.04
Posted by N'
,

[TSP1] Traveling Salesman Problem 1

개발이야기/알고스팟2022. 1. 4. 17:59

Java 로 풀어보는 알고리즘입니다. 📖
코딩테스트를 대비하여 JAVA1.8 부터 제공되는 함수형 API 는 사용하지 않았습니다.

문제 : https://www.algospot.com/judge/problem/read/TSP1

 

algospot.com :: TSP1

Traveling Salesman Problem 1 문제 정보 문제 NP-Complete 문제의 가장 유명한 예 중 하나인 여행하는 외판원 문제 (Traveling Salesman Problem) 은, 여러 개의 도시와 그 도시 간의 거리가 주어졌을 때, 각 도시를

www.algospot.com


풀이입니다. 🤔

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
import java.util.*;
 
public class Main {
    private static final double[][] distances = new double[8][8];
    private static final boolean[] visited = new boolean[8];
 
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int cases = scanner.nextInt();
        while (cases-- > 0) {
            int n = scanner.nextInt();
            for (int i = 0; i < n; ++i) {
                for (int j = 0; j < n; ++j) {
                    distances[i][j] = scanner.nextDouble();
                }
            }
 
            System.out.printf("%.10f\n", getMinVisitDistance(n));
            Arrays.fill(visited, false);
        }
    }
 
    private static double getMinVisitDistance(int n) {
        double ret = Double.MAX_VALUE;
        for (int i = 0; i < n; ++i) {
            visited[i] = true;
            ret = Math.min(ret, getMinVisitDistance(n, i, 1)); // 시작하는 도시마다, 총 방문거리가 달라질 수 있다.
            visited[i] = false;
        }
 
        return ret;
    }
 
    private static double getMinVisitDistance(int n, int cur, int visitedCount) {
        if (visitedCount >= n) return 0; // 기저사례 : 모든 도시를 방문
 
        double ret = Double.MAX_VALUE;
        for (int i = 0; i < n; ++i) {
            if (cur == i) continue;
            if (visited[i]) continue;
 
            visited[i] = true;
            ret = Math.min(ret, distances[cur][i] + getMinVisitDistance(n, i, visitedCount + 1));
            visited[i] = false;
        }
 
        return ret;
    }
}
 cs


이 풀이는 기존에 풀었던 아래 문제와 유사합니다.

 

[PICNIC] 피크닉


완전탐색으로 도시를 방문하는 모든 순서에 따라 총 거리를 구한 뒤, 최소 값을 출력하도록 합니다. 
이 방법은 가장 비효율적이며 도시의 수가 적기 때문(최대 8개)에 가능한 방법입니다.

추 후 메모이제이션을 이용하여 더 빠르게 정답을 구할 수 있는 방법을 소개해보도록 하겠습니다.

 

 

 

이 포스트를 읽어주셔서 감사합니다. 🙇🏻‍♂️

 

반응형

'개발이야기 > 알고스팟' 카테고리의 다른 글

[FIX] 문제 순서는 난이도 순이 아닙니다  (0) 2022.01.05
[CSBASEBALL] 각본 없는 야구  (0) 2022.01.05
[NQUEEN] N-Queen  (0) 2022.01.04
[FIXPAREN] Mismatched Parenthesis  (0) 2022.01.04
[BRACKETS2] Mismatched Brackets  (0) 2022.01.03
Posted by N'
,

[NQUEEN] N-Queen

개발이야기/알고스팟2022. 1. 4. 16:48

Java 로 풀어보는 알고리즘입니다. 📖
코딩테스트를 대비하여 JAVA1.8 부터 제공되는 함수형 API 는 사용하지 않았습니다.

문제 : https://www.algospot.com/judge/problem/read/NQUEEN

 

algospot.com :: NQUEEN

N-Queen 문제 정보 문제 N-Queen 퍼즐은 N x N 크기의 체스판에 N 개의 퀸을, 서로 공격할 수 없도록 올려놓는 퍼즐이다. (퀸은 체스에서 가장 강력한 기물로, 자신의 위치에서 상하좌우, 그리고 대각선

www.algospot.com


풀이입니다. 🤔

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
import java.util.*;
 
public class Main {
    private static final int[][] boards = new int[12][12];
 
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int cases = scanner.nextInt();
        while (cases-- > 0) {
            int n = scanner.nextInt();
            System.out.println(getCount(n, 0));
        }
    }
 
    private static int getCount(int n, int y) {
        if (y >= n) return 1;
        int ret = 0;
        for (int x = 0; x < n; ++x) {
            if (boards[y][x] != 0) continue;
            put(n, y, x, 1);
            ret += getCount(n, y + 1);
            put(n, y, x, -1);
        }
 
        return ret;
    }
 
    private static void put(int n, int y, int x, int count) {
        boards[y][x] += count;
        for (int i = 1, len = n - y; i < len; ++i) {
            boards[y + i][x] += count;
            if (x - i >= 0) boards[y + i][x - i] += count;
            if (x + i < n) boards[y + i][x + i] += count;
        }
    }
}
 cs


이 풀이는 기존에 풀었던 아래 문제와 유사합니다. 

 

[PICNIC] 피크닉


재귀로 행마다 하나의 퀸을 배치해보면 총 경우의 수를 구할 수 있습니다. 
같은 경우의 수를 방지하기 위해, 아래 행을 향하여 공격범위를 기록하며 위에서 아래 행으로만 가짓수를 세도록 합니다.

 

 

이 포스트를 읽어주셔서 감사합니다. 🙇🏻‍♂️

반응형

'개발이야기 > 알고스팟' 카테고리의 다른 글

[CSBASEBALL] 각본 없는 야구  (0) 2022.01.05
[TSP1] Traveling Salesman Problem 1  (0) 2022.01.04
[FIXPAREN] Mismatched Parenthesis  (0) 2022.01.04
[BRACKETS2] Mismatched Brackets  (0) 2022.01.03
[SHISENSHO] Shisen-sho  (0) 2022.01.03
Posted by N'
,
Daum / Designed by i2i Labs

티스토리툴바