분류 전체보기

각 정렬의 특징 및 장단점 & 시간복잡도 + 코드

선택정렬 (Selection Sort) 선택정렬은 앞에서부터 차례대로 먼저 주어진 리스트 중에 최소값을 찾고 그 값을 맨 앞에 위치한 값과 교체하는 방식으로 진행하는 정렬 방법이다. 코드가 직관적이기에 구현도 비교적 간단하다. n개 원소에 대해 n개의 메모리를 사용하기에 데이터를 하나씩 정밀 비교가 가능하며 정렬을 위한 비교 횟수는 많으나 교환 횟수는 상당히 적다는 것이 장점이다. 따라서 교환이 많이 이루어져야하는 자료 상태에서 가장 효율적으로 적용될 수 있다. 선택 정렬이 가장 적합한 자료 상태는 역순 정렬이다. 즉, 내림차순으로 정렬되어 있는 자료를 오름차순으로 재정렬할 때 최적의 효율을 보여준다. 반대로 이미 정렬된 상태에서 소수의 자료가 추가됨으로 재정렬하게 되는 때에는 최악의 처리 속도를 보여준..

[C++] min max 함수 (algorithm 라이브러리)

0. std::min & std::max 1. ①비교할 값들이 많거나, ②ArrayㆍVector와 같은 일련의 컨테이너에 저장되어 있다면, 최소값ㆍ최대값을 구하기 위해 min_element 또는 max_element 함수를 사용할 수 있다. (해당 함수에 대해서는 나중에 포스팅 하겠다.) 2. std::min와 std::max는 algorithm 라이브러리에 3가지 형태로 존재한다. 『① Default Constructor 』 『② Custom Constructor 』 『③ Initializer List Constructor 』 가 이에 해당한다. 1. std::min & std::max 『① Default Constructor 』 함수 원형 /* -- Default Constructor -- */ #i..

[C] min max 매크로함수

1. The old C macro way 매크로 원형 /* min */ #define min(a, b) (((a) (b)) ? (a) : (b)) 단점 : double-evaluation side effect 발생 /* Input */ #include #define min(a, b) (((a) (b)) ? (a) : (b)) int main(int argc, char * argv[]) { int a = 2, b = 3; printf("%d\n", min(a, b)); printf("a : %d b : %d\n\n", a, b..

코딩테스트 문제 풀이 전, 시/공간 복잡도 이해하기

복잡도 코딩테스트를 준비하기 전, 시간 복잡도와 공간복잡도 이해 해야한다. 대부분의 코딩테스트 문제에는 제한 시간과 메모리가 존재한다. 이를 바탕으로 적절한 시/공간 복잡도를 계산한 뒤 적절한 알고리즘을 사용할 필요성이 있다. 시간 복잡도 '제한시간'안에 알고리즘 문제를 해결하기 위해서는 시간복잡도를 이해해야 한다. 일반적으로 O(N)과 같은 빅오 표기법을 기준으로 연산 횟수를 계산한다. for 문으로 문제를 해결할 시 시간복잡도는 다음과 같다. 단일 for문: O(N) 이중 for문: O(N²) 삼중 for문: O(N³) N값이 어떻게 주어지냐에 따라 시간복잡도를 계산해보자면 N = 500 O(N³)일 경우 1.25 * 10⁸의 연산 횟수가 필요하다. O(N²)일 경우 2.5 * 10⁵의 연산 횟수가 ..

[C] 문자열에서 공백을 제거하는 함수

문자열 중앙에 있는 공백도 제거하는 함수가 필요해서 만들었다. 아래의 DeleteSpace함수는 인수로 받는 문자열에서 문자열에서 앞, 뒤, 가운데에 있는 모든 공백을 제거해서 제거된 문자열을 반환하는 함수다. 사용법: char *str = DeleteSpace("공백이 있는 문자열"); char str[] = DeleteSpace("공백이 있는 문자열"); #include #include char* DeleteSpace(char s[]) { char* str = (char*)malloc(sizeof(s)); int i, k = 0; for (i = 0; i < strlen(s); i++) if (s[i] != ' ') str[k++] = s[i]; str[k] = '\0'; return str; } i..

[C] 재귀함수(Recursive/리쿼시브)의 개념과 공부하는 이유

재귀란 무엇인가? 컴퓨터 과학에 있어서 재귀(再歸, Recursion)는 자신을 정의할 때 자기 자신을 재참조하는 방법을 뜻하며, 이를 프로그래밍에 적용한 재귀 호출(Recursive call)의 형태로 많이 사용된다. 또 사진이나 그림 등에서 재귀의 형태를 사용하는 경우도 있다. (위키백과) 위키백과에서 가져온 재귀의 컴퓨터 과학 측면에서의 정의이다. 쉽게 말해서, "재귀적으로 정의했다" 라는 말은 자기 자신을 정의할 때 자기 자신을 이용했다는 것이다. 가령 5! (5 팩토리얼)을 정의할 때도, 5! = 5 * 4! 라고 나타낼 수 있으므로 이를 일반화하면 n! = n * (n - 1)! 라고 나타낼 수 있게 된다. 이 등식에서 팩토리얼을 정의하는데 있어서 팩토리얼을 사용했다는 것은, 재귀적 정의를 활..

[C#] 문자열(String)이 null인지 공백인지 확인하는 방법

IsNullOrEmpty IsNullOrEmpty 메서드는 문자열이 null 또는 빈 문자열("")인 경우 true를 반환하며, 그렇지 않으면 false를 반환한다. Console.WriteLine("String.IsNullOrEmpty(\"\"): " + String.IsNullOrEmpty("")); Console.WriteLine("String.IsNullOrEmpty(null):" + String.IsNullOrEmpty(null)); Console.WriteLine("String.IsNullOrEmpty(String.Empty):" + String.IsNullOrEmpty(String.Empty)); Console.WriteLine("String.IsNullOrEmpty(\" \"): " + S..

[C++] 공백 포함 문자열 입력받기

1. getline 이용 getline을 쓰면 알아서 공백 포함하여 문자열을 입력받는다. int main() { string s; getline(cin, s); cout

[C] 공백 포함 문자열 입력 받기 (scanf, gets, fgets)

#include #define LEN 1000000 int main(){ char str[LEN]; scanf("%s",str); printf("%s",str); } 1. scanf[] scanset character scanset character [] 를 scanf 함수에 추가해 주는 방법이다. [^"문자"]의 의미는 해당 문자가 나오기 전 까지 모든 문자열을 받겠다는 뜻이다. 개행(엔터)를 의미하는 문자인 "\n" 를 ^뒤에 넣어주면, 개행(엔터)가 나오기 전 까지 모든 문자열을 받겠다는 뜻이 된다. 따라서, 공백도 포함해서 입력을 받을 수 있게 되는 것이다. /* scanset character 예시 */ #include #define LEN 1000000 int main(void){ char s..

유클리드 호제법 - 최대공약수(GCD) 구하기

유클리드 알고리즘(Euclidean algorithm)은 2개의 자연수의 최대공약수를 구하는 알고리즘이다. 비교대상의 두 개의 자연수 a와 b에서(단 a>b) a를 b로 나눈 나머지를 r이라고 했을때 GCD(a, b) = GCD(b, r)과 같고 "r이 0이면 그때 b가 최대공약수이다."라는 원리를 활용한 알고리즘이다. ex) GCD(24,16) -> GCD(16,8) -> GCD(8,0) : 최대공약수 = 8 구현 재귀 함수 활용 int GCD(int a, int b) { if(b==0)return a; else return GCD(b,a%b); } 반복문 활용 int GCD(int a,int b){ while(1){ int r = a%b; if(r==0) return b; a = b; b = r; }..