Python/알고리즘 - 이론

BFS 이론 BFS는 너비 우선탐색이라고도 부르며, 그래프에서 가까운 노드부터 우선적으로 탐색하는 알고리즘이다. BFS는 큐 자료구조를 이용하며, 구체적인 동작 과정은 아래와 같다. 탐색 시작 노드를 큐에 삽입하고 방문 처리한다. 큐에서 노드를 꺼낸 뒤에 해당 노드의 인접 노드 중에서 방문하지 않는 노드를 모두 큐에 삽입하고 방문처리한다. 2번의 과정을 수행할 수 없을때 까지 반복한다. 기본 형태 from collections import deque # BFS 함수 정의 def bfs(graph, start, visited): # 큐(Queue) 구현을 위해 deque 라이브러리 사용 queue = deque([start]) # 현재 노드를 방문 처리 visited[start] = True # 큐가 빌 ..

이진 탐색 알고리즘 순차 탐색 : 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 확인하는 방법 이진 탐색 : 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법 이진 탐색은 시작점, 끝점, 중간점을 이용하여 탐색 범위를 설정한다. 이진 탐색 동장 예시 이미 정렬된 10개의 데이터 중에서 값을 찾는 방법 시작점, 끝점과 중간점을 설정한다. - 중간 값이 2개일 경우 소수점 이하 제거 중간점을 기준으로 찾는 데이터가 우측에 있는지 좌측에 있는지 구분 만약 좌측에 있다면 시작점은 그대로 내버려두고 현재의 중간점을 끝점으로 수정 수정한 시작점과 끝점을 기준으로 중간점을 다시 설정 이후 중간점 위치의 값이 찾고자하는 데이터가 같아질 때까지 반복 시간복잡도 단계마다..

계수 정렬 특정한 조건이 부합 될 때만 사용할 수 있지만 매우 빠르게 동작한다. 계수 정렬은 데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을 때 사용 가능 데이터의 갯수가 N, 데이터중 최댓값이 K일 때 최악의 경우에도 수행시간이 O(N+K)를 보장한다. 동작 예시 1. 가장 작은 데이터부터 가장 큰 데이터까지의 범위가 모두 담길 수 있도록 리스트를 생성한다. 2. 데이터의 값과 동일한 인덱스의 데이터를 1씩 증가시킨다. 3. 리스트의 첫 번째 데이터부터 하나씩 그 값만큼 반복하여 인덱스를 출력한다. 소스 코드 # 모든 원소의 값이 0보다 크거나 같다고 가정 array = [7, 5, 9, 0, 3, 1, 6, 2, 9, 1, 4, 8, 0, 5, 2] # 모든 범위를 포함하는 리스트 선언 (..

퀵 정렬 기준 데이터를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸는 방법이다. 일반적인 상황에서 가장 많이 사용되는 정렬 알고리즘 중 하나이다. 병렬 정렬과 더불어 대부분의 프로그래밍 언어의 정렬 라이브러리의 근간이 되는 알고리즘이다. 가장 기본적인 정렬은 첫 번째 데이터를 기분 데이터로 설정한다. 동작 예시 1. 첫번째 원소를 피벗으로 설정한다. 2. 왼쪽에서 부터 피벗 값보다 큰 값, 오른쪽에서부터 피벗 값보다 작은 값을 선택한다. 3. 선택된 두개의 값들의 위치를 바꾸어준다. 4. 위 동작들을 반복한다. 5. 위치가 엇갈리는 경우 피벗 값과 작은 값의 위치를 바꾸어준다. 6. 피벗 값을 기준으로 좌우로 나누어 2개의 리스트로 분할하여 준다. 7. 왼쪽 오른쪽 리스트에 대해 1번부터..

정렬 정렬이란 데이터를 특정한 기준에 따라 순서대로 나열한 것이다. 일반적으로 문제 상황에 따라서 적절한 정렬 알고리즘이 공식처럼 사용된다. 선택 정렬 처리되지 않은 데이터 중에서 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸는 것을 반복 처리되지 않은 데이터 중에서 가장 작은 데이터를 선택해 가장 앞의 데이터와 바꾼다. 앞선 1번의 과정을 반복한다. 정렬되지 않은 데이터가 하나가 남은 경우 처리하지 않아도 완성이 된다. array = [7, 3, 5, 4, 2, 6, 1, 0] for i in range(len(array)): min_index = i for j in range(i+1, len(array)): if array[min_index] > array[j]: min_index = j a..