공부28 퀵 정렬 지난 게시글과 이어지는 내용입니다 퀵 정렬 quick sort - 빠른 정렬 알고리즘 - 배열의 원소를 나누어 계산하는 원리 - 대표적인 분할 정복 방법 중 하나 - 특정한 값을 기준으로 큰 숫자와 작은 숫자를 나눈다. 특정한 값 = 피벗 (pivot) 보통 첫 번째 값으로 잡음 과정 피벗을 기준으로 왼쪽에서는 피벗보다 큰 숫자, 오른쪽에서는 피벗보다 작은 숫자를 고른다. 자리를 바꿔준다. 계속 수행한다. 엇갈리는 상황이 온다면? → 왼쪽에 있는 값(작은 값)과 피벗을 바꾸어준다. 엇갈린다 == 작은 값의 index가 큰 값의 index보다 큰 상황 피벗이 정렬되면 다시 왼쪽 / 오른쪽 집합으로 나누어 정렬을 수행한다. - 즉 퀵 정렬은 분할한 뒤에 더하면 전체적으로 봤을 때 연산 횟수가 훨씬 줄어드는 .. 2021. 8. 26. 버블정렬, 선택정렬, 삽입정렬 정렬 문제는 알고리즘의 효율성 차이를 극명하게 보여준다. 선택정렬 selection sort - 전체적으로 훑어보며 가장 작은 값을 골라 앞으로 보내는 방식 - 최솟값과 그 주소를 저장해둘 변수가 필요함 - 선택의 범위가 앞에서부터 점점 줄어듦 (= 왼쪽 끝부터 고정됨) 버블정렬 bubble sort - 바로 옆 값과 비교해 자리를 바꿔주는 방식 - 선택의 범위가 뒤에서부터 점점 줄어듦 (= 한 바퀴 돌고 나면 가장 큰 값이 오른쪽 끝에 가 있음 ➜ 오른쪽 끝부터 고정됨) - 한바퀴 == 패스스루 passthrough - 가장 쉽지만, 그만큼 오래 걸리기 때문에 효율성이 떨어짐 삽입정렬 insertion sort - 각 숫자를 적절한 위치에 삽입하는 방식 - 앞의 원소들이 '이미 정렬되어 있다'고 가정 .. 2021. 8. 24. 백준 10951번 (A+B - 4, EOF) C언어 문제 입력이 끝날 때까지 A+B를 출력하는 문제. EOF에 대해 알아 보세요. EOF란? End Of File. 파일의 끝을 표현하기 위해 -1로 정의된 상수 입력이 끝나면 (= 파일의 끝) 빠져 나오도록 해주면 된다. #include int main() { int a; int b; while ((scanf("%d%d", &a, &b))!=EOF) printf("%d\n", a+b); return 0; } 두들낙서 47강을 듣다가 생각나서 다시 풀어보았음 (2021/7/15) 정리 feof는 파일을 끝까지 읽으면 true를 반환한다. 예를 들어 while (!feof(스트림명)) {...} 에서 파일이 다 읽히면 !(true) ➡️ false가 되어 반복문을 빠져나오게 된다. 파일의 끝에 도달했음을 확인.. 2021. 7. 7. 이전 1 ··· 5 6 7 8 9 10 다음
