Happy rewyear

퀵 정렬 원소을 하나 정하여 이를 pivot(기준 원소)으로 삼고, 해당 pivot보다 작은 수들과 큰 수로 나누는 방식의 정렬. 퀵 정렬을 한번 마치고 나면 pivot을 기준으로 다음과 같이 정렬됨. 왼쪽은 pivot 보다 작은(혹은 작거나 같은) 수 오른쪽은 pivot을 기준으로 큰 수 pivot의 위치는 확정됨(정렬되었음을 의미) 위와 같은 규칙을 가지고 재귀 호출을 통해 구현 구현 #include using namespace std; void my_swap(int *x, int *y) { int tmp; tmp = *y; *y = *x; *x = tmp; } /* 퀵 정렬 */ void quick_sort(int arr[], int start, int end) { if(start >= end) /..

합병 정렬 분할 정복(divide and conquer)을 이용하는 정렬 방식으로서 정렬할 원소의 집합을 작게 분할 후 정렬하고, 다시 합치는 방식으로 정렬을 진행 1. 왼쪽 배열을 합병 정렬 2. 오른쪽 배열을 합병 정렬 3. 정렬해 가면서 합치기(merge) 재귀 호출을 활용하여 구현 구현 #include using namespace std; void merge(int arr[], int lstart, int lend, int rstart, int rend) { int i = lstart; int j = rstart; int tmp[10]={0,}; // 임시 저장 배열 int tmpIdx = 0; // 임시 저장 배열의 인덱스 while(i

삽입정렬 원소를 적절한 위치에 삽입하는 방법으로서, 이미 정렬이 되어있는 앞의 원소와 비교해 나아가면서 필요할 때만 위치를 변경 #include using namespace std; void my_swap(int *x, int *y) { int tmp; tmp = *y; *y = *x; *x = tmp; } /*삽입 정렬 */ void insertion_sort(int arr[], int cnt) { int j; for(int i=0; i=0 && arr[j] > arr[j+1]) { my_swap(&arr[j], &arr[j+1]); j--; } } } int ary[10] = { 1, 10 ,5, 3, 8, 7, 6, 4, 2, 9}; int main() { insertion_sort(ary,10);..

버블 정렬 인접한 원소를 비교하여 큰 수를 뒤로 보내는 정렬 방식 #include using namespace std; void my_swap(int *x, int *y) { int tmp; tmp = *y; *y = *x; *x = tmp; } /* 버블 정렬 */ void bubble_sort(int arr[], int cnt) { for(int i=0; i

정렬: 어떤 원소들의 집합을 특정 기준을 적용하여 나열함 알고리즘에서 "정렬"은 알고리즘의 성능을 극명히 보여주는 알고리즘. 선택정렬 선택정렬은 정렬 중 가장 기본적인 정렬 방식으로, 원소 중 가장 작은 값을 찾아 앞으로 보내는 방식. 구현코드 #include using namespace std; void my_swap(int *x, int *y) { int tmp; tmp = *y; *y = *x; *x = tmp; } /* 선택 정렬 */ void selection_sort(int arr[], int cnt) { int min; for(int i=0; i

특정 원소 집합의 정렬이 필요할 때 C++ STL의 에 있는 sort()함수를 이용하면 굳이 정렬을 구현하지 않아도 쉽게 정렬할 수 있다. 구현된 sort()함수는 "quick sort" 기반으로 구현되어 있으며, default로 오름차순 정렬을 수행함. 기본적인 배열 정렬 #include #include using namespace std; int main() { int arr[10] = {10,4,7,1,3,2,6,5,9,8}; // 정렬 전 원소 출력 for(int i=0; i

Stack 후입 선출(LIFO)의 stack을 구현한 STL #include #include using namespace std; int main(){ stack st; //int자료형을 저장하는 스택 생성 st.push(4); //원소(4) 삽입 st.pop(); // 마지막 삽입된 원소 pop printf("%d\n", st.top()); // 마지막 삽입된 원소 값 출력 printf("%d\n", st.empty()); //스택이 비어있다면 1 아니면 0 printf("%d\n", st.size()); //스택에 저장되어 있는 원소의 수 출력 return 0; } Queue #include #include using namespace std; int main(){ queue q; //int자료형을 ..

Vector 동적 배열을 구현한 STL #include #include using namespace std; int main(){ vector vec1; //int 자료형을 저장하는 동적배열 vector vec2; //double 자료형을 저장하는 동적배열 vector vec3; //사용자가 정의한 Node 구조체를 저장하는 동적배열 vector vec4(n); //벡터의 초기 크기를 n으로 설정 vector vec5(n, 1); //벡터의 초기 크기를 n으로 설정하고 1로 초기화 vector vec6(n, vector(m, 0)); //크기가 n*m인 2차원 벡터를 선언하고 0으로 초기화 // 또는 하기와 같이 2차원 벡터 초기화 /* for(int i=0; i

C++ 기본 #include using namespace std; 헤더로 #include 을 선언하게 되면 stl header 하나하나 include할 필요 없이 한번에 include. namespace를 사용함으로서 std 생략 가능 입력 모든 알고리즘 문제들은 test case의 입력을 받아 문제를 해결해 나아가야 한다. C / C++에는 여러가지 입력 함수가 있는데 대표적으로 scanf, cin이 있다. scanf(): white space(띄어쓰기, 줄바꿈 등의 공백) 이전까지 설정한 format에 맞춰 입력 받음 cin: 개행문자(\n) 이전까지 입력 받음 대개 형태가 정해져있는 input 값을 입력 받는 방식에 대한 case별 정리 case1 하기와 같은 n x m 행렬 형태의 데이터를 입력 ..

#include using namespace std; int main() { // C 스타일의 입력 // scanf를 이용하여 입력의 끝일 때까지 입력 받음 // 끝에 도달하면 scanf는 EOF를 반환 char c; while(scanf("%c", &c) != EOF) { printf("%c", c); } // C ++ 스타일의 입력 // getline 함수를 통해 줄 단위로 입력 받음(공백 포함) // 입력이 없으면 문자열의 길이가 0인 것을 활용해 조건식 작성 string str; getline(cin,str); while(str.length() > 0) { cout