문제 >> 1012 : 유기농배추



dfs를 이용


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
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
 
public class Main_1012 {
//유기농 배추
    
    static int[][] map;
    static int[] dy = {0,0,-1,1};
    static int[] dx = {-1,1,0,0};
    static int M,N;
    
    
    public static void main(String[] args) throws Exception {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        
        int T = Integer.parseInt(bf.readLine());
        
        for(int tc=1;tc<=T;tc++) {
            
            StringTokenizer st = new StringTokenizer(bf.readLine()," ");
            M = Integer.parseInt(st.nextToken()); //가로
            N = Integer.parseInt(st.nextToken()); //세로
            int K = Integer.parseInt(st.nextToken()); //배추개수
            
            map = new int[N][M];
            
            
            
            for(int i=0;i<K;i++) {
                st = new StringTokenizer(bf.readLine()," ");
                int x = Integer.parseInt(st.nextToken());
                int y = Integer.parseInt(st.nextToken());
                map[y][x]=1;
            }
            
            int ans=0;
            for(int i=0;i<N;i++) {
                for(int j=0;j<M;j++) {
                    if(map[i][j] == 1) {
                        dfs(i,j);
                        ans++;
                    }
                }
            }
            System.out.println(ans);
        }//end of tc
    }
 
 
    static void dfs(int y, int x) {
        map[y][x]=0; //visited check
        
        for(int i=0;i<4;i++) {
            int ny = y+dy[i];
            int nx = x+dx[i];
            
            if(ny<0 || ny>N-1 || nx<0 || nx>M-1) continue;
            if(map[ny][nx] == 1) dfs(ny,nx);
        }
        
        return ;
    }
}
 
cs


저작자표시

'Algorithm Problem Solving' 카테고리의 다른 글

[SWEA] 1861 : 정사각형 방  (0) 2019.03.07
[BOJ] 8983 : 사냥꾼 / [JUNGOL] 2364 : 사냥꾼  (1) 2019.03.07
[BOJ] 1931 : 회의실배정 (++그리디 알고리즘에 대한 고찰)  (2) 2019.02.17
[SWEA] 2819 격자판의 숫자 이어 붙이기  (0) 2019.02.16
[BOJ] 9999 : 구구 **결정적 힌트**  (5) 2019.02.13

* Greedy 알고리즘 (탐욕적 알고리즘)


완전탐색 , 동적 계획법 --> 모든 선택지를 고려해 보고 그중 전체 답이 가장 좋은 것을 찾는다.


그리디 알고리즘 --> 각 단계마다 지금 당장 가장 좋은 방법만을 선택한다. 

     즉, 지금의 선택이 앞으로 남은 선택들에 어떤 영향을 끼칠지는 고려하지 않는다.


따라서 알고리즘의 정당성을 증명하는 과정이 필수적이다.!



문제보기 >> 백준 1931 : 회의실배정 


가장 먼저 끝나는 회의를 선택하고, 이 회의와 겹치지 않는 회의중 가장 먼저 끝나는 회의를 선택하는 것을 반복한다.


((정당성의 증명))

" 가장 종료 시간이 빠른 회의를 포함하는 최적해가 반드시 존재한다." 를 증명해보자.


S는 회의 목록, Smin 은 가장 일찍 끝나는 회의.


S의 최적해 중 Smin을 포함하지 않는 답이 있다고 가정하자

이 답은 서로 겹치지 않는 회의의 목록이다.

이 목록에서 첫번째로 개최되는 회의를 지우고 Smin 을 추가해 새로운 목록을 만든다.

Smin은 S에서 가장 일찍 끝나는 회의의기 때문에, 지워진 회의는 Smin보다 일찍 끝날수 없다.

따라서 두번쨰 회의와 Smin이 겹치는 일은 없으며, 새로 만든 목록도 최적해가 될 수 있다.


==> 항상 Smin을 포함하는 최적해는 존재한다.

==> 가장 일찍 끝나는 회의를 선택해서 최적해를 얻는 것이 불가능해지는 경우는 없다.



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
import java.awt.Point;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;
import java.util.StringTokenizer;
 
public class Main_1931 {
    //회의실배정
    static int N;
    static int[][] arr;
 
    public static void main(String[] args) throws Exception {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        
        N = Integer.parseInt(bf.readLine());
        arr=new int[N][2];
        for(int i=0;i<N;i++) {
            StringTokenizer st = new StringTokenizer(bf.readLine()," ");
            arr[i][0] = Integer.parseInt(st.nextToken());
            arr[i][1] = Integer.parseInt(st.nextToken());
        }
        
        Arrays.sort(arr,new Comparator<int[]>() {
            //0 : o1==o2
            //1 : o1>o2
            //-1 : o1<o2
            //arr[n][1]을 기준으로 오름차순 정렬
            @Override
            public int compare(int[] o1, int[] o2) {
                if(o2[1]==o1[1]) {
                    return o1[0]-o2[0];
                }
                else return o1[1]-o2[1];
        
            
            }
        });
    
    
        
 
        System.out.println(solve());
        
    
    }
    
    static int solve(){
        
        int now=0;
        int cnt=1;
        
        for(int i=1;i<N;i++) {
            //다음 회의의 시작시간이 현재 회의의 종료시간보다 작으면 continue
            if(arr[i][0]<arr[now][1]) continue;
        
            cnt++;
            now=i;
        }
        
        
        return cnt;
 
        
    }//end of solve
 
}
 
cs



++) 고민해야할 예외 상황



2

2 2

1 2


와같은 입력이 있다면,


(1 2) -> (2 2) 


의 순서로 회의실 배정을 할 수 있고 답은 2일것이다.


하지만 회의 종료시간만을 기준으로 data를 정렬하면


(2 2) 가 우선 순위가 되어 (1 2) 배정은 불가능하다고 판단할수도 있다.


따라서 정렬 과정에서,


회의 종료시간이 같다면, 회의 시작시간을 기준으로 한 오름차순 정렬을 해줘야한다.

저작자표시

'Algorithm Problem Solving' 카테고리의 다른 글

[BOJ] 8983 : 사냥꾼 / [JUNGOL] 2364 : 사냥꾼  (1) 2019.03.07
[BOJ] 1012 : 유기농배추  (1) 2019.02.17
[SWEA] 2819 격자판의 숫자 이어 붙이기  (0) 2019.02.16
[BOJ] 9999 : 구구 **결정적 힌트**  (5) 2019.02.13
[SW Expert Academy] 1247. [S/W 문제해결 응용] 3일차 - 최적 경로  (2) 2019.02.13

문제 >> 2819. 격자판의 숫자 이어 붙이기 

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
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.StringTokenizer;
 
public class Main_2819 {
    static HashSet<String> hs;
    static int[] dy = { -1, 1, 0, 0 };
    static int[] dx = { 0, 0, -1, 1 };
    static char[][] map = new char[4][4];
 
    public static void main(String[] args) throws Exception {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
 
        int T = Integer.parseInt(bf.readLine());
 
        for (int tc = 1; tc <= T; tc++) {
            hs = new HashSet<String>();
            for (int i = 0; i < 4; i++) {
                StringTokenizer st = new StringTokenizer(bf.readLine(), " ");
                for (int j = 0; j < 4; j++) {
                    map[i][j] = st.nextToken().charAt(0);
                }
            } // 입력 받기
 
            for (int i = 0; i < 4; i++) {
                for (int j = 0; j < 4; j++) {
                    solve(i, j, 0, "" + map[i][j]);
                }
            }
 
            System.out.println("#" + tc + " " + hs.size());
        } // end of tc
    }
 
    static void solve(int y, int x, int depth, String s) {
 
        if (depth >= 6) {
            hs.add(s);
            return;
        } else {
            for (int i = 0; i < 4; i++) {
                int ny = y + dy[i];
                int nx = x + dx[i];
 
                if (ny < 0 || ny > 3 || nx < 0 || nx > 3)
                    continue;
 
                s = map[ny][nx]+s;
                
                solve(ny, nx, depth+1, s);
                
                s=s.substring(1);
        
            }
        }
 
    } // end of solve
}
 
cs


중복체크를 위해 Hashset을 사용했다.

Hashset은 중복된 원소에 대한 체크를 자동으로 해주기때문에

모든 경우를 Hashset에 삽입하고, 마지막에 Hashset의 size를 출력해주었다.


보통 중복체크는 boolean 타입의 배열을 사용하지만

문제에서  "0으로 시작하는 0102001과 같은 수를 만들 수도 있다." 라는 부분때문에

인덱스로 사용하지 못할 것으로 판단했다.


하지만 일곱자리 수로 결정되어있으므로 0으로 시작하는 숫자도 Integer 형으로 변환시키면

자동으로 앞의 0이 제거되면서 중복되지 않는 index가 될 수 있다.

0000123 => 123

0010234 => 10234

이런식으로 활용이 가능하다 

중복이 되지 않는 이유는 7자리로 고정되어있기때문이고

자리수가 고정되어있지않으면 활용이 불가능하다

 !


저작자표시

'Algorithm Problem Solving' 카테고리의 다른 글

[BOJ] 1012 : 유기농배추  (1) 2019.02.17
[BOJ] 1931 : 회의실배정 (++그리디 알고리즘에 대한 고찰)  (2) 2019.02.17
[BOJ] 9999 : 구구 **결정적 힌트**  (5) 2019.02.13
[SW Expert Academy] 1247. [S/W 문제해결 응용] 3일차 - 최적 경로  (2) 2019.02.13
[SW Expert Academy] 1244. [S/W 문제해결 응용] 2일차 - 최대 상금  (2) 2019.02.12
01_유승아_스레드

1주차(thread) 0218

 

프로세스와 스레드

프로세스

  • 사전적 의미

    • "컴퓨터에서 연속적으로 실행되고 있는 컴퓨터 프로그램"

    • 메모리에 올라와 실행되고 있는 프로그램의 인스턴스

    • 운영체제로부터 시스템 자원을 할당받는 작업의 단위

      • CPU시간
      • 운영되기 위해 필요한 주소 공간
      • 메모리 영역(Code, Data, Stack, Heap)

  • 특징

    • 기본적으로 프로세스당 최소 1개의 스레드(메인스레드)를 가지고 있다.
    • 각 프로세스는 별도의 주소공간에서 실행되며, 한 프로세스는 다른 프로세스의 벼수나 자료구조에 겁근할 수 없다.
    • 한 프로세스가 다른 프로세스의 자원에 접근하려면 프로세스간의 통신(IPC, inter-process communication)을 사용해야 한다.(Ex. 파이프, 파일, 소켓 통신)

 

스레드

  • 사전적 의미

    • "프로세스 내에서 실행되는 여러 흐름의 단위"
    • 프로세스의 특정한 수행 경로
    • 프로세스가 할당받은 자원을 이용하는 실행의 단위

  • 특징

    • 스레드는 프로세스 내에서 각각 Stack만 따로 할당 받고 Code, Data, Heap 영역은 공유한다.
    • 스레드는 한 프로세스 내에서 동작되는 여러 실행의 흐름으로, 프로세스 내의 주소 공간이나 자원들을 같은 프로세스 내에 스레드끼리 공유하며 실행된다.
    • 각각의 스레드는 별도의 레지스터와 스택을 갖고 있지만, 힙 메모리는 서로 읽고 쓸 수 있다.
    • 한 스레드가 프로세스 자원을 변경하면, 다른 이웃 스레드(sibling thread)도 그 변경된 결과를 즉시 볼 수 있다.

멀티 프로세스

  • 멀티프로세싱이란?

    • 하나의 응용프로그램을 여러 개의 프로세스로 구성하여 각 프로세스가 하나의 작업을 처리하도록 하는 것.

  • 장점

    • 여러 개의 자식 프로세스 중 하나에 문제가 발생하면 그 자식 프로세스만 죽는 것 이상으로 다른 영향이 확산되지 않는다.

  • 단점

    • Context Switching 오버헤드

      • Context Switching과정에서 캐쉬 메모리 초기화 등 무거운 작업이 진행되고 많은 시간이 소모되는 등의 오 버헤드가 발생하기 된다.
      • 프로세스는 각각의 독립된 메모리 영역을 할당받았기 때문에 프로세스 사이에서 공유하는 메모리가 없어, Context Switching이 발생하면 캐쉬에 있는 모든 데이터를 전부 리셋하고 다시 캐쉬정보를 불러와야 한다.

    • 하나의 프로그램에 속하는 프로세스들 사이의 변수를 공유할 수 없다.

 

멀티스레드

  • 멀티스레드란?

    • 하나의 응용프로그램을 여러 개의 스레드로 구성하고 각 스레드로 하여금 하나의 작업을 처리하도록 하는 것.
    • 웹 서버는 대표적인 멀티 스레드 응용프로그램이다.
    • 윈도우, 리눅스 등 많은 운영체제들이 멀티 스레딩을 기본으로 멀티프로세싱을 지원한다.

  • 장점

    • 시스템 자원 소모 감소(자원의 효율성 증대)

      • 시스템콜(프로세스를 생성하여 자원을 할당하는 과정)이 줄어들어 자원을 효율적으로 관리할 수 있다.

    • 시스템 처리량 증가(처리 비용 감소)

      • 스레드 간 데이터를 주고받는 것이 간단해지고 시스템 자원 소모가 줄어든다.
      • 스레드 사이의 작업량이 작아 Context Switching이 빠르다.

    • 스레드는 프로세스 내의 Stack영역을 제외한 모든 메모리를 공유하기 때문에 통신의 부담이 적다.

  • 단점

    • 설계 / 디버깅이 까다롭다.
    • 단일프로세스 시스템의 경우 효과를 기대하기 어렵다.
    • 자원을 공유하므로 동기화 문제가 발생한다.
    • 하나의 스레드에 문제가 발생하면 전체 프로세스가 영향을 받는다.

멀티스레드 vs 멀티프로세스

  • 멀티프로세스 대신 멀티 스레드를 사용하는 이유?

    • 프로그램을 여러 개 키는 것보다 하나의 프로그램 안에서 여러 작업을 해결하는 것이다.

  • 멀티프로세스로 할 수 있는 작업을 멀티 쓰레딩으로 하는 이유?

    • 프로세스를 생성하여 자원을 할당하는 시스템 콜이 줄어들어 자원을 효율적으로 관리할 수 있다.
    • 프로세스 간의 Context Switching시 오버헤드가 크기 때문.
    • 스레드는 프로세스 내의 메모리를 공유하기 때문에 스레드간 데이터를 주고 받는 것이 간단해지고 시스템 자원소모가 줄어든다.
저작자표시

'Computer Science > Operating System' 카테고리의 다른 글

가상메모리(virtual memory)와 요구페이징(demand paging)  (1) 2019.04.19
프로세스 동기화 (Process Synchronization)  (1) 2019.04.17
CPU 스케줄러  (0) 2019.03.03
스케줄러 Scheduler  (0) 2019.02.23

백준 7대 난제 중 한 문제인 구구


문제 >> 9999 : 구구


<<HINT>>


1. 여자 가수다.

2. 가사는 영어가 아니다.

3. 앨범과 노래 제목이 동일하다


---------------------

이미 공개된 힌트

1. ep --> 가수 이름의 이니셜

2. 제목이 12byte

3. e로 끝난다

4. 1915년 출생, 1950년 발매된 앨범의 수록곡


저작자표시

'Algorithm Problem Solving' 카테고리의 다른 글

[BOJ] 1931 : 회의실배정 (++그리디 알고리즘에 대한 고찰)  (2) 2019.02.17
[SWEA] 2819 격자판의 숫자 이어 붙이기  (0) 2019.02.16
[SW Expert Academy] 1247. [S/W 문제해결 응용] 3일차 - 최적 경로  (2) 2019.02.13
[SW Expert Academy] 1244. [S/W 문제해결 응용] 2일차 - 최대 상금  (2) 2019.02.12
[BOJ] 10819 : 차이를 최대로  (0) 2019.02.08

 문제 >> 1247. [S/W 문제해결 응용] 3일차 - 최적 경로

 

Permutation 알고리즘을 이용해 고객의 집에 대한 모든 순서를 먼저 만든다 (index 이용)

각각의 경우에 대해 거리를 계산하고, 최소값을 갱신한다.

최소값을 출력한다.

 

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
import java.io.BufferedReader; 
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
 
class pair {
    int y;
    int x;
 
    public pair(int y, int x) {
        this.y = y;
        this.x = x;
    }
}
 
public class Solution1247 {
    static pair home;
    static pair company;
    static pair[] cus;
    static int ans = Integer.MAX_VALUE;
 
    public static int getDistance(pair p1, pair p2) {
        return Math.abs(p1.x - p2.x) + Math.abs(p1.y - p2.y);
    }
 
    public static void swap(int[] set, int i, int index) {
        int temp = set[i];
        set[i] = set[index];
        set[index] = temp;
    }
    
    
    static int solve(int[] set) {
        int sum=0;
        sum += getDistance(company, cus[set[0]]);
        for(int i=0;i<set.length-1;i++) {
            int idx = set[i];
            int next = set[i+1];
            sum+= getDistance(cus[idx], cus[next]);
        }
        sum+=getDistance(cus[set[set.length-1]], home);
        
        return sum;
    }
    
 
    
    public static void perm(int[] set, int size, int n, int k) {
        if (size == k) { //종료조건
            int s = solve(set);
 
            ans = ans > s? s: ans;
            return;
        }
 
        for (int i = size; i < n; i++) {
            swap(set, i, size);
            perm(set, size + 1, n, k);
            swap(set, i, size);
        }
    }
 
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int TC = Integer.parseInt(br.readLine());
 
        for (int tc = 1; tc <= TC; tc++) {
            int N = Integer.parseInt(br.readLine()); // 고객 수
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
            int y = Integer.parseInt(st.nextToken());
            int x = Integer.parseInt(st.nextToken());
            ans = Integer.MAX_VALUE;
            int[] set = new int[N];
            company = new pair(y, x);
 
            y = Integer.parseInt(st.nextToken());
            x = Integer.parseInt(st.nextToken());
            home = new pair(y, x);
 
            cus = new pair[N];
            for (int i = 0; i < N; i++) {
                y = Integer.parseInt(st.nextToken());
                x = Integer.parseInt(st.nextToken());
                cus[i] = new pair(y, x);
            }
 
            for (int i = 0; i < N; i++) {
                set[i] = i;
            }
 
            perm(set, 0, N, N);
            
            System.out.println("#"+tc + " "+ans);
 
        }
    }
}
 
 cs
저작자표시

'Algorithm Problem Solving' 카테고리의 다른 글

[SWEA] 2819 격자판의 숫자 이어 붙이기  (0) 2019.02.16
[BOJ] 9999 : 구구 **결정적 힌트**  (5) 2019.02.13
[SW Expert Academy] 1244. [S/W 문제해결 응용] 2일차 - 최대 상금  (2) 2019.02.12
[BOJ] 10819 : 차이를 최대로  (0) 2019.02.08
[BOJ] 1987 : 알파벳  (0) 2019.02.08

문제 >> 1244. [S/W 문제해결 응용] 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
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
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.HashSet;
import java.util.StringTokenizer;
 
public class Solution_1244 {
 
        
    
    public static void main(String[] args) throws Exception {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        
        int TC = Integer.parseInt(bf.readLine()); 
        int change;
        int ans;
        
        for(int tc=1;tc<=TC;tc++) {
            StringTokenizer st = new StringTokenizer(bf.readLine()," ");
            String s = st.nextToken();
            Integer[] board = new Integer[s.length()];
            change = Integer.parseInt(st.nextToken());//교환 횟수            
                
            int[] check = new int[10];
            Arrays.fill(check, -1);
            ArrayList<Integer> al = new ArrayList<Integer>();
            for(int i=0;i<board.length;i++) { //숫자판
                board[i] = s.charAt(i)-'0';
                if(check[board[i]] != -1) { //중복된 숫자가 들어온 경우
                    //al리스트에 중복된 숫자들의 인덱스를 저장해논다.
                    if(al.isEmpty())al.add(check[board[i]]);
                    al.add(i);
                }
                else check[board[i]] = i;    
            }
            
            for(int i=0;i<board.length;i++) { //선택정렬
                if(change==0) break;
                
                int maxIndex = i;
                for(int j=i;j<board.length;j++) {
                    if(board[maxIndex]<=board[j]) {
                        maxIndex = j;
                    }
                }
                if(maxIndex != i) {
                    int tmp = board[maxIndex]; //1.가장 큰 숫자위치와 가장 왼쪽 원소 swap
                    board[maxIndex]=board[i]; 
                    board[i]=tmp;
                    change --;                    
                } 
            } //end of for 선택정렬
            
            //교환횟수가 남은 경우
            
            //동일한 숫자가 존재하면, 값의 변동없이 교환회수를 감소시킬 수 있다.
            HashSet<Integer> hs = new HashSet<Integer>(Arrays.asList(board));
            
            if(hs.size() != board.length) { // 같은 숫자 존재
                /* 처음에 저장해논 중복된 숫자들의 인덱스를 이용해 
                 * 중복 숫자들과 교환된 숫자들을 추출 후, tmpArr 배열에 저장한다.
                 * 
                 * 해당 숫자들을 sort 후 다시 입력한다.
                 * 
                 * ex ) 
                 * 3 2 1 8 8 8 , 3번 교환
                 * 알고리즘에 의하면
                 * 8 8 8 1 2 3 
                 * 이 되지만, 실제 답은
                 * 8 8 8 3 2 1 이다.
                 * 즉, 중복 숫자들과 교환된 숫자들은 다시 sort 후 대입한다. 
                 */
                Integer[] tmpArr = new Integer[al.size()];
                
                for(int i=0;i<al.size();i++) {
                    tmpArr[i] = board[al.get(i)];
                }
                
                Arrays.sort(tmpArr, new Comparator<Integer>() { //내림차순 정렬
                    @Override
                    public int compare(Integer o1, Integer o2) {
                        return o2-o1;
                    }
                });
                
                int idx = 0;
                for(int i : al) {
                    board[i] = tmpArr[idx++];
                }
            }
            
            
            
            //짝수번 남았으면 무시, 홀수 번이면 1의 자리와 10의자리를 바꿔준다.
            if(change%2 == 1 && hs.size() == board.length) {
                int len = board.length-1;
                int tmp = board[len]; //1.가장 큰 숫자위치와 가장 왼쪽 원소 swap
                board[len]=board[len-1]; 
                board[len-1]=tmp;
            } 
        
            
            
            System.out.print("#"+tc+" ");
            for(int i=0;i<board.length;i++) System.out.print(board[i]);
            System.out.println();
        }//end of tc
        
    }//end of main
}
 
 cs

 

저작자표시

'Algorithm Problem Solving' 카테고리의 다른 글

[BOJ] 9999 : 구구 **결정적 힌트**  (5) 2019.02.13
[SW Expert Academy] 1247. [S/W 문제해결 응용] 3일차 - 최적 경로  (2) 2019.02.13
[BOJ] 10819 : 차이를 최대로  (0) 2019.02.08
[BOJ] 1987 : 알파벳  (0) 2019.02.08
[BOJ] 10798 : 세로읽기  (0) 2019.02.08

문제 >> 차이를 최대로

 

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
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
 
class pair {
    int now;
    int weight;
    public pair(int now, int weight) {
        super();
        this.now = now;
        this.weight = weight;
    }
}
 
public class Main {
    static int n,m;
    static boolean[][] map;
 
    static int[] rst;
    static Scanner sc = new Scanner(System.in);
 
    static int bfs(int start) {
        boolean[] visited = new boolean[n+1];
        Queue<pair> q = new LinkedList<pair>();
        visited[start]=true;
        q.add(new pair(start,0));
        int score=0;
        
        while(!q.isEmpty()) {
            int now = q.peek().now;
            int weight = q.peek().weight;
            score+=weight;
            q.poll();
            
            for(int i=1;i<=n;i++) {
                if(map[now][i] && !visited[i]) {
                    visited[i]=true;
                    q.add(new pair(i,weight+1));
                }
            }
        }
        
        return score;
    }
    
    public static void main(String[] args) {
        n = sc.nextInt(); // 유저의 수
        m = sc.nextInt(); // 관계 수
        
        map = new boolean[n+1][n+1];
        rst = new int[n+1];
        
        for(int i=0;i<m;i++) {
            int a=sc.nextInt();
            int b=sc.nextInt();
            
            map[a][b] = true;
            map[b][a] = true;
        }
        
        int min=Integer.MAX_VALUE;
        int ans = 0;
        for(int i=1;i<=n;i++) {
            
            rst[i] = bfs(i);
            
            if(rst[i]<min) {
                min = rst[i];
                ans = i;
            }
        }
        
        System.out.println(ans);
        
    }//end of main
}
 
 cs
저작자표시

'Algorithm Problem Solving' 카테고리의 다른 글

[SW Expert Academy] 1247. [S/W 문제해결 응용] 3일차 - 최적 경로  (2) 2019.02.13
[SW Expert Academy] 1244. [S/W 문제해결 응용] 2일차 - 최대 상금  (2) 2019.02.12
[BOJ] 1987 : 알파벳  (0) 2019.02.08
[BOJ] 10798 : 세로읽기  (0) 2019.02.08
[BOJ] 6588 : 골드바흐의 추측  (0) 2019.02.08

+ Recent posts

티스토리툴바