NAIAHD

07-1 집합

집합이란 객관적으로 범위를 규정한 '어떤 것'의 모임이며 , 그 집합 안에서 각각의 '어떤 것'을 요소 라고 합니다.

부분집합 과 진부분집합(poper subset)

진부분집합  집합 A의 모든 요소가 집합 B의 요소이면서 집합 A와 집합 B가 같지않을 때 'A는 B의 진부분집합' 이다.

집합의 연산

합집합  AUB

교집합  A∩B

차집합  A-B

07-2 배열로 집합 만들기

배열로 집합 만들기

모든 요소가 같은 자료형으로 구성된 집합은 배열로 표현할 수 있습니다.

max: 집합의 최대 크기를 나타내는 필드입니다.

num: 집합의 요소 개수 입니다.

set: 집합을 저장할 배열입니다. 배열의 메모리 확보는 생성자에게 합니다.

요소를 검색하는 indexOf메소드 :

검색하여 검색에 성공하면 찾은 요소 n의 인덱스를 반환하고 , 실패하면 -1을 반환합니다.

요소 n이 있는지 확인하는 contains메서드

요소 n을 집합에 추가하는 add메서드

요소 n을 집합에서 삭제하는 remove메서드

다른 집합으로 복사하는 copyTo메서드

다른 집합을 복사하는 copyFrom메서드

다른 집합과 같은지 확인하는 equalTo메서드

두 집합의 합집합을 복사하는 unionOf메서드

집합을 문자열로 변환하는 toString메서드

오버라이드 : 상속받은 클래스가 부모의 메서드를 다시 정의하는 것입니다. 

08. 문자열 검색

08-1 부루트-포스법

문자열 검색이란 어떤 문자열 안데 다른 문자열이 들어있는지 조사하고 들어 있다면 그 위치를 찾아내는 것을 말합니다.

쉡게 검색할 문자열 : 패턴 

문자열 원본을 : 텍스트

브루트-포스법

선행 검색을 확장한 알고리즘으로 단순법 ,소박법이라고도 합니다.

옆으로 이동하면서 검색한다.

단점 : 이미 검사를 진행한 위치를 기억하지 못하므로 블루트-포스법의 효율은 좋지 않다고 할 수 있습니다.

static int bfMath(String txt, String pat){
	int pt = 0;
    int pp = 0;
    
    while(pt!= txt.length() && pp!= pat.length()){
    	if(txt.charAt(pt)== pat.charAt(pp)){
        	pt++;
            pp++;
        }else{
        	pt= pt-pp+1;
            pp = 0;
        }
    }
    if(pp == pat.length())
    	return pt-pp;
    return -1;
    
}

String.indexOf 문자열 검색하기

indexOf

lastIndexOf

브루트-포스법은 다른 문자를 만나면 패턴에서 문자를 검사했던 위치 결과를 버리고 다음 텍스트의 위치로 1칸 이동한 다음 다시 패턴의 첫번째 문자부터 검사합니다.

08-2 kmp법 =>브루트-포스법보다 복잡합니다.

검사했던 위치 결과를 버리지 않고 이를 효율적으로 활용하는 알고리즘입니다.

"몇 번쨰 문자부터 다시 검색할지" 에 대한값을 미리 "표"로 만들어 이 문제를 해결합니다.

static int kmpMatch(String txt, String pat){
	int pt = 1;
    int pp= 0;
    int[] skip = new int[pat.length() +1] ;
    
    skip[pt] = 0;
    while(pt != pat.length()){
    	if(pat.charAt(pt) == pat.charAt(pp))
            skip[++pt] = ++pp
        else if(pp==0)
            skip[++pt] = pp;
        else
            pp = skip[pp];
        }
    }
    
    pt = pp = 0;
    while(pt != txt.length() && pp != pat.length()){
    	if(txt.charAt(pt) == pat.charAt(pp))
            pt++;
            pp++;
        else if(pp==0)
            pt++;
        else
        	pp = skip[pp];
    }
    
    if(pp==pat.length())
    	return pt-pp;
    return -1;
}

단점 : 브루트 -포스법보다 복잡하다

Boyer-Moore법보다 성능이 같거나 좋지 않아 실제 프로그램에서는 거의 사용하지 않습니다.

08-3 Boyer-Moore법 

Boyer-Moore법 : 브루트 -포스법을 개선한 kmp법보다 효율이 더 우수하기 때문에 실제로 문자열 검색에 널리 사용하는 알고리즘입니다.

이 알고리즘은 패턴의 마지막 문자부터 앞쪽으로 검사를 진행하면서 일치하지 않는 문자가 있으면 미리 준비한 표에 따라 패턴을 옮길 크기를 정합니다.

각각의 문자를 만났을 때 패턴을 옮길 크기를 저장할 표를 미리 만들어야 합니다.

static int bmMatch(String txt, String pat){
	int pt;
    int pp;
    int txtLen = txt.length();
    int patLen = pat.length();
    int[] skip = new int[Character.MAX_VALUE +1];
    
    for(pt = 0; pt<Character.MAX_VALUE; pt++)
    	skip[pt] = patLen;
    for(pt = 0; pt<patLen-1; pt++)
    	skip[pat.charAt(pt)] = patLen - pt -1;
        
    while(pt < txtLen){
    	pp = patLen -1;
        while(txt.charAt(pt) == pat.charAt(pp){
        	if(pp==0)
            	return pt;
            pp--;
            pt--;
        }
        pt+= (skip[txt.charAt(pt)] > patLen -pp) ? skip[txt.charAt(pt)] : patLen - pp;
    }
    return -1;
}

출처 : 자료구조와 함께 배우는 알고리즘 입문 자바편