Algorithm4 [Python] 파이썬으로 DFS와 BFS 구현하기 DFS와 BFS DFS와 BFS는 그래프의 탐색 방법 목적: 한 정점에서 시작하여 연결되어 있는 모든 정점을 1번씩 방문 DFS 한 우물을 깊이 파면서 탐색 재귀함수 혹은 스택으로 구현 가능 d_check = [False for _ in range(n + 1)] def dfs(x): d_check[x] = True print(x, end = ' ') for y in edge[x]: if d_check[y] == False: dfs(y) BFS 여러 우물을 동시에 같은 깊이로 탐색 최단 경로 찾기에 사용 from collections import deque def bfs(): queue = deque([start]) b_check = [False for _ in range(n + 1)] b_check[st.. 2021. 8. 18. [Python] 스택, 큐 사용하기 스택(Stack) 스택 연산 연산 내용 시간 복잡도 push 스택에 요소 추가 O(1) pop 스택에 요소 제거 O(1) 스택 생성 파이썬에서 리스트로 스택을 사용한다. stack = [] 스택의 삽입(push) stack = [1, 2, 3] stack.append(4) 스택의 제거(pop) stack = [1, 2, 3] top = stack.pop() stack top stack = [1, 2, 3] top = stack[-1] stack empty if not stack: print("empty") 큐(Queue) 큐 연산 연산 내용 시간 복잡도 enqueue 큐에 요소 추가 O(1) dequeue 큐에 요소 제거 O(1) 큐 생성 큐는 list가 아닌 collection 모듈의 deque를 사용.. 2021. 8. 18. C언어로 RSA 암호화 프로그램 만들기 RSA는 대표적인 비대칭 키 암호화 기법이다. SSL/TSL에 가장 많이 사용되는 비대칭 키 암호화 알고리즘이라고 한다. 비대칭 키 암호화 방식은 암호화와 복호화에 사용하는 키가 서로 다르다. 따라서 하나는 공개해서 공개키(public key)로 사용하고 다른 하나는 개인이 비밀로 가지고 있어 개인 키(private key)라 부른다. 이렇게 되면 공개 키로 암호화한 내용은 개인키로만, 개인키로 암호화한 내용은 공개키로만 해독할 수 있다. RSA 암호화는 엄청 큰 숫자는 소인수분해하기 힘들다는 것을 이용하여 암호화한다. 두 소수를 곱하는 것은 누구나 할 수 있는 쉬운 연산이지만 두 소수를 곱한 값에서 그 소수를 찾아내는 것은 어렵다. 예를 들어 22,637 곱하기 58,391은 1,321,797,067이.. 2021. 7. 31. 퀵 정렬 (Quick sort) 쉽게 알기 퀵 정렬(Quick sort) 퀵 정렬은 평균적으로 매우 빠른 속도를 자랑하는 정렬 방법입니다. 그렇기에 이름부터가 다소 건방진 '퀵' 정렬인데요. 보통 다른 정렬 방법들은 이름으로부터 어떻게 정렬을 하는지 유추할 수 있습니다. 선택 정렬은 최솟값을 찾아 선택한다고 해서 선택 정렬이라든지 병합 정렬은 병합하면서 정렬한다고 해서 병합 정렬이라든지. 퀵 정렬을 그런 방식으로 이름을 바꾸면 피벗 정렬(pivot sort)이 될 거 같네요. 퀵 정렬은 피벗을 기준으로 목록을 큰 값과 작은 값으로 나누어 가며 정렬하기 때문입니다. 퀵 정렬 예시로 살펴보기 실제 알고리즘을 보면서 어떻게 정렬을 하는지 살펴보죠. 실생활의 예를 들어보려 합니다. 9명의 학생이 운동장에 떠들고 있으니 선생님이 한 마디 합니다. 학창 시.. 2021. 7. 21. 이전 1 다음
