본문 바로가기

Tech Interview8

[Python] Trie 자료구조 Trie(트라이) 자료구조는 문자열 집합에서 키를 효율적으로 저장하고 조회하는데 사용된다. 스펠 체커나 자동완성 기능에서 사용된다. 파이썬에서는 딕셔너리 자료구조를 이용해 쉽게 구현할 수 있다. insert (단어 삽입) 단어의 키(문자)가 커서에 존재하지 않는 경우 해당 키로 딕셔너리를 생성하고, 커서 위치를 업데이트 해준다. 단어 삽입이 완료되면 * 키를 생성해서 끝임을 표기한다. search (단어 조회) 단어의 키(문자)가 커서에 존재하지 않는 경우 False를 반환하고, 커서 위치를 업데이트 해준다. 단어 순회가 완료되었을 때 * 키가 커서에 있을 경우 True를 반환하고 없을 경우 False를 반환한다. startswith (접두어 조회) 단어의 키(문자)가 커서에 존재하지 않는 경우 Fals.. 2021. 10. 10.
정렬 알고리즘 표 (Python 코드포함) 인터뷰 대비를 위한 기본적인 정렬 알고리즘 표입니다. Python 버전의 코드 구현도 함께 비교할 수 있습니다. 클릭해서 보시는 것을 추천드립니다. 2021. 9. 17.
[Python] Leader https://codility.com/media/train/6-Leader.pdf Leader는 크기 N인 배열A 에서 과반수 이상 (N//2+1) 의 갯수를 가지고 있는 요소를 말한다. Leader를 조사하는 방법을 아래와 같이 정리하였다. 1. Sorting 정렬 후 중앙값의 카운트를 계산한다. 카운트가 n//2 보다 크다면 Leader에 해당한다. Detected time complexity O(N * log(N)) def solution(A): n = len(A) s_A = sorted(A) leader = None count = 0 for i in range(n): if s_A[i] == s_A[n//2]: count += 1 if count > n // 2: leader = s_A[n//2] .. 2021. 4. 5.
[Python] 순열 알고리즘 다음 순열 구하는 알고리즘 A[i-1] 0 and a[i-1] >= a[i]: i -= 1 # 더이상 다음 순열을 구할 수 없음 = False 리턴 if i = a[j]: j -= 1 # 3번 a[i-1], a[j] = a[j], a[i-1] # 4번 j = len(a)-1 while i < j: a[i], a[j] = a[j], a[i] i += 1 j -= 1 return True a = [2,3,1,7,6,5,4] next_perm(a) prin.. 2021. 3. 15.
[Python]Insertion Sorting 삽입정렬은 자기 위치를 기준으로 앞 인덱스의 값과 비교해서 크기가 작다면 앞에다가 삽입(swap)하는 것이다. 장점은 N의 크기가 작을때 효과적이라는 것 단점은 성능이 좋지 않다는 것이다. 평균 시간복잡도 O(N^2) 정리 현재 인덱스를 정렬될 리스트의 끝으로 보고 전체 순회 현재 인덱스 값을 앞 인덱스 값과 비교/스와핑 후 인덱스 업데이트 반복 업데이트 반복 조건은 idx > 0 and arr[idx-1] > arr[idx def insertion_sort(a): n = len(a) for i in range(n): for j in range(i-1, -1, -1): if a[i] < a[j]: a[i], a[j] = a[j], a[i] i = j 2019. 5. 10.
[Python]Selection Sorting i번째 인덱스를 최소값으로 선택하고, i+1부터 순회하면서 i보다 작은 값을 가진 인덱스 위치가 발견되면 swap 한다 장점은 구현하기 간단하고 비교 및 교환의 횟수가 버블, 삽입 정렬보다 적다는 특징을 가진다. 단점은 성능이 O(N^2)으로 좋지 않다. 정리 첫 인덱스부터 끝 인덱스까지 순회 Min Index 공간 1개 필요, 저장 현재 인덱스 값과 Min Index 스왑 def selection_sort(arr): for i in range(len(arr)): min_idx = i for j in range(i+1,len(arr)): if arr[j]< arr[min_idx]: min_idx = j arr[i],arr[min_idx] = arr[min_idx],arr[i] return arr 2019. 5. 9.
[Python]Bubble Sorting 버블정렬은 거품이 올라오는 모양처럼 정렬한다고 해서 붙여진 이름이다. 장점은 구현하기 가장 간단하다는 특징을 가지고 있다 단점은 성능이 좋진 않다는 것. 평균 시간 복잡도 O(N^2) 정리 인접한 값과 비교 후 교환 스와핑 위한 공간 1개 필요 총 n-1번 루핑 def bubble_sort(arr): for _ in range(len(arr)-1): for j in range(len(arr)-1): if arr[j] > arr[j+1]: arr[j],arr[j+1] = arr[j+1],arr[j] return arr 2019. 5. 9.
[Python]보이어무어 알고리즘 본 코드는 text안에 찾는 pattern 이 있으면 1 없으면 0 을 출력해주는 코드이다 보이어무어 알고리즘을 적용했다. 보이어무어 알고리즘이란 다음과 같다 pattern의 오른쪽 끝 문자와 text의 현재 위치의 문자가 일치하는지 검사 끝이 일치하면 pattern과 text를 다 검사한다. 마지막까지 일치하지 않으면 패턴길이만큼 skip 끝이 일치하지않으면 text의 현재위치 문자가 skip배열에 있는지 확인. 있으면 인덱스만큼 skip, 없으면 패턴길이만큼 skip 텍스트 끝 도달할 때까지 반복 text = 'a pattern matching algorithm' pattern = 'rithm' s = pattern[::-1] skip = list(range((len(pattern)))) i = le.. 2019. 4. 27.
728x90
반응형

티스토리툴바