seoyoung.dev

[ 파이썬 알고리즘 인터뷰_알고리즘 스터디 리뷰 ] * 해시 테이블(해시 맵) : 키를 값에 매핑할 수 있는 구조 - 해시 함수 : 임의의 크기의 데이터를 고정 크기의 값으로 매핑하는 데 사용할 수 있는 함수 = 해싱 : 해시 함수를 사용해 해시 테이블에 인덱싱하기 위한 것 * 동일 키 값 - 충돌 발생 1. Separate Chaining : 연결 리스트로 연결 2. Open Addressing : 충돌 발생 시, 테이블 공간 내 탐사를 통해 빈 공간을 찾아 해결한다. ex) 빈도 요소 순에서 상위 k 번째 요소 import collections nums = [1,1,1,2,2,3] k = 2 count = collections.Counter(nums) print(count) print( list(zi..

[ 파이썬 알고리즘 인터뷰_알고리즘 스터디 리뷰 ] * 데크(deque) - 앞, 뒤 양쪽 방향에서 element 를 추가하거나 제거할 수 있다. - 양 끝 element 접근하여 삽입 또는 제거 시, O(n) 이 소요되는 리스트에 반해, O(1) 로 접근 가능 from collections import deque deq = deque() deq.append(10) deq.appendleft(0) deq.pop() deq.popleft() deq.remove(10) from collections import deque deq = deque([1,2,3,4,5]) deq.rotate(1) # [5,1,2,3,4] deq.rotate(-1) # [1,2,3,4,5] * 우선순위 큐 -> 대부분의 우선순위 큐..

[ 파이썬 알고리즘 인터뷰_알고리즘 스터디 리뷰 ] * 괄호 문제 - 열린 괄호면 stack 에 넣기 - 닫힌 괄호 만나면 해당 괄호의 열린 괄호가 stack 에 있는지 확인 - 마지막에 stack 에 열린 괄호가 있다면 짝이 맞지 않는 것 stack = [] table = { ')':'(', ']':'['. '}':'{', } for char in s: if char not in table: stack.append(char) elif not stack or table[char] != stack.pop(): return False return len(stack) == 0 * 빗물 트래킹 / 온도 / 주식 등등 - 더 낮은 or 더 높은 값 나올때까지 각 요소들은 얼마나 기다리거나 걸리는지 -> stack..

[ 파이썬 알고리즘 인터뷰_알고리즘 스터디 리뷰 ] * 팰린드롬 판별 -> deque 활용 ( 리스트 에서 pop(0) 과 pop() 으로 비교할 경우, pop 연산을 할 때마다 값들이 shift 되기 때문에 O(n) 소요 ) - 이중 연결 리스트 구조의 deque 를 사용하면, popleft() 와 pop() 을 비교하는 연산 수행 시 O(1) 소요된다. from collections import deque deq = deque() while len(deq)>1: if deq.popleft() != deq.pop(): return False * 연산자 우선순위 - and 연산자가 or 보다 우선순위 높다. - 슬라이싱 > 배열 >..지수 > 비트연산 not : 우선순위가 꽤 높은 연산자들 - 이런거 헷..

[ 파이썬 알고리즘 인터뷰_알고리즘 스터디 리뷰 ] * 리스트 -> 숫자와 인덱스 둘 다 사용할 경우, enumerate 활용 + nums[i] : 인덱스 로 숫자 접근 + nums.index(n) : 숫자 로 인덱스 접근 * 브루트 포스 -> in 과 해시테이블로 시간 단축 - 딕셔너리로 해시 테이블 : key =숫자, value = 인덱스 -> target 에서 뺀 수가 딕셔너리에 있는지 확인, value 출력 # 더해서 target 이 되는 두 수의 인덱스 nums = [2,7,11,15] target = 9 nums_map = {} for i,num in enumerate(nums): if target-num in nums_map: print([nums_map[target-num],i]) nums..

[ 파이썬 알고리즘 인터뷰_알고리즘 스터디 리뷰 ] * 문자열에서 문자랑 숫자만 사용하기 1) isalnum() 으로 판별 -> bool 리턴 2) re.sub('[^a-z0-9]'),'',s) : ^은 not 을 의미 -> a-z랑 0-9 처럼 문자나 숫자가 아닌 글자는 ''로 대체 * 팰린드롬인지 판별 // 앞뒤로 똑같은 문장 1) pop(0) 이랑 pop() 비교 - 같지 않은 부분이 있으면 판단 종료 while (len(strs) > 1: if strs.pop(0) != strs.pop(): print('false') * lambda 이중조건 + sort의 정렬 기준 key 1) lambda x: ( 첫번째 조건, 두번째 조건..) + 조건 내에서 split() 하고 바로 사용하면 문장->단어->..