반응형 개발/자료구조5 삽입정렬(Insertion Sort)이란 무엇일까? 삽입정렬 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘 해당 원소의 값과 앞의 원소들의 값을 비교해나가며 자신의 위치를 찾아서 삽입한다. 삽입을 하기 위해 데이터들의 이동이 불가피하여 데이터 양이 많아질 수록 효율이 저하된다. 시간복잡도 O(n^2) 이해를 돕는 이미지 이해를 돕는 영상 [C 코드] void insertion_sort ( int *data, int n ) { int i, j, remember; for ( i = 1; i = 0 && remember < data[j] ){ //선택된 원소값이 비교하는 원소의 값보다.. 2020. 12. 31. 버블정렬(Bubble Sort, Sinking Sort)이란 무엇일까? 버블정렬 두 인접한 원소를 비교하여 정렬하는 방법 시간 복잡도가 O(n^2)로 상당히 느리다 양방향으로 번갈아 수행하면 칵테일 정렬이 된다. 버블정렬은 이해하기 쉽고 코드도 간단하지만 시간복잡도 때문에 비교할 데이터의 개수가 많아질수록 성능이 저하됩니다. 이해를 돕는 영상 [C++] int* bubble_sort(int arr[], int n) { int i, j, temp; for (i=n-1; i>0; i--) { for (j=0; j arr[j+1]) { //앞에 값이 더 크기때문에 서로 스왑 temp = arr[j]; arr[j] = arr[j+1]; arr[j+1] = temp; } } } return arr; } 2020. 12. 30. 선택정렬(Selection Sort)란 무엇일까? 선택정렬 제자리 정렬 알고리즘중 하나이다. O(n2)만큼의 시간이 걸린다. 메모리가 제한적인 경우 사용시 성능 상의 이점이 있다. 선택정렬은 다음과 같은 순서로 이루어집니다. 1. 첫번째 인덱스에 들어갈 리스트중 최소값을 찾는다. 2. 찾은 최소값과 첫번째 인덱스 값을 교체한다. 3. 두번째 인덱스로 넘어간다. 4. 1~2방법을 반복하며 마지막인덱스까지 진행한다. 이해를 돕는 영상 [C++] void selectionSort(int *list, const int n) { int i, j, indexMin, temp; for (i = 0; i < n - 1; i++) { indexMin = i; for (j = i + 1; j < n; j++) { if (list[j] < list[indexMin]) { .. 2020. 12. 29. Stack(스택)이란 무엇일까? "Stack"은 사전적 의미로 (보통 깔끔하게 정돈된) 무더기[더미] (깔끔하게 정돈하여) 쌓다[포개다]; 쌓이다, 포개지다 라고 합니다. 자료구조에서 스택이란 데이터와 같은 것을 쌓다가 맞는 표현인 것 같습니다. 일반 적으로 쌓은 물건을 꺼낼때 어떻게 할까요? 가장 마지막에 쌓은 물건을 하나씩 꺼내 써야 합니다. 그림으로 표현 하자면 스택은 이렇게 마지막으로 입력된 데이터가 먼저 출력되는 방식입니다. LIFO(Last in First out)이라고도 합니다. 활용 예를 들어보면 문서작업할때 작업을 할때 마다 행동 하나하나가 스택에 쌓이고 되돌리기(Ctrl+z)를 사용하면 마지막 행동을 하나씩 다시 불러옵니다. 2020. 9. 20. Queue(큐)란 무엇일까? "Queue"는 사전적인 의미로는 무엇을 기다리는 줄, 또는 대기 행렬이라고 합니다. 즉 대기열, 기다리는 줄이죠. 마치 일상생활에서의 버스를 기다리는 줄 같은 것입니다. 버스 줄은 새치기를 하지 않는 이상 먼저 기다렸던 사람부터 버스에 타기 시작합니다. 프로그래밍에서도 같은 개념입니다. 그럼 그림으로 나타내보겠습니다. "Queue"는 이렇게 입력 시 대기열의 마지막에 저장되고 큐에서 대기 중인 것을 순서대로 하나씩 출력시킵니다. "FIFO(First In First Out)" 자료구조입니다. 말 그대로 먼저 들어온 것이 먼저 나가는 말입니다. Queue는 언제 사용할까요? 바로 어떤 작업을 순서대로 실행시키기 위해 사용됩니다. 예를 들면 턴 제 게임에서 차례대로 1번 스킬 2번 스킬 3번 스킬을 한번에.. 2020. 9. 18. 이전 1 다음 728x90
