알고리즘-수학1

수학

입출력 글(https://foxtrotin.tistory.com/90)에서 알고리즘 문제풀이의 과정을 (1)문제를 읽고 (2)입력을 받아서 (3)계산하고 (4)결과를 출력한다 라고 했었습니다. 하지만 엄밀히 따지면 이 과정은 전체 과정 중 ‘구현’ 부분에 해당합니다. 그러면 ‘구현’ 이전에 해야 하는 과정은 또 뭐가 있을까요? 바로 문제를 해결할 방법을 생각하는 것입니다. 위에 네 단계에서는 (1)과 (2) 사이에 들어가는 과정이겠네요. 아무리 뛰어난 코딩 실력이 있어도 어떻게 풀지 모른다면 코딩 실력은 무의미해질 것입니다. 그래서 ‘문제 해결 능력’이 보통 문제 풀이에서 가장 중요한 능력으로 여겨집니다. 이번 주에는 우리가 잘 알고 있는 수학 몇 가지를 다루면서 문제를 어떻게 해결하는지, 어떻게 프로그램적으로 표현하는지에 대해 다뤄보겠습니다.

 

 

1. 나머지 연산

C언어에는 사칙연산 이외에도 나머지를 구하는 연산자가 있습니다. 정수와 정수를 나눌 때, 예를 들어 7/4를 한다고 하면 수학에서는 몫은 1 나머지는 3이 나옵니다. 하지만 C언어에서는 7/4만 하면 나머지는 다 생략되고 몫으로 1만 출력합니다. 이때 나머지를 구하는 연산이 바로 %입니다.

#include <stdio.h>
 
int main(){
    printf("%d %d", 7/4, 7%4);
}
 
//1 3

 

나머지 연산은 나누어 떨어진다면 나머지가 0이 나오고, 나눠 떨어지지 않는다면 0이 아닌 수가 나옵니다. 이 성질을 이용하여 나머지 연산은 보통 특정 수의 배수인지 판별할 때 사용합니다. 또는 매우 큰 경우의 수가 주어지는 문제에서, 큰 정수의 구현보다는 나머지 연산으로 정답을 출력하는 문제도 많이 만날 수 있을 것입니다.

 

 

 

주의

나머지 연산은 실수에서 사용할 수 없습니다. 또한 0으로 나눌 수 없습니다.

#include <stdio.h>
 
int main() {
    printf("%f", 7.1 % 4.2);
    printf("%d", 7 % 0);
}

 

 

2. 소수

소수는 약수가 1과 자기자신 밖에 없는 수입니다. 소수를 판별할 때도 나머지 연산을 이용할 수 있습니다. 어떤 수가 주어졌을 때 2부터 그 수보다 작은 수를 하나씩 곱하면서 하나라도 나누어 떨어지는 수가 있다면 그 수는 소수입니다. 프로그램으로 구현하면 for문 하나, if문 하나로 해결할 수 있습니다.

#include <stdio.h>
int num, i;
int main() {
    printf("정수를 입력하세요: ");
    scanf("%d", &num);
    for (i = 2; i < num; i++) {
        if (num%i == 0) break;
    }
    if (num == i) printf("%d는 소수입니다\n", num);
    else printf("%d는 소수가 아닙니다\n", num);
}

 

6번 줄) 1은 소수가 아니기 때문에 제외하고, 자기자신도 제외해야 하기 때문에 i < num입니다.

7번 줄) 하나라도 i에 나누어 떨어지면 소수가 아닌 수가 됩니다. 하나라도 걸리면 for문을 강제 종료합니다.

9번 줄) 위에 if문에서 걸렸다면 i가 num까지 증가하지 못한 상태에서 for문을 빠져 나오게 됩니다. 만약 끝까지 for문을 돌아서 i==num이라면 소수고, 중간에 빠져 나왔으면 소수가 아니라고 출력합니다.

 

 

그런데 사실, 이렇게 하나의 수마다 그 아래 수를 전부 계산해보는 방법은 범위가 조금만 늘어나도 처리 시간이 한없이 늘어납니다. 그러면 문제의 제한 시간에 못 맞추고 시간초과가 뜨겠죠. 소수를 더 빨리 구하는 방법에는 ‘에라토스테네스의 체’가 있습니다.

 

1) 1부터 n까지 모든 정수를 적고 1은 소수가 아니므로 지웁니다.

2) 아직 지우지 않은 수 중 가장 작은 수를 찾아 그 수의 배수들을 전부 지웁니다.

3) 2번 과정을 모든 수에 한 뒤, 지워지지 않은 수들이 n 이하의 소수입니다.

 

에라토스테네스의 체에 대한 자세한 설명은 수학2 게시글(https://foxtrotin.tistory.com/96)에 있습니다.

 

 

3. 팩토리얼

팩토리얼은 1부터 자기 자신까지의 양의 정수를 곱한 것입니다. 공식으로 표현하면 n! = 1*2*3*…*n 입니다. 프로그램으로 구현할 때도 공식과 똑같이 하면 됩니다.

#include <stdio.h>
int n, res=1;
 
int main(){
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        res *= i;
    }
    printf("%d", res);
}

 

 

추천 문제

10430 나머지 – 그냥 구현하면 됩니다

3052 나머지 – 배열을 하나 선언해서 42로 나눈 나머지를 저장해둡니다. for문을 돌면서 나온 나머지들을 더합니다. 중복이 있어도 하나로 칩니다.

2576 홀수 – n%2를 하면 홀수인지 짝수인지 알 수 있습니다.

1978 소수 찾기 – 위에서 다룬 내용입니다

10872 팩토리얼 – 위에서 다룬 내용입니다