따..딱히 공부하려고 포스팅하는 건 아니니까..!

참고사이트http://hannom.tistory.com/36http://hannom.tistory.com/37

1. 힙 자료구조 최솟값 혹은 최댓값을 빠른 시간에 접근하도록 만들어진 자료구조 2. 자료구조의 특징1) 각 노드의 값이 자식노드의 값들보다 크거나 작다 2) 완전 이진 트리(complete binary tree)이다3) 트리의 마지막 층에 있는 이파리 노드들은 왼쪽부터 꽉 차 있는 형태를 가진다4) 순서는 위->아래, 왼쪽->오른쪽5) 왼쪽 노드와 오른쪽 노드의 순서는 상관 없다 3. 노드k는 높이, i는 정수이고 i번째 노드라고 할때, 힙 크기 : 2^k -1부모 노드 : i/2왼쪽 자식 노드 : 2i오른쪽 자식 노드 : 2i+1 4. 알고리즘 구현 힙 자료구조의 특징(완전 이진트리)을 이용한 알고리즘으로, 데이터를 모두 힙에 넣었다가 다시 꺼내서 정렬하는 것이다. 1) DownHeap 함수의 내용 ..

정렬 알고리즘은 말그대로 정렬하는 알고리즘이다. 1. 분류 1) 내부정렬 입력의 크기가 주기억 장치의 공간보다 크지 않은 경우에 수행되는 정렬 2) 외부정렬 입력의 크기가 주기억 장치의 공간보다 커, 보조 기억 장치에 있는 입력을 여러 번 나누어 주기억 장치에 읽어들인 후, 보조 기억 장치에 다시 저장하는 과정을 반복하는 정렬 2. 알고리즘 1) 버블 정렬 이웃하는 숫자를 비교하여 작은 수를 앞쪽으로 이동시키는 과정을 반복하여 정렬, 즉 마지막 값이 가장 큰 값이 되도록 만드는 것 2) 선택 정렬 입력 배열 전체의 최솟값을 선택하여 배열의 0번의 값과 바꾸고 0번을 제외한 나머지 원소에서 위의 과정을 반복하는 방법 3) 삽입 정렬 정렬이 된 부분과 안된 부분으로 나누고 정렬이 안된 부분의 가장 왼쪽 원소..

인접 리스트(Adjacency List) 정의 각각의 정점에 인접한 정점들을 연결 리스트로 표시한 것 특징1) 각 연결 리스트의 노드들은 인접 정점을 저장2) 연결 리스트들은 헤더 노드를 가지고 있고 헤더 노드들은 하나의 배열로 구성되어 있다.3) 정점의 번호를 이용하여 배열의 인덱스에 접근할 수 있으므로 정점 리스트에 쉽게 접근할 수 있다.4) 정점의 개수에 비해 연결된 선분이 적을 때 사용하면 좋다 #include using namespace std; // enum으로 정점을 숫자로 치환, 배열을 이용하여 다시 되돌림enum vertices{ a, b, c, d, e, f };char vertices[] = { 'a', 'b', 'c', 'd', 'e', 'f' }; typedef int LData;..

퀵 정렬 (Quick Sort) - 정의 : 2개의 부분문제로 분할하나 각 부분문제의 크기가 일정하지 않은 형태의 분할 정복 알고리즘- 문제점 : 정복 후 분할하는 특징이 있어 이 정렬을 수행하기 위해 다시 정렬(Sort)를 해주어야 하는 문제가 있다. 최악 경우 시간복잡도 : O(n^2)최선 경우 시간복잡도 : 피봇과의 비교횟수 X 층수 = O(n) X log2n = O(nlog2n) - 피봇 선정 방법: 퀵 정렬의 불균형한 분할을 완화하기 위해 피봇 선정 방법이 생김 1) 랜덤2) 세 숫자의 중앙값으로 선정하는 방법 : 가장 왼쪽, 중간, 가장 오른쪽 숫자 중에서 중앙값을 피봇으로 정한다.ex) 가장 왼쪽 숫자 11, 중간 숫자 1, 가장 오른쪽 숫자 20이라고 할때 가장 중간에 가까운 11을 피봇으..

분할 정복 알고리즘 주어진 문제의 입력을 분할하여 문제를 해결(정복)하는 방식의 알고리즘 분류 분할되는 부분문제의 수와 부분문제의 크기에 따라 분류 1) 합병 정렬(Merge Sort)2) 퀵 정렬(Quick Sort)3) 선택 문제(Selection)4) 최근접 점의 쌍 찾기(Closest Pair) 1) 합병 정렬 (Merge Sort) 정의 : 입력이 2개의 부분문제로 분할되고, 부분문제의 크기가 1/2로 감소하는 분할 정복 알고리즘 합병의 시간복잡도 : 2개의 정렬된 두 배열의 크기가 각각 n, m 일때, 최대 비교 횟수는 n+m-1, 시간복잡도는 O(n+m)합병 정렬의 공간복잡도 : O(n)합병 정렬의 시간복잡도 : 층수 X O(n) = log2n X O(n) = O(nlogn) 외부 정렬의 기..

배열리스트(Array List) 연결리스트(Linked List) 특징 메모리가 연속적으로 배치 배열의 단점을 극복하기 위해 만듬 장점 1. 데이터의 참조가 쉽다. 즉, 인덱스값을 기준으로 어디든 한번에 참조 가능 1. 크기가 유동적이다 2. 메모리 중간에 삽입/삭제가 자유롭다. 단점 1. 배열의 길이가 정해져있다.(변경 불가) 2. 중간에 메모리의 삽입 삭제가 번거롭다 1. 포인터 공간이 하나이상이 추가되어서 메모리가 크다. 2. 메모리 할당/삭제때문에 성능 저하 ∴ 삽입/삭제가 필요할 때 : 리스트 크기가 작거나 빈공간에 채우는 방법이 필요할 때 : 배열