코딩인터뷰 퀘스천"메모" 그래프 알고리즘, 정렬

.

.

책 읽으면서 메모했던 내용들 옮겨봅니다.

​

-

​

챕터9 그래프 알고리즘

서울에서 뉴욕까지 가는 가장 빠른 노선은? 같이 객체간의 관계에 대한 정보 자료구조가 그래프.

정점 노드들의 집합 V와 간선(정점의 쌍)들의 집합 E를 사용하여 (V, E)로 나타냄.

Directed Edge : 방향성을 가지는 간선

Undirected Edge : 방향을 가지지 않은 간선

Directed Graph

Undirected Graph

​

그래프 어플리케이션

전자 회로 컴포넌트간 관계 표현,

운송 네트워크, 컴퓨터 네트워크, 데이터베이스

​

챕터10 정렬

정렬 알고리즘의 분류 기준

비교 횟수(최선은 O(nlogn), 최악은 O(n^2) 복잡도)

도치(값 교환) 횟수, 메모리 사용, 반복, 안정성, 작용성

​

비교 기반 정렬 알고리즘

버블 정렬 O(n^2): 간단. i와 i+1 요소 비교, 도치. 마지막까지 반복.

선택 정렬 O(n^2): 작은 양의 데이터 유용. 키 기반 선택. 제자리 정렬. 최소값을 선택, 앞으로 보냄.

삽입 정렬 O(n^2): 간단, 효과적. 매 반복마다 뒤쪽 정렬되지 않은 요소를 앞쪽에 이미 정렬된 목록에 삽입.

셸 정렬 O(n): 증분감소 정렬.삽입 정렬 일반화. 여러 개의 부분으로 나눠 삽입 정렬로 사전 정렬 수행. 부분 배열의 크기가 계속줄어듬. = 증분. 중간크기 정렬에 적합, 큰 정렬에 부적합.

병합 정렬 : 분할 정복의 좋은 예. 두 부분으로 나누고 하나로 조합. 재귀적 처리. 퀵 정렬의 보완.

힙 정렬 : 우선 순위 큐 챕터 참고.

퀵 정렬 : 분할 정복의 좋은 예. 분할 교환 정렬이라고도 함. 재귀 호출. 비교 기반 알고리즘 중 가장 유명.

피봇 지점 선택. 두 부분으로 분할. 피봇보다 작은 값, 큰 값. 재귀적으로 반복. 피봇이i번째면 i-분할.

트리 정렬 : 이진 탐색 트리 사용. 탐색트리 내 적절한 위치에 위치시킴. 1= 배열 요소들로 이진 탐색 트리 생성. 2= 중위 운행법으로 이진 탐색 트리 운행. 정렬된 배열 얻음.

​

선형 정렬 알고리즘

계수 정렬(Counting Sort) : 각 입력 요소 X에 대해, X보다 작은 요소의 수를 결정. X를 적당한 곳에 위치시키는데 사용.가령, X보다 작은 요소가 10개 있다면X는 결과의 11번째에위치.

버킷 정렬 : 계수 정렬을 일반화한 것. i번째 카운터는 i번째 요소가 나타난 횟수 저장. 두 개의 버킷을 사용, 퀵 정렬 효율화 시킨 형태.

기수 정렬(Radix Sort) : 숫자의 자릿수, 문자수에 종속적. 자릿수로 정렬하고, 끝에서 두 번째 자릿수로 정렬하고 마지막 자릿수로 정렬할 때 안정성을 가진 정렬 알고리즘을 사용.

토폴로지 정렬 : 그래프 알고리즘 챕터 참조

.

.

.