bit가 눈 앞에서 왔다갔다

데이터 특성 상관 없이 가장 많이 사용되는 정렬 알고리즘 라이브러리에서 정렬함수를 호출하면 대부분 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..

틈틈히 공부하는 내용 추가해서 업데이트 중! *자료형 정수(양, 음, 0), 실수(숫자에 . 찍으면 실수로 인식 ex a = 10.) 연산 별도 처리 없이 그대로 a = 5 b = -0.5 print(a+b) #실수형 -> 정수형 ; 기본 내장 함수 int 사용 a = (int)(10.) 지수 표현 방식 1e9 -> 10의 9제곱(1,000,000,000) INF = 1e9 print(INF) #2진수체계에서는 실수 정보 표현 한계, 미세한 오류 만들어냄 -> round() a = 0.3 + 0.6 print(a) #결과: 0.8999999 print(round(a,2)) #소수점 둘째자리에서 반올림 #결과: 0.9 *연산 나누기 / (-> C++과 같이 딱 떨어지게 나오는게 아니라 실수형으로 나옴) 나..