String

문자열이란 말 그대로 문자를 나열한 것을 말합니다.  


패턴 매칭 알고리즘

- 본문이 되는 String에서 특정한 String을 패턴이라하며 이러한 패턴을 찾는 방법을 패턴 매칭이라고 합니다.

고지식한 패턴 검색(Brute Force)

- 본문 String을 처음부터 끝까지 차례대로 순회하면서 패턴 내의 문자들을 일일이 비교하는 방식입니다.

특정 문자열에서 찾고자하는 패턴이 존재하는지 확인하려면 다음과 같은 알고리즘을 생각해볼 수 있습니다.

원본[0]과 패턴[0] 비교하여 다르면 원본의 인덱스를 증가시키고 패턴의 인덱스는 다시 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
25
26
27
28
29
30
31
32
public class BruteForce {
    public static void main(String[] args) {
        String origin = "abc 1, 2 ABC";
        char[] originArr = origin.toCharArray();
        
        String search = "1, 2";
        char[] searchArr = search.toCharArray();
        
        System.out.println(bruteForce(originArr, searchArr));
    }
    
    private static boolean bruteForce(char[] origin, char[] search) {
        int index = 0;
        while(index + search.length <= origin.length) {
            boolean match = true;
            for(int j=0; j<search.length; j++) {
                if(origin[index+j] != search[j]) {
                    index++;
                    match = false;
                    break;
                }
            }
            
            if(match) {
                return true;
            }
        }
        
        return false;
    }
}
 
cs




KMP 알고리즘

불일치가 발생한 텍스트 스트링의 앞 부분에 어떤 문자가 있는지를 미리 알고 있으므로, 불일치가 발생한 앞 부분에 대하여 다시 비교하지 않고 매칭을 수행한다. 


그림에서 보는것처럼 패턴(빨간색) 매칭 도중 E에서 매칭실패가 일어났을 때 비교 인덱스를 1만 이동하는 것이 아니라 4만큼 이동한다. 이 이동거리는 전처리 과정에서 미리 구할 수 있다. 



위의 배열은 전처리 과정으로 구한 배열이고 패턴 매칭이 실패할 경우 패턴의 인덱스를 저장하고 있다. B(1번째) 패턴 매칭이 실패했을 경우 패턴의 비교덱스를 A(0)번째로 이동한 후 다시 비교하라는 것이다. 

( 사실 인덱스0의 값이 왜 -1인지 모르겠음..)



KMP 알고리즘 구현

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
 
public class KMP {
    public static void main(String[] args) {
        char[] data = "zzzzabcdzzabcdabcefz".toCharArray();
        char[] pattern = "abcdabcef".toCharArray();
        int[] failIndex = {0, 0, 0, 0, 0, 1, 2, 3, 0};
        
        System.out.println(solution(data, pattern, failIndex));
    }
    
    public static int solution(char[] data, char[] pattern, int[] failIndex) {
        int patternIndex = 0 ;
        int resultIndex = -1;
        for(int i=0; i<data.length-pattern.length+1; i++) {
            boolean isMatch = true;
            for(int j=patternIndex; j<pattern.length; j++) {
                
                if(data[i+j] != pattern[j]) {
                    patternIndex = failIndex[j];
                    isMatch = false;
                    break;
                }
            }
            
            if(isMatch) {
                resultIndex = i;
                break;
            }
        }
        
        return resultIndex;
    }
}
 
cs


보이어-무어 알고리즘

패턴을 오른쪽에서 왼쪽으로 비교하고 패턴에 오른쪽 끝에 있는 문자가 불일치하고, 이 문자가 패턴 내에 존재하지 않는 경우 이동거리는 패턴의 길이 만큼이 된다.




위의 예시는 문자열의 B와 패턴의 끝인R은 불일치하고 B는 WATER에 존재하지 않으므로 WATER의 길이인 5만큼 이동한 예시이다.  불일치하는 문자가 패턴에 존재하는 경우는 어떻게 될까?


문자열의 A와 패턴의 끝인 R은 불일치하지만 A는 WATER에 존재하므로 3칸을 이동하여 A의 위치를 일치시킨다. 



보이어-무어 알고리즘에서도 KMP 알고리즘처럼 패턴의 문자가 불일치할 경우 이동해야 할 위치를 데이터 전처리하여 저장한다.

패턴과 불일치하는 문자가 W일 경우는 패턴을 4칸 이동, A일 경우 3칸이동 W, A, T, E, R 외의 모든 문자는 5칸을 이동하면 된다. 

보이어-무어 알고리즘 구현

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
import java.util.HashMap;
import java.util.Map;
 
public class 보이어_무어 {
    public static void main(String[] args) {
        char[] data = "a pattern matching algorithm".toCharArray();
        char[] pattern = "rithm".toCharArray();
        Map<Character, Integer> failIndex = new HashMap<>();
        failIndex.put('r', 4);
        failIndex.put('i', 3);
        failIndex.put('t', 2);
        failIndex.put('h', 1);
        failIndex.put('m', 0);
        System.out.println(solution(data, pattern, failIndex));
    }
    
    public static int solution(char[] data, char[] pattern, Map<Character, Integer> failIndex) {
        
        int patternIndex = pattern.length-1;
        
        for(int i=0; i<data.length-pattern.length+1; i=i+patternIndex) {
            boolean match = true;
            for(int j=pattern.length-1; j>=0; j--) {
                if(data[i+j] != pattern[j] ) {
                    char failChar = data[i+j];
                    Integer index = failIndex.get(failChar);
                    if(index == null) {
                        patternIndex = pattern.length;
                    } else {
                        patternIndex  = index;
                    }
                    match = false;
                    break;
                }
            }
            
            if(match) {
                return i;
            }
        }
        return -1;
    }
}
 
cs


저작자표시

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

Stack(2) - DP(동적 계획법), DFS(깊이우선탐색)  (0) 2019.03.23
Stack(1) - 스택과 memorization  (0) 2019.03.19
Sort(정렬)에 대해서 - Selection Sort  (0) 2019.02.09
검색  (0) 2019.02.09
부분 집합 문제  (0) 2019.02.09

이번 포스팅에서는 컴퓨터에서 문자를 표현하는 방법에 대해 알아보겠습니다.


컴퓨터에서 문자를 저장하는 방법

컴퓨터에서는 숫자만 저장할 수 있기 때문에 문자 'A' 를 숫자로 변환하여 저장합니다. 영어 알파벳을 예로들면, a~Z까지 52개가 존재하는데 이는 6비트를 조합하면(64개) 모두 표현이 가능합니다. 000001 = 'a' 라고 규칙을 정해놓는 셈입니다. 


하지만 전세계적으로 네트워크가 발달하여 각 나라에서 사용하는 코드체계가 달라 서로 소통하기가 어렵고 6비트만으로는 전세계의 언어를 표현할 수가 없었습니다.  예를 들어 미국에서 000001 = 'a' 이지만 한국에서는 000001이 = 'ㄱ' 으로 사용했었다면 같은 비트더라도 해석하는 방법이 다르기 때문에 어려움이 있었습니다. 


이러한 문제를 해결하기위한 코드체계 표준안을 만들게 되었습니다.


ASCII (American Standard Code For Information Interchange)

아스키는 문자 인코딩 표준으로 7bit 인코딩으로 128문자를 표현하는 코드체계입니다. 33개의 출력 불가능한 제어 문자들과 공백을 비롯한 95개의 출력 가능한 문자들로 이루어져 있습니다. 아래에서는 정수, 16진수, 8진수, 문자형으로 표현한 아스키코드표입니다. 



확장 아스키

표준 문자 이외의 악센트 문자, 도형 문자, 특수 문자, 특수 기호 등 부가적인 문자 128개를 더 추가할 수 있게하는 부호. 하지만 부가적인 문자는 컴퓨터 생산자나 소프트웨어 개발자에 의해 할당되므로 서로 다른 생산자, 개발자끼리는 공용으로 사용할 수 없습니다.


유니코드

아스키는 알파벳을 기준으로 만들어진 코드체계이고 전 세계의 다양한 언어를 표현하지 못합니다. 이러한 다국어 처리를 위한 표준이 유니코드입니다.



유니코드는 다시 Character-Set에 따라 UCS-2(Universal Character Set 2), UCS-4(Universal Character Set 4)로 구분됩니다. 이는 유니코드를 저장하는 변수의 크기를 정의하는데 문자(파일)을 인식할 때 UCS-2인지, UCS-4인지 구분해서 구현해야 하는 문제가 생겼습니다. 이러한 문제를 해결하기위해 변수 크기에 따라 표준안을 만들게 되었습니다. 


유니코드 인코딩

UTF-8 (in web) - 한 문자를 표현하는데 최소 1바이트 ~ 최대 4바이트를 사용합니다.
UTF-16(in windows, java) - 한 문자를 표현하는데 최소 2바이트 ~ 최대 4바이트를 사용합니다.
UTF-32(int unix) - 한 문자를 표현하는데 최소,최대 4바이트를 사용.



저작자표시

'CS > 개발지식' 카테고리의 다른 글

base64 인코딩/디코딩 원리  (0) 2017.04.04
OOP  (0) 2017.03.21
프로세스와 쓰레드의 차이점  (0) 2017.03.20
Runnable 과Thread의 차이  (0) 2017.03.19

선택 정렬 

주어진 자료중 가장 작은 값의 원소부터 차례대로 선택하여 위치를 교환하는 방식입니다. 저장되어 있는 자료를 전체 정렬한 뒤에 k 번째의 원소를 가져오는 것과는 차이가 있는 것 같습니다.

  1. 주어진 리스트 중에서 최소값을 찾습니다.
  2. 그 값을 리스트의 맨 앞에 위치한 값과 교환합니다.
  3. 맨 처음 위치를 제외한 나머지 리스트를 대상으로 위의 작업을 반복합니다.


{64, 25, 10, 22, 11}을 선택 정렬하는 과정

1. 리스트에서 최소값을 찾습니다. 현재 시작위치는 64이고 최소값은 10입니다.

64 

25 

10 

22 

11 


2. 리스트의 맨 앞에 위치한 값과 교환합니다. 10은 정렬이 완료되었습니다.

10 

25 

64 

22 

11 


3. 아직 정렬되지 않은 리스트에서 최소값을 찾습니다. 현재 위치는 25이고 10을 제외한 최소값은 11입니다. 

10 

25 

64 

22 

11 


4. 아직 정렬되지 않은 리스트의 맨 앞에 위치한 값과 교환합니다. 10과 11은 정렬이 완료되었습니다.

10 

11 

64 

22 

25 


5. 위의 작업을 반복합니다..



Selection 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
 
public class 선택정렬 {
    public static void main(String[] args) {
        int[] arr = {64, 25, 10, 22, 11};
        int[] sortedArr = selectionSort(arr);
        
        for(int i=0; i<sortedArr.length; i++) {
            System.out.printf(sortedArr[i]+" ");
        }
    }
    
    private static int[] selectionSort(int[] arr) {
        for(int i=0; i<arr.length-1; i++) {
            int min = i;
            for(int j=i+1; j<arr.length; j++) {
                if(arr[j] < arr[min]) {
                    min = j;
                }
            }
            int temp = arr[i];
            arr[i] = arr[min];
            arr[min] = temp;
        }
        return arr;
    }
}
 
cs


저작자표시

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

Stack(1) - 스택과 memorization  (0) 2019.03.19
문자열 (String)  (0) 2019.02.16
검색  (0) 2019.02.09
부분 집합 문제  (0) 2019.02.09
2차원 배열  (0) 2019.02.03

검색

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

검색의 종류

순차 검색

일렬로 되어 있는 자료를 순서대로 검색하는 방법입니다. 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

이번 포스팅에서는 JPA에서 식별자를 생성하는 방식에 대하여 알아보도록 하겠습니다. 식별자 생성 방식에는 애플리케이션에서 직접 생성하는 방식(특별한 식별자 규칙이 있는 경우)과 JPA 에서 생성하는 방식이 있습니다. JPA가 식별자를 생성하는 방식은 다시 식별 칼럼 방식, 시퀀스 방식, 테이블 방식이 있습니다.


JPA에서 식별자를 생성하는 방식


식별 칼럼 방식

JPA가 식별 칼럼을 이용해서 식별자를 생성하려면 @Id 애노테이션 대상에 추가적인 설정이 필요합니다. @GeneratedValue 애노테이션을 추가하고 strategy 값을 설정하면 됩니다.
@Entity
@Table(name="hotel_review")
public class Review {
    @Id
    @GeneratedValue(strategy=GenerationType.IDENTITY)
    private Long id;
}


GenerationType.IENDTITY 는 식별자 생성을 데이터베이스의 식별자 생성 방식을 사용하여 식별자를 생성하는 방법입니다. 데이터베이스에서 기본키(식별자)를 auto_increment로 생성한다면 이에 의존하여 엔티티의 식별자를 생성하는 것이죠. 


사실 데이터베이스의 식별 칼럼이라는 것을 잘 모르겠어서 아래에서 정리할 "시퀀스 방식"과 큰 차이점을 모르겠네요.. 글을 읽으신 선배님이 계시다면 가르침 부탁드립니다 ㅠㅠ 


시퀀스[각주:1] 방식

@SequenceGenerator 애노테이션을 이용하면 데이터베이스의 시퀀스를 이용하여 식별자를 생성할 수 있습니다. 

    @Id
    @SequenceGenerator(
        name = "review_seq_gen",
        sequenceName = "hotel_review_seq",
        allocationSize = 1
    )
    @GeneratedValue(generator="review_seq_gen")
    private Long id;



@SequenceGenerator의 name으로 설정한 값은 @GeneratorValue 애노테이션에서 generator로 사용됩니다. sequenceName으로 설정한 값은 실제 데이터베이스의 시퀀스이며, allocationSize는 시퀀스 증가값을 설정합니다. 참고로 allocationSize의 기본값은 50인데 1로 사용해야 별탈없이 사용이 가능한데 다음에 기회가 된다면 정리하도록 하겠습니다.


시퀀스 방식을 사용하는 경우는 persist() 시점에 insert 쿼리를 실행하지 않고 시퀀스 관련 쿼리만 실행하여 식별자를 생성합니다.


1
2
3
transaction.begin();
Review review = new Review("KR-S-01", 5, "최고입니다", new Date());
entityManager.persist(review); // select hotel_review_seq.nextval from dual 
cs



테이블 방식

식별자를 구분하기 위해 사용할 주요키 칼럼과 다음 식별자로 사용할 숫자를 보관할 컬럼을 가지는 테이블을 이용하는 방법입니다. 아래의 id_gen 테이블은 entity 컬럼에서 엔티티를 구분하기위한 용도로 사용되고 nextid 컬럼은 해당 엔티티의 다음 식별자로 사용된다.


1
2
3
4
create table id_gen(
    entity varchar(100) not null primary key,
    nextid int
) engine innodb character set utf8;
cs


그럼 테이블 방식으로 엔티티의 식별자를 생성해보도록 하겠습니다. 


1
2
3
4
5
6
7
8
9
10
11
12
13
@Entity
public class City {
    @Id
    @TableGenerator(name = "idgen",
        table = "id_gen",
        pkColumnName = "entity",
        pkColumnValue = "city",
        valueColumnName = "nextid",
        initialValue = 0,
        allocationSize = 1)
    @GeneratedValue(generator = "idgen")
    private Long id;
}
cs


  • name : 테이블 생성기의 이름을 지정합니다. @GeneratedValue의 generator 속성값으로 사용됩니다.
  • table: 식별자를 생성할 때 사용할 테이블을 지정합니다.
  • pkColumnName: 식별자 생성용 테이블의 주요키 칼럼을 지정합니다.
  • pkColumnValue: 주요키 칼럼에 사용할 값을 지정합니다. 각 @TableGenerator마다 다른 값을 사용해야하며 보통 엔티티 클래스의 이름을 사용합니다.
  • valueColumnName: 생성할 식별자를 갖는 칼럼을 지정합니다.
  • initialValue: 식별자의 초기값을 지정합니다. 
  • allocationSize: 식별자를 해당값만큼 증가시킵니다. 이 값 역시 1로 설정해야 합니다.


1
2
3
4
5
6
7
8
9
10
11
transaction.begin();
 
City city = new City("서울");
entityManager.persist(city);
 
transaction.commit();
 
 
//select tbl.nextid from id_gen tbl where tbl.entity='city' for update
//insert into id_gen (entity, nextid) values ('city', 1) // 레코드가 존재하지 않을 때 식별자 테이블에 insert, 이미 식별자가 존재하는 경우는 쿼리 
//update id_gen set nextid=2 where nextid=1 and entity='city'
cs



위의 코드는 persist() 메서드를 실행하는 시점에 식별자 테이블에서 식별자를 구하고 다음에 식별자로 사용할 값을 업데이트하는 것을 확인할 수 있습니다.

  1. 순차적으로 증가하여 유일한 값을 생성해주는 객체 [본문으로]
저작자표시

'웹 개발 > JPA 프로그래밍' 카테고리의 다른 글

EntityManager 와 영속 컨텍스트  (0) 2019.03.03
@Embeddable  (0) 2019.02.19
엔티티(Entity)와 엔티티매니저(EntityManager)  (0) 2019.01.01
JPA란  (0) 2018.12.29

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

+ Recent posts

티스토리툴바