삽입 정렬 : 점진적인 방법 사용 원소 A[j]를 정렬된 부분 배열 A[1 .. j-1]의 적절한 위치에 삽입 2.3.1 분할정복 접근법 재귀적 구조 : 주어진 문제를 풀기 위해 자기 자신을 재귀적으로 여러 번 호출함으로써 밀접하게 연관된 부분 문제를 다룸. => 분할정복 접근법 분할정복 접근법 : 전체 문제를 원래 문제와 유사하지만 크기가 작은 몇 개의 부분 문제로 분할하고, 부분 문제를 재귀적으로 품. 찾은 해를 결합하여 원래 문제의 해를 만들어 낸다. 분할정복의 3단계 ...
2.2 알고리즘의 분석 알고리즘의 분석은 그 알고리즘을 실행하는 데 필요한 자원을 예측하는 것을 의미한다. 메모리, 통신 대역, 하드웨어 등 대부분은 계산 시간을 의미한다. 이 책에서의 가정 알고리즘은 단일 프로세서와 랜덤 접근 기계(RAM, random-access machine) 모델로 가정 : 명령어는 동시X, 하나씩 실행 산술 연산, 데이터 이동연산, 제어 연산 등 : 상수 시간 RAM 모델의 데이터형 : 정수(integer)와 부동소수(floating point) 각 워드 크기에 제한을 가정 : 입력 크기가 n인 입력을 다룰 때 정수는 상수 c>= 1에 대해 clg2비트로 표현된다고 가정(워드는 상수로 처리하므로 너무 크면 안된다.) ...
2.1 삽입정렬 정렬문제 입력 : n개 수들의 수열 $$ <a_1, a_2, …, a_n> $$ 출력 : $$ a’_1 <= a’_2 <= … <= a’_n $$ 을 만족하는 입력 수열의 순열(재배치) $$ <a’_1,a’_2, …, a’_n> $$ 정렬하고자 하는 숫자를 키라고 한다. 의사코드와 “실제” 프로그램 코드의 차이는, 의사 코드에서는 알고리즘을 가장 분명하고 간결하게 서술할 수 있다면 어떤 표현 방법을 사용해도 좋음. 영어, 한글 문장등이 들어갈 수 도 있음. 데이터 추상화, 모듈화, 오류처리 등의 소프트웨어 공학 관점의 문제를 고려하지 않음. ...