문자열

hashCode() hashCode()는 객체, 즉 Object에 정의되어 있다. hashCode()는 객체의 주소 값을 변환하여 생성한 고유한 정수 값이다. 만약 같은 객체를 참조하고 있다면 hashCode 값은 동일하게 나온다. 예시로, 다음과 같이 작성하여 출력해보면 정수값을 확인해볼 수 있다. class Person { } public class Test { public static void main(String[] args) { System.out.println(new Person().hashCode()); // ex) 798154996 } } Java의 모든 객체의 최상위 부모는 Object이므로 hashCode() 메서드를 Override하여 재정의할 수 있다. equals()와 hashCo..

보이어-무어 알고리즘(Boyer-Moore Algorithm) 보이어-무어 알고리즘은 문자열 검색에 사용되는 알고리즘이다. 보이어-무어 알고리즘은 일반적인 상황에서 문자열은 앞부분보다 뒷부분에서 불일치가 일어날 확률이 높다는 성질을 활용한다. 때문에 오른쪽 끝부터 비교하게 된다. 보이어 무어 알고리즘은 다음과 같이 이동할 칸의 개수를 저장해 놓은 테이블을 미리 만들어 저장해 놓는다. 오른쪽 끝과 일치하지 않는 경우 오른쪽 끝 문자가 일치하지 않는다면, 패턴에 해당 문자가 존재하는지 검사한다. 만약 패턴에 존재하지 않는다면, 패턴의 길이만큼 패턴을 이동시킨다. 만약 패턴에 존재한다면, 패턴의 오른쪽 끝에서부터 그 문자까지의 칸 수를 세서, 해당 칸수만큼 이동시킨다. 오른쪽 끝과 일치하는 경우 오른쪽 끝 문..

트라이 트리(Trie Tree)? 트라이 트리는 문자열 검색을 빠르게 해주는 트리 형태의 자료구조이다. radix tree, prefix tree, retireval tree 라고도 한다. 여기서 트라이(Trie)는 retireval에서 따온 단어이다. 구현 위 그래프 처럼 car, cb, do, dog라는 단어를 저장한다고 가정한다. 먼저 노드를 하나 만들어 주어야 한다. import java.util.HashMap; import java.util.Map; public class Node { private final Map children; private boolean endOfWord; public Node() { children = new HashMap(); } public Map getChildr..