돌딤

노트정리/자료구조

계산 복잡도 - 빅오 표기법(big O)

직접 구현하지 않고서도 알고리즘의 효율성을 따져보는 기법으로 알고리즘의 복잡도 분석이 있다.이 방법에는 2가지 방법이 있는데 알고리즘의 수행시간을 분석하는 시간 복잡도 , 알고리즘이 사용하는 기억공간을 분석 하는공간 복잡도가 있다. 알고리즘 복잡도를 이야기할 떄는 대게 시간 복잡도를 뜻하며 시간 복잡도의 표시는 빅오 표기법(big-oh notation)으로 한다. 빅오 표기법(Big-Oh Notation) 1. 시간 복잡도 표기법시간 복잡도 함수 중에서 가장 큰 영향력을 주는 n에 대한 항만을 표시함.O(3n+2) = O(3n) = O(n)이 된다.2. 수학적 정의모든 N >= N0 에 대해서 f(N) n0인 모든 n에 대해 f(n) < c g (n)을 만족하는 2개의 양의 상수 c, n0 이 존재하면 ..

노트정리/자료구조

[그래프 알고리즘] 깊이 우선 탐색(DFS) 와 너비 우선 탐색(BFS)

깊이 우선 탐색- 무방향 그래프에서 어떤 정점에 대하여 검색이 끝나면 인접한 정점 중 검색하지 않은 정점을 찾아가 다시 검색하는 방법.무방향 그래프 G(V,E)를 구성하는 V(G)에 속하는 모든 정점들을 방문하는 방법을 그래프의 운행이라 하고, 스택을 이용하는깊이 우선 검색(DFS)과 큐를 이용하는 너비 우선 검색(BFS) 방법이 있다.탐색 과정- DFS는 정점의 방문 시 최근의 주변 정점을 먼저 방문함.- 시간 복잡도 O(| V |^2) DFS 너비 우선 탐색- 무방향성 그래프에서 어떤 정점을 검색하고 그 정점에 인접한 모든 정점들을 검색한 후 이정점에 인접한 모든 정점들을 검색하는 방법으로 큐를 이용.탐색 과정- 무방향 그래프G(V,E)에서 시작하며 정점 V를 방문한 후 V에 인접한 아직 방문하지 않..

노트정리/자료구조

정렬 알고리즘 3부 - 계수,기수,버킷 정렬

계수 정렬계수 정렬은 입력키가 어떤 범위, 예를 들어 1부터 k 사이의 작은 정수 범위에 있다는 것을 알고 있을 때에만 적용할 수 있는 방법으로어떤 입력 키 x의 정렬 위치는 x보다 작은 키가 몇 개나 입력에 나타나는지를 알면 결정할 수 있다. 예를 들어 입력키들이숫자일 때 입력에 10이라는 키가 있고 이보다 작은 키가 5개 있다면 10 은 정렬 순서에서 여섯 번째에 위치한다. 계수 정렬에서는입력키들이 범위 k 내의 각 값에 대하여 입력키가 실제로 입력에 나타나는 횟수를 계산한다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676..

노트정리/자료구조

정렬알고리즘2부 - 퀵,합병,히프 정렬

퀵 정렬 퀵 정렬 의 기본 개념은 기준이 되는 숫자 피벗을 정한 후에 그 숫자를 기준으로 작은 데이터와 큰 데이터를 나누고 다시분리한 양쪽의 데이터에서 다시 기준이 되는 숫자를 정한 후 그숫자를 기준으로 작은 데이터와 큰 데이터를 나누는 작업을반복하는 것입니다.. 이러한 작업을 위해선 기준이 되는 값보다 작은 값을 찾기 위한 인덱스와 큰 값을 찾기 위한인덱스가 필요합니다..작은 값을 찾기 위한 인덱스는 왼쪽에서 진행하고 큰 값을 찾기 위한 인덱스는 오른쪽부터 진행합니다.왼쪽에서 진행하는 인덱스는 기준값보다 크거나 같은 경우에 멈추고 오른쪽에서 진행하는 인덱스는 기준값보다 작거나 같은경우에 멈춥니다. 그 상태에서 해당 인덱스에 위치한 데이터의 위치를 서로 바꿉니다. 이 작업을 반복하면 기준값을 기준으로 좌..