검색

검색이란 저장되어 있는 자료중에서 원하는 항목(탐색키)을 찾는 작업을 말합니다. 

검색의 종류

순차 검색

일렬로 되어 있는 자료를 순서대로 검색하는 방법입니다. Array나 연결 리스트 등 순차구조로 구현된 자료구조에서 유용하지만 데이터가 많은 경우 비효율적인 알고리즘입니다.

  • 데이터가 정렬되어 있을 경우

순차검색에서 데이터가 정렬되어 있을 경우에는 일반적인 for문 방식과 같으므로 자세하게 설명하지 않겠습니다.


  • 데이터가 정렬되어 있지 않을 경우

데이터가 오름차순으로 정렬된 경우 자료를 순차적으로 검색하면서 키값을 비교하는데 원소의 키 값이 검색 대상의 키 값보다 크면 원소가 없다는 것이므로 더 이상 검색하지 않고 검색을 종료하는 방법.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
    public static void main(String[] args) {
        int[] arr = {2, 4, 7, 9, 11, 19, 23};
        
        
        for(int i=0; i<arr.length; i++) {
            if(arr[i] == 10) {
                System.out.println("찾았다!!");
                break;
            } else if(arr[i] > 10) {
                System.out.println("10 없음!!");
                break;
            }
        }
    }
cs


이진 검색


이진검색은 자료의 가운데에 있는 항목의 키 값과 비교 후 다음 검색 위치를 결정합니다. 검색 범위를 반으로 줄여가기 때문에 순차 검색보다 효율적입니다. 다만 이진 검색은 자료가 정렬된 상태에서만 사용이 가능합니다. 
  1. 자료의 중앙에 있는 원소를 선택
  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
 
public class 이진검색 {
    public static void main(String[] args) {
        int[] arr = {2, 4, 7, 9, 11, 19, 23};
        boolean searchResult = binarySearch(arr, 0, arr.length-1, 7);
        System.out.println(searchResult);
    }
    
    private static boolean binarySearch(int[] arr, int start, int end, int key) {
        int middle = (start+end) / 2;
        
        if(start == end) {
            return false;
        }
        
        if(key < arr[middle]) {
            return binarySearch(arr, start, middle-1, key);
        } else if(key > arr[middle]) {
            return binarySearch(arr, middle+1, end, key);
        } else {
            return true;
        }
    }
}
 
cs



인덱스

데이터베이스에서 유래되었으며 인덱스 저장공간을 이용하여 테이블에 대한 동작 속도를 높여주는 자료 구조입니다.  인덱스는 키-필드만 갖고있기 때문에 저장공간을 적게 차지합니다. 



저작자표시

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

문자열 (String)  (0) 2019.02.16
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

유한 개의 정수로 이루어진 집합이 있을 때, 이 집합의 부분집합 중에서 그 집합의 원소를 모두 더한 값이 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

티스토리툴바