알고리즘) 코딩(1)

 

 

 

x.c = c;가 필요한 이유는 새로 만든 노드에 '어떤 문자를 담당하는 노드인지' 이름을 붙여주는 과정이기 때문입니다.

 

데이터 저장: 방금 new Node()로 만든 노드는 비어있는 상태입니다. 여기에 현재 처리 중인 문자 c를 저장해두지 않으면, 나중에 get이나 다른 put을 할 때 이 노드가 어떤 알파벳을 의미하는 노드인지 알 방법이 없습니다.

 

 

 

제안 구조가 안 되는 이유

else { // 문자가 일치할 때 (c == x.c)
    x.mid = put(x.mid, key, val, d+1); // 무조건 d+1을 해서 다음 노드로 보냄
}

if(d == key.length()) { ... } // 여기서 값을 저장하려고 하면 이미 늦음

• 문제점: 만약 key가 "CAT"이고 현재 d가 2(마지막 글자 'T')라면, else 블록에서 d+1을 해서 put(..., 3)을 호출해버립니다.
• 그러면 key.charAt(3)을 호출하는 순간 인덱스 초과 에러가 납니다.
• 즉, TST는 마지막 글자에 해당하는 노드에 도착했을 때 그곳에 값을 딱! 저장하고 멈춰야 합니다. mid로 더 내려가면 안 됩니다.

 

 

 

 

왜 length() - 1 인가? (에러 방지)

코드의 첫 줄을 보세요:
char c = key.charAt(d);

• 만약 key가 "CAT"이라면 길이는 3입니다. (인덱스는 0, 1, 2)
• 만약 d == 3 (즉 d == length)인 상태로 함수가 호출되면, key.charAt(3)을 실행하려는 순간 **IndexOutOfBoundsException(인덱스 초과 에러)**이 발생하며 프로그램이 멈춥니다.
• 따라서 d는 반드시 0부터 2까지만 움직여야 합니다.

 

 

 

 

 

• 왼쪽(left) 길로 가서 작업했나요? -> 그래도 이 현재 노드 x를 리턴해야 합니다.
• 오른쪽(right) 길로 가서 작업했나요? -> 그래도 이 현재 노드 x를 리턴해야 합니다.
• 중간(mid) 길로 가서 작업했나요? -> 그래도 이 현재 노드 x를 리턴해야 합니다.

어느 가지(Branch)를 탔든 상관없이, **결국 부모 입장에서는 "내가 보낸 내 자식 x가 작업 다 끝내고 돌아오는 것"**을 기다리고 있습니다.

 

 

 

 

아 그니깐, 내자식들을 다 만들어주고 나서 나 자신을 리턴하기 위해서인가, ㅇㅇㅇ

 

근데 그러면, root, 혹은 제일 처음 시작 부분도 이런 할당하는 부분있을텐데, 아 어차피 그건 x.mid가 아니라 제일 왼쪽 혹은 오른쪽인가, ㄴㄴ

 

아닌가 굳이 제일 왼쪽일리는 없나 중간으,ㅣ 왼쪽 노드일수도 있으려나 ㅇㅇ

 

 

 

/put일때는 연결하고, get일때는 return get()ㅇ형태인건가ㅇㅇ

 

 

 

   if(c< x.c){

찾고자 하는 얘를 주인공으로 두니깐 덜 헷갈리는듯

 

 

 

 

 

root = put(root, ...)

root null이어도 put연산은 없을때 노드를 만들어주니깐 

root참조할때 문제 안생김 

 

 

 

 

dfa할때

두개의 포인터가 있음(그래야 멈추는 조건이 되니까 ㄴ) 

 

 

//j가 인덱스니깐, j<=M일 경우는 없긴한데 

 

 

 

 

 

appleapple이면 apple일떄, 이러면 두번째 a가 리턴되는거 아닌가 j가 덮어씌워지니깐

ㄴㄴㄴ

apple다 찾으면 j=5가 되서 

j<M false됨 

 

 

 

 

 

 

 

 

이미 i++가 한 번 더 실행된 상태에서 루프가 종료되기 때문에, -1을 더 해줄 필요 없이 딱 i - M을 하면 시작 위치가 나오게 됩니다.

 

 

시작 = 끝 - 길이 + 1

우리가 보통 "마지막 위치"를 알고 있을 때 시작 위치를 구하는 공식은 이렇습니다.

• 예: 텍스트 A B C D (인덱스 0, 1, 2, 3)
• 패턴 B C D (길이 3)
• 패턴이 끝나는 인덱스: 3 ('D')
• 시작 인덱스 구하기: 3(끝) - 3(길이) + 1 = 1
• 이 공식에서는 +1이 들어갑니다.

 

 

 

 

1. 패턴을 찾아서 끝난 경우 (j == M): 이때 i는 N보다 작을 확률이 매우 높습니다. (텍스트 중간에 패턴이 있을 테니까요.)
2. 텍스트를 다 읽어서 끝난 경우 (i == N): 이때는 패턴을 못 찾았을 확률이 높습니다.

(걍 N-M)하면 안되는 이유

 

 

 

 

브루트 폴스는 j가 안쪽 반복문 

 

 

 

 

            if (j == M) return i; // pattern이 시작되는 text의 위치 j++이라서 j==M-1이 아니고?

반복문의 어느위치인지 

 

 

자바나 C 같은 언어의 for 루프에서 **"모든 요소를 다 돌았다"**는 것을 체크할 때는 항상 index == length 인지를 확인하는 것이 표준적인 방법입니다

 

 

1차이 

 

최대인덱스일떄 멈추면 안되기때문에 key.length일떄 에러 나지말라고 멈추라는건가,

d==key.length()

트라이 방식은 문자는 길에 있기때문에 한번 더 가는거 

 

tst

종료 조건 (d < key.length() - 1인 동안 mid로 이동)

 

 

 

 

 

 

"put처럼 할당 방식(x.next[c] = delete(...))인 이유"

이게 삭제 로직의 핵심입니다.

• get은 데이터를 읽기만 하므로 연결을 수정할 필요가 없어 return get(...)만 하면 됩니다.
• 하지만 delete는 put처럼 트리의 구조를 바꿀 수 있습니다.

 

 

 

           char c=key.charAt(d);
            x.next[c]=delete(x.next[c],key,d+1); 근데 이부분에서 x.next[c]가 첫번째 매개변수인 이유가 뭐지 x의 역할이 뭐지 현재 노드인가, ㅇㅇㅇ