목록해쉬 (3)
DevSSOM
해쉬 : 식별자(Key)가 있는 데이터, 시간복잡도↓(항상 O(1)) / 공간복잡도↑ 배열 : 식별자(Key)가 없는 데이터, 시간복잡도↑(O(N)) / 공간복잡도↓ 만약, 시간복잡도를 얻으려면 공간복잡도를 포기하고, 해쉬보다는 배열의 자료구조를 선택해야 효율적인 알고리즘을 짤 수 있음. 이렇게 하나를 얻기위해 하나를 포기해야 한다는 의미로 trade-off라는 말을 씀. 자료구조에서 특히 많이 쓰이는 말.
연습문제 : 애너그램 탐지 애너그램(Anagram)은 한 문자열의 문자를 재배열해서 다른 뜻을 가지는 다른 단어로 바꾸는 것을 의미함. 두 개의 문자열이 주어졌을 때, 서로가 서로의 애너그램인지 아닌지의 여부를 탐지하는 함수를 만들어봐. elice 와 leice 는 애너그램. True를 리턴해야 함. cat 과 cap 는 애너그램이 아님. False를 리턴해야 함. iamlordvoldemort 와 tommarvoloriddle 은 애너그램. True를 리턴해야 함. 문자열의 모든 문자는 영어 소문자라고 가정. def isAnagram(str1, str2): return None def main(): print(isAnagram('iamlordvoldemort', 'tommarvoloriddle')) #..
해쉬 파이썬에서의 Dictionary.key + Value의 조합. Key에 Value를 저장하는 데이터 조합. studentIds = { "이다솜" : 123, "오정철" : 145, "이주경" : 563 } # 이름이 Key, 숫자가 value 위의 코드를 보기 좋게 정리하면 아래의 표. "이다솜" 123 "오정철" 145 "이주경" 563 ... ... 이때 해쉬 자료구조에서 가장 중요한 것은 Key는 중복될 수 없다는 것. 해쉬의 시간복잡도 1. Key를 이용해서 Value 가져올 때 : 대략 O(1) print(studentIds["이다솜"]) # 크기와 상관없이 키를 입력하면 바로 나오니까 Big-O 시간복잡도 = 대략 O(1) 2. Key가 존재하는지 확인할 때 : 대략 O(1) if("이다..