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
package basic;
 
import java.util.ArrayList;
import java.util.Arrays;
 
public class NumberOfCases {
    static char[] arr = { 'a', 'b', 'c', 'd' };
    static int r = 2;
 
    public static void main(String[] args) {
 
        set = new char[r];
        // System.out.println("==조합==");
        // nCr(0,0);
        //comb(r,arr.length);
        // System.out.println("==중복조합==");
        // nHr(0,0);
        //System.out.println("==중복순열==");
        //nPir(0);
        setList = new ArrayList<>();
        //subset(0,0);
        
        visit = new boolean[arr.length];
        nPr(0);
    }
 
    static char[] set;
 
    public static void nCr(int len, int k) { // 조합
        if (len == r) {
            System.out.println(Arrays.toString(set));
            return;
        }
 
        for (int i = k; i < arr.length; i++) {
            set[len] = arr[i];
            nCr(len + 1, i + 1);
        }
    }
 
    public static void comb(int depth, int idx) {
        if (depth==0) {
            System.out.println(Arrays.toString(set));
        } else if (idx < depth) {
            return;
        } else {
            //System.out.println(depth + " " + idx );
            set[depth-1] = arr[idx-1];
 
            comb(depth - 1, idx - 1);
            comb(depth, idx-1);
        }
 
    }
 
    public static void nHr(int len, int k) { // 중복조합
        if (len == r) {
            System.out.println(Arrays.toString(set));
            return;
        }
 
        for (int i = k; i < arr.length; i++) {
            set[len] = arr[i];
            nHr(len + 1, i);
        }
    }
    static boolean[] visit;
    public static void nPr(int len) {// 순열
        if(len==r) {
            System.out.println(Arrays.toString(set));
            return;
        }
        
        for(int i=0;i<arr.length;i++) {
            if(!visit[i]) {
                set[len]=arr[i];
                visit[i]=true;
                nPr(len+1);
                visit[i]=false;
            }
        }
    }
 
    public static void nPir(int len) {// 중복순열
        if(len==r) {
            System.out.println(Arrays.toString(set));
            return;
        }
        
        for(int i=0;i<arr.length;i++) {
            set[len]=arr[i];
            nPir(len+1);
        }
    }
 
    static ArrayList<Character> setList;
    public static void subset(int len, int k) {// 부분집합
        System.out.println(setList);
        if(len==arr.length) {
            return;
        }
        for(int i=k;i<arr.length;i++) {
            setList.add(arr[i]);
            subset(len+1,i+1);
            setList.remove(setList.size()-1);
        }
    }
}
 
cs
저작자표시

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

[java] Dijkstra 다익스트라 알고리즘  (0) 2019.02.19
Kruskal 크루스칼 알고리즘  (0) 2019.02.18
DisjointSets  (0) 2019.02.18
[java] Insertion Sort 삽입정렬  (0) 2019.01.28
Permutation 순열  (0) 2019.01.17
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
package Z_Project;
 
import java.util.Arrays;
 
/**
 * Dijkstra: 하나의 선택한 정점에서 각 정점까지 갈 수 있는 최단거리를 구하는 알고리즘
 *  Greedy 방식, 음이 아닌 가중치 일 경우만 사용가능
 *                음의 가중치가 있는 경우는 => 벨만포드 알고리즘을 통해서 구해야한다
 *    시간복잡도 O(n^2)
 */
public class Z38_Dijkstra {
    public static void main(String[] args) {
        final int M = Integer.MAX_VALUE;
        int[][] G = {
                {0,3,5,M,M,M},
                {M,0,2,6,M,M},
                {M,1,0,4,6,M},
                {M,M,M,0,2,3},
                {3,M,M,M,0,6},
                {M,M,M,M,M,0}
        };
        
        int s = 0; //시작정점
        int[] D = G[s].clone(); // 가중치 배열, 시작정점의 진출차수로 가중치배열을 초기화
        boolean[] used = new boolean[G.length]; //사용한 정점들을 저장할 배열
        
        for (int n = 0; n < used.length; n++) { //정점 하나씩 선택하기
            //사용하지 않은 정점중에서, 가중치가 최소인 정점을 찾아서 used배열에 정점 추가
            int minIndex = -1; //최소 가중치가 저장된 D배열의 인덱스
            int minVal = M; //최소가중치
            for(int i=0;i<D.length;i++) {
                if(!used[i] && minVal>D[i]) {
                    minIndex=i;
                    minVal=D[i];
                }
            } //가중치 최소인 장점을 찾음. 
            used[minIndex] = true;
            
            //선택한 정점을 통해서 갈수 있는(인접한) 정점의 가중치를 갱신
            for(int i=0;i<D.length;i++) {
                //사용하지 않은 정점, 인접한 정점, 가중치가 지금보다 더 작으면 =>갱신
                if(!used[i] && G[minIndex][i] != M && D[i]>D[minIndex]+G[minIndex][i] ) {
                    D[i] = D[minIndex]+G[minIndex][i];
                }
            }
        }
        
        System.out.println(Arrays.toString(D));
    } //end of main
}//end of class
 
 
cs


저작자표시

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

경우의 수( 순열 / 중복순열 / 조합 / 중복조합 / 부분집합 )  (0) 2019.06.05
Kruskal 크루스칼 알고리즘  (0) 2019.02.18
DisjointSets  (0) 2019.02.18
[java] Insertion Sort 삽입정렬  (0) 2019.01.28
Permutation 순열  (0) 2019.01.17
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
package Z_Project;
 
import java.util.Arrays;
import java.util.Scanner;
 
/**
 * MST 알고리즘 중 KRUSKAL이 더 직관적이고 간단(많이 사용됨) DisjointSets
 */
 
/*
 * 
input
6 11
5 3 18
1 2 21
2 6 25
0 2 31
0 1 32
3 4 34
5 4 40
2 4 46
0 6 51
4 6 51
0 5 60
output
5-3 18
1-2 21
2-6 25
0-2 31
3-4 34
2-4 46
 * 
 * */
public class Z37_KRUSKAL {
    public static int[] p; //부모를 저장할 배열
    public static int[] rank;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int V = sc.nextInt();
        int E = sc.nextInt();
        p = new int[V+1];
        rank = new int[V+1];
        
        Edge[] ed = new Edge[E];
        
        for(int i=0;i<E;i++) {
            ed[i] = new Edge(sc.nextInt(),sc.nextInt(),sc.nextInt());
        }
        Arrays.sort(ed); //정렬하기 위해서 compareTo()를 작성해야한다.
        
        for(int i=0;i<p.length;i++) {
            makeSet(i);
        }
        
        for(int i=0;i<ed.length;i++) { //가중치가 낮은 간선부터 선택하기
            Edge e = ed[i];
            if(findSet(e.a) != findSet(e.b)) { //서로 다른 집합일 경우만 합치기
                union(e.a,e.b);
                System.out.println(e.a+"-"+e.b+" "+e.val);
            }
        }
    }//end of main
    
    public static void printSet() {
        System.out.print("index : ");
        for(int i=0;i<p.length;i++) {
            System.out.printf("%2d ", i);
        }
        System.out.print("\nparent: ");
        for(int i=0;i<p.length;i++) {
            System.out.printf("%2d ", p[i]);
        }        
        
        System.out.println("\n");
    }
    
    
    /*멤버 x를 포함하는 새로운 집합을 생성*/
    public static void makeSet(int x) {
        p[x]=x; //부모 : 자신의 index로 표시 or -1
        //rank[x] = 0;//초기값 0임, 생략가능
    }
    
    /*멤버 x를 포함하는 집합의 대표자를 리턴*/
    public static int findSet(int x) {
        if(x==p[x]) return x;
        else {
            p[x]=findSet(p[x]); // Path Compression
            //rank[x]=1;//할 필요 없다. 대표자의 깊이(rank)만 알면된다.
            return p[x];
        }
    }
    
    public static void union(int x,int y) {
        int px = findSet(x);
        int py= findSet(y);
        
        // 서로 다른 집합일 경우만 합친다.
 
        if(px!=py) {
        //    p[py]=px; //대표자 합치기    
            link(px,py);
        }
    }
    
    /*x의 대표자의 집합과 y의 대표자의 집합을 합침, rank도 맞춤*/
    public static void link(int px, int py) {
        if(rank[px]>rank[py]) {
            p[py]=px; //작은쪽에 큰쪽을 붙인다.
        } else {
            p[px]=py;
            
            if(rank[px]==rank[py]) { //같은 경우는 rank 값이 증가
                rank[py]++;//집합의 대표자 랭크가 증가됨.
            }
        }
    }
    
    public static class Edge implements Comparable<Edge>{
        int a; //정점1
        int b; //정점2
        int val; //가중치
        public Edge(int a, int b, int val) {
            this.a = a;
            this.b = b;
            this.val = val;
        }
        @Override
        public int compareTo(Edge o) { //비교기준
            return this.val-o.val;
        }
        
        
    }
}
 
 cs
저작자표시

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

경우의 수( 순열 / 중복순열 / 조합 / 중복조합 / 부분집합 )  (0) 2019.06.05
[java] Dijkstra 다익스트라 알고리즘  (0) 2019.02.19
DisjointSets  (0) 2019.02.18
[java] Insertion Sort 삽입정렬  (0) 2019.01.28
Permutation 순열  (0) 2019.01.17
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
package Z_Project;
 
import java.util.Arrays;
 
/*
 * 상호배타 집합 => MST(크루스칼 알고리즘에 활용)
 * 
 * makeSet(int x) 멤버 x를 포함하는 새로운 집합을 생성
 * findSet(int x) 멤버 x를 포함하는 집합의 대표자를 리턴
 * union(int x, int y) 멤버 x,y의 대표자를 구해서 두 집합을 통합
 * link(int px, int py) x의 대표자의 집합과 y의 대표자의 집합을 합침
 * 
 */
public class Z36_DisjointSets2 {
    public static int[] p = new int[10]; //부모를 저장할 배열
    public static int[] rank=new int[10];
    public static void main(String[] args) {
        
        for(int i = 0;i<p.length;i++) {
            makeSet(i);
        }
        
        printSet();
        union(0,1);printSet();
        union(2,3);printSet();
        union(0,3);printSet();
        
    }//end of main
    
    public static void printSet() {
        System.out.print("index : ");
        for(int i=0;i<p.length;i++) {
            System.out.printf("%2d ", i);
        }
        System.out.print("\nparent: ");
        for(int i=0;i<p.length;i++) {
            System.out.printf("%2d ", p[i]);
        }        
        
        System.out.println("\n");
    }
    
    
    /*멤버 x를 포함하는 새로운 집합을 생성*/
    public static void makeSet(int x) {
        p[x]=x; //부모 : 자신의 index로 표시 or -1
        //rank[x] = 0;//초기값 0임, 생략가능
    }
    
    /*멤버 x를 포함하는 집합의 대표자를 리턴*/
    public static int findSet(int x) {
        if(x==p[x]) return x;
        else {
            p[x]=findSet(p[x]); // Path Compression
            //rank[x]=1;//할 필요 없다. 대표자의 깊이(rank)만 알면된다.
            return p[x];
        }
    }
    
    public static void union(int x,int y) {
        int px = findSet(x);
        int py= findSet(y);
        
        // 서로 다른 집합일 경우만 합친다.
 
        if(px!=py) {
        //    p[py]=px; //대표자 합치기    
            link(px,py);
        }
    }
    
    /*x의 대표자의 집합과 y의 대표자의 집합을 합침, rank도 맞춤*/
    public static void link(int px, int py) {
        if(rank[px]>rank[py]) {
            p[py]=px; //작은쪽에 큰쪽을 붙인다.
        } else {
            p[px]=py;
            
            if(rank[px]==rank[py]) { //같은 경우는 rank 값이 증가
                rank[py]++;//집합의 대표자 랭크가 증가됨.
            }
        }
    }
}
 
 cs
저작자표시

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

[java] Dijkstra 다익스트라 알고리즘  (0) 2019.02.19
Kruskal 크루스칼 알고리즘  (0) 2019.02.18
[java] Insertion Sort 삽입정렬  (0) 2019.01.28
Permutation 순열  (0) 2019.01.17
Dijkstra 최단경로 알고리즘  (2) 2019.01.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
 
import java.util.Arrays;
import java.util.LinkedList;
 
public class Z21_InsertionSort {
//    public static void main(String[] args) {
//        int[] arr= {6,4,8,5,7,2,9,3,0,1};
//        
//        for(int i=1;i<arr.length;i++) {
//            //삽입할 위치를 찾아 넣기
//            for(int j=i-1;j>=0;j--) {
//                if(arr[j]>arr[j+1]) { //뒤쪽에서 앞으로
//                    int temp = arr[j+1];
//                    arr[j+1]= arr[j];
//                    arr[j]=temp;
//                }
//            }
//        }
//        
//        for(int i=1;i<arr.length;i++) {
//            //삽입할 위치를 찾아 넣기
//            int num=arr[i];
//            int j;
//            for(j=i-1;j>=0;j--) {
//                if(arr[j]>num) { //뒤쪽에서 앞으로
//
//                    arr[j+1]= arr[j];
//
//                } else {
//                    break; //성능을 높일 수 있다.
//                }
//            }
//            arr[j+1] = num;
//        }
//        System.out.println(Arrays.toString(arr));
//    }
    
    public static void main(String[] args) {
        //Linked List 사용하기
        //Swap(쉬프트)작업을 안하는 것으로 성능을 개선
        
        int[] arr= {6,4,8,5,7,2,9,3,0,1};
        LinkedList<Integer> ll = new LinkedList<Integer>();
        
        for(int i=0;i<arr.length;i++) {
            int idx=0;
            for(idx = 0; idx<ll.size();idx++) { //정렬된 데이터에 삽입할 위치 찾기.
                if(arr[i]<ll.get(idx)) {
                    break; //삽입은 밖에서.
                    //0번째에서는 데이터가 없으니 해당 포문을 돌지않아 데이터가 들어가지 않는다.
                }
            }
            ll.add(idx,arr[i]); //ll의 idx번째 자리에 arr[i]를 삽입
        }
        System.out.println(ll);
    }
}
 
cs

저작자표시

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

[java] Dijkstra 다익스트라 알고리즘  (0) 2019.02.19
Kruskal 크루스칼 알고리즘  (0) 2019.02.18
DisjointSets  (0) 2019.02.18
Permutation 순열  (0) 2019.01.17
Dijkstra 최단경로 알고리즘  (2) 2019.01.08

순열 흐름도


n P k

재귀함수 종료조건 if( len == k )

즉 고른 숫자의 길이가 K일때 함수 종료.


흐름도에서 밑으로 레벨이 한단계 깊어질 수록 len이 +1 된다.

k = 1이면 len=1까지 (1레벨)만 진행되고,

k = 4일때 (즉 , 4 P 4 ) 일때 가장 깊은 레벨까지 재귀함수가 실행된다.


종료 조건 안의 배열 print는 len==k 길이 만큼 된다.

크기가 4인 배열의 함수에 숫자가 들어있어도 len(=k)만큼만 출력된다.


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
#include <iostream>
#include <memory.h>
int n = 2; //n개를 골라라
int m = 4; //인덱스범위
int arr[4];
int idx[4]={0,1,2,3};
 
void permutation(int len){
    if(len == n){
        for(int i=0 ;i<len;i++){
            printf("%d ", idx[i]);
        }
        printf("\n");
        return;
    }
    
    for(int i=len;i<m;i++){
        swap(i,len);
        permutation(len+1); //len을 증가시키기 위함
        swap(i,len);
    }
    
    
}
 
int main(int argc, const char * argv[]) {
    
    permutation(0);
 
    return 0;
}
 
cs


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

[java] Dijkstra 다익스트라 알고리즘  (0) 2019.02.19
Kruskal 크루스칼 알고리즘  (0) 2019.02.18
DisjointSets  (0) 2019.02.18
[java] Insertion Sort 삽입정렬  (0) 2019.01.28
Dijkstra 최단경로 알고리즘  (2) 2019.01.08

1. 개념

https://namu.wiki/w/%EB%8B%A4%EC%9D%B5%EC%8A%A4%ED%8A%B8%EB%9D%BC%20%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98



2. 기본 문제(BOJ)

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



3. 소스

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
#include<stdio.h>
#include<iostream>
#include<vector>
#include<queue>
 
 
#define INF 987654321
#define MAX_E 300001
 
using namespace std;
 
typedef struct NODE {
    int end;
    int weight;
};
 
int dist[20000] = { 0, };
vector<NODE> map[MAX_E];
 
int start;
 
 
void dijkstra() {
 
    priority_queue <pair<int, int>> pq;
    pq.push({ 0,start }); //시작점 삽입
 
    while (!pq.empty()){//큐가 빌때까지 반복 
        int now_node = pq.top().second; 
        int cost = -1 * pq.top().first;
        pq.pop(); //제일 우선순위 높은 ... (?) 노드 삭제
 
        for (int k = 0; k < map[now_node].size(); k++) { //now_node에 연결된 정점 체크
        
            int new_val = dist[now_node] + map[now_node][k].weight; 
            int before_val = dist[map[now_node][k].end];
 
            if (new_val < before_val) {
                dist[map[now_node][k].end] = new_val;
                pq.push({ -1 * new_val , map[now_node][k].end });
            } // 간선 weight 갱신
            
 
        }
    }
 
}
 
int main() {
 
    int v, e; //v:정점 e:간선
    
    int from, to, w;
 
    int i, j;
 
    scanf("%d %d", &v, &e);
    scanf("%d", &start); //시작점
 
    for (i = 1;i <= e;i++) {
        scanf("%d %d %d", &from, &to, &w);
        map[from].push_back(NODE{to,w});
    }
 
    for (i = 1;i <= v;i++) {
        dist[i] = INF;
    }
 
    dist[start] = 0;
 
    dijkstra();
 
 
    for (i = 1;i <= v;i++) {
        if (dist[i] != INF) printf("%d\n", dist[i]);
        else printf("INF\n");
    }
 
    return 0;
}
 
cs




처음에 map 벡터에 연결된 정점들과 해당 weight를 저장해준다.

우선순위 큐는 min_heap ! (weight이 작은것부터 방문하는 이유)

* 우선순위 큐는 기본적으로 큰 원소가 pop의 우선순위를 가지기 때문에,

음의 가중치로 바꾸어 우선순위 큐에 넣는다. (-1을 곱하는 이유)

  ex) weight이 10, 9, 8 이라는 값이 들어왔다면 우선순위는 1 2 3 이어야함.

저작자표시

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

[java] Dijkstra 다익스트라 알고리즘  (0) 2019.02.19
Kruskal 크루스칼 알고리즘  (0) 2019.02.18
DisjointSets  (0) 2019.02.18
[java] Insertion Sort 삽입정렬  (0) 2019.01.28
Permutation 순열  (0) 2019.01.17

+ Recent posts

티스토리툴바