본문 바로가기

알고리즘 개념14

스택(Stack), 큐(Queue) 스택- 제일 나중에 들어온 원소가 제일 먼저 나가는 구조 ( LIFO - Last In First Out )- 알고리즘보다는 자료구조에 가까운 개념이다.  -> 알고리즘은 이러한 스택이나 큐를 이용해서 문제를 해결하는 방법이다. #include#includeusing namespace std;int main(){ stack s; s.push(7); s.push(5); s.push(4); s.pop(); s.push(6); s.pop(); while(!s.empty()){ cout - STL 라이브러리 문법을 이용해 사용한다.- 직접 구현해 볼 수 있지만 너무 간단하므로 생략하기로 한다. 큐- 들어온 것이 먼저 나가는 구조 ( FIFO - First In First Out ) #incl.. 2022. 2. 15.
계수 정렬 ( Counting Sort ) 계수 정렬'범위 조건'이 있는 경우에 한해서 굉장히 빠른 알고리즘 -> 속도 : O(N)단순하게 '크기를 기준'으로 세는 알고리즘 문제) 주어진 5 이하 자연수 데이터들을 오름차순 정렬하시오.     1 3 2 4 3 2 5 3 1 2 3 4 4 3 5 1 2 3 5 2 3 1 4 3 5 1 2 1 1 1크기를 기준으로 갯수만 세주면 되기 때문에 다른 정렬들처럼 위치를 바꿀 필요가 없다.모든 데이터에 한 번씩만 접근하면 된다는 점에서 매우 효율적이다. 초기 상태1 3 2 4 3 2 5 3 1 2 3 4 4 3 5 1 2 3 5 2 3 1 4 3 5 1 2 1 1 1크기 = 1크기 = 2크기 = 3크기 = 4크기 = 500000 1. 첫번째 상태1 3 2 4 3 2 5 3 1 2 3 4 4 3 5 1 2 .. 2022. 2. 15.
힙 정렬 ( Heap sort ) 힙정렬시간복잡도가 O(nlogn)으로 퀵정렬, 병합정렬과 같은 시간복잡도를 가진 정렬 알고리즘병합정렬과는 다르게 추가적인 메모리 필요 X항상 O(nlogn)의 성능을 보여주기 때문에 최악의 경우 O(n^2)의 성능을 보이는퀵정렬보다 안정적인 성능을 보인다.이론적으로는 퀵 정렬 병합 정렬보다 우위에 있지만, 단순히 속도만 가지고 본다면 퀵 정렬이평균적으로 더 빠르기 때문에 힙 정렬이 많이 사용되지는 않는다.배열을 최대힙 or 최소힙으로 만들어 root에 있는 값을 정렬하는 식으로 구현한다.힙(Heap)완전이진트리 형태의 자료구조힙은 최소힙과 최대힙 두가지로 나뉜다.힙은 일반적인 배열로 표현할 수 있다.  최대 힙 : "부모 노드 > 자식 노드"를 모든 노드에서 만족하는 완전이진트리   최소 힙 : "부모 .. 2022. 2. 11.
C++ STL sort() 함수 다루기 실제 알고리즘 대회에서 정렬 문제가 나올 때 빠르게 풀기 위해 sort()를 사용해 간단하게 정렬을 구현한다. sort() 헤더에 정의되어 있다. default 설정 => 오름차순으로 정렬 퀵 정렬을 기반으로 구현되어 있다. 퀵 정렬과 달리 모든 경우에 시간 복잡도 O(N * logN)을 보장한다. sort(start, end, 정렬기준); 사용 예시 1) sort(arr, arr + n); => 세번째 인자를 안 쓰면 default로 오름차순 정렬됨 2) sort(v.begin(), v.end()); => 세번째 인자를 안 쓰면 default로 오름차순 정렬됨 3) sort(v.begin(), v.end(), greater()); => 내림차순으로 정렬 4) sort(arr, arr + n, compa.. 2022. 2. 10.
병합 정렬 ( Merge sort ) 병합 정렬- 분할 정복(Divide & Conquer) 방법을 사용하는 알고리즘- 알고리즘을 구현함에 있어서 추가적인 임시 배열이 필요 ( 다른 정렬 알고리즘보다 메모리를 더 잡아먹음 )  시간 복잡도O(N * logN)   퀵 정렬 vs 병합 정렬퀵 정렬은 최악의 경우 O(N * logN) 을 보장하지 못함 ( 최악의 경우 => O(N^2) )병합 정렬은 최악의 경우에도 O(N * logN)을 보장함둘 다 O(N*logN)만큼 걸리더라도 보통 병합 정렬보다 퀵 정렬이 더 빠름 병합 정렬의 동작 원리 분할 ( 가장 작은 단위까지 분할 )   :   하나의 list를 두 개의 균등한 크기로 분할 정렬 ( 가장 작은 단위부터 정렬 )   :   분할된 부분 list를 정렬          =>  위 1,2 .. 2022. 2. 9.
버블 정렬 ( Bubble sort ) 버블 정렬- 바로 옆에 있는 값과 비교하면서 비교할 때마다 값을 스위칭하면서 이동- 선택 정렬과 시간 복잡도는 같지만 실제 수행시간이 가장 느림    => 버블 정렬 : 매번 비교할 때마다 값을 스위칭   => 선택 정렬 : 전체 원소를 비교해서 최솟값을 찾은 후 가장 마지막에만 값을 스위칭 시간 복잡도- O(N^2) #include#includeint main(){ int data[] = {1,5,9,8,2,5,6,3,7,10}; int i,j; for(i = 0; i data[j+1]) std::swap(data[j],data[j+1]); } } for(i=0;i 2022. 2. 9.

티스토리툴바