Algorithm
-
bisect algorithm(python)algorithm 2019. 10. 9. 16:04
Bisect는 여러방면으로 활용이 가능하다. 정렬된 List를 삽입 후에 정렬된 상태를 유지시켜 새로운 아이템을 추가하더라도 다시 정렬할 필요 없이 삽입할 위치를 찾아준다. 그리고 구간의 Index를 얻는데도 매우 효율적이다. 위 두가지 예시를 들어보자. >>> scores = [60, 70, 80, 90] >>> bisect.bisect_left(scores, 71) 2 >>> bisect.insort_left(scores, 71) >>> print(scores) [60, 70, 71, 80, 90] 정렬된 scores에 새로운 값(71)을 삽입할 수 있다. >>> bisect.bisect_left(scores, 50) 0 >>> bisect.bisect_right(scores, 80) 4 >>> pr..
-
Daily Coding Problem #11algorithm 2019. 3. 15. 15:32
문제Good morning! Here's your coding interview problem for today.This problem was asked by Twitter.Implement an autocomplete system. That is, given a query string s and a set of all possible query strings, return all strings in the set that have s as a prefix.For example, given the query string de and the set of strings [dog, deer, deal], return [deer, deal].Hint: Try preprocessing the dictionary ..
-
Daily Coding Problem #6algorithm 2019. 3. 14. 12:56
XORXOR은 배타적논리합이다. 무슨말이냐면 두 값중 하나만 배타적으로 참일 경우에만 참이된다. * 이 연산은 더해서 mod 2를 구하는것과 동일하다AND연산은 값이 더 커질 수가 없고, OR 연산은 값이 더 작아 질 수가 없다. 하지만 XOR은 값이 커질 수도, 작아질 수도 있는 특성을 가지고 있다.XOR을 특성을 이용하면 두 값을 암호화하고 복호화하는게 가능하다.Theory of operation X⊕X = 0 X⊕0 = X X⊕Y = Y⊕X (X⊕Y)⊕Z = X⊕(Y⊕Z)So.. X⊕Y = KEY Y⊕KEY = X XOR LinkedList(Memory Efficient Doubly Linked List)xor linkedlist는 위의 xor 개념을 이용하여 하나의 변수에 이전(prev) 주소값과..
-
정렬알고리즘(sorting algorithm) 정리algorithm 2019. 3. 13. 19:14
1.버블정렬(Bubble sort)버블정렬은 가장 쉬운 정렬 알고리즘이지만 시간복잡도가 좋은 퍼포먼스를 내지 못해서 실제로는 잘 사용되지 않는다.시간복잡도는 O(n²)이며 공간복잡도는 하나의 배열만 사용하여 정렬을 진행하기 때문에 O(n)이다.버블정렬 소스코드def bubbleSort(alist): for loop_count in range(len(alist)-1, 0, -1): for idx in range(loop_count): if alist[idx] > alist[idx+1]: tmp = alist[idx] alist[idx] = alist[idx+1] alist[idx+1] = tmp return alist버블정렬 테스트결과각 테스트는 n = 10000으로 진행하였다. — — Finished! ..
-
Timsort python sorted 알고리즘programming 2019. 3. 13. 19:06
요즘 Programming peals 책을 읽고 있는데 정렬에 대한 언급이 나와서문득 Python을 사용하면서 데이터 sorting을 할때 bulit-in function인 sorted만 사용하고 있는것을 깨달았다.생각해보면 Python으로 되어있는 오픈소스 코드에서도 sorting할때 sorted를 사용하지 않는 경우는 딱히 못본거 같다.sorted 함수의 원형은 아래와 같다.sorted(iterable[, cmp[, key[, reverse]]])Pamater를 통해 key를 지정해주면 해당 key 기준으로 sorting을 해주고 reverse가 필요하면 reserver 옵션만 넣어주면 오름차순,내림차순 또한 마음대로 받아볼 수 있다.그렇다면 sorted 내부 sorting algorithm은 뭐가 ..