코테 스터디 41일차 TIL + 오늘의 학습 키워드 트리 자료 구조

- 오늘의 학습 키워드 트리 자료구조

- 공부한 내용 본인의 언어로 정리하기

트리 자료 구조: 문자열을 효율적으로 저장하고 검색한다.

 

1. 각 노드는 문자 하나를 나타낸다.
2. 루트에서 특정 노드까지의 경로가 하나의 문자열을 형성한다.
3. 각 노드들은 자식 노드들을 가리키는 배열, 맵을 가진다.
4. 단어의 끝을 표시하는 플래그가 필요하다

수도 코드

TrieNode 클래스:
  -children: 자식 노드들을 저장하는 배열 
  -isEndOfWord: 이 노드에서 단어가 끝나는지 표시
  
Trie 클래스:
  -root: 루트 노드
  
  insert(word):
     현재 노드 = 루트
     for 각문자 in word:
       if 해당 문자의 자식이 없다면:
         새 노드 작성
         
       현재 노드 = 자식 노드로 이동
      현재 노드의 isEndOfWord = true
      
  search(word):
    현재 노드= 루트
    for 각 문자 in word:
      if 해당 문자의 자식이 없다면:
        return false
        
      현재 노드 = 자식 노드로 이동
      return 현재 노드의 isEndOfWord
      
      
  startWith(prefis)
    현재 노드 = 루트
    for 각 문자 in prefix:
      if 해당 문자의 자식이 없다면:
        return false
        
      현재 노드 = 자식 노드로 이동
      return true

- 오늘의 회고
  - 어떤 문제가 있었고, 나는 어떤 시도를 했는지

왜 접두사 검색에서 containsKey() 를 안쓰는지

 

  - 어떻게 해결했는지

 

접두사 검색은 경로의 존재여부를 확인하는 것

containsKey()는 정확한 키의 존재여부를 확인하는 것이어서 목적이 다름
  - 무엇을 새롭게 알았는지

toCharArray(): String 문자열을 char 개별 문자로 나누고 

 

char[] 배열에 차례대로 해당하는 값을 넣어서 반환

 

   
   
   String[] examples = {"가나다라", "Hello", "12345", "가B3라"};
        
        for (String example : examples) {
            System.out.println("\n입력 문자열: \"" + example + "\"");
            
            //string -> char[]
            char[] charArray = example.toCharArray(); 
            //문자열의 각 문자를 개별적으로 처리하기 위함
            //문자열이 char 배열로 분해됨

  - 내일 학습할 것은 무엇인지