CS66

• [boj 10989] 카운팅 정렬 이 정렬법은 O(n+k)의 시간 복잡도를 가진다. 이때 k는 정렬하고자 하는 수 배열의 최대값이다. n개의 배열을 한 번 훑으며 개수를 체크해야 하므로O(n)인데 최대값 k에 따라서 메모리가 증가한다. 알고리즘 count배열을 선언한다. 이때 배열의 크기는 정렬하고자 하는 수의 최대값으로 정한다. #include #include int main() { int n; scanf("%d", &n); int input; int count[10000]; // 초기화 해야함 memset(count, 0, 10000*sizeof(int)); // 입력을 어레이로 받지 않고 단일 int로 받는것에 주의 for(int i=0;i CS/Algorithm 2022. 7. 20.

• call by value, address, reference 차이점 정리 call by value, address, reference 차이점 정리 Call by Value (값 호출) 함수에 인자를 넘겨줄 때, 변수의 값을 넘겨준다. #include void swap(int a, int b) { int tmp; tmp = a; a = b; b = tmp; printf("In func: a=%d, b=%d\n", a, b); } int main() { int a=1; int b=2; printf("main: a=%d, b=%d\n", a, b); swap(a, b); printf("After func: a=%d, b=%d\n", a, b); } 실행시켜보면, 함수를 빠져나왔을 때 값이 변하지 않았음을 확인할 수 있다. 즉 주소를 전달한 게 아니라 값만 함수에 전달했기 때문에 함.. CS/C++ 2022. 7. 19.

• lvalue와 rvalue의 이해, 증감연산자와 앰퍼센드 연산자 lvalue와 rvalue의 이해, 증감연산자와 앰퍼센드 연산자 l-value와 r-value left value와 right value를 의미하며, int a = 3; 같은 식에서 왼쪽의 a가 l-value, 오른쪽이 r-value이다. 즉 l-value: 식 이후에도 남아있는 값. 주소를 가지고있음. r-value: 메모리 주소가 없고, 표현식 범위에만 있는 임시 값. 임시 변수! 예를들면 if(a CS/C++ 2022. 7. 19.

• STL sort 함수 사용법 헤더를 인클루드 해야한다. C++ STL에서 제공한다. O(NlogN) 시간 복잡도를 가진다. 퀵정렬은 피봇을 어떻게 잡느냐에 따라 최악의경우 O(N^2)의 시간 복잡도를 가지지만 sort 함수의 알고리즘은 최악의 경우에도 O(NLogN)을 보장하는 intro sort로 구현되어있다. 사용법 sort(배열 시작주소, 배열 끝주소+1); 로 사용한다. 즉, 배열의 원소가 n이라면 sort(arr, arr+n)으로 사용하면 된다. 아래는 사용 코드 예시 #include #include #include using namespace std; int main() { int len = 5; int arr[len] = {1,3,5,2,4}; sort(arr, arr+len); for(int i=0;i CS/C++ 2022. 7. 19.

• [GDB] 브레이크포인트 확인/설정/삭제 브레이크포인트 걸기b *0x8060480: 주소에 걸기b *main: 메인함수에 걸기b 15: 15번째줄에 걸기브레이크포인트 확인info b: 모든 브레이크포인트 나옴브레이크포인트 활성화 / 비활성화enable br 1: 1번 브레이크포인트 활성화disable br 1: 1번 bp 비활성화브레이크포인트 삭제d 2: 2번 브레이크포인트지움d: 모든 브레이크포인트 지움 CS 2022. 7. 18.

• scanf 사용시 버퍼에 남은 linefeed 처리 scanf 사용시 버퍼에 남은 linefeed 처리 3 a 위와 같은 인풋을 아래의 scanf로 받는다고 하자. scanf("%d", &num); scanf("%c", &ch); 결과는 str에 a 캐릭터가 들어가지 않고 빈 문자열이 들어간다. scanf가 3을 받고나서 버퍼에 \n가 남아있는 상태가 되고, 두번째 scanf가 \n을 받고 끝내버리기 때문이다. 이를 방지하기 위해서는 캐릭터를 입력받는 scanf의 포맷스트링 앞에 ' ' 공백을 추가해주면 된다. scanf(" %c", &ch); 버퍼 앞의 공백, \n, \t가 모두 무시된다. CS/C++ 2022. 7. 14.

• 우분투에서 scanf()로 EOF 입력하기/받기 우분투에서 scanf()로 EOF 입력하기/받기 scanf() 함수로 EOF 받기 입력값의 길이를 모르고 형식만 알 때, 예를 들어 아래와 같이 정수 3개가 공백 간격으로 t번 반복된다고 하자. 1 2 3 3 4 5 ... 3 3 2 t번을 알 수 없을 때, scanf를 while문 안에 넣어 EOF를 탐지할 수 있다. while(scanf("%d %d %d", &a, &b, &c)!=EOF) { // 대충 a, b, c로 무언가 하는 코드 } 우분투 콘솔에서 EOF 입력넣기 Ctrl+d를 두 번 입력해주어야 한다. tmux 사용 시에는 shell exit을 일으킬 수 있다. CS/C++ 2022. 6. 29.

• 포인터변수의 이해와 주소연산자 포인터변수의 이해와 주소연산자 엠퍼센드 연산자의 용례 엠퍼센드 연산자는 아래의 3가지로 쓰인다. & bitwise and 연산자로서 사용 주소연산자로 사용 int* ptr = &b; (주소를 리턴하는 연산자) 레퍼런스변수로서 사용 이중 두 번째 주소연산자로서 사용하는 경우를 알아보자. 포인터와 &의 사용 포인터는 주소값을 저장하는 변수고, &는 주소값을 리턴하는 연산자다. #include int main() { int val = 10; int* ptr; ptr = &val; // 포인터는 주소값을 저장하는 변수 } 포인터 변수를 선언할 때 int*등을 쓰는데, 이때의 int는 변수의 자료형이 int라는 뜻이 아니라, 포인터 변수의 주소가 가리키는 값이 해당 자료형이다라는 뜻. CS/C++ 2022. 6. 28.

• 배열과 포인터의 공통점과 차이점 배열과 포인터 배열과 포인터는 표현에서 비슷한 점이 많다. 배열 표현식과 포인터 표현식을 interchangably 쓸 수 있다. #include int main() { int val = 10; int* ptr; int arr[3] = {1,2,3}; ptr = &val; // arr = &val; // 얘는 안된다. arr변수는 '배열'로 선언되었기 때문. // 한번 세팅하면 주소값을 바꿀 수 없는 const pointer와 비슷한 느낌? printf("ptr value: %x\n", ptr); // 주소값 printf("ptr pointer: %d\n\n", *ptr); // 10 printf("ptr[0]: %d\n", ptr[0]); // 포인터를 배열처럼 printf("*(arr+.. CS/C++ 2022. 6. 28.

• [백준 10815] 이분 탐색법(binary search) 숫자 카드: 백준 10815번 문제 n개의 카드를 받았을 때, m개의 숫자카드 중 가지고있는 카드가 무엇무엇인지를 판단하는 문제 문제 이해 및 풀이 arr1에 n개의 숫자를 받고, std::sort 알고리즘으로 미리 정렬해놓는다. sort 알고리즘은 헤더파일에 있고 퀵소트로 정렬하여 O(nlogn)의 시간복잡도를 가진다. sort(start, end, compare)으로 첫번째인자는 시작주소, 두번째인자는 끝주소, 마지막인자는 비교함수를 옵션으로 넣어줄 수 있다. 기본값은 오름차순 정렬이다. 다시 돌아와서, m개의 숫자를 받아 각 숫자가 n개의 카드에 존재하는지 여부를 출력해주기 위해 바이너리서치 함수로 전달한다. 함수로 배열을 전달할 때 길이정보가 같이 넘어가지는 않으므로, 꼭 인자로 따로 넘겨주어야 .. CS/Algorithm 2022. 6. 24.

• 

  [백준 2609] 최대공약수와 최소공배수 최대공약수와 최소공배수 구하기 일반적으로 교과과정에서 배운 최대공약수 구하는 법은 두 수를 2나 3, 나뉠만한 소수로 계속 나눠보는 것이다. 위와 같이 더이상 나눠지지 않는 수까지 나눈 후에, 즉 A와 B를 서로소가 될 때까지 나눈 후에 왼쪽 나눈 수들을 전부 곱한 값이 gcd, 최대공약수이고 A, B를 gcd로 나눈 몫들을 모두 gcd와 곱한 값을 lcm, 최소공배수라 한다. 최대공약수 gcd = greatest common divisor 최소공배수 lcm = least common multiple 이는 사실 A와 B를 소인수분해한 후, 공통약수를 모두 골라내는 작업과 같다. 하지만 이 계산법들은 A와 B가 커질수록 소인수분해하기 어려워진다. 유클리드 호제법: Euclidean algorithm 원이름.. CS/Algorithm 2022. 6. 21.

• [백준 20353] C언어 기본 자료형 정리 C언어 자료형 정리 백준 20353 Atrium 문제 날먹할 외국어 문제 찾아보다가, 의외로 브론즈 4랭크인 20353번 Atrium 문제에서 10번이나 "틀렸습니다"를 받아 포스팅한다. (15610번과 같은 문제) 이번 기회에 자료형을 확실히 정리하고 넘어가야겠다.. 분명 입력값이 single integer a(1 CS/Algorithm 2022. 6. 16.