bit가 눈 앞에서 왔다갔다

DFS : 현재 정점에서 갈 수 있는 점들까지 (끝까지) - 모든 노드를 방문해야할 때 - 경로에 특징을 저장해둬야 하는 문제 - 검색 대상 그래프가 클 경우 - (BFS보다 간단하지만 느림) BFS : 현재 정점에서 연결된 가까운 점들부터 - 재귀적으로 동작하지 않음 - 최단거리, 임의의 경로 문제 - 규모가 작고 원하는 대상이 멀지 않을때 - 큐 사용, FIFO 원칙 둘 다 - 어떤 노드를 방문했는지 여부 검사 반드시! (or 무한루프,,)

특정 조건일 때만 사용 가능하며 매우 빠름 데이터 크기 범위가 제한 되어 있을 경우와 정수 형태로 표현 할 수 있을 때 사용 안정정렬 복잡도 분석: 데이터 개수 N, 최대값(양수) K이다. 최악의 경우(데이터의 범위가 너무 큰 경우 ex. 0 ~ 99999)에도 O(N+K) 유지 알고리즘 입력받는 데이터의 범위를 포함할 수 있는 리스트를 생성한다. 생성한 리스트에서 각 데이터에 해당하는 인덱스의 값을 증가시킨다. array = [7, 5, 9, 0, 3, 1, 6, 2, 9, 1, 4, 8, 0, 5, 2] count = [0] * (max(array)+1) #모든 범위를 포함하는 리스트 생성 for i in range(len(array)): count[array[i]] += 1 #각 데이터에 해당하는 ..

데이터 특성 상관 없이 가장 많이 사용되는 정렬 알고리즘 라이브러리에서 정렬함수를 호출하면 대부분 quick sort나 merge sort 복잡도 분석: 표준 라이브러리 이용시 항상 O(NlogN) 보장, 이상적인 경우- 왼쪽 오른쪽이 균등하게 나눠진 경우, 최악의 경우 - 편향된 경우 알고리즘 left는 피벗보다 큰 데이터를 찾을 때까지 왼쪽에서 오른쪽으로 탐색한다 right는 피벗보다 작은 데이터를 찾을 때까지 오른쪽에서 왼쪽으로 탐색한다 left와 right가 엇갈릴 경우 작은 데이터와 피벗의 위치를 바꾼다 새롭게 생긴 두 리스트를 재귀함수로 호출해 퀵정렬을 시행한다 #데이터 특성 상관없이 일반적으로 가장 많이 사용되는 정렬알고리즘 #정렬 라이ㅣ브러리의 근간이 되는 (+병합정렬) #기본적인 형태- ..

정렬되어 있는 리스트에 새로운 값을 적절한 위치에 삽입하는 과정 반복 배열을 정렬된 부분과 정렬되지 않은 부분으로 나누어서 사용하는 것으로 생각 안정된 정렬, 데이터 수가 적을 경우와 이미 정렬되어 있는 경우 유리 복잡도 분석: 삽입정렬 외부루프 n-1번 실행, 각 단계에서 1번의 비교와 2번의 이동이 이루어짐. 총 비교횟수 n-1번, 총 이동횟수 2(n-1)번. 따라서 최선의 경우 O(n) 입력 자료가 역순일 경우는 최악의 경우. 전부 한 칸씩 이동 O(n^2) 알고리즘 인덱스 0은 이미 정렬되었다고 생각, 인덱스 1부터 시작 현재 정렬된 배열은 i-1까지 이므로 j(삽입하고자 하는 원소 위치)를 i-1부터 역순으로 진행 j가 왼쪽 원소보다 작을 경우 swap array = [7, 5, 9, 0, 3,..

제자리정렬(in-place sorting): 입력배열 외에는 다른 추가 메모리를 요구하지 않는 정렬방법 안정정렬 성능분석: 비교횟수 - 두개의 for 루프 중 외부루프 n-1번, 내부루프 0 ~ n-2까지 변하는 i에 대해 (n-1)-i번 반복. (n-1)+(n-2)+...+1=n(n-1)/2 = O(n^2) 알고리즘 첫번째 인덱스를 최소값 인덱스로 설정한다 그 다음 인덱스부터 마지막 인덱스의 값(array[j])과 최소값 인덱스의 값을 비교한다 만약 array[j]의 값이 최소값 인덱스보다 작다면 최소값 인덱스를 변경한다. swap을 통해 자리를 바꿔준다 for i in range(len(array)): min_index = i #최소값 인덱스 설정 for j in range(i+1, len(array..

DFS(Depth First Search) 깊이 우선 탐색: 시작 노드를 방문처리 하고 방문처리 되지 않은 노드로 진행 선택된 노드는 방문처리 되고 새로운 시작 노드가 되어 같은 방법을 반복하다가 방문처리 되지 않은 노드가 없을 경우 되돌아 감 BFS(Breadth First Search) 너비 우선 탐색: 시작 노드로부터 가까운 노드를 먼저 방문하고 멀리 떨어져 있는 노드를 나중에 방문. 시작 노드에서 인접한 노드들을 방문하고 그 노드들과 인접한 노드들을 방문 DFS-구현 가능한 방법 또는 활용하는 자료구조: 1. 순환호출(재귀함수) 2. 스택(Stack)- 순환호출 이용 def dfs(graph, v, visited): visited[v] =True print(v, end=' ') for i in g..

Kruskal 알고리즘 전제 지식으로 배웠다. Kruskal 알고리즘이 정확히 기억 안 나서 책을 다시 봤다. Kruskal - MST(Minimmum Spanning Tree; 최소비용 신장 트리)의 일종으로써 Greedy Method를 이용한다. MST의 원리에 따라 1. 각단계 사이클을 이루지 않는(T!) 최소 비용 간선을 선택하며, 2. 모든 정점을 최소 비용으로 연결하는 최적 해답을 구한다. 또한 Greedy Method의 원리에 따라 최적의 해를 구한다. Union-Find는 연결성을 표현하는 연산의 일종으로, 꼭 Kruskal 알고리즘에서만 사용되는 것은 아니다. (중요하다ㅏ) 정의 Union-Find(Disjoint-Set) - 두 노드를 선택하고 같은 그래프에 속하게 하거나, 같은 그래프..

BFS는 그래프를 탐색하는 방법 중 하나로, 너비를 우선적으로 탐색하는 알고리즘이다. 필요한 자료구조: 큐 (First In First Out) *다음에 방문할 후보를 담아두는 역할 그림을 보면 그냥 아무 생각 없이 트리라고 생각하기 쉽다. 근데 그래프임. (트리도 그래프에 속하긴 함. 트리와 그래프의 가장 큰 차이는 트리는 사이클이 없음. 트리 탐색은 반복적 순회, 레벨 순회, 이진 탐색 트리 같은 애들이 하는 듯함 ) 처음 배울 때 쓴 그래프를 따왔당 얘는 중간에 간선이 더 있어서 트리랑 덜 헷갈린다.ㅎ 전반적인 BFS 내용: 1) 1 값을 갖는 노드를 우선으로 탐색한다고 한다. 1을 방문 표시한다. -> 큐에 push (현재 큐 : 1 && 방문 : 1) 2) 큐의 front 1을 pop 하는데, ..