알고리즘 공부 방향성 # 💡 Summary # [ 목적 ] 코딩테스트 더 효율적인 코드 구현 능력 향상 : “왜?”에 집중하여 학습하자 Snippet 만들기 : 깃허브 기스트 [ 기본서 ] 파이썬 알고리즘 인터뷰 [ 언어 ] 파이썬 [ 문제풀이 플랫폼 ] LeetCode 방향성 # 나의 1차적 목적은 코딩테스트이다. 하지만 더 멀게는 효율적인 코드 구현 능력 향상을 목적으로하며 “왜?”에 집중하여 학습하고자 한다. 전체적으로 파이썬 알고리즘 인터뷰 책을 따라 학습하며 ...
[ LeetCode #234 ] Palindrome Linked List 팰린드롬 연결 리스트 # [ LeetCode #234 ] Palindrome Linked List 바로가기 # 💡 유용한 지식 # 러너 기법 연결 리스트를 순회할 때 2개의 포인터를 동시에 사용하는 기법 빠른 러너와 느린 러너를 생성하여 병합 지점이나 중간 위치, 길이 등을 판별할 때 유용 빠른 러너가 연결 리스트의 끝에 도달하면 느린 러너는 연결 리스트의 중간 지점을 가리키게 되어 중간 위치를 찾아내면 값 비교하거나 뒤집기를 시도하는 등 다각도로 활용이 가능 ## runner 기법 # - fast, slow 는 모두 Linked List # - fast 에 값이 있다면 길이가 홀수인 경우이므로 한칸 더 전진시킨다. ...
[ LeetCode #1 ] Two Sum 두 수의 합 # [ LeetCode #1 ] Two Sum 바로가기 # 💡 유용한 지식 # index() 함수 start, end 인자 ## index()함수 인자 # - start, end ; (optional)조회하려는 리스트 시작과 끝 인덱스 index(value, start, end) Dictionary 의 조회는 O(1) 키/값 구조로 이루어져 있으며 입력 순서가 유지(버전 3.7이상)되며 내부적으로는 해시 테이블로 구현되어 있다. 다양한 타입을 키로 지원하면서도 입력과 조회 모두 분할 상환 분석에 따른 시간 복잡도는 O(1)로 가능하다. ...
[ LeetCode #5 ] Longest Palindrome Substring 가장 긴 팰린드롬 부분 문자열 # [ LeetCode #5 ] Longest Palindromic Substring 바로가기 # 💡 유용한 지식 # max() 함수 key 활용 max( result, two_pointer(i, i+1), two_pointer(i, i+2), key = len) 투포인터 좁히는 방향이 아닌 확장하며 탐색 def two_pointer(left, right): while left >= 0 and right < len(s) and s[left] == s[right]: left -= 1 right += 1 return s[left+1:right] 문제 # Given a string s, return the longest palindromic substring in s. ...
[ LeetCode #49 ] Group Anagrams 그룹 애너그램 # [ LeetCode #49 ] Group Anagrams 바로가기 # 💡 유용한 지식 # Dictionary defaultdict 객체 존재하지 않는 키를 조회할 경우 에러 메시지 대신 디폴트 값을 기준으로 키에 대한 딕셔너리 아이템을 생성해줌 # defaultdict() 사용으로 불필요한 if 연산 제거 from collections import defaultdict groups = defaultdict(list) 문제 # Given an array of strings strs, group the anagrams together. ...
[ LeetCode #819 ] Most Common Word 가장 흔한 단어 # [ LeetCode #819 ] Most Common Word 바로가기 # 💡 유용한 지식 # Dictionary TIPS! # 빈도 세기 from collections import Counter count_dict = Counter(re.sub('[^a-z0-9]',' ',paragraph.lower()).split()) # key 삭제 for word in banned: del count_dict[word] # 가장 높은 빈도 추출 : most_common() # - (0)이 아닌 (1) 이 가장 높은 빈도 # - return = (key,value) count_dict. ...
[ LeetCode #937 ] Reorder Log Files 로그 파일 재정렬 # [ LeetCode #937 ] Reorder Log Files 바로가기 # 💡 유용한 지식 # 리스트 정렬 # 리스트 정렬 index 반환 index = sorted(range(len(s)), key = lambda x : s[x]) s = [s[i] for i in index] # string split list로 sort s.sort(key = lambda x: (x.split(' ')[1:], x.split(' ')[0])) # 함수를 이용한 sorting def fn(s): return s[0], s[-1] sorted(a, key=fn) sorted(a, key=len) 문제 # You are given an array of logs. ...
[ LeetCode #344 ] Reverse String 문자열 뒤집기 # [ LeetCode #344 ] Reverse String 바로가기 # 💡 유용한 지식 # 리스트 역순으로 정렬 # reverse() 함수 활용 s.reverse() # 슬라이싱 방법 활용 s = s[::-1] s[:] = s[::-1] # 투포인터를 활용하는 방법도 있다. def reverseString(s): left, right = 0, len(s)-1 while left < right: s[left], s[right] = s[right], s[left] left += 1 right -= 1 return s 문제 # Write a function that reverses a string. ...
[ LeetCode #125 ] Valid Palindrom 유효한 팰린드롬 # [ LeetCode #125 ] Valid Palindrome 바로가기 # 💡 유용한 지식 # ‘팰린드롬’ 이란? 앞뒤가 똑같은 단어나 문장으로, 뒤집어도 같은말이 되는 단어 또는 문장 리스트 pop(0) 과 데크 popleft() 리스트 pop(0) 이 O(n) 인데 반해 deque popleft() 가 O(1) 이기 때문에 n번씩 반복하면 리스트는 O(n2), deque 구현은 O(n)으로 성능 차이가 크다. 문자열 슬라이싱 ...