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("이다..

연습문제 : 배열의 회전 정수들이 포함되어 있는 배열과, 숫자 k가 입력으로 주어짐. 이때 해당 배열을 k 만큼 회전 시켜봐. 예를 들어서, [1, 2, 3, 4, 5, 6, 7, 8, 9] 와 4가 입력으로 주어졌을 경우 [6,7,8,9,1,2,3,4,5] 를 반환하면 됨. k 는 배열의 길이 n 보다 작다고 가정. 다양한 방법으로 풀어 볼 수 있음. (추가) 공간 복잡도 O(1)으로 풀 수 있는 방법도 생각. 이때 주어진 함수 partialReverse를 활용해도 됨. # 이 함수를 수정 해 주세요. def rotateArray(nums, k): return nums # 다음 함수는 추가적인 공간 사용 없이 배열의 일부를 뒤집어 주는 함수입니다. # 예를 들어, nums = [1,2,3,4,5] # ..

배열 가장 기본적인 자료 구조 nums = [1, 2, 3, 4, 5, 6] 배열에서 주의할 점 : 첫 번째 원소의 인덱스는 [1]이 아니라 [0]이라는 것. 배열의 공간복잡도 = O(N). 배열의 크기만큼 차지하기 때문에. 배열 인덱싱 nums[2] # nums의 3번째 원소를 뜻함 nums = [1, 2, 3, 4, 5] nums[2:5] # [2, 3, 4] # nums의 인덱스 2부터 (5-1)인 4까지. 2~4까지 해당하는 부분배열 nums = [1, 2, 3, 4, 5] nums[len(nums)-1] # 인덱스가 [4]인 마지막 원소 5 # nums의 마지막 원소 nums[-1] # 이것 또한 배열의 마지막 원소 배열의 Big-O 시간복잡도 1. 인덱스를 알 때 : O(1) 어떤 배열 num..

연습문제 : 0 이동시키기 여러 개의 0과 양의 정수들이 섞여 있는 배열이 주어짐. 이 배열에서 0들은 전부 뒤로 빼내고, 나머지 숫자들의 순서는 그대로 유지한 배열을 반환하는 함수를 만들어봐. 예를 들어서, [0, 8, 0, 37, 4, 5, 0, 50, 0, 34, 0, 0] 가 입력으로 주어졌을 경우 [8, 37, 4, 5, 50, 34, 0, 0, 0, 0, 0, 0] 을 반환하면 됨. 공간 복잡도 O(1)으로 이 문제를 풀 수 있음? def moveZerosToEnd(nums): return nums def main(): print(moveZerosToEnd([0, 8, 0, 37, 4, 5, 0, 50, 0, 34, 0, 0])) if __name__ == "__main__": main() >..

연습문제 : 중복된 수 제거하기 0보다 큰 정수들이 있는 리스트가 주어짐. 이 리스트는 작은 것부터 큰 순서대로 오름차순 정렬이 되어있으며, 중복을 포함함. 이 리스트에서 중복된 수를 없애고 정렬되어 있는 리스트를 출력해봐. 예를 들어 [1, 1, 2, 2, 2, 2, 5, 7, 7, 8] 이 입력되었다면, 중복되어 있는 ‘1’ 1개, ‘2’ 3개, ‘7’ 1개를 제거하고 [1, 2, 5, 7, 8]을 출력하면 됨. def removeDuplicate(nums): return [] def main(): print(removeDuplicate([1, 1, 2, 2, 2, 2, 5, 7, 7, 8])) # [1, 2, 5, 7, 8]을 리턴해야 합니다 if __name__ == "__main__": main..

연습문제 : 가장 큰 부분합 구하기 정수들의 리스트가 입력으로 들어옴. 이 정수들의 리스트를 일부분만 잘라내어 모두 더했을 때의 값을 부분합이라 부름. 이때 가장 큰 부분합을 구해봐. 예를 들어, [-10, -7, 5, -7, 10, 5, -2, 17, -25, 1]이 입력으로 들어왔다면 [10, 5, -2, 17]을 모두 더한 30이 정답. ※입력에는 최소 하나 이상의 양수가 존재. ※이 문제에는 여러 종류의 풀이법이 존재. 각 풀이법의 시간 복잡도를 고려하면서 여러가지 방법으로 문제를 풀어봐. def maxSubArray(nums): return 0 def main(): print(maxSubArray([-10, -7, 5, -7, 10, 5, -2, 17, -25, 1])) # 30이 리턴되어야 합..