문자열 검색
브루트-포스법
찾을 문자열인 ‘패턴’을 검색 문자열의 첫 요소와 차례로 비교한다. 다른 문자를 만나면 패턴을 1칸씩 옮긴 후 패턴의 처음부터 다시 검사하는 방법.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public int bfMatch(String txt, String pat)
{
int pt = 0; //txt 커서
int pp = 0; //pat 커서
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;
}
KMP법
브루트포스 방법을 개선한 방법으로 텍스트와 패턴의 겹치는 부분을 찾아내어 검사를 다시 시작할 위치를 구한다. 패턴의 이동을 최소화해 효율을 높인다.
단, KMP법은 브루트포스보다 복잡하고 Boyer-Moore과는 성능이 같거나 좋지 않아 거의 사용되지 않는다.
Boyer-Moore
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
public 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; // 모든 문자에 일단 patLen인 4만큼 skip할 수 있도록 저장
for(pt = 0; pt < patLen - 1; pt++)
skip[pat.charAt(pt)] = patLen - pt - 1; // 패턴의 문자와 일치하는 문자는 patLen - pt - 1 이때 -1은 인덱스 이기 때문
while(pt < txtLen)
{
pp = patLen - 1;
while(txt.charAt(pt) == pat.charAt(pp))
{
if(pp == 0)
return pt;
pt--;
pp--;
}
pt += (skip[txt.charAt(pt)] > patLen - pp) ? skip[txt.charAt(pt)] : patLen - pp;
}
return -1;
}
리스트
선형리스트
- 리스트는 데이터를 순서대로 나열해 놓은 자료구조를 말한다.
삽입, 삭제의 경우 모든 요소를 뒤로 밀거나 앞으로 당겨야 한다. 즉, 배열로 구현한 선형리스트는 쌓이는 데이터의 크기를 미리 알아야하고 효율이 좋지 않다.
연결리스트
- 다음 노드를 가리키는 포인터를 각 노드에 포함시키는 리스트 구조.
1
2
3
4
class Node<E>{
E data;
Node<E> next;
}
노드는 이러한 구조를 가지며 꼬리 노드는 next가 null을 참조하도록 한다.
- 생성자
1
2
3
public LinkedList(){
head = crnt = null;
}
1
2
3
4
Node(E data, Node<E> next){ // 노드 생성
this.data = data;
this.next = next;
}
연결리스트 클래스에는 Node head, Node crnt 가 존재한다. head는 머리노드를 가리키고 crnt는 현재 선택한 노드를 가리킨다.
head = null 이면 노드가 하나도 없는 비어있는 상태이다. 데이터가 1개인 경우는 head.next = null 이다. 데이터가 2개인 경우는 head.next.next = null 이다.
해당 노드가 꼬리노드인지 판단하는 방법은 p.next = null인 경우 이다.
선택 노드를 삭제하는 경우 순회해서 선택 노드를 찾고, 선택 노드를 가르키던 전 노드의 next를 선택노드의 다음 노드를 가리키도록 하면 된다.
커서를 이용한 연결리스트
next를 포인터로 가리키는 비용은 무시할 수 없다. 데이터 수가 크게 바뀌지 않고 데이터 수의 최댓값을 미리 알 수 있는 경우 배열을 사용해 효율적으로 연결리스트를 운용할 수 있다.
next를 배열의 인덱스를 가리키도록 한다.
** 배열의 비어있는 요소 처리하기. 배열을 이용할 경우 삭제한 노드를 관리해 주어야 한다. 프리리스트를 만들어 삭제한 여러 레코드를 관리하기 위해 그 순서를 저장한다.
원형 이중 연결리스트
- 원형 리스트: 꼬리노드가 머리노드를 가르키는 구조.
- 이중 연결리스트: 앞쪽의 노드를 찾지 못한다는 단점을 개선하기 위해 다음 노드에 대한 포인터와 앞쪽 노드에 대한 포인터를 저장하는 구조.
1
2
3
4
5
class Node<E>{
E data;
Node<E> prev;
Node<E> next;
}
- 원형 이중 연결 리스트: 머리 노드의 prev가 꼬리 노드를 가리키고 꼬리 노드의 next가 머리 노드를 가리키는 구조가 원형 이중 연결 리스트
원형 이중 연결 리스트에서는 삽입, 삭제를 원활하게 하기 위해 데이터를 갖지 않는 노드를 리스트의 머리에 계속 존재시킨다. 이러한 더미 노드는 prev는 자기 자신을, next도 자기 자신을 가리킨다.