처음에 성공하지 못하면 시도하고 다시 시도하십시오.

미리 사과드립니다. 제목이 생각나서 이 글을 작성하게 되었습니다. 게다가 요즘 제 삶에 꽤 적용이 된 것 같아요 😂

아무리 해도! 공부를 계속하면서 시도에 대해 조금 소개하고 싶었습니다!

시도란 무엇입니까?

트리는 트리의 시간 및 공간 복잡성 문제를 해결하기 위한 비교적 새로운 컴퓨터 프로그래밍 개념입니다.

주로 알파벳 문자에 사용되며 단어나 패턴을 생성하기 위해 쉽게 순회할 수 있도록 트리와 같은 구조로 저장합니다. 트리는 알파벳의 모든 단일 문자에 대한 노드에 연결되거나 연결된 빈 루트 노드로 시작합니다.

참고: 즉, 사용 중인 알파벳에 따라 50개 이상의 서로 다른 노드가 될 수 있습니다!

노드 자체는 값과 다른 노드에 대한 하나 이상의 참조를 순서대로 보유합니다.

빅 오

시도의 시간 복잡성은 평균적으로 O(n)이며, 최악의 경우 전체 단어가 시도에 존재하고 몇 번의 순회에서 간단히 false를 반환할 수 없습니다. 그러나 최선의 경우, 아마도 하나의 문자만 검색하는 경우 시간 복잡도는 O(1)이 될 것입니다.

공간 복잡성의 경우 시도는 실제로 대부분 문자열일 뿐이며 각 문자에 대해 새 노드를 생성하는 경우에도 O(n) 공간 이상을 차지하지 않습니다. 다시 말하지만, 우리의 문자열이 단지 하나의 문자인 유사한 경우에서 그것은 최선의 경우 O(1)이 될 것입니다.

코드 예

그래서 저는 rubyguides에 실제로 멋진 예가 있다고 생각하고 모두를 위해 여기에서 복제하겠습니다. 하지만 좀 더 이해하기 쉬운 방식으로 함수를 작성하겠습니다.

먼저 값, 모든 참조를 포함하는 다음 배열, 찾고 있는 단어를 찾았거나 완성했는지 나타내는 단어 값을 갖는 노드 클래스를 초기화합니다.

class Node
  attr_reader   :value, :next
  attr_accessor :word
  def initialize(value)
    @value = value
    @word  = false
    @next  = []
  end

다음으로 몇 가지 다른 메서드가 있는 trie 클래스가 있습니다. 하나는 이미 존재하는 캐릭터를 찾거나 추가하는 트리에 캐릭터를 추가하는 것입니다. 존재하는 경우에만 문자를 찾는 또 다른 방법입니다. 그리고 마지막으로 트리에 단순히 노드를 추가하는 방법입니다.

class Trie
  def initialize
    @root = Node.new("*")
  end

  def add_character(character, trie)
    trie.each do |node|
      if node.value == character
        return node
      end
    end
    add_node(character, trie)
  end

  def find_character(character, trie)
    trie.each do |node|
      if node.value == character
        return node
      end
    end
  end

  def add_node(character, trie)
    new_node = Node.new(character)
    trie.push(new_node)
  end
end

이제 노드 및 트리 클래스를 설정했으므로 트리를 실제로 사용할 메서드를 만들 수 있습니다!

def add_word(word)
  base = @root
  word.each_char do |letter|
    base = add_character(letter, base.next)
    base.word = true
  end
end

def find_word(word)
  base = @root
  word_found =
  word.each_char.all? { |letter| base = find_character(letter, base.next) 
  }
  yield word_found, base if block_given?
  base
end

add_word 메서드는 단어를 반복하고 해당 단어를 만들기 위해 문자를 추가한다는 점에서 매우 명확합니다. find_word에 대한 두 번째 방법은 내가 찾은 것만큼 수정하지 않았습니까? 방법은 단순화하기 어려웠다. 각 문자에 대해 대소문자가 참인지 효과적으로 알아낸 다음 참을 반환합니다. 일치하는 항목을 찾으면 yield를 통해 해당 항목을 반환합니다.

자원

시도 학습에 도움이 되는 몇 가지 유용한 리소스를 찾았습니다.

Trying to Understand Tries

읽어주셔서 감사하고 모두 멋진 주말 보내세요!