첫째 줄에는 두 개의 자연수가 주어진다. 이 둘은 10,000이하의 자연수이며 사이에 한 칸의 공백이 주어진다.
출력
첫째 줄에는 입력으로 주어진 두 수의 최대공약수를, 둘째 줄에는 입력으로 주어진 두 수의 최소 공배수를 출력한다.
입력
출력
24 18
6 72
풀이
최소공배수는 두 수를 곱한 후 최대공약수로 나누면 구할 수 있다.
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
int main(void)
{
int a, b;
int i, j;
scanf("%d %d", &a, &b);
// 최대공약수 구하기
if (a < b)
i = a;
else
i = b;
while (1) {
if (a % i == 0 && b % i == 0)
break;
else
i--;
if (i == 1)
break;
}
printf("%d\n", i);
printf("%d", (a * b) / i);
return 0;
}
두 자연수 A와 B가 있을 때, A = BC를 만족하는 자연수 C를 A의 약수라고 한다. 예를 들어, 2의 약수는 1, 2가 있고, 24의 약수는 1, 2, 3, 4, 6, 8, 12, 24가 있다. 자연수 A의 약수의 합은 A의 모든 약수를 더한 값이고, f(A)로 표현한다. x보다 작거나 같은 모든 자연수 y의 f(y)값을 더한 값은 g(x)로 표현한다.
자연수 N이 주어졌을 때, g(N)을 구해보자.
입력
첫째 줄에 자연수 N(1 ≤ N ≤ 1,000,000)이 주어진다.
출력
첫째 줄에 g(N)를 출력한다.
입력
출력
1
1
2
4
10
87
풀이
처음에 푼 방식
1부터 N까지 하나씩 약수를 확인한 후 약수의 합을 구했다. i가 1부터 4까지, j가 1부터 i까지 도는 이중 for문을 사용하였다.
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
int main(void)
{
int N;
int sum = 0;
scanf("%d", &N);
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= i; j++) {
if (i % j == 0)
sum += j;
}
}
printf("%d\n", sum);
return 0;
}
그러나 이 방식은 시간 초과로 실패하였다.
두 번째 푼 방식
몫을 활용한다.
예를 들어, N을 5로 가정
5 이하의 수 중 1을 약수로 가지는 수의 개수: 5
5 이하의 수 중 2을 약수로 가지는 수의 개수: 2
5 이하의 수 중 3을 약수로 가지는 수의 개수: 1
5 이하의 수 중 4을 약수로 가지는 수의 개수: 1
5 이하의 수 중 5을 약수로 가지는 수의 개수: 1
여기서 개수는 5를 어떤 수로 나눴을 때, 몫이 된다. >> N / i
N = 5, g(N) = 21
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
int main(void)
{
int N;
long long sum = 0;
scanf("%d", &N);
for (int i = 1; i <= N; i++) {
sum += (N / i) * i;
}
printf("%d\n", sum);
return 0;
}
9095번을 숫자 하나를 입력하면 순서를 고려하지 않은 더하기 경우의 수를 출력하도록 변형했다.
입력
4
출력
5
경우의 수 >>
1 + 1 + 1 + 1
1 + 1 + 2
1 + 3
2 + 2
4
입력
출력
4
5
풀이
풀이 핵심
>> 조합 사용
1) bucket 정보
n개의 공간 동적으로 할당
2) 경우의 수를 셀 전역 변수 사용
pick 함수 내에서 변수를 선언한다면 재귀 호출이 되었을 때 0으로 돌아가기 때문에 전역변수로 받았다. 물론 함수 매개변수로 받아도 문제는 없다.
// 1, 2, 3 더하기 쉽게 변형
// 중복 조합
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
int result = 0;
void pick(int n, int* bucket, int m, int k)
{
int i, lastIndex, smallest;
int total = 0;
lastIndex = m - k - 1;
for (i = 0; i <= lastIndex; i++)
total += bucket[i] + 1;
if (total == n) { // 다 뽑았으면
result++;
return;
}
else if (total > n)
return;
if (m == k)
smallest = 0;
else
smallest = bucket[lastIndex];
for (i = smallest; i < n; i++) {
bucket[lastIndex + 1] = i;
pick(n, bucket, m, k - 1);
}
}
int main(void)
{
int n;
int* bucket;
scanf("%d", &n);
bucket = (int*)malloc(sizeof(int) * n);
pick(n, bucket, n, n);
printf("%d\n", result);
return 0;
}
'어떤 범위에서 사용이 가능한가?'이다. 범위는 가시성(visibility)라고도 한다. 범위 속성은 주로 변수가 정의되는 위치에 따라서 결정된다.
- 생존 시간(linkage)
'변수가 메모리 상에 얼마나 오랫동안 존재하는지'를 뜻한다.
- 연결(linkage)
'서로 다른 영역에 있는 변수를 연결하는데 쓰이는 속성'이다.
# 지역변수
- 지역변수(local variable)
함수 또는 블록 안에서 정의되는 변수
int main(void)
{
int x = 3;
}
지역변수는 블록 안에서 선언되는 변수이다. 블록이란 중괄호로 둘러싸인 영역이다. 함수의 몸체, 반복문 안 등...
지역변수는 변수가 선언된 블록 안에서만 접근과 사용이 가능하다. 블록이 다르면 이름이 같아도 다른 변수로 취급한다.
- 지역변수의 생존 시간
전역변수는 프로그램이 시작되기 전에 만들어지고 프로그램이 끝날 때까지 존재한다. 그러나 지역변수는 변수가 선언된 블록이 시작할 때 시스템 스택(stack)이라 불리는 메모리 공간에 만들어지며 동시에 초기화된다. 지역변수에 할당된 메모리 공간은 블록 끝에서 반환 된다. 즉 선언된 블록이 끝나면 자동으로 소멸된다.
예제>>
#include <stdio.h>
int main(void)
{
int i;
for (i = 0; i < 5; i++) {
int temp = 1;
printf("%d\n", temp);
}
}
for문 안에 선언된 지역변수 temp는 for문이 끝나면 사라진다.
- 지역변수의 초기 값
지역변수의 초기 값을 정해주지 않았다면 의미 없는 값이 들어가 있는데 이러한 값을 쓰레기 값(garbage value)이라고한다.
- 함수의 매개변수
함수의 헤더 부분에 정의되어 있는 매개변수도 일종의 지역변수이다. 다만 다른 점은 함수 호출 시의 인수 값으로 초기화되어있다는 점이다.
# 전역변수
- 전역변수(global variable)
함수의 외부에서 선언되는 함수
int x;
int main(void)
{
...
}
- 전역변수의 초기 값과 생존 기간
프로그래머가 전역 변수를 초기화하지 않으면 컴파일러에 의해 0으로 초기화된다.
#include <stdio.h>
int num;
int main(void)
{
printf("num = %d\n", num);
return 0;
}
실행 결과 >>
- 전역변수의 사용
스파게티 코드 : 전역변수들로 인해 코드가 꼬이는 현상
어디서나 접근 가능하다는 것이 장점이자 단점. 따라서 전역변수로 데이터 교환을 하기보다는 잘 정의된 인터페이스를 통해 데이터를 교환하는 편이 낫다.
모듈화 프로그래밍 : 특정 작업을 수행하는 독립된 모듈로 분리하는 것
모듈화 프로그래밍에서 각각의 모듈들은 독립적이어야 한다. 독립적이란 의미 -> 함수는 자신의 작업에 필요한 데이터와 코드를 모두 포함하여야 한다는 뜻. 그러나 전역변수를 사용하면 모듈 밖의 데이터를 사용하게 되어 각 모듈의 독립성을 위반하게 된다.
그러나 상황에 따라서 효율성을 위해 전역변수를 사용하기도 한다.
거의 모든 함수에서 사용하는 공통적인 데이터는 전역변수로 할 수 있다.
일부의 함수들만 사용하는 데이터는 전역변수로 하지 말고 함수의 인수로 전달한다.
# 정적 할당 & 자동 할당
- 정적 할당(static allocation)
프로그램이 실행되는 동안에는 계속하여서 변수에 저장 공간이 할당되어 있는 방법
- 자동 할당(automatic allocation)
블록이 시작되면서 변수에 저장 공간이 할당되고 블록이 종료되면 저장 공간이 회수되는 방법
- 변수의 생존 시간이 결정되는 요인
1. 변수가 선언되는 위치
전역변수 - 정적 할당
지역변수 - 자동 할당, 앞에 저장 유형 지정자를 붙이면 정적 할당으로도 가능
2. 저장 유형 지정자(storage class specifier)
auto 지정자
함수나 블록 내에 선언되는 지역변수는 기본적으로 자동 할당이 된다. "자동"이라고 하는 이유는 변수를 선언한 위치에서 생성되고 블록을 벗어나면서 자동으로 소멸되기 때문이다. 자동 변수로 선언하려면 원칙적으로 auto 키워드를 붙여야한다. 그러나 함수나 블록 안 변수는 키워드를 안붙여도 자동 할당.
static 지정자
블록을 벗어나도 자동으로 제거되지 않는 변수 지정
예제>>
#include <stdio.h>
void f()
{
static int a = 0;
int b = 0;
printf("a = %d\t", a);
printf("b = %d\n", b);
a++;
b++;
}
int main(void)
{
f();
f();
f();
return 0;
}
실행 결과>>
register 지정자
레지스터 : CPU의 일부분, CPU만 사용 -> 데이터를 읽고 쓰는 속도가 매우 빠르다.
volatile 지정자
하드웨어가 변수의 값을 수시로 변경하는 경우에 사용
# 연결
전역변수만이 연결을 가질 수 있다.
- 외부 연결
여러 개의 소스 파일로 이루어져 있는 경우. extern 키워드를 붙여 사용.
- 내부 연결
전역변수 앞에 static이 붙으면 내부 연결이 된다. 즉 하나의 소스 파일 안에서만 사용 가능하다.
프로그램이 하는 일을 설명하기 위해 쓴다. 주석은 프로그램의 실행 결과에 영향을 미치지 않는다. 주석은 꼭 필요한 것은 아니다. 그렇지만 다른 사람이 내가 짠 코드를 읽었을 때 가독성을 높여주기 위해 사용한다. 주석에는 프로그램의 구조와 동작을 설명해주는 문장이 들어간다.
<<사용 방법 >>
한 줄로 된 주석을 사용할 때는 이중 슬래시 //를 사용한다.
// 한 줄로 된 주석
여러 줄로 된 주석을 사용할 때는 /* ... */를 사용한다.
/* 여러 줄로
된
주석 */
# 전처리기
#include <stdio.h>
위의 문장은 전처리기 지시어이다. 위 문장은 헤더 파일 stdio.h를 소스코드 안에 포함하라는 의미의 문장이다.
<<헤더 파일>>
코드의 일부분이 들어 있는 텍스트 파일로서 ".h"의 확장자를 가진다. stdio.h는 "standard input output"의 줄임말로 표준 입출력을 뜻한다. 실제로 표준 입력과 표준 출력에 관한 라이브러리 함수들의 정의가 들어 있다. 출력을 할 때 쓰이는 printf() 함수의 정의는 stdio.h 헤더 파일에 들어 있기 때문에 printf()함수를 사용하기 위해서는 반드시 stdio.h가 포함되어야 한다.
#include <stdio.h>
int main(void)
{
printf("HELLO WORLD !");
return 0;
}
# 함수
함수는 특정 기능을 수행하는 처리 단계들을 괄호로 묶어서 이름을 붙인 것이다.
<<함수의 구조>>
int main(void) // 함수의 출력 타입, 함수의 이름, 함수의 입력 타입
{
...
}
"int main(void)"는 함수 정의의 첫 번째 행으로, 함수 헤더로 불린다. 차례대로 함수의 출력 타입, 함수의 이름, 함수의 입력 타입이 차례대로 나타난다.
