'알고리즘'에 해당되는 글 23건

JAVA/알고리즘

백준 4936 - 섬의개수

결국은 순회하면서 하는 DFS를 했는데 다음번에는 DP 또는 그래프 문제를 좀 많이 풀어 보고 싶다.


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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
import java.util.*;
 
public class Main {
 
    public static void main(String[] args) {
 
        // 붕어빵 개수
        Scanner sc = new Scanner(System.in);
        List<LandDto> lands = new ArrayList<>();
 
        while (true) {
            int weight = sc.nextInt();
            int height = sc.nextInt();
 
            if (weight == 0 && height == 0) {
                break;
            }
 
            int[][] dataMatrix = new int[height][weight];
            for (int y = 0; y < height; y++) {
                for (int x = 0; x < weight; x++) {
                    dataMatrix[y][x] = sc.nextInt();
                }
            }
 
            lands.add(new LandDto(weight, height, dataMatrix, new boolean[height][weight]));
        }
 
        lands.forEach(land -> {
            calLandCount(land);
        });
 
    }
 
    private static void calLandCount(LandDto landDto) {
        int count = 0;
        for (int y = 0; y < landDto.getHeight(); y++) {
            for (int x = 0; x < landDto.getWeight(); x++) {
                if (!landDto.getVisited()[y][x]) {
                    if (landDto.getDataMatrix()[y][x] == 1) {
                        count++;
                        findLand(x, y, landDto);
                    } else {
                        landDto.getVisited()[y][x] = true;
                    }
                }
            }
        }
        System.out.println(count);
    }
 
    private static void findLand(int x, int y, LandDto landDto) {
        landDto.getVisited()[y][x] = true;
 
        if (checkIsGo(x + 1, y, landDto)) {
            findLand(x + 1, y, landDto);
        }
 
        if (checkIsGo(x + 1, y - 1, landDto)) {
            findLand(x + 1, y - 1, landDto);
        }
 
        if (checkIsGo(x, y - 1, landDto)) {
            findLand(x, y - 1, landDto);
        }
 
        if (checkIsGo(x - 1, y - 1, landDto)) {
            findLand(x - 1, y - 1, landDto);
        }
 
        if (checkIsGo(x - 1, y, landDto)) {
            findLand(x - 1, y, landDto);
        }
 
        if (checkIsGo(x - 1, y + 1, landDto)) {
            findLand(x - 1, y + 1, landDto);
        }
 
        if (checkIsGo(x, y + 1, landDto)) {
            findLand(x, y + 1, landDto);
        }
 
        if (checkIsGo(x + 1, y + 1, landDto)) {
            findLand(x + 1, y + 1, landDto);
        }
 
    }
 
    private static boolean checkIsGo(int x, int y, LandDto landDto) {
        return x >= 0 && y >= 0 && x < landDto.getWeight() && y < landDto.getHeight() && landDto.getDataMatrix()[y][x] == 1 && !landDto.getVisited()[y][x];
    }
 
    static class LandDto {
        private int weight;
        private int height;
 
        private int[][] dataMatrix;
        private boolean[][] visited;
 
        LandDto(int weight, int height, int[][] dataMatrix, boolean[][] visited) {
            this.weight = weight;
            this.height = height;
            this.dataMatrix = dataMatrix;
            this.visited = visited;
        }
 
        public int getWeight() {
            return weight;
        }
 
        public int getHeight() {
            return height;
        }
 
        public int[][] getDataMatrix() {
            return dataMatrix;
        }
 
        public boolean[][] getVisited() {
            return visited;
        }
 
    }
 
}
 
cs

자세한 소스는 git 참고

https://github.com/weduls/algorithm/tree/master/%EA%B7%B8%EB%9E%98%ED%94%84/%EC%84%AC%EC%9D%98%20%EA%B0%9C%EC%88%98

JAVA/알고리즘

백준 알고리즘 2583 - 영역 구하기

백준 알고리즘 2583번 영역구하기 문제는 DFS를 사용해서 구현해봤다. 문제지를 보자마자 읽기 싫어졌지만 읽어보면 되게 단순하게 많이 접해봤던 문제인거 같다.


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

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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
import java.util.*;
 
public class Main {
 
    private static int M; // 세로
    private static int N; // 가로
    private static List<AreaWeightCntDto> areaWeightCntList = new ArrayList<>(); // 결과를 보관할 리스트
    private static List<Dot> visisted = new ArrayList<>();     // 방문여부를 체크할 리스트
    private static Set<Dot> box = new HashSet<>();             // box의 위치를 부여하는 hashset
 
    public static void main(String[] args) {
 
        Scanner in = new Scanner(System.in);
        M = in.nextInt();
        N = in.nextInt();
        int K = in.nextInt();
 
        // 공간 개수
        int areaCnt = 0;
 
        // 현재 박스의 위치 좌표를 모두 보관
        for (int i = 0; i < K; i++) {
            int x1 = in.nextInt();
            int y1 = in.nextInt();
            int x2 = in.nextInt();
            int y2 = in.nextInt();
 
            for (int tmpX = x1; tmpX < x2; tmpX++) {
                for (int tmpY = y1; tmpY < y2; tmpY++) {
                    box.add(new Dot(tmpX, tmpY));
                }
            }
        }
 
        //
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (enableGo(i, j)) {
                    ++areaCnt;
                    AreaWeightCntDto areaWeightCnt = new AreaWeightCntDto(1);
                    areaWeightCntList.add(areaWeightCnt);
                    visisted.add(new Dot(i, j));
                    getResult(i, j, areaWeightCnt);
                }
            }
        }
 
        // 결과 정렬
        areaWeightCntList.sort((o1, o2) -> {
            return o1.getCnt() > o2.getCnt() ? 1 : -1;
        });
 
        // 개수 출력
        System.out.println(areaCnt);
 
        // 출력
        areaWeightCntList.stream().forEach((e) -> {
            System.out.print(e.getCnt() + " ");
        });
 
    }
 
    /**
     * 공간들의 합을 저장할 Dto
     */
    static class AreaWeightCntDto {
        private int cnt;
 
        public AreaWeightCntDto(int cnt) {
            this.cnt = cnt;
        }
 
        public int getCnt() {
            return cnt;
        }
 
        public void setCnt(int cnt) {
            this.cnt = cnt;
        }
 
        public void increCnt() {
            ++this.cnt;
        }
    }
 
    /**
     * 공간 넓이 구하기
     *
     * @param x
     * @param y
     * @param sum
     */
    private static void getResult(int x, int y, AreaWeightCntDto sum) {
        if (enableGo(x, y + 1)) {
            visisted.add(new Dot(x, y + 1));
            sum.increCnt();
            ;
            getResult(x, y + 1, sum);
        }
 
        if (enableGo(x + 1, y)) {
            visisted.add(new Dot(x + 1, y));
            sum.increCnt();
            getResult(x + 1, y, sum);
        }
 
        if (enableGo(x, y - 1)) {
            visisted.add(new Dot(x, y - 1));
            sum.increCnt();
            getResult(x, y - 1, sum);
        }
 
        if (enableGo(x - 1, y)) {
            visisted.add(new Dot(x - 1, y));
            sum.increCnt();
            getResult(x - 1, y, sum);
        }
    }
 
    /**
     * 해당 좌표가 지나갈 수 있는 좌표인지 여부 확인
     *
     * @param x
     * @param y
     * @return
     */
    private static boolean enableGo(int x, int y) {
        // 경로 이탈 확인
        if (x < 0 || y < 0 || x >= N || y >= M) {
            return false;
        }
 
        // 이미 방문했는지, 박스가 있는 위치인지 여부 확인.
        return (!box.contains(new Dot(x, y)) && !visisted.contains(new Dot(x, y)));
    }
 
    /**
     * 좌표를 담는 Dot 객체
     */
    static class Dot {
 
        public Dot(int x, int y) {
            this.x = x;
            this.y = y;
        }
 
        private int x;
        private int y;
 
        @Override
        public boolean equals(Object obj) {
            if (!(obj instanceof Dot)) {
                return false;
            }
 
            Dot tmp = (Dot) obj;
 
            return Objects.equals(this.x, tmp.x) && Objects.equals(this.y, tmp.y);
        }
 
        @Override
        public int hashCode() {
            return Objects.hash(this.x, this.y);
        }
    }
 
}
cs




JAVA/알고리즘

백준 1929번 소수 구하기 문제

일반적으로 소수 구하는 방식으로 진행하면 시간이 너무 걸려서 에러가 발생한다. 그래서 고민하던 중에이런 생각이 났다. 모든 수는 자신의 제곱근 이상의 수로 나눠지지 않기 때문에 자신의 제곱근까지 2이상의 자연수로 나눠지는지 판단하면 된다고 생각했다. 

그 결과 된다.
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
50
51
52
53
54
55
56
import java.math.BigDecimal;
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
 
public class Main {
 
    public static void main(String[] args) {
 
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int m = in.nextInt();
 
        List<Integer> result = new ArrayList<>();
 
        // 순환
        for (int i = n; i <= m; i++) {
            if (isDecimal(i)) {
                result.add(i);
            }
        }
 
        // 결과 출력
        result.stream().forEach((e) -> {
            System.out.println(e);
        });
 
    }
 
    /**
     * 소수 체크
     *
     * @param num
     * @return
     */
    private static boolean isDecimal(int num) {
 
        if (1 == num) {
            return false;
        }
 
        /**
         * 자연수는 자신의 제곱근 이상의 수로 나눠지지 않는다는 조건을 이용해서, 자신의 제곱근 수 까지의 수로 나눠지는지 여부를 판단.
         */
        int sqrpData = new BigDecimal(Math.sqrt(num)).intValue();
 
        for (int i = 2; i <= sqrpData; i++) {
            if (num % i == 0) {
                return false;
            }
        }
 
        return true;
    }
 
}
cs


JAVA/알고리즘

백준 알고리즘1032 명령프롬프트 문제

문제

입력된 파일 리스트를 보고 공통적으로 사용될 수 있는 Regex를 찾아서 출력하는 문제이다.


코드

코드는 간단하게 처음입력받은 파일명을 기준으로 잡고 추가로 들어오는 나머지 파일명들과 다른 부분에 대해서 모두 ?로 바꿔버렸다.


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
import java.util.Scanner;
 
public class Main {
 
 
    public static void main(String[] args) {
 
        Scanner sc = new Scanner(System.in);
 
        // 파일 개수 입력
        int wordCnt = sc.nextInt();
 
        // 첫 번째 파일이름
        char[] creteria = sc.next().toCharArray();
 
        // 나머지 파일들 이름을 받으면서 Regex todtjd
        for (int i = 1; i < wordCnt; i++) {
            String fileName = sc.next();
 
            // 첫 번째 이름을 기준으로 이름이 다른 부분에 대해서 ? 처리
            for (int j = 0; j < creteria.length; j++) {
                char data = creteria[j];
 
                if (data != '?') {
                    if (data != fileName.charAt(j)) {
                        creteria[j] = '?';
                    }
                }
            }
        }
 
        for (char ch : creteria) {
            System.out.print(ch);
        }
    }
}
 
cs

자세한 코드는 Git 참고
https://github.com/weduls/algorithm/blob/master/%EB%AC%B8%EC%9E%90%EC%97%B4%20%EC%B2%98%EB%A6%AC/%EB%AA%85%EB%A0%B9%20%ED%94%84%EB%A1%AC%ED%94%84%ED%8A%B8/wedul/Main.java

JAVA/알고리즘

백준 알고리즘 11650 - 좌표 정렬하기

문제
입력된 좌표를 정렬해서 보여주는 문제이다.


코드

좌표를 담는 하나의 DTO 객체를 만들어서 comparable을 정의해서 사용해도 되나 좀 다르게 해보고 싶었다. 각 x좌표를 키로 사용하는 map을 만들고 각 x좌표마다 y좌표들을 담는 리스트가 존재한다. y좌표값이 채워질때는 정렬이 된 상태로 삽입된다. insertSort 메소드는 ATM 알고리즘에서 사용했던 것 가져왔다.

그리고 Map을 출력할 때는 Key를 기준으로 정렬한 후 forEach를 사용하여 정렬한다.

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
50
51
52
53
54
import java.util.*;
 
public class Main {
 
 
    public static void main(String[] args) {
 
        Scanner sc = new Scanner(System.in);
 
        int count = sc.nextInt();
        Map<Integer, List<Integer>> datas = new LinkedHashMap<>();
 
        for (int i = 0; i < count; i++) {
            int x = sc.nextInt();
            int y = sc.nextInt();
 
            // x 좌표를 키로 y 좌표들을 보관하고 있는 List를 value로 사용함.
            if (datas.containsKey(x)) {
                insertSort(datas.get(x), y);
            } else {
                List<Integer> dataList = new LinkedList<>();
                insertSort(dataList, y);
                datas.put(x, dataList);
            }
        }
 
        // 키 값들을 정렬한 후 stream에 foreach를 사용하여 정렬
        datas.entrySet().stream().sorted(Map.Entry.comparingByKey()).forEach(e -> {
            int key = e.getKey();
            for (Integer value : e.getValue()) {
                System.out.println(key + " " + value);
            }
        });
    }
 
    /**
     * 데이터를 정렬하면서 삽입
     *
     * @param list
     * @param insertData
     */
    private static void insertSort(List<Integer> list, int insertData) {
        for (int index = 0; index < list.size(); index++) {
            if (list.get(index) > insertData) {
                list.add(index, insertData);
                return;
            }
        }
 
        list.add(insertData);
    }
 
}
 
cs
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
50
51
52
53
54
import java.util.*;
 
public class Main {
 
 
    public static void main(String[] args) {
 
        Scanner sc = new Scanner(System.in);
 
        int count = sc.nextInt();
        Map<Integer, List<Integer>> datas = new LinkedHashMap<>();
 
        for (int i = 0; i < count; i++) {
            int x = sc.nextInt();
            int y = sc.nextInt();
 
            // x 좌표를 키로 y 좌표들을 보관하고 있는 List를 value로 사용함.
            if (datas.containsKey(x)) {
                insertSort(datas.get(x), y);
            } else {
                List<Integer> dataList = new LinkedList<>();
                insertSort(dataList, y);
                datas.put(x, dataList);
            }
        }
 
        // 키 값들을 정렬한 후 stream에 foreach를 사용하여 정렬
        datas.entrySet().stream().sorted(Map.Entry.comparingByKey()).forEach(e -> {
            int key = e.getKey();
            for (Integer value : e.getValue()) {
                System.out.println(key + " " + value);
            }
        });
    }
 
    /**
     * 데이터를 정렬하면서 삽입
     *
     * @param list
     * @param insertData
     */
    private static void insertSort(List<Integer> list, int insertData) {
        for (int index = 0; index < list.size(); index++) {
            if (list.get(index) > insertData) {
                list.add(index, insertData);
                return;
            }
        }
 
        list.add(insertData);
    }
 
}
 
cs


자세한 소스코드는 github참고


https://github.com/weduls/algorithm/blob/master/%EC%A0%95%EB%A0%AC/%EC%A2%8C%ED%91%9C%20%EC%A0%95%EB%A0%AC%ED%95%98%EA%B8%B0/wedul/Main.java

 [ 1 ]  [ 2 ]  [ 3 ]  [ 4 ]  [ 5 ] 

푸터바

알림

이 블로그는 구글에서 제공한 크롬에 최적화 되어있고, 네이버에서 제공한 나눔글꼴이 적용되어 있습니다.

카운터

  • Today : 41
  • Yesterday : 627
  • Total : 55,492