분할통치4 [알고리즘] ep5-3++) 분할통치법 vs DP 문제) 여행의 최소비용을 구하는 알고리즘을 작성하라.airtelDC(분할통치 버전)와 airtelDP(동적프로그래밍 버전)를 구현하고 실행시간을 비교 프로그램 요구사항: 1) 각 해결버전의 정방향, 역방향 버전 가운데 자유롭게 하나를 선택하여 구현하라. 2) 출력예시: 최종적으로 다음과 같이 인쇄되어야 한다. ※ 참고1) 아래는 MAX = 30인 경우의 인쇄결과임.2) X.XXXXXXXX는 cputime in milliseconds. 주의:반드시 아래 가이드라인의 main 함수 내용과 동일하게 실행하고 출력을 구하라.n = 6로 한 테스트실행 결과가 수작업실행 결과와 일치하는지 확인한 후 n = MAX로 한 본실행을 시도할 것.경로가 아닌 최소비용만을 요구하는 문제이므로, 만약 최소비용 경로가 두 .. 2024. 7. 24. [알고리즘] 정렬 알고리즘 선택 매뉴얼 ㅇ버블정렬 - 실무에서는 아예 사용하면 안된다"제자리 + stable" O(n^2) ㅇ선택정렬: 우선순위 큐 (무순 리스트로 구현)"제자리 + unstable" O(n^2): 느리다 - 소규모 입력에 적합 ㅇ삽입정렬: 우선순위 큐 (순서 리스트로 구현)"제자리 + stable" O(n^2): 느리다 - 소규모 입력에 적합 ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ ㅇ힙정렬: 우선순위 큐 (힙으로 구현)"제자리 + unstable" O(nlog(n)): 빠르다 - 대규모 입력에 적합 ㅇ병합정렬: 분할통치"제자리 X + stable" O(nlog(n)): 빠르다 - 초대규모 입력 + stable 결과에 적합 ㅇ퀵정렬: 분할통치"제자리 + unstable".. 2024. 7. 7. [알고리즘] ep1-6) 퀵정렬(quick sort) ㅇ퀵정렬(quick sort): 분할통치법에 기초한 정렬 알고리즘"제자리 + unstable" O(nlog(n))※ 최악의 시간 복잡도: O(n^2) (이미 정렬된 리스트에서 항상 최악의 피벗을 선택하는 경우) 이름에서 알 수 있듯이 복잡하지만 매우 효율적인 알고리즘이다 일각에서는 이렇게 지칭한다 '살아있는 레전드' *피벗(pivot): 기준점1. 피벗을 기준점으로 잡는다2. 피벗보다 작으면 왼쪽에, 피벗보다 크면 오른쪽에 둔다3. 왼쪽과 오른쪽을 각각 정복한다 [분할 함수(partition 함수) 과정] 다양한 피봇 선정 방식 -> 다양한 퀵소트 버전 (참고)퀵정렬 트리: quickSort의 실행을 이진트리로 보이기이진트리의 각 노드는 quickSort의 재귀호출을 표현하며 다음을 저장- 실행.. 2024. 7. 7. [알고리즘] ep1-5) 병합정렬(merge sort) ㅁ분할정복법 == 분할통치법(Divide and Conquer): 문제를 작은 부분으로 나누어 해결한 후, 그 결과를 결합하여 전체 문제를 해결하는 방법e.g. 병합정렬, 퀵정렬, 이진탐색, 하노이탑 ㅇ병합정렬 = 합병정렬(merge sort): 비교 기반의 정렬 알고리즘 중 하나로, 분할 정복 기법을 사용"제자리 X + stable" O(nlog(n))폰 노이만이 개발했으며 stable 특성 때문에 실무에서 많이 사용된다 병합(merge) 예시 - 연결리스트로 구현한 merge 함수 (참고) 합병정렬 트리: mergeSort의 실행을 이진트리로 보이기이진트리의 각 노드는 mergeSort의 재귀호출을 표현하며 다음을 저장한다- 실행 이전의 무순리스트 및 분할- 실행 이후의 정렬리스.. 2024. 7. 5. 이전 1 다음
