C언어세미나 (2)

블로그를 너무 오래쉬어서 세미나 기록!

 

01 다중 반복문

구구단문제

02 소트인 사이드

1427번 : 방문배열 사용하기

 

- visited배열을 만들어준다.

- 해당하는 인덱스의 값을 추가해주면된다.

 

> 방문배열의 인덱스

   방문을 체크할 대상

 

> 방문배열의 각 칸의 정보

   해당 인덱스가 나타나는 대상이 방문된 횟수

 

03 알고리즘 헤더파일

크기 비교함수

최솟값 반환함수 : min(A,B)

최댓값 반환함수 : max(A,B)

 

- 전달 받은 두 수중 더 큰(작은)수를 반환한다

- 두 수의 자료형이 같아야한다.

 

두 수 교환함수

swap(A,B)

int tmp = A;

A= B;

B =tmp;

 

 

 

04 cmath 헤더파일

abs(숫자) : 절댓값

pow(A,B): 지수값을 더블형으로 반환

sqrt(숫자): 제곱근을 더블형으로 반환

 

---

문자열

c에서 문자열 생성방법

char배열이름[문자열길이 +1];

- 문자열 끝에 널문자'\0' 포함

- 실제 문자열 길이보다 하나 크게 선언(널을위해)

- 배열 요소 접근은 모든 배열이 동일

 

문자열 입력

scanf("%s",입력받을 배열의 이름)

- &없이 이름만(문자열일때는)

- 탭 문자 입력전까지 입력받은 문자를 모두 배열에 저장 > 엔터('\n') or 공백(' ')

 

공백 문자를 포함한 문자열 입력

scanf("%[^\n]s",입력받을 배열)

여러줄에 걸쳐 문자열입력시 getchar()함수 필수

 

ex)

scanf("%[^\n]s",입력받을 배열)

getchar()

scanf("%[^\n]s",입력받을 배열)

요런식으로

 

문자열출력

printf("%s:, 출력배열 이름);

 

strlen()함수

- int strlen(배열의 이름)

- 인수로 전달된 문자열의 길이를 반환하는 함수(널 제외)

- 인수로는 배열만

- cstring헤더 파일

 

string클래스를 이용한 문자열 방법

#include <string>

-문자열 끝에 널문자 포함 x

- 스트링 객체 선언하여 문자열 저장

 

string문자열 이름;

- 문자열 길이 명시 x

- 배열처럼 인덱스 이용해서 특정위치의 문자에 접근가능

 

string클래스를 사용한 문자열의 올바른 출력

char 배열이름[문자열길이+1];

scanf("%s",배열이름);

string 문자열 이름 = 배열이름;

printf("%s",문자열이름.c_str());

출처:alcuk

 

문자열길이

int 문자열이름. length()

int 문자열이름.size()

- string 헤더파일 인클루드

- 함수를 호출한 문자열 길이 반환함수. 

- length가 대부분임.

 

문자열 연산

- string 클래스는 문자열 더하기 연산가능

- 더하기 연산자를 중심으로 순서가 바뀌지않고 연산

- 문자 + 문자열, 문자열 +문자, 문자열 +문자열

 

 

배열 초기화 함수

memset(배열이름, 초기화값,sizeof(배열이름));

- 배열전체 초기화함수

- cstring헤더파일

- 배열의 자료형에 따라 초기화값 다르게 입력

 

 

---

함수

int sum(x,y)

반환 자료형 ex) int

함수이름 ex) sum

매개변수 목록 ex) x,y

반환 타입

- 반환 값이 없는 타입 : void

 

함수에 인수 전달방법

01: 값에 의한 전달

02: 참조에 의한 전달

 

 

01) 값에 의한 전달

call by value

- 인수로 전달되는 변수가 가지고있는 값만 함수 내의 매개변수에 복사하는 방식

- 함수 내에서의 매개변수 조작은 인수로 전달되는 변수에 아무런 영향을 미치지 않음.

 

 

02) 참조에 의한 전달

call by reference

- 인수로 전달된 변수의 값을 복사 x

원본 데이터를 직접 전달하는 방식

 

- 동일한 작업 수행

c언어에서는 포인터로, c++ 에서는 참조자로

출처: alcuk

 

참조자?

타입 변수이름;

타입 & 참조자이름 = 변수이름;

- 대상 변수와 같은 메모리 위치 참조

- 참조자를 이용해 연산을 하게 되면 새로 선언된 참조 변수 뿐 아니라,

참조한 대상 변수도 같이 변경됨

- 주의! 변수타입 일치, 초기화 필수, 참조 대상 변경 불가능

 

 

재귀호출

- 함수 내부에서 함수가 자기 자신을 또 다시 호출하는것

- 호출 중단 명령문 필수!

 

시간 복잡도

- 문제를 해결하는데 걸리는 시간

- 알고리즘의 시간복잡도는 빅-오 표기법 사용

 

 

04 최대 공약수, 최소공배수

O(N)

1. 두개의 자연수를 입력받는다(더 큰수 a, 더 작은수 b)

2. 2부터b까지의 수로 a와 b를 모두 나누어보면 가장 큰 공약수를 구할 수 있다.

출처 : alcuk

 

O(log N)

유클리드 호제법

1. 두개의 자연수 a,b에 대해 a를 b로 나눈 나머지를 r이라고한다(a>b)

2. a와b의 최대 공약수는 b와 r의 최대공약수와 같은것을 이용하면 최대공약수를 구할 수 있다.

 

GCD

1) 입력받은 두개의 자연수중 큰값을 a, 작은값을 b

2) a를 b로 나눈다 (나머지가 발생하지않는경우 4번으로 ,b가 a의 약수라는소리)

3) a를 b로 나누어서 발생한나머지를 r이라고 하고 a에 b값을 대입하고, b에 r값을 대입하여2번을 반복

4) 나머지가 발생하지 않을때 ,(r이 0일때) b의 값이 입력받은 두 수의 최대공약수

 

LCM

- 최소 공배수는 두 자연수의 공통된 배수중 가장 작은수

- 최소공배수는 최대공약수를 통해 구할 수 있음