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;
}
출처 : 자료구조와 함께 배우는 알고리즘 입문 자바편
'책 > Do it! 자료구조와 함께 배우는 알고리즘 입문 자바편' 카테고리의 다른 글
09. 리스트,10. 트리,11. 해시 (0) | 2020.09.17 |
---|---|
06. 정렬 (0) | 2020.08.30 |
04. 스택과 큐 05. 재귀 알고리즘 (0) | 2020.08.27 |
03. 검색 (0) | 2020.08.25 |
02. 기본자료구조 (0) | 2020.08.23 |