SMALL CS study/Algorithm9 3. 완전검색, 분할정복 최적해 문제를 푸는 방법 완전 검색 → 중복 제거 → 개선된 알고리즘 완전 검색 알고리즘 → 분할정복, 그리디기법, 동적 계획법 완전 검색 문제의 해를 얻기 위해 가능한 모든 경우들을 나열해보고 확인하는 기법 문제에 포함된 자료의 크기가 작을 경우 유용 해답을 찾지 못할 확률이 적음 단점 문제의 크기가 커지면 시간 복잡도가 매우 크게 증가 속도 문제로 인해 그리디기법, 동적계획법 등을 이용해서 효율적인 알고리즘을 찾아나가야 함 분할 정복 "분할 + 정복 + 통합"의 Top-Down 방식 분할 : 해결할 문제를 여러 개의 작은 부분 문제들로 분할 정복 : 나눈 작은 문제들을 각각 해결 통합 : 해결된 답들을 모음 예시 : 퀵 정렬, 병합 정렬, 이진검색, 거듭제곱 2021. 8. 26. 2. 부분집합, 순열, 조합 부분집합 비트연산자를 이용 # A : 집합A 리스트 N = len(A) for i in range(1 2021. 8. 12. 1. 정렬 알고리즘 정렬 알고리즘 알고리즘 평균 최악 기법 특징 버블 정렬 O(n^2) O(n^2) 비교, 교환 쉬움 카운팅 정렬 O(n+k) O(n+k) 비교환 n이 작을때만, k는 정수의 최대값 선택 정렬 O(n^2) O(n^2) 비교, 교환 교환 수가 버블, 삽입 보다 적음 퀵 정렬 O(n logn) O(n^2) 분할 정복 평균적으로 가장 빠름 삽입 정렬 O(n^2) O(n^2) 비교, 교환 n의 개수가 작을 때 효과적 병합 정렬 O(n logn) O(n logn) 분할 정복 링크드리스트의 경우 가장 효율적 힙 정렬 O(n logn) O(n logn) 힙 자료구조 버블 정렬 첫 번째 원소부터 인접한 원소끼리 자리를 교환하면서 맨 마지막 자리까지 이동 한 단계가 끝나면 가장 큰 원소 또는 가장 작은 원소가 마지막 자리로.. 2021. 8. 11. 이전 1 2 다음 LIST
