sort

[C++] 코딩테스트를 위한 C++ 기본

안녕하세요:) 코테 문제 풀 때 주로 C++사용하는데요 여러문제에서 아주유용하게 사용하면서, 자주사용한다 싶은 코드위주로 요약해서 설명드릴려고해요 (사실 정리해두고 제가 쓰려고하는...) 1.using namespace std; 저는 처음에 책으로 c++배울때는 무조건 std를 일일이 붙여줘야하는 줄 알았습니다. 위 코드를 상단에 써놓으면 std를 일일이 안붙여주어도 cin,cout등을 그냥 사용가능합니다. #include using namespace std; int main() { cout > N; int* arr = new int[N]; delete[] arr; //메모리 해제 } +2차원배열 동적할당 이것도 은근 많이 씁니다! 1차원 배열을 만든뒤 각 행에 배열을 추가하여 2차원 배열을 나타내도록 ..

[알고리즘]삽입정렬(Insertion Sort)

삽입정렬이란? 두번째 수부터 자신 왼쪽의 수와 비교하여 내가 더 작으면 왼쪽으로 이동하고, 크면 오른쪽 위치를 유지합니다. 위치를 유지했으면 그 수에 대한 비교는 종료 왼쪽으로 이동했으면, 다시 자신의 왼쪽 수와 비교를 반복합니다. 내 왼쪽과 비교 내가 더 크면 현재 위치 유지 내가 더 작으면 왼쪽 수와 교체(swap) 다시 1번단계부터 비교 반복 마지막 수 까지 비교완료하면 종료 시간복잡도 최악의 경우는 역으로 정렬되어 있는 경우 n-1, n-2, ... 1만큼 비교하여 시간복잡도 O(n^2)입니다. 소스코드(C++) #include using namespace std; void insertion_sort(int arr[],int size){ //삽입정렬 for(int i = 1;i0&&arr[j-1]..

[알고리즘]선택정렬(Selection Sort)

선택정렬이란? 선택정렬은 앞에서부터 쭉 탐색하면서 가장 작은 수를 찾습니다.(오름차순의 경우) 그리고 그 수를 (정렬되지 않은 부분의)맨앞의 수와 교체합니다. 이 과정을 정렬되지 않은 수가 1개 남을 때까지 반복하면 됩니다. 이 때 배열을 정렬된 부분과 정렬되지 않은 부분으로 나눌 수 있습니다. 탐색은 정렬되지 않은 부분에 대해서만 이루어 집니다. 주황색 - 정렬된 부분 흰색 - 정렬되지 않은 부분 하늘색 - 정렬되지 않은 수 중 가장 작은 수 정렬되지 않은 부분에서 가장 작은 수를 찾는다. 정렬되지 않은 부분의 맨 앞의 수와 가장 작은 수를 교환(swap)한다. 교환된 가장 작은 수는 정렬된 부분이 된다. 정렬되지 않은 부분에서 위 과정을 반복하고, 모두 정렬되면 종료 시간복잡도 가장 작은 수를 찾는데..