C++/알고리즘

C++ 정렬 알고리즘 (버블정렬, 삽입정렬, 선택정렬, 합병정렬, 퀵정렬, 힙정렬, 셀정렬, 기수정렬)

본 게시글은 실전 기술을 정리해 놓은 '실전 압축' 입니다. 업데이트 중입니다. 버블 정렬( Bubble Sort ) 삽입 정렬( Insertion Sort ) 선택 정렬( Selection Sort ) 합병 정렬( Merge Sort ) 퀵 정렬( Quick Sort ) 힙 정렬( Heap Sort ) 셸 정렬( Shell Sort ) 기수 정렬 ( Radix Sort ) ◾ 제자리 정렬 정렬에 추가적인 메모리 공간이 들지 않는다. 아예 안 드는 것은 아니고 거의 무시할 정도의 메모리를 사용한다. • Insertion, Bubble, Selection, Quick • Tip : 최악이 O(n^2)인 것들이라고 기억 ◾ 안정 정렬 ( Stable Sort ) 정렬 전의 순서를 유지하고 정렬된다. • In..

[실전 압축 알고리즘] - 실수형을 특정 소수점 까지 출력

본 게시글은 실전 기술을 정리해 놓은 '실전 압축' 입니다. 몇 번째 자리에서 반올림 하여라. 또는 절대/상대 오차가 10^-9까지 허용한다. 이런식으로 주어지는 문제에서는 반드시 조건에 맞게 출력을 해주어야 합니다. 소숫점 9자리 까지 출력한다고 가정하였을 때 printf("%.9lf", a/b); cout > setprecision(8) = 33.14159200 ex) 3.141596 fixed >> setprecision(5) = 3.14160 정리 cout 사용시 n번째 자리 까지 출력해야 한다면 = 절대/상대 오차가 n 이라면 1. 정밀도를 위해 float형 대신 double형 쓰세요 2. fixed >> setprecision(숫자); // (꼭 fixed 를 붙여 자리수 넘어가면 0으로 채우..

[실전 압축 알고리즘] - C/C++ 문자 숫자 변환

본 게시글은 실전 기술을 정리해 놓은 '실전 압축' 입니다. C 스타일 변환 함수 변환 모습 설명 문자열 -> 숫자 #incldue (stdlib.h) 정수형 atoi, atol, atoll 실수형 atof int atoi (const char* str); "4" -> 4 "123" -> 123 문자열을 숫자로 변환해준다. 다른 형으로는 atof, atol, atoll 이 있다. 숫자 -> 문자열 #incldue (stdlib.h) char * itoa ( int value, char * str, int base ); 5 -> "5" 123 -> "123" value를 base진법으로 변환하여 str에 저장 비표준 함수이기 때문에 MS VS 에서만 가능 표준 호환 대안은 sprintf 일 수 있습니다 ...

[실전 압축 알고리즘] - 비트 연산

본 게시글은 실전 기술을 정리해 놓은 '실전 압축' 입니다. Bitwise Operators 연산자 예시 계산 쉬프트 과정 (2진법) 결과 활용 >1 5>>2 12 >> 2 2 * 2^-1 5 * 2^-2 12 * 2^-3 00010 -> 00001 00101 -> 00001 01100 -> 00011 1 1 3 2의 -n승 & (AND) 2 & 1 3 & 1 10 & 01 -> 00 11 & 01 -> 01 0 1 짝수 = 0 홀수 = 1 | (OR) 1 | 1 2 | 1 3 | 1 01 | 01 -> 01 10 | 01 -> 11 11 | 01 -> 11 1 3 3 방문 check ^ (XOR) 5 ^ 6 1 ^ 1 2 ^ 1 00101 ^ 00110 -> 00011 01 ^ 01 -> 00 10 ^..

[실전 압축 알고리즘] - C++ 입출력

본 게시글은 실전 기술을 정리해 놓은 '실전 압축' 입니다. 입출력 언어 입력 출력 C++ scanf / cin printf / cout Java Scanner System.out Python input print C++ #define _CRT_SECURE_NO_WARNINGS #include int main() { int n; scanf("%d", &n); printf("%d", n); return 0; } #define _CRT_SECURE_NO_WARNINGS는 Visual Studio에서만 넣어주면 됩니다. scanf는 나온 지 오래된 함수라 입력 값의 길이를 설정할 수가 없습니다. 따라서 보안에 취약하기 때문에 Visual Studio에서는 사용하지 말라는 경고가 출력되고 컴파일 에러가 발생하는..

[실전 압축 알고리즘] - 시간, 공간 복잡도

본 게시글은 실전 기술을 정리해 놓은 '실전 압축' 입니다. C++ 기준으로 작성하였습니다. 시간 복잡도 작동하는 알고리즘의 수행시간을 정량화하는 것을 의미합니다. 시간 복잡도를 표기하기 위한 방법에 빅-오, 빅-오메가, 세타 등이 있으며 일반적으로 최악의 케이스(Worst Case)를 가정하고 계산 하므로 빅-오 표기법을 빅오 표기법은 최고차항의 차수만을 표기합니다. N^3 + N^2 + N + 1 = O(N^3) 숫자 빨리 읽기 0을 3개씩 묶어서 숫자 단위를 빠르게 파악하도록 암기합니다. 숫자 읽기 1'000 천 1'000'000 백만 1'000'000'000 10억 배열을 만들 때 arr[10000000] 보다는 arr[10'000'000] 이런식으로 작은 따옴표를 넣어서 가독성을 높이고 실수를 ..