알고리즘 (4) 썸네일형 리스트형 C++ 삽입 정렬 - 정렬3 삽입 정렬은 O(n²) 정렬 알고리즘 중 가장 효율적인 알고리즘이다 삽입 정렬은 한 원소를 선택하여 그 원소를 알맞은 위치에 삽입하는 알고리즘이다 아이디어는 1. 한 원소를 선택하여 2. 선택한 원소보다 작은 원소를 만날때까지 앞의 원소와 비교한다 3. 앞의 원소가 선택한 원소보다 작다면 선택한 원소와 자리를 바꾼다 4. 선택한 원소보다 작은 원소를 만나면 멈춘다 언뜻 보면 버블 정렬과 유사해 보이지만 다른 점은 정렬을 멈추는 지점을 알기 때문에 선택 정렬이나 버블 정렬과 다르게 불필요한 정렬을 하지 않는다 선택 정렬에서는 왼쪽의 원소들은 이미 정렬이 되어있다는 가정을 하기 때문에 왼쪽으로 탐색했을 때 자기 자신보다 작은 원소가 있다면 거기서 멈추면 된다 int* InsersionSort(int* arr.. C++ 선택정렬 - 정렬1 정렬중에서 가장 간단하고 직관적인 정렬이다 아이디어는 1. 배열중에서 가장 작은 숫자를 선택한다 2. 선택한 숫자와 가장 앞에있는 숫자를 교체한다 int* SelectionSort(int* arr, int size){ int min, index = 0, temp; for(int i=0; i < size; i++){ min = 10000; for(int j=i; j < size; j++){ //~i 까지 정렬이 되어있으므로 i에서 부터 시작 if(arr[j] < min){// 배열의 최소값을 찾는다 min = arr[j]; index = j; } } temp = arr[i];//최솟값과 가장 앞의 값을 교체한다 arr[i] = arr[index]; arr[index] = temp; } return arr;.. C++ 문자열 동적 할당 c++의 string과 getline함수의 느린 동작을 보완하기 위해서 나만의 문자열 동적 할당 함수를 작성하게 되었다 V.1 char* getstring(){ char temp[STRING_SIZE]; fgets(temp, STRING_SIZE, stdin); char* s = new char[strlen(temp)]; strcpy(s, temp); return s; } 1. 임시 배열 temp를 먼저 선언하고 2. fgets를 통해 사용자 입력을 받아 3. 입력의 크기만큼 새롭게 할당한 메모리에 4. 문자열을 붙여넣는다 이 인풋은 정상적으로 실행이 되었지만 한가지 문제가 있었다 바로 개행문자까지 저장이 된다는 것이다 $ asdfasdlkj//인풋 -> asdfasdlkj\n//결과물 그래서 마지막 개.. C++ 입력 정리 1. 변수 입력 std::cin의 경우 int a, b; std::cin >> a; std::cin >> a >> b; //다중 입력 c++ 강의를 들으면 처음으로 배우는 c++국룰 입력 방법이다 하지만 이 방식에는 문제가 있다. 첫번째로 입력의 형태이다 $10//터미널 입력 10\n//실제 입력 터미널에 10을 입력하고 엔터를 누르면 10뒤에 \n까지 입력이 된다 그렇기 때문에 정수를 입력할때 cin은 숫자뒤에 \n을 놔두고 숫자만 입력하게 된다. 문제는 이것을 string이나 char입력을 같이 사용할때 나타난다 숫자는 \n을 입력하지 못하므로 \n을 버리고 입력하는데, \n을 포함할 수 있는 string이나 char을 입력하게되는 경우 그 전에 cin에서 입력하고 버퍼에 남은 \n을 입력하게 된다... 이전 1 다음
