반응형 언어별 개념 정리19 [파이썬] 탐색 알고리즘 정리 - 깊이 우선 탐색(DFS) (python) 깊이 우선 탐색 (Depth First Search, DFS) 시작 정점의 한 방향으로 갈 수 있는 경로가 있는 곳까지 깊이 탐색하다가 갈 수 있는 곳이 없으면, 가장 마지막에 만났던 갈림길 간선이 있는 정점으로 돌아와 다른 방향의 정점으로 탐색을 계속 반복하여 모든 정점을 방문하는 방법 특징 가장 마지막에 만났던 정점으로 돌아가 다시 탐색을 반복하므로 LIFO 구조의 스택 사용 넓게 탐색하기 전에 깊게 탐색하므로 깊이 우선 탐색(DFS) 깊이 우선 탐색(DFS)이 넓이 우선 탐색(BFS)보다 간단 탐색 속도는 DFS가 BFS보다 느림 스택과 재귀 알고리즘의 형태로 구현 가능 트리에서 사용되는 모든 순회는 DFS 의 종류 DFS의 탐색 과정 출처 : https://commons.wikimedia.org/.. 2023. 2. 26. [파이썬] 탐색 알고리즘 정리 - 너비 우선 탐색(BFS) (python) 너비 우선 탐색(Breadth First Search, BFS) 루트노드(혹은 다른 노드)에서 시작해서 인접한 노드를 먼저 탐색하는 방법 시작 정점으로부터 가까운 정점을 방문해나가 가장 멀리 떨어진 정점을 나중에 방문하는 순회 방법 말그대로 넓게 탐색하는 방법 (방문한 노드를 기준으로 주변을 탐색해나가므로) 깊이 우선 탐색보다 조금 더 복잡함 특징 거리에 따라 단계별로 탐색하므로 직관적이지 않은 면이 있음 그래프 탐색의 경우 어떤 노드를 방문했는지 반드시 검사해야 함 → 그렇지 않을 경우 무한 루프에 빠질 위험 있음 재귀적으로 동작하지 않음 방문한 노드를 차례로 저장한 후 꺼내는 큐(Queue)를 사용(선입선출의 원칙) 시간 복잡도는 O(N)의 시간 소요 (단, 실제 수행 시간은 DFS > BFS) 방문.. 2023. 2. 22. 소수 판별 알고리즘 - 에라토스테네스의 체 📃에라토스테네스의 체 고대 그리스 수학자 에라토스테네스가 만들어낸 소수를 찾는 방법 🌓 특징 2~n까지의 숫자에서 숫자들의 배수를 모두 제거한 뒤 제거되지 않은 숫자를 소수로 판별하는 방식 실제 계산은 무식하지만 프로그래밍에선 상당히 효율적인 방법론 구하자고하는 수의 √(n)에 해당하는 소수의 배수만 확인하여 지우면 되기 때문에 빠름 👏 과정(예시 : 2~120까지 모든 소수 찾기) 2~120까지의 숫자 나열 2는 소수이므로 오른쪽에 2를 쓰고 2의 배수를 모두 지움 남아있는 숫자에서 3은 소수이므로 오른쪽에 3을 쓰고 3의 배수를 모두 지움 남아있는 숫자에서 5는 소수이므로 오른쪽에 5을 쓰고 5의 배수를 모두 지움 남아있는 숫자에서 7은 소수이므로 오른쪽에 7을 쓰고 7의 배수를 모두 지움 위 과정을.. 2023. 2. 21. [파이썬] 메모이제이션과 동적 프로그래밍 메모이제이션(memoization) 과 동적 프로그래밍(Dynamic Programming) 특징 컴퓨터 프로그램을 실행할 때 이전에 계산한 값을 메모리에 저장해서 매번 다시 계산하지 않도록 하여 전체적인 실행속도를 빠르게 하는 기술. 재귀처럼 이전으로 돌아가는게 아니라 이미 저장된 값을 불러오는 것 재귀 vs 메모이제이션 대표적으로 피보나치 수열을 생각해보자. # 재귀로 구현한 피보나치 수열 def fibo(n): if n =2 and len(memo) 2023. 2. 19. [파이썬] 큐(Queue) 자료구조 정리 Queue 스택이 바닥이 막힌 세로로 세운 통이라면 큐는 양쪽이 뚫린 가로로 된 통의 형태 삽입, 삭제의 위치가 제한적인 자료구조 데이터 값을 저장하는 기본적인 구조이며, 일차원의 선형 자료구조 선입선출(First In First Out, FIFO)의 형태를 가짐 활용 스트리밍(streaming) 너비 우선 탐색(Breath First Search, BFS) Queue의 주요 연산 enQueue(tiem) : 큐의 뒤쪽에 원소를 삽입하는 연산 deQueue() : 큐의 앞쪽에서 원소를 삭제하고 반환하는 연산 createQueue() : 공백 상태의 큐를 생성하는 연산 isEmpty() : 큐가 공백상태인지를 확인하는 연산 isFull() : 큐가 포화상태인지를 확인하는 연산 Qpeek() : 큐의 앞쪽에.. 2023. 2. 15. [파이썬] 정렬 알고리즘 - 선택 정렬 선택 정렬(Selection Sort) 정렬과정 리스트 내의 최소값을 찾음 그 값을 리스트의 맨 앞에 위치한 값과 교환 맨 처음 위치를 제외한 나머지 값들을 대상으로 위 과정 반복 (시간 복잡도 O(n^2) Step 최솟값 7을 찾아 맨앞 35와 교환하고 다시 최소값을 찾음 다시 정렬 안된 리스트와 교환하고 위의 과정을 반복함 정렬되지 않은 마지막 원소가 가장 큰 값을 가지므로 정렬 완료 코드 구현 def selectionsort(arr) : n = len(arr) for i in range(n-1) : min_arr = i for j in range(i+1, n) : if arr[min_arr] > arr[j]: min_arr = j arr[i], arr[min_arr] = arr[min_arr], a.. 2023. 2. 12. 이전 1 2 3 4 다음 반응형
