Algorithm
[1028 알고리즘 22] 유클리드호제법 : 최댓값 구하기
# GCD # GCD : Greatest common divisor : 최대공약수 # 유클리드 호제법 # : a,b에 대해 a를 로 나눈 나머지를 r이라 하면 # a,b의 최대 공약수는 b와 r의 최대 공약수와 같다. # a b # 192 162 # 162 30 # 30 12 # 12 6 >> 최대 공약수 6 def gcd(a, b): print("---" + str(a) + ", " + str(b)) if a % b == 0: return b else: return gcd(b, a % b) print(gcd(192, 162)) 출처 https://youtu.be/7C9RgOcvkvo
[1028알고리즘 FROM 동빈나 21]그래프 탐색 : DFS vs BFS
DFS Depth-first search : 깊이 우선탐색 - 스택(선입후출, 바구니, append, pop), 재귀함수로 구현 1. 탐색 시작 노드를 스택에 삽입하고 방문처리를 한다. 2. 스택의 최상단 노드에 방문하지 않는 인접한 노드가 하나라도 있으면 >>>>>>>>파이썬 : https://youtu.be/7C9RgOcvkvo graph = [ [], [2,3,8], [1,7], [1,4,5], [3,5], [3,4], [7], [2,6,8], [1,7] ] visited = [False] *9 dfs(graph, 1, visited) bfs(graph, 1, visited) GFS BFS 1>2>3 넣었다 꺼냄 > 1>2 1>4>5 넣었따 꺼냄 1>4>6 ... from __future__ imp..
[1028알고리즘 20]Dynamic Programming
피보나치 수열. _ 재귀함수. 1,1,2,3,4,8 1 + 1 = 2 fibo(1)=1 fibo(2)= 1 fibo(3) =fibo(1)+fibo(2) fibo(n) = fibo(n-2) + fibo(n-1) 같은 계산을 N^n 반복. 결과를 기록해서 이용. = 메모이제이션 Memoization 문제를 쪼갤수 있는 구조= 겹치는 부분문제 = Overlapping subproblem. input = 100 # memo 라는 변수에 Fibo(1)과 Fibo(2) 값을 저장해놨습니다! memo = { 1: 1, 2: 1 } # Top Down 방식. 반대는 바텀업 def fibo_dynamic_programming(n, fibo_memo): if n in fibo_memo: return fibo_memo[n]..
[1028알고리즘 19]해쉬
해쉬 테이블 : "키", "데이터"를 저장함으로써 즉각적으로 데이터를 받아오고 업데이트 하고 싶을 때 사용하는 자료구조 해쉬함수 : 임의의 길이를 갖는 메시지를 입력하여 고정된 길이의 해쉬값을 출력하는함수입니다. 해쉬 테이블의 내부 구현은 키를 해쉬 함수를 통해 임의의 값으로 변경한 뒤 배열의 인덱스로 변환하여 해당하는 값에 데이터를 저장합니다. 만약, 해쉬 값 혹은 인덱스가 중복되어 충돌이 일어난다면? 체이닝과 개방주소법으로 해결. items = [None]*8 hash("가") %86 hash("나")%8 5 items[hash("가") %8]="가위" items[hash("나") %8]="나비" 결과 :: items[None, None, None, None, None, '나비', '가위', None..