본문 바로가기
728x90

ALGORITHM/개념 정리15

[Algorithm] 탐욕 알고리즘 (Greedy Algorithm) 탐욕(Greedy) 알고리즘 최적해를 구하는 데 사용되는 근시안적 방법 여러 경우 중 하나를 결정해야 할 때마다 그 순간에 최적이라고 생각되는 것을 선택하여 최종 해답에 도달 ex) 거스름 돈의 지폐/동전 개수 최소화 각 선택의 시점에서 이루어지는 결정은 지역적으로는 최적이지만, 그 선택들을 계속 수집하여 최종적인 해답을 만들었다고 하여 그것이 최적이라는 보장은 없음 탐욕 알고리즘 동작 과정 해 선택 : 현재 상태에서 부분 문제의 최적 해를 구한 뒤, 이를 부분해 집합(Solution Set)에 추가 실행 가능성 검사 : 새로운 부분해 집합이 실행 가능한지 확인, 문제의 제약 조건을 위반하지 않는지 검사 해 검사 : 새로운 부분해 집합이 문제의 해가 되는지 확인 해 검사 : 아직 전체 문제의 해가 완성되.. 2021. 8. 22.
[Algorithm] 검색 - 완전 검색, 순차 검색, 이진 검색 검색/탐색 알고리즘 (Search Algorithm) 저장되어 있는 자료 중에서 원하는 항목을 찾는 작업 탐색 키(Search Key) : 자료를 구별하여 인식할 수 있는 키 완전 검색(Exaustive Search) 문제의 해법으로 생각할 수 있는 모든 경우의 수를 나열해보고 확인하는 기법 수행 속도 느리지만 해답 찾아내지 못할 확률 작음 경우의 수가 상대적으로 작을 경우 유용 문제 풀 때 완전 검색으로 해답 도출 후, 성능 개선 위해 다른 알고리즘 사용하고 해답 확인하는 것이 바람직 완전 검색 종류 Brute-force : for문 사용하여 처음부터 끝까지 탐색 👉 Brute-force 적용해보기 비트 마스크 : 비트 연산 사용(&, |, ^, ~, ) 백트래킹 : 해를 찾아가는 도중 해가 될 가능성.. 2021. 8. 20.
[Algorithm] 정렬 - 버블정렬, 카운팅 정렬, 선택 정렬 정렬 (Sort) 데이터를 정해진 순서대로 나열 대표적인 정렬 방식 버블 정렬 카운팅 정렬 선택 정렬 퀵 정렬 삽입 정렬 병합 정렬 arr = [5, 6, 2, 9, 7, 1, 8, 3, 4, 0] 위와 같은 배열을 오름차순 정렬한다고 할 때, 정렬별로 어떻게 구현할 수 있을까? 버블 정렬 (Bubble Sort) 인접한 두 개의 원소를 비교하며 자리를 계속 교환하는 방식 첫 번째 원소부터 인접한 원소끼리 계속 자리를 교환하면서 맨 마지막 자리까지 이동 (가장 큰 원소부터 맨 마지막 자리에서 점점 앞으로 채워 넣기) 비교와 교환 O(n^2) # Bubble sort def BubbleSort(arr): for i in range(len(arr)-1, 0, -1): for j in range(0, i): .. 2021. 8. 16.
728x90

티스토리툴바