알고리즘
-
파이썬: Tarjan 알고리즘 (Strongly Connected Components)컴퓨터/파이썬 2020. 11. 23. 22:10
Tarjan's Algorithm Tarjan's strongly connected components algorithm an algorithm in graph theory for finding the strongly connected components (SCCs) of a directed graph. en.wikipedia.org 1. 소개 타르잔 알고리즘은 Kosaraju 알고리즘처럼 방향 그래프에서 strongly connected component들을 찾아내는 더 나은 알고리즘이다. (코사라주는 DFS 2개, 타르잔은 DFS 1개를 이용해 linear하게 찾을 수 있음) (Airport Connections와 같은 문제에서 사용할 수 있다.) 아래는 William Lin이라는 고등학생 학생과 a..
-
Python: LRU 캐시 만들어보기컴퓨터/파이썬 2020. 11. 16. 22:07
Least Recently Used 가장 오래 사용하지 않은 페이지 교체 알고리즘 Cache replacement policies - Wikipedia Page replacement algorithm. en.wikipedia.org 1. LRU 파이썬 functools.lru_cache 소스: @Github from functools import lru_cache @lru_cache(maxsize=32) def fibo(n): if n == 1: return 0 elif n == 2: return 1 else: return fibo(n - 1) + fibo(n - 2) 파이썬 실제 lru_cache는 이 글 구현된 버전보다 빠르다, (따로 linked class를 만들지도 않고, 다 함수 안에서 끝난다...
-
TypeScript: Bubble Sort (거품 정렬)컴퓨터/HTML & JS & TS 2020. 11. 8. 21:31
TypeScript Typed JavaScript at Any Scale. TypeScript extends JavaScript by adding types to the language. www.typescriptlang.org # TypeScript 1일차 언어를 공부할 때 정렬 알고리즘부터 시작하는 편이다. Go언어, Python type hinting 버전과 비슷한 느낌이지만, interface, JS 기능들이 많이 미숙하기에 공부가 더 필요 1. 문법 소개 one-line swapping (한 줄로 값 변경) 특이하게, array안에 넣어서 해야한다. (함수에서 두가지를 return 할 때도 return [a, b]로 쓸 수도 있다. [array[i], array[i + 1]] = [array[i..
-
Python Singly Linked List 함수들컴퓨터/파이썬 2020. 11. 3. 22:22
단일 연결 리스트 연결 리스트 - 위키백과, 우리 모두의 백과사전 위키백과, 우리 모두의 백과사전. ko.wikipedia.org 만들어 볼 것 Magic methods ( lt, gt, pos, repr ) print 함수 add 함수 ( add([1,2,3,4,5] ) getNodesInArray ( head.getNodesInArray() = [1,2,3,4,5] ) linkedify ( [1,2,3,4,5] 배열을 받으면, 1 -> 2 -> 3 -> ...) swap ( a.value, b.value = b.value, a.value) reverse (뒤집기) ( 1 -> 2 -> 3을 3 -> 2 -> 1로) Python sort 함수 이용 정렬 Bubble sort (거품 정렬) Selecti..
-
딥러닝 옵티마이저: Adabelief Optimizer컴퓨터/파이썬 2020. 10. 27. 12:48
Adabelief v0.1.0 Adapting Stepsizes by the Belief in Observed Gradients Adabelief Optimizer 설명 juntang-zhuang.github.io 1. 소개 공식 소개 Adam처럼 빠르고, SGD처럼 일반화 잘하고, GAN을 트레인 하기에 충분히 안정적이다. Adabelief는 Adam을 수정한 딥러닝 최적화 알고리즘이다. (실제로 Adam에서 한 줄만 바꿔도 됨) 더 빠른 트레이닝 수렴 더 안정적인 트레이닝 더 나은 일반화 더 높은 모델 정확도 2. Adam에서의 문제 SGD(확률적 경사 하강법)의 초반 트레이닝에서 수렴이 너무 느린 문제를 해결한 Adam. 하지만 Adam은, 기울기(gradient)가 크지만, 분산(variance)..
-
Python kth Hamming number (해밍 수)컴퓨터/파이썬 2020. 10. 19. 23:50
해밍 수 Regular Number 1. Hamming number 해밍 수란 인수가 2, 3, 5으로만 이루어진 수를 말한다. 그래서 5-smooth number, ugly number라고도 불린다. 한마디로, 아래 식을 만족하는 수 (다음 수들은 해밍 수이다. 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, ...) H=2i∗3j∗5k, (i,j,k>=0) 2. 파이썬 시간 복잡도: O(n), 결과를 바로바로 출력하면 공간 복잡도 O(1) 가능 프로그램: n 보다 작거나 같은 모든 해밍 수를 배열에 넣고 출력할 것이다. n = 25 base = [2, 3, 5] nums = [1] append = nums.append # tweak candidates_indic..
-
파이썬, 자바 Trie[트라이] 비교컴퓨터/JAVA 2020. 10. 16. 16:10
Trie [트라이] 또는 디지털 트리, suffix/prefix (접두/접미) 트리 1. 소개 Trie는 탐색 트리의 일종이며 주로 문자열로 이루어진 트리 자료 구조이다. Boggle Board 같은 알고리즘에서 원하는 단어를 얻어낼 때 유용하다. 이 글 Trie 구조는 아래 words(String[]) 배열을 결과물처럼 만들 것이다. endSymbol = asterisk(*)로 지정해서 *까지 도달하면 그 문자열은 찾은 걸로 표시한다. (full word) words = [ "안녕하세요", "안녕", "하세요", "반갑습니다", "트라이", "트라이앵글", ] # 결과물 {'안': {'녕': {'하': {'세': {'요': {'*': '안녕하세요'}}}, '*': '안녕'}}, '하': {'세': {'..