_스타디/알고리'듬' 03_stack&queue 스텍 큐 Stack : 잘 알다시피 입구와 나가는곳이 같다. 문어같은거 생각하면 편함. 문어도 구멍이 하나여서 거기로 먹고 뱉음 First in Last Out 이다. 먼저집어넣으면 젤 아래 들어가서 꺼내기 위해선 나머지 다 빼야함. 스택을 구현하는 법 : 1. 배열로 구현하기 원래대로라면 하나 들어올때마다 하나씩 밀어야하나 그러기엔 복잡하니까 그냥 그 뒤에다 넣는걸로 가정하자. 아무튼 그러면 다 받는데 이걸로 받으면 문제점이 배열을 처음에 선언할때 크기를 지정해뒀어야해서 다 차버리면 방법이 없다는 점이다. STATIC이라서 어느 정도 이상 들어갈 수 없음. #include using namespace std; int main(){ int arr[10] = {0,}; //size : 10 int count = 0.. _스타디/알고리'듬' 2021. 7. 16. 02:08 03-divide and conquer -Quick sort Divide and conquer 하는법 1. 어떤 문제를 작게 쪼개야 할 때. 2. 충분히 작지 않으면 충분히 작아질때까지 쪼개기. 3. 필요하다면 합쳐서 필요한 답 찾기 *Divide and conqure 쓰면 안될 때 -버블정렬이 더 빠를 때 -나누었더니 나누어진 사이즈가 원래 사이즈와 거의 같을 때. -나누었더니 그 문제의 크기만큼 작은 문제들로 나누어질때.(ex. 펙토리얼) 새 기술 : 퀵소트 Quick sort 아무배열이 들어오면 그중 아무 숫자나 하나 잡아서 그 숫자를 기준으로 정렬을 한다. 최악의 경우에는 O(n2)번의 비교를 수행하고, 평균적으로 O(n log n)번의 비교를 수행한다. 예를 들어 17 22 27 12 15 37 54 가 있다고 하고 아무튼 피봇으로 22를 고르면 17 1.. _스타디/알고리'듬' 2021. 7. 8. 23:30 02-Divide_and_Conquer_분할정복 큰 배열이 있으면 이걸 반쪼가리 낸다. (divide) 정렬되어있어야 계산하기 편하니까 정렬 할 수 있을 만큼의 크기가 되어야 한다. 그러니까 반쪼가리 또 낸다.(divide) 그걸 계속 반복하다보면 한칸단위로 나오게 된다. 한칸은 정렬(conquer)할 필요가 없기에 컴터가 딱보면 안다. 그럼 이제 크기비교를 해가면서 합치면 된다.(merge) 그렇게 다 비교해가면서 합치면(merge) 해결이 된다. 여야 하는데... 배열여러개 만들면 복잡하기에 그냥 커다란 한 배열로 해서 원래 배열 새 배열 이렇게 코드를 작성했습니다. 19부터 0까지 역으로 가져다 놓은걸 자기가 알아서 잘 세서 0부터 19까지 오름차순으로 해주는 코드 입니다. #include using namespace std; int *sorte.. _스타디/알고리'듬' 2021. 7. 6. 17:20 01-SORT-bubble, counting, selection, radix 버블 카운팅 셀렉션 라딕스 거품정렬 계수정렬 선택정렬 기수정렬 c++ c 20210704 1.버블정렬 bubble sort 라고도 하고 가장 무지성 정렬인것. #include using namespace std; void bubblesort(int arr[]) { int temp = 0; for (int i = 0; i < 5; i++) { //n for (int j = 0; j < i; j++) { //n-1 if (arr[j] < arr[j + 1]) { temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = temp; } } } } /* * 처음엔 n개를 비교함. * 그다음엔 n-1개 비교함. * ... * O(n^2) */ int main() { int arr[5] = { 7,4,5,1,3 }; bubblesort(arr); for (i.. _스타디/알고리'듬' 2021. 7. 5. 19:53 이전 1 다음
