Vienna

오늘치 백준 문제를 풀려고 보니 힙정렬에 대한 언급이 나와 힙정렬에 대해 먼저 공부하고 싶었다. ◇ 힙? 부모의 값이 자식의 값보다 항상 크다는 조건을 만족하는 완전이진트리. (이때 부모의 값이 자식보다 항상 작아도 힙이라고 한다. 부모와 자식 요소의 관계만 일정하면 된다.) 부모와 자식 관계는 일정. 형제 사이의 대소 관계는 일정하지 않다. 이 때문에 부분순서트리(parttial ordered tree)라고도 한다. 힙의 요소를 배열에 저장하면 부모와 자식의 인덱스 사이에 다음과 같은 관계 성립 부모는 a[(i-1)/2] 왼쪽 자식은 a[(i-1)/2+1] 오른쪽 자식은 a[(i-1)/2+2] ◇ 힙 정렬? 선택 정렬을 응용한 알고리즘. 힙(heap)의 특성을 이용하여 정렬을 수행한다. 즉, "가장 큰..

오늘은 알고리즘 말고 유니티를 계속 마저할까 했는데 (유니티 교과서는 진짜 짧다. 벌써 4챕터 밖에 안 남았다 아마 정말 기초만 담았나보다.) 알고리즘은 하루 건너뛰면 왠지 빨리 잊을 것 같기도하고... 퀵 정렬이 꽤 재밌어서 빨리 그 다음 내용도 공부하고 싶어서 오늘도 알고리즘을 공부하기로 했다. 오늘도 화이팅! 1. 실습_6-9 #define _CRT_SECURE_NO_WARNINGS #include #include #define swap(type,x,y) do{type t=x;x=y;y=t;}while(0) void Quick(int a[], int left, int right) { int pl = left; int pr = right; int x = a[(pl+pr) / 2]; // 피벗 do {..

오늘은 C#을 좀 많이 공부해서 조금밖에 못할 것 같다. 하지만 오늘도 화이팅 1. 실습_6-6 셸 정렬 버전1 #define _CRT_SECURE_NO_WARNINGS #include #include void Shell(int a[], int n) { int i, j, h; for (h = n / 2; h > 0; h /= 2) { for (i = h; i = 0 && a[j] > tmp; j -= h) a[j + h] = a[j]; a[j + h] = tmp; } } } int main() { int i, nx; int* x; puts("셸 정렬"); printf("요소 개수: "); scanf("%d", &nx); ..

Q11. Q10의 알고리즘은 삽입할 위치의 검색은 빠르지만 삽입을 위해 요소를 하나씩 뒤쪽으로 미는 작업 비용이 단순 삽입 정렬 알고리즘과 같습니다. 요소를 뒤쪽으로 미는 작업을 표준 라이브러리의 memmove 함수를 사용해서 구현하면 비용을 줄여 좀 더 빠른 속도를 얻을 수 있습니다. 이 아이디어를 바탕으로 이진 삽입 정렬 함수를 수정하세요. 우선 memmove부터 찾아봐야겠다. 설명 해석: source의 num만큼의? 값들을 복사해 destination으로 복사한다. 복사는 중간버퍼를 사용하는데, 이미 데이터가 있다면 덮어 씌워질 수 있다. source와 destication 포인터가 가리키는 요소의 타입과 이 기능은 관련이 없다. null 체크는 하지 않고 항상 num bytes 만큼 복사한다. 오..

Q10. 단순 삽입 정렬을 배열의 요소 개수가 많아지면 많아질수록 요소 삽입에 필요한 비교, 대입 비용이 무시할 수 없을 정도로 커집니다. 이때 배열에서 이미 정렬된 부분은 이진 검색을 사용할 수 있기 때문에 삽입할 위치를 더 빨리 찾을 수 있습니다. 이진 검색을 사용하여 프로그램을 수정하세요. 정답: idx = pl

Q9. 단순 삽입 정렬에서 배열의 첫 요소부터 데이터를 저장하지 않고 a[1]부터 데이터를 저장하면 a[0]을 보초로 하여 삽입을 마치는 조건을 줄일 수 있습니다. 이 아이디어를 적용한 단순 삽입 정렬 함수를 수정하세요. 내 답변: void insertion(int a[], int n) { int j; for (int i = 1; i tmp; j--) a[j] = a[j - 1]; if (j!=0) a[j] = tmp; } } 정답: int tmp=a[0]=a[i]; 대입을 한 줄로 깔끔하게 할 수 있단 걸 계속 잊는다. 기억하자. 그리고 그냥 if(j)라고 썼네. 더 짧게 코드를 쓸 수 있..

Q.8. 요소의 삽입 과정을 자세하게 출력할 수 있도록 단순 삽입 정렬 프로그램을 수정하세요. 오른쪽처럼 현재 선택한 요소 아래에 기호 +, 삽입하는 위치의 요소 아래에 기호 ^, 그 사이에 기호 -를 출력하세요. 삽입하지 않는(요소의 이동이 필요없는) 경우에는 선택한 요소 아래에 +만 출력하면 됩니다. 내 답변: void insertion(int a[], int n) { int j; for (int i = 1; i 0 && a[j - 1] > tmp; j--) { a[j] = a[j - 1..

Q7. 요소의 교환 과정을 자세하게 출력할 수 있도록 단순 선택 정렬 프로그램을 수정하세요. 오른쪽처럼 정렬하지 않은 부분의 첫 번째 요소 위에는 기호 *를, 정렬하지 않은 부분의 가장 작은 값의 요소 위에는 기호 +를 출력하세요. 내 답변: void insertion(int a[], int n) { for (int i = 0; i

Q6. 다음의 배열을 정렬한다고 가정하겠습니다. {9,1,3,4,5,6,7,8} 이 배열은 두 번째 요소부터는 정렬은 되어 있지만 버전 3의 버블 정렬 알고리즘을 사용해도 빠른 시간 안에 정렬 작업을 마칠 수는 없습니다. 왜냐하면 맨 앞에 있는 요의 값(9)은 1회의 패스를 거쳐도 한 칸만 뒤로 옮겨지기 때문입니다. 그래서 홀수 번째의 패스는 가장 작은 요소를 맨 앞으로 옮기고 짝수 번째 패스는 가장 큰 요소를 맨 뒤로 옮기는 방식을 사용하면 (패스의 스캔 방향을 교대로 바꾸면) 이런 정렬을 더 적은 횟수로 비교를 수행할 수 있습니다. 버전 3의 프로그램을 개선하여 양방향 버블 정렬을 수행하는 프로글매을 작성하세요. 내 답변: 우선 while문에서 for 문으로 변경했다. 진행되고 있는 패스의 숫자를 하..

Q5. 연습문제 Q2(204쪽)와 마찬가지로 비교, 교환 과정을 자세히 출력하는 프로그램(실습 6-3)으로 수정하세요. 내 답변: 6-3과 같이 key와 last 변수를 추가했다. 그리고 교환이 일어날 때마다 last를 업데이트 하게 했다. 그래서 해당 패스에서 교환이 일어난 가장 작은 인덱스를 저장한다. 그럼 진행중인 패스의 검사를 마쳤을 때 a[0]부터 a[last] 까지는 정렬된 상태일 것이다. 즉, 다음 패스에서 그 사이의 인덱스는 검사할 필요가 없다. 하지만 last 변수는 다음 패스에서 다시 초기화가 진행되기 때문에 패스가 끝나기 전에 key 변수에 last의 값을 대입시킨다. 그리고 매 패스는 key까지만 검사를 진행하게 된다. void bubble(int a[], int n) { int i..