유한 개의 정수로 이루어진 집합이 있을 때, 이 집합의 부분집합 중에서 그 집합의 원소를 모두 더한 값이 0이 되는 경우가 있는지 확인하는 알고리즘을 알아보겠습니다.


먼저 문제를 풀기 위한 절차는 아래와 같이 생각해볼 수 있습니다.

  1.  완전 검색기법으로 모든 부분집합을 구하기
  2.  부분집합을 모두 더해서 0과 일치하는지 확인해보기

전체적인 성능에 영향을 미치는 (1)번 절차의 알고리즘을 만들어보도록 하겠습니다.


1. 반복문을 이용한 부분집합 구하기


1
int[] arr = {1, 2, 3, 4}
cs
  1.  1이 부분집합에 포함되었을 경우와 안되었을 경우 ( 2가지 )
  2.  2가 부분집합에 포함되었을 경우와 안되었을 경우 ( 2가지 )
  3.  3이 부분집합에 포함되었을 경우와 안되었을 경우 ( 2가지 )
  4.  4가 부분집합에 포함되었을 경우와 안되었을 경우 ( 2가지 )

위의 과정을 개발 코드로 구현해보도록 하겠습니다. bitArr은 인덱스 요소의 표현 여부를 정하는 비트(0, 1)을 저장하고 있습니다.  즉 bitArr[0]의 값이 1이면 arr[0]을 부분집합으로 가지는 것입니다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4};
        int[] bitArr = new int[4];
        
        for(int i=0; i<2; i++) {
            bitArr[0] = i%2==0 ? 0:1;
            for(int j=0; j<2; j++) {
                bitArr[1] = j%2==0 ? 0:1;
                for(int k=0; k<2; k++) {
                    bitArr[2] = k%2==0 ? 0:1;
                    for(int l=0; l<2; l++) {
                        bitArr[3] = l%2==0 ? 0:1;
                        
                        for(int m=0; m<4; m++) {
                            if(bitArr[m] != 0 ) {
                                System.out.printf(arr[m]+", ");
                            }
                        }
                        System.out.println("");
                    }
                }
            }
        }
    }
cs


위 코드를 이해하기 쉽게 그림으로 일부 표현해 보았습니다.  아래와 같이 진행한다면 네 번째 반복문에는 16개의 (0 0 0 0 ~ 1 1 1 1)의 bitArr 형태를 만들어 낼 것입니다. 각 배열에서 값이 1인 인덱스만 arr[인덱스] 로 출력하면 총 16개의 부분집합을 구할 수 있습니다. 



2. 비트연산자를 이용한 부분집합 구하기

비트연산자를 이용하여 부분집합을 구하기 전에 아래의 연산을 이해해야 합니다. 
  1. 1 << n 은 원소가 n개일 경우 모든 부분집합의 수 
  2. i & ( 1<< j )  은 i 의 j번째 인덱스가 0인지 1인지 확인가능

위에서 배운 bitArr ( 0 0 0 0 ~ 1 1 1 1 )을 정수형으로 변환하면 0~15입니다.  즉 0~ 15까지 반복하면서 각 인덱스의 자리가 1인지 0인지 판별하여 부분집합을 구하는 방법입니다. 1인지 0인지 판별하는 부분은 i & ( 1 << j ) 연산으로 수행합니다. 



1
2
3
4
5
6
7
8
9
10
11
12
    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4};
        
        for(int i=0; i<(1<<4); i++) {
            for(int j=0; j<4; j++) {
                if( (i & (1<<j)) >= 1) {
                    System.out.printf("%d, ", arr[j]);
                }
            }
            System.out.println("");
        }
    }
cs




저작자표시

'알고리즘 > SW Expert Academy' 카테고리의 다른 글

Sort(정렬)에 대해서 - Selection Sort  (0) 2019.02.09
검색  (0) 2019.02.09
2차원 배열  (0) 2019.02.03
Sort(정렬)에 대해서 (1) - Bubble Sort와 Counting Sort  (0) 2019.01.20
탐욕 알고리즘(Greedy Algorithm)을 이용한 Baby-gin  (0) 2019.01.20

2차원 배열

2차원 배열은 세로길이(행의 개수), 가로길이(열의 개수)를 필요로 합니다. 아래는 2차원 배열 int example[2][4]의 예시입니다.


int [0][0]

int [0][1]

int [0][2]

int [0][3]

int [1][0]

int [1][1]

int [1][2]

int [1][3]



2차원 배열의 순회

n x m 배열의 n*m 개의 모든 원소를 조사하는 방법


행 우선 순회

행을 우선으로 Array의 원소를 조사하는 방법입니다.

1
2
3
4
5
for(int i=0; i<4; i++) {
    for(int j=0; j<5; j++) {
        //arr[i][j]
    }
}
cs



열 우선 순회

열을 우선으로 Array의 원소를 조사하는 방법입니다.

1
2
3
4
5
for(int j=0; j<5; j++) {
    for(int i=0; i<4; i++) {
        //arr[j][i]
    }
}
cs



지그재그 순회

첫 행은 우측으로, 다음 행은 좌측으로 진행하여 Array의 원소를 조사하는 방법입니다.



1
2
3
4
5
6
    
for(int i=0; i<4; i++) {
    for(int j=0; j<5; j++) {
        //arr[i][j+(5-1-2*j)*(i%2)];
    }
}
cs



델타를 이용한 탐색

2차 Array의 한 좌표에서 네 방향의 인접 Array 요소를 탐색할 때 사용하는 방법입니다. 델타 값은  한 좌표에서 네 방향의 좌표와  x,y의 차이를 저장한 Array입니다. 델타값을 이용하면 특정 우너소의 상하좌우에 위치한 원소에 접근할 수 있습니다.



전치행렬

행과 열의 값이 반대인 행렬을 말합니다.


1
2
3
4
5
6
7
8
9
for(int i=0; i<2; i++) {
    for(int j=0; j<2; j++) {
        if(i > j ) {
            int temp = arr[i][j];
            arr[i][j] = temp[j][i];
            tem[[j][i] = temp;
        }
    }
}
cs





저작자표시

'알고리즘 > SW Expert Academy' 카테고리의 다른 글

검색  (0) 2019.02.09
부분 집합 문제  (0) 2019.02.09
Sort(정렬)에 대해서 (1) - Bubble Sort와 Counting Sort  (0) 2019.01.20
탐욕 알고리즘(Greedy Algorithm)을 이용한 Baby-gin  (0) 2019.01.20
완전 검색을 이용한 Baby-gin  (0) 2019.01.19

Sort(정렬)이란?  

2개 이상의 자료를 특정 기준에 의해 작은 값부터 큰 값(오름차순) 혹은 그 반대의 순서(내림차순)대로 재배열 하는 것



Sort 방식의 종류

  1. Bubble Sort(버블 정렬)
  2. Counting Sort(카운팅 정렬)
  3. Selection Sort(선택 정렬)
  4. Quick Srot(퀵 정렬)
  5. Insertion Sort(삽입 정렬)
  6. Merge Sort(병합 정렬)


Bubble Sort(버블정렬) - O^2 

입전한 두 개의 원소를 비교하며 자리를 계속 교환하는 방식

  1. 첫번째 원소부터 인접한 원소끼리 게속 자리를 교환하면서 맨 마지막 자리까지 이동
  2. 한 단계가 끝나면 가장 큰 원소 또는 가장 작은 마지막 자리로 정렬됨 


{55, 7, 78, 12, 42} 를 Bubble Sort하는 과정


 1단계

55 

7 

78 

12 

42 

 2단계

7 

55 

78 

12 

42 
 3단계

7

55 

78

12 

42 

 4단계

7

55 

12 

78 

42 

 5단계

7

55 

12 

42 

78 


  1. 55와 7을 비교하여 55가 더 큰 숫자이니 7과 자리를 바꾼다.
  2. 자리를 바꾼 후 55와 78을 비교하는데 78이 더 크므로 자리 이동이 일어나지 않는다.
  3. 78과 12를 비교하여 78이 더 큰 숫자이니 12와 자리를 바꾼다.
  4. 자리를 바꾼 후 78과 42를 비교하여 78이 더 크니 42와 자리를 바꾼다.
  5. 78이 가장 마지막 위치에 자리하였으므로 원소 1개에 대해서 정렬이 완료된 것이다.



 1단계

 7

 55

 12

 42

 78

 2단계

 7

 55

 12

 42

 78

 3단계

 7

 12

 55

 42

 78

 4단계

 7

 12

 42

 55

 78


  1. 7과 55를 비교하였으나 55가 더 크므로 자리를 변경하지 않는다.
  2. 55와 12를 비교하여 숫자 55가 더 크므로 12와 자리를 바꾼다
  3. 55와 42를 비교하여 5가 더 크므로 42와 자리를 바꾼다
  4. 78은 이미 정렬된 원소이기 때문에 비교대상이 아니고, 55는 마지막 위치에 자리하였기 때문에 또 하나의 원소에 대해서 정렬이 완료된 것이다.

위와 같은 작업을 반복하면 최종적으로 {7, 12, 42, 55, 78} 로 정렬이 완료될 것이다.

Bubble Sort 구현하기. 



Counting Sort(카운팅 정렬)

항목들의 순서를 결정하기 위해 집합에 각 항목이 몇 개씩 있는지 세는 작업을 하여, 선형 시간에 정렬하는 효율적인 Algorithm

→ 정수나 정수로 표현할 수 있는 자료에 대해서만 적용 가능. 각 항목의 발생 회수를 기록하기 위해, 정수 항목으로 인덱스되는 카운트들의 배열을 사용하기 때문임.  예를 들어 { 0, 4, 1, 3, 1, 2, 4, 1 } 를 Counting Sort를 이용하여 정렬하기 위해서는 { 1, 3, 1, 1, 2 } 란 Counts 배열이 필요함.


{ 0, 4, 1, 3, 1, 2, 4, 1 } 을 Counting Sort 하는 과정.


1. Data 배열과 Counts 배열 준비

Data 배열
 data[0]data[1] data[2] data[3] data[4] data[5] data[6] 

data[7] 

 0

4 

1 

3 

1 

2 

4 

1 


Counts 배열

  - Counts 배열은 Data 배열의 요소를 인덱스로 하고 그 값은 요소의 개수로 한다. 그 작업 결과는 아래와 같다.

 counts[0]

counts[1] 

counts[2] counts[3] 

counts[4] 

 1

 3

 1

 1

 2


 - Data 배열의 원소가 정렬될 때 배열의 몇 번째 위치에 들어가야 하는지 보여주는 Counts 배열로 변경해야 한다. 그 작업은 다음과 같다.

counts[0] = counts[0], counts[1] = counts[0]+counts[1], counts[2] = counts[1]+counts[2] ... counts[4] = counts[3] + counts[4] 


 counts[0]

counts[1]

counts[2]

counts[3]

counts[4] 

 1

 4

 5

 6

 8


2. Data의 마지막 항목부터 정렬을 진행한다. Data의 마지막 항목은 1 이므로 Counts 배열의 1번 인덱스를 확인(4)하고 값을 1감소 시킨 후(3) Counts에       저장하고 Temp 배열에 4번째에 1을 삽입한다.


 data[0]data[1]  data[2]data[3] data[4] data[5] data[6] data[7] 

 0

4 

1 

3 

1 

2 

4 

1 


 counts[0]

counts[1] 

counts[2] 

counts[3] 

counts[4] 

 1

 3

 5

 6

 8


 temp[0]

temp[1] 

temp[2]

temp[3] 

temp[4] 

temp[5] 

temp[6] 

temp[7] 

 

 

 

 1

 

 

 

 



3. Data의 마지막에서 두 번째 항목은 4이므로 Counts 배열의 4번 인덱스를 확인(8)하고 값을 1 감소시킨 후 Counts에 저장(7)한 뒤 Temp 배열의 8번째     에 4 저장. 


data[0] 

data[1] 

data[2] 

data[3] 

data[4] 

data[5] 

data[6]

data[7]

 0

 4

 1

 3

 1

 2

 4

 1


 counts[0]

counts[1] 

counts[2]

 counts[3]

 counts[4]

 1

 3

 5

 6

 7


temp[0] 

temp[1] 

temp[2] 

temp[3] 

temp[4] 

temp[5] 

temp[6] 

temp[7] 

 

 

 

 1

 

 

 

 4


4. 위와같은 작업을 반복하면 최종적인 결과는 아래와 같음


 data[0]

data[1] 

data[2] 

data[3] 

data[4] 

data[5] 

data[6] 

data[7] 

 0

4 

1 

3 

1 

2 

4 

1 


 counts[0]

counts[1] 

counts[2] 

counts[3] 

counts[4] 

 0

1 

4 

5 

6 


temp[0] 

temp[1] 

temp[2] 

temp[3] 

temp[4] 

temp[5] 

temp[6] 

temp[7] 

 0

1 

1 

1 

2 

3 

4 

4 



Counting Sort 구현하기

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.Scanner;
 
public class CountingSort {
    public static void main(String[] args) {
        int[] data = new int[8]; 
        
        Scanner sc = new Scanner(System.in);
        for(int i=0; i<data.length; i++) {
            data[i] = sc.nextInt();
        }
        int[] counts = getCounts(data);
        int[] sorted = countingSort(data, new int[data.length] , counts);
        
        for(int i=0;i <sorted.length; i++) {
            System.out.printf(sorted[i]+" ");
        }
    }
    
    public static int[] getCounts(int[] data) {
        // 요소의 최대값 구함
        int max = data[0];
        for(int i=0; i<data.length; i++) {
            if(max < data[i]) {
                max = data[i];
            }
        }
        // 요소의 값을 인덱스로 하고, 요소의 개수를 값으로 가지는 count 배열 생성
        int[] counts = new int[max+1];
        for(int i=0; i<data.length; i++) {
            counts[data[i]] = counts[data[i]]+1;
        }
        
        // count배열에 요소를 정렬하였을 때 위치를 표시
        for(int i=1; i<counts.length; i++) {
            counts[i] = counts[i-1] + counts[i];
        }
        return counts;
    }
    
    public static int[] countingSort(int[] data, int[] sort, int[] counts) {
        for(int i=data.length-1; i>=0; i--) {
            counts[data[i]] = counts[data[i]] - 1;
            sort[counts[data[i]]] = data[i];
        }
        
        return sort;
    }
}
 
cs


저작자표시

'알고리즘 > SW Expert Academy' 카테고리의 다른 글

검색  (0) 2019.02.09
부분 집합 문제  (0) 2019.02.09
2차원 배열  (0) 2019.02.03
탐욕 알고리즘(Greedy Algorithm)을 이용한 Baby-gin  (0) 2019.01.20
완전 검색을 이용한 Baby-gin  (0) 2019.01.19

탐욕 알고리즘(Greedy Algorithm)이란 ?

- 최적해를 구하는데 사용되는 방법
- 여러 경우 중 하나를 선택해야 할 때마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식으로 진행하며 각 선택의 시점에서 이루어지는 결정은    지역적으로는 최적이지만 그것들을 계속 진행하였을 때 나온 해답이 최적이라는 보장은 없음.


예를 들어, 거스름 돈 830원을 받아야 하는데 동전의 개수를 가장 적게 받고 싶다면 당연히 500원 짜리로 받을 수 있는 만큼 많이 받고, 그 다음 100원으로 받을 수 있는 만큼 받아야 동전의 개수가 가장 적어질 것이라 생각할 것이다. 이 문제의 경우 실제로 그렇겠지만 말이다.


또는 이전의 완전 검색(Exhaustive Search) 방식에서 보았던 Baby-gin 문제를 Greedy Algorithm 방식으로 문제에 접근한다고 가정해보자.


" Baby-gin은 어차피 앞의 숫자 3개, 뒤의 숫자 3개만 검사하니까 숫자를 정렬한 후 앞,뒤 숫자3개만 run 또는 triple인지 비교하도록 해보자" 


이렇게 접근했을 때 과연 최적의 해답을 구할 수 있을까? "{ 6, 4, 4, 5, 4, 4 }" 라는 숫자를 정렬하면 "{ 4, 4, 4, 4, 5, 6 }" 로 Baby-gin에 해당된다. 그러나

" { 1, 2, 3, 1, 2, 3} 은 이대로 두면 Baby-gin에 해당되지만 정렬하면 { 1, 1, 2, 2, 3, 3} 으로 Baby-gin에 해당하지 않는다.


즉, Greedy Algorithm 방식의 접근은 최적의 해 또는 해답을 보장하지 않는다는 것이다. 


Baby-gin 문제를 또 다른 Greedy Algorithm 방식으로 구현해보자. 

" 숫자 6개의 개수를 표현하는 배열(numbers)에 담아서 run 또는 triple에 해당되면 확인 후 숫자의 개수를 감소시키자. "는 방향으로 접근하여 구현하였다.




저작자표시

'알고리즘 > SW Expert Academy' 카테고리의 다른 글

검색  (0) 2019.02.09
부분 집합 문제  (0) 2019.02.09
2차원 배열  (0) 2019.02.03
Sort(정렬)에 대해서 (1) - Bubble Sort와 Counting Sort  (0) 2019.01.20
완전 검색을 이용한 Baby-gin  (0) 2019.01.19

완전 검색(Exhaustive Search)이란 ? 

- 쉽게 말하자면 모든 경우의 수를 테스트한 후 해답을 도출하는 방법. Brute-force 혹은 Generate-andTest 기법이라고도 불림. 

- 경우의 수가 적은 경우에 유용함



Baby-gin 게임에 완전검색 적용해보기


Baby-gin 게임이란 ?

- 0~9 숫자 카드에서 임의의 카드 6장을 뽑았을 때 3장의 카드가 연속적인 번호를 갖는 경우를 run 이라하고, 3장의 카드가 동일한 번호를 갖는 경우를 triple 라고 함.
- 6장의 카드는 run, triple로만 이루어져 있어야 Baby-gin임


6개 숫자가 입력되었을 때 Baby-gin 인지 확인하는 프로그램을 작성해보자.

1. 6개의 숫자로 조합할 수 있는 모든 경우의 수를 생성한다
   ex) 0 1 5 9 3 2 가 입력 되었을 때 조합할 수 있는 경우의 수.
        0 1 5 9 2 3
        0 3 9 5 1 2
        ... 

2. 각각의 경우에 대하여 Baby-gin 인지 확인한다. 




Baby-gin 확인하기 프로그램 구현




저작자표시

'알고리즘 > SW Expert Academy' 카테고리의 다른 글

검색  (0) 2019.02.09
부분 집합 문제  (0) 2019.02.09
2차원 배열  (0) 2019.02.03
Sort(정렬)에 대해서 (1) - Bubble Sort와 Counting Sort  (0) 2019.01.20
탐욕 알고리즘(Greedy Algorithm)을 이용한 Baby-gin  (0) 2019.01.20

+ Recent posts

티스토리툴바