IT공부/알고리즘 (9) 썸네일형 리스트형 C++ STL sort() 함수다루기02 C++ STL sort() 함수다루기02 "C++ STL sort() 함수다루기01" 객체로 정렬하는 방법에 대해 알아보았다. 하지만 객체로 정렬하는 경우 프로그램 속도상 별로 좋지 않다. 클래스를 정의하고 정렬방법에 대해 정의해야 하기 때문이다. 실제 프로그래밍 대회에서는 클래스를 사용하는 방법은 적절하지 않다. 객체를 사용하는 방법은 실무에서 사용하며 프로그래밍 대회에서는 페어(Pair) 라이브러리를 사용한다. 아래 예제를 보자. 데이터가 2개이고 한 개의 데이터(점수)로 정렬하는 방법 #include #include #include using namespace std; int main(void){ vector v; //점수로 정렬이 이루어진다. 클래스를 정의하지 않고 빠르게 정렬할 수 있다. => .. C++ STL sort() 함수다루기01 C++ STL sort() 함수다루기01 정렬은 컴퓨터 공학의 오래된 연구 분야이므로 이미 아주 훌륭한 정렬관련 라이브러리가 존재한다. 그렇기 때문에 필요시 이 라이브러리를 가져다 쓰면 된다. sort() 함수의 기본 사용방법 sort() 함수는 C++ algorithm 헤더에 포함되어 있다. 기본 사용법은 아래와 같다. #include //cout을 사용하게 해줌. #include using namespace std; void show(int sort[]){ for(int i = 0; i < 10; i++){ cout score < student.score; } }; void show(Student students[]){ for(int i = 0; i < 5; i++){ cout 병합정렬(Merge Sort) 병합정렬(Merge Sort) 퀵 정렬과 같이 병합정렬도 '분할 정복' 알고리즘이다. 시간복잡도가 O(N * logN)을 가진다. 퀵 정렬은 최악의 경우 O(N ^ 2)의 시간복잡도를 가진다. 하지만 병합정렬은 정확히 반절씩 나눈다는 점에서 최악의 경우에도 O(N * logN)을 보장한다. 다음의 숫자들을 오름차순으로 정렬하는 프로그램을 작성하세요. 7 6 5 8 3 5 9 1 병합정렬은 퀵 정렬과 다르게 피벗 값이 없다. 항상 반으로 나누기 때문이다. 바로 이 특징이 단계의 크기가 logN이 되도록 만들어준다. 아래는 병합정렬 과정을 그림으로 나타낸 것이다. 1단계에서 2개씩 정렬을 한다. 즉, 7과 6을 묶어 7과 6중 작은 숫자가 앞으로 오게 정렬이 된다. 5와 8을 묶어 5가 앞으로 오고 8이 뒤.. 기초 정렬 알고리즘 문제 풀이 기초 정렬 알고리즘 문제 풀이 백준 온라인 저지 = https://www.acmicpc.net/ 문제 1 https://www.acmicpc.net/problem/2750 데이터의 개수가 1000개 이하이다. N^2을 하면 백만이다. 일반적으로 온라인 채점 시스템같은 경우는 1초에 1억번 정도 연산을 할 수 있다고 보면 된다. 즉, 백만개정도의 연산은 무리없이 가능하다. #include //선택정렬 //데이터 개수가 1000개므로 1001개까지 배열을 만든다. //이유는 배열의 인덱스가 0부터 시작하기 때문이다. //즉, 인덱스를 0 ~ 1000까지 갖도록하게 하기 위함이다. int array[1001]; void show(int number){ int i; for(i = 0; i < number; i+.. 퀵 정렬의 시간복잡도와 작동원리 퀵 정렬의 시간복잡도와 작동원리 퀵 정렬은 이름 그대로 빠른 알고리즘이다. 시간복잡도가 O(N * logN)이다. 2 ^ 10 = 1,000 2 ^ 20 = 1,000,000 log2N -> N이 1,000,000 일 때? 20 3 7 8 1 5 9 6 10 2 4 -> 3을 기준으로 오른쪽을 봤을 때 3보다 큰값(7)과 왼쪽을 봤을 때 3보다 작은 값(2)를 바꾼다. 3 2 8 1 5 9 6 10 7 4 -> 다시 오른쪽과 왼쪽을 보면서 큰값과, 작은 값을 찾아 바꾼다. 3 2 1 8 5 9 6 10 7 4 -> 이번에 서로 엇갈렸다(작은 값의 인덱스가 큰 값의 인덱스보다 더 작을 때). 이럴때는 작은 값과 3을 바꾼다. 1 2 3 8 5 9 6 10 7 4 -> 3보다 왼쪽에 있는 값은 3보다 작다... 삽입정렬 삽입정렬 다음의 숫자들을 오름차순으로 정렬하는 프로그램을 작성하세요. 1 10 5 8 7 6 4 3 2 9 먼저 1을 보자.1은 이미 가장 앞에 위치하기 때문에 삽입할 위치가 없다. 1 10 5 8 7 6 4 3 2 9 10을 보자. 10은 앞에 들어갈 수 있는 위치가 2군데이다. _1_ 10 5 8 7 6 4 3 2 9 5를 보자. 들어갈 위치가 총 3군데 이다. 5가 들어갈 가장 적절한 위치는 가운데 이다. _1_10_ 5 8 7 6 4 3 2 9 -> 1 5 10 8 7 6 4 3 2 9 8을 보자. 8은 들어갈 수 있는 곳이 4군데이다. 3번째에 위치해야 한다. _1_5_10_ 8 7 6 4 3 2 9 -> 1 5 8 10 7 6 4 3 2 9 7을 보자. 들어갈 수 있는 곳이 5군데이다. 3번째.. 버블정렬 버블정렬 버블정렬은 바로 가까이에 있는 두 숫자끼리 비교를 해서 당장 더 작은 숫자를 앞으로 보내주는 것을 반복하는 것이다. 다음의 숫자들을 오름차순으로 정렬하는 프로그램을 작성하세요. 1 10 5 8 7 6 4 3 2 9 #include //버블정렬 //선택 정렬과 같이 등차수열이기 때문에 시간복잡도는 선택정렬과 같이 // O(N * N)이다. //하지만 선택정렬보다 더 느리다. //계속 바로 옆에 값과 자리를 바꾸는 연산을 하기 때문이다. //선택 정렬은 가장 작은 요소를 골라서 마지막에 한 번 스와핑을 한다. //버블 정렬은 선택정렬보다 훨씬 더 비효율적이다. //시간복잡도는 선택정렬과 같지만 실제 수행시간은 선택정렬보다 더 걸린다. //알고리즘 중에서 가장 느리다. int main(void){ i.. 정렬의 개요와 선택정렬 정렬의 개요와 선택정렬 먼저 비효율적인 정렬 알고리즘을 구현해보자. 뒤에서 효율적인 알고리즘과 비교하면서 효율적인 알고리즘을 작성해야 하는 이유에 대해 알 수 있다. 다음의 숫자들을 오름차순으로 정렬하는 프로그램을 작성하세요. 1 10 5 8 7 6 4 3 2 9 #include //선택정렬 //선택정렬은 많은 시간이 소비된다. // 1 2 3 4 5 6 7 8 9 10 // 10 + 9 + 8 + .. + 1 -> 등차수열 // -> 10 * (10 + 1) / 2 = 55 -> 10 + 9 + 8 + .. + 1을 더한 값. // 최소 55번의 비교연산을 해야한다. // N * (N + 1) / 2 -> 컴퓨터에서는 N값이 굉장히 크다는 가정하에 2로 나누거나 1을 더한값이 //의미가 없기 때문에 생.. 이전 1 2 다음
