알고리즘 | 유클리드 알고리즘(최대공약수)
유클리드 알고리즘 (최대공약수) 최대 공약수A = aG; (280 = 2810)B = bG; (30 = 310) A-B = aG - bG = (a-b) * G(a-b) 와 b는 역시 서로소 이므로 A-B와 B의 최대 공약수는 역시 G [뺄셈 이용] -> 성능 최악 임의의 두 정수 u와 v를 입력 받는다 v가 u보다 크다면 v와 u의 값을 교환한다 u
Category: algorithm
알고리즘 | 선택정렬
선택 정렬(Selection Sort) 정렬 되지 않은 데이터들에 대해 가장 작은 데이터를 찾아 가장 앞의 데이터와 교환해나가는 방식 선택 정렬의 비교 횟수= (n-1) + (n-2) + (n-3) + … + 1= n(n-1)/2 시간 복잡도 평균, 최악, 최고: O(n^2) 기존의 레코드들이 정렬이 되어 있던, 되어 있지 않던 상관 없이 레코드들의 가장
알고리즘 | 삽입정렬
삽입정렬(Insert Sort) 데이터 집합을 순회하면서 정렬이 필요한 요소를 뽑아내어 이를 다시 적당한 곳에 삽입해 나가는 알고리즘 아직 정렬 되지 않은 임의의 데이터를 이미 정렬 된 부분의 적절한 위치에 삽입해가며 정렬하는 방식 시간 복잡도 최선 list가 이미 정렬 되어 있는 경우에는 외부 루프 n-1번만 실행되고 각 단계에서 데이터의 이동 없이
알고리즘 | 버블정렬
버블정렬(Bubble Sort) 데이터 집합을 순회하면서 집합 내의 이웃 요소들끼리의 교환을 통해 정렬을 수행 제일 큰 원소를 오른쪽으로 옮기는 방법 버블 정렬의 비교 횟수= (n-1)+(n-2)+…+(n-(n-2))+(n-(n-1))= (n-1)+(n-2)+…+3+2+1 = (n-1)(n/2)비교횟수 T(n)= (n(n-1))/2 시간복잡도 평균, 최악
알고리즘 | start
Categories 알고리즘 | 개념 자료구조의 분류 선형구조: 선형리스트(배열), 연결 리스트, 스택, 큐, 데크 비선형 구조: 트리, 그래프 정렬(Sorting) 알고리즘 | 정렬 시간복잡도 내부 정렬 소량의 데이터를 주기억장치에만 기억시켜서 정렬하는 방식 알고리즘 | 버블정렬 알고리즘 | 삽입정렬 알고리즘 | 선택정렬 알고리즘 | 퀵정렬 알고