DevSSOM

연습문제 : 틀린 문자 찾기 두 개의 문자열이 주어짐. 이때 두번째 문자열은 첫번째 문자열에 하나의 문자를 추가한 후, 그 순서를 랜덤하게 뒤섞은 문자. 이때 추가된 문자를 찾아봐. 예를 들어서, apple 과 azlppe 가 주어졌을 경우 추가된 문자는 z임. 추가된 문자는 하나라고 가정해도 좋음. 추가된 문자가 이미 리스트에 존재하던 문자 일 수도 있음. def findDifference(str1, str2): return '' def main(): print(findDifference("apple", "azlppe")) if __name__ == "__main__": main() >>> def findDifference(str1, str2): str1List = list(str1) str2List ..

연습문제 : 세번째로 큰 숫자 찾아내기 0보다 큰 정수들의 배열이 주어짐. 이 배열에서 세번째로 큰 수를 찾아내봐. 예를 들어서, [2, 8, 19, 37, 4, 5, 12, 50, 1, 34, 23] 가 입력으로 주어졌을 경우 가장 큰 수는 50, 두번째로 큰 수는 37, 세번째로 큰 수는 34임. 따라서 34를 반환해야함. 시간 복잡도를 고려하면서 여러가지 방법으로 문제 풀어보기. def thirdMax(nums): return 0 def main(): print(thirdMax([2, 8, 19, 37, 4, 5, 12, 50, 1, 34, 23])) # should return 34 if __name__ == "__main__": main() >>> def thirdMax(nums): nums.s..

해쉬 : 식별자(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() >..