알고리듬

기반컴퓨팅에서 알고리듬의 역할시작하기함수의 성장분할 정복확률적 분석과 무작위 알고리듬정렬과 순서 통계힙 정렬퀵 정렬선형 시간 내 정렬중앙값과 순서 통계자료 구조기초 자료 구조해시 테이블이진 탐색 트리레드 블랙 트리자료 구조 증강하기고급 설계와 분석 기법동적 프로그래밍탐

알고리듬 algorithm은 어떠한 값 혹은 값의 집합을 입력 input으로 받아 어떤 값 혹은 값의 집합을 출력 output으로 내놓는 잘 정의된 계산 과정. 즉, 알고리듬이란 입력을 출력으로 만드는 순차적 계산 과정.알고리듬은 잘 정의된 계산 문제 computati

2. 시작하기 2.1 삽입 정렬 삽입 정렬은 정렬 문제 sorting problem을 해결함. 입력: n 개의 순차적 숫자 <a1, a2, …, an>. 출력: 입력에 대해 a'1 ≤ a'2 ≤ … ≤ a'n을 만족하는 (재배열한)

3. 함수의 성장 알고리듬의 실행 시간 성장률을 통해 알고리듬의 효율성을 간단하게 알 수 있고 다른 알고리듬과 비교해 상대적으로 성능을 비교할 수 있음.

분할: 문제를 동일한 여러 하위 문제로 분할정복: 하위 문제들 재귀적/직접적으로 해결.결합: 하위문제의 해법을 결합해 원본 문제의 해법 겟.하위 문제가 재귀적으로 풀 수 있을 만큼 클 때 이를 재귀 명제 recursive case라 부름. 재귀적으로 풀 수 없을 만큼

중간에 5편인 확률적 분석 및 무작위 알고리듬은 스킵했습니다.합병정렬처럼 O(n lg n)임."힙"이라는 자료구조 사용해서 정보 관리. 힙 정렬에 있어 힙이 제일 유용할 뿐만 아니라 효율적인 우선순위 큐 만드는데 좋음."힙"이 원래 힙 소트에서 온 거긴 한데, "가비지

최악의 경우 Θ(n2). 그럼에도 평균의 경우에서 Θ(n lg n)이고, 여기에 숨은 상수도 값이 작아서 상당히 효율적임. 게다가 공간 복잡도도 Θ(1)고, 특히 가상 메모리 환경에서 잘 돎.퀵 정렬도 합병 정렬도 분할정복 패러다임. 부분열 Ap..r에 대한 분할정복

이 단원에서 다루는 중요한 세 가지: 동적 프로그래밍 (15 단원), 탐욕 알고리듬 (16 단원), 분할 상환 분석 (17 단원).동적 프로그래밍은 보통 최적의 해를 구하는 문제를 풀 때, 그 도중에 몇 가지 선택을 해야하는 경우 적합함. 이때 보통 선택지가 전부 동