딥러닝 공부방

이 포스팅은 파이썬 알고리즘 인터뷰를 공부하면서 정리한 내용입니다. 출처 : 파이썬 알고리즘 인터뷰 코드 출처 : 파이썬 알고리즘 인터뷰 깃허브 13. 팰린드롬 연결 리스트 리트코드 234. Palindrome Linked List 문제입니다. 풀이 문제 난이도는 easy 이지만, 연결 리스트에 대한 이해도가 부족하면 풀이 방법을 떠올리기 어렵습니다. 책에서는 두 가지 풀이방법을 제시합니다. 첫 번째는 연결 리스트를 리스트로 바꿔서 펠린드롬을 확인하는 풀이입니다. 두 번째는 연결 리스트의 중앙값을 기준으로 역순 연결 리스트를 만들고 값을 비교하는 풀이입니다. # 1. 리스트 변환 def isPalindrome(self, head): q = collections.deque() node = head whil..

이 포스팅은 파이썬 알고리즘 인터뷰를 공부하면서 정리한 내용입니다. 출처 : 파이썬 알고리즘 인터뷰 코드 출처 : 파이썬 알고리즘 인터뷰 깃허브 12. 주식을 사고팔기 가장 좋은 시점 리트코드 121. Best Time to Buy and Sell Stock 문제입니다. leetcode.com/problems/best-time-to-buy-and-sell-stock/ 풀이 price의 최소값을 계속 갱신하면서, 가격 차이를 계산하여 차이가 클 경우 최대값을 저장하는 풀이입니다. def maxProfit(self, prices): profit = 0 min_price = sys.maxsize # 최소값과 최댓값을 계속 생신 for price in prices: min_price = min(min_price..

이 포스팅은 파이썬 알고리즘 인터뷰를 공부하면서 정리한 내용입니다. 출처 : 파이썬 알고리즘 인터뷰 코드 출처 : 파이썬 알고리즘 인터뷰 깃허브 11. 자신을 제외한 배열의 곱 리트코드 238. Product of Array Except Self 문제입니다. leetcode.com/problems/product-of-array-except-self/ 풀이 모든 nums 값을 곱한 다음에 nums[i]로 나눠주는 풀이를 떠올렸지만, 나눗셈을 하지 않는 제약조건이 있어서 다른 방법을 생각해야 했습니다. 도저히 생각이 안나서 책에 있는 풀이를 참고했습니다. 책에는 왼쪽 곱셈 결과에 오른쪽 곱셈 결과를 곱하는 풀이방법이 나와있었습니다. def productExceptSelf(self, nums): p = 1 o..

이 포스팅은 파이썬 알고리즘 인터뷰를 공부하면서 정리한 내용입니다. 출처 : 파이썬 알고리즘 인터뷰 코드 출처 : 파이썬 알고리즘 인터뷰 깃허브 10. 배열 파티션 I 리트코드 561번 문제입니다. leetcode.com/problems/array-partition-i/ 풀이 nums를 정렬하고 for문으로 짝수 index를 가져옵니다. 해당 index와 다음 index의 값중 최소값을 results에 추가한 뒤 모든 값을 더해서 return 합니다. def arrayPairSum(self, nums): nums.sort() results = [] for i in range(0,len(nums),2): results.append(min(nums[i],nums[i+1])) return sum(results..

이 포스팅은 파이썬 알고리즘 인터뷰를 공부하면서 정리한 내용입니다. 출처 : 파이썬 알고리즘 인터뷰 코드 출처 : 파이썬 알고리즘 인터뷰 깃허브 9. 세 수의 합 리트코드 15번 문제입니다. leetcode.com/problems/3sum/ 풀이 책에서는 브루트포스, 투 포인터 풀이가 나와있습니다. 핵심은 중복된 값을 건너뛰기를 구현하는 것입니다. 1. 브루트 포스 풀이 def threeSum(nums): result = [] for i in range(len(nums)-2): # 중복된 값 건너 뛰기 if i > 0 and nums[i] == nums[i-1]: continue for j in range(i+1,len(nums)-1): if j > 0 and nums[j] == nums[j-1]: co..

이 포스팅은 파이썬 알고리즘 인터뷰를 공부하면서 정리한 내용입니다. 출처 : 파이썬 알고리즘 인터뷰 코드 출처 : 파이썬 알고리즘 인터뷰 깃허브 8. 빗물 트래핑 리트코드 42번 문제입니다. leetcode.com/problems/trapping-rain-water/ 풀이 hard 문제답게 손도 못대보았습니다. 책에는 두 가지 풀이법이 제시되었습니다. 1. 투포인터를 활용한 풀이 양쪽의 포인터가 제일 높은 높이를 향해서 한 칸씩 이동합니다. 이동하면서 이전 값과 현재 값의 차이로 물의 양을 계산합니다. def trap(self, height): if not height: return 0 left, right = 0, len(height)-1 left_max, right_max = height[left],..

이 포스팅은 파이썬 알고리즘 인터뷰를 공부하면서 정리한 내용입니다. 출처 : 파이썬 알고리즘 인터뷰 코드 출처 : 파이썬 알고리즘 인터뷰 깃허브 6. 가장 긴 팰린드롬 부분 문자열 리트코드 5번 문제입니다. leetcode.com/problems/longest-palindromic-substring/ 풀이 팰린드롬은 홀수, 짝수 펠린드롬으로 나눠서 생각해 볼 수 있습니다. 책에서는 홀수, 짝수 펠린드롬을 각각 판별하도록 풀어냈습니다. 펠린드롬을 판별하는 함수를 정의하고 홀수, 짝수 펠린드롬을 문자열 처음부터 판별해나갑니다. max 함수에 key 인자를 len으로 입력하여 문자열 길이를 기준으로 최대값을 취할 수 있다는 것을 배웠습니다. def longestPalindrome(self, s): # 팰린드롬..

이 포스팅은 파이썬 알고리즘 인터뷰를 공부하면서 정리한 내용입니다. 출처 : 파이썬 알고리즘 인터뷰 5. 그룹 애너그램 리트코드 49번 문제입니다. leetcode.com/problems/group-anagrams/ 풀이 dictionary의 키에 정렬된 strs 입력하고 값을 정렬되지 않은 strs 입력한다는게 신선했습니다. sorted 함수는 list 값을 반환하므로 딕셔너리의 key로 지정할 수 없습니다. 따라서 join 함수로 리스트를 제거하여 key로 입력합니다. def groupAnagrams(self, strs): anagrams = collections.defaultdict(list) for word in strs: # list 벗기기 위해 .join 이용 anagrams[''.join(s..

이 포스팅은 파이썬 알고리즘 인터뷰를 공부하면서 정리한 내용입니다. 출처 : 파이썬 알고리즘 인터뷰 4. 가장 흔한 단어 리트코드 819번 문제입니다. leetcode.com/problems/most-common-word/ 풀이 paragraph를 전처리 하는 과정이 핵심이었습니다. banned에 해당하는 문자와 특수기호, 띄어쓰기를 제거해야 합니다. 파이썬 리스트컴프리헨션을 이용해 한줄로 전처리하는 코드가 인상깊었습니다. def mostCommonWord(self, paragraph, banned): words = [word for word in re.sub(r'[^\w]',' ',paragraph) .lower().split() if word not in banned] counts = collecti..

이 포스팅은 파이썬 알고리즘 인터뷰를 공부하면서 정리한 내용입니다. 출처 : 파이썬 알고리즘 인터뷰 3. 로그 파일 재정렬 리트코드 937번 문제입니다. 풀이 sort함수 key인자에 lambda를 활용하여 [1] 인덱스 기준으로 정렬하고 값이 동일하면 [0] 인덱스로 정렬하도록 하는 것이 핵심이었습니다. def reorderLogFiles(self, logs): digits, letters = [], [] for log in logs: if log[1].isdigit(): digits.append(log) else: letters.append(log) letters.sort(key=lambda x: (x.split()[1], x.split()[0])) return letters + digits