전체 글
[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..
[1028알고리즘 18]정렬
정렬 데이터를 순서대로 나열하는 방법을 의미합니다. 버블정렬 앞뒤 숫자 비교해서 정렬: 1st 와 2nd, 2nd와 3nd, 3nd와4th 와 비교 input = [10, 4,2] def bubble_sort(input): n = len(input) for loop1 in range(n - 1): for loop2 in range(n - 1 - loop1): print(loop2, loop2 + 1, input) if input[loop2] > input[loop2 + 1]: input[loop2], input[loop2 + 1] = input[loop2 + 1], input[loop2] return input print(bubble_sort(input)) 선택정렬 선택해서 정렬. : 가장 작은 숫자를 ..