생활속 재미있는(?) 수학이야기

오늘은 재미삼아 생활 속의 수학이야기를 해보려고 한다. 재미있을지는 잘 모르겠으나 어쩄든..
우리가 사는 일상생활속에는 수학과 관련된 것 들이 아주 많이 존재 한다. 그 중에서 숫자와 관련된 이야기를 해보려고 한다. 주민등록번호, 군번, 휴대폰번호, 신용카드번호 등 모두 다양한 숫자로 이루워져 있다. 그냥 보기에는 아무 번호나 막 갖다 붙인 듯(?) 보이지만 실제로는 규칙이 정해져 있다. 주민번호는 뭐 다들 아시다시피 성별, 행정구역 (뒷자리)등으로 숫자가 부여받게 되는 것은 누구나 잘 아는 규칙일 듯 싶다. 그 중에서 오늘 살펴볼 숫자는 신용(체크) 카드 번호의 비밀을 알아보고자 한다.

카드 앞쪽에는 16개의 숫자로 이루워져 있다. 딱 보기에는 별 의미 없어 보일 수도 있지만 여기에도 규칙이 숨어있다.
한번 알아보자.

카드의 맨앞자리 숫자는 카드 종류의 따라 결정 된다. 예를 들어 맨 앞자리 숫자가 4인 경우는 비자카드, 5인 경우는 마스터 카드, 9인 경우는 국내용 카드, 35이면 JBC 카드 기타 등등으로 종류가 나누어 진다.
그리고 맨 앞자리부터 여섯 번째 짜리까지는 BIN(Bank Identifier Number)로 카드의 발급 기간 식별이 가능하다. 여기까지는 카드 종류와 발급에 따라 숫자가 부여 된다.
그렇다면 만약 맨 앞 숫자가 9인 경우는 해외에서는 사용하지 못하는 걸까? 흠..

다음으로 나오는 7번째 부터 15번째 까지의(마지막 숫자만 제외) 숫자는 카드사가 임의의 규칙에 따라서 부여가 된다. 이건 카드사 마음대로 할 수 있는 부분인 듯하다. 카드사 마다 다르겠지만 어떤 특정한 알고리즘을 사용할 수 도 있고 아니면 그냥 임의의 숫자를 랜덤으로 돌릴 수도 있을 듯하다. 이건 카드사의 개발자나 관리자들만 알겠지..

그럼 마지막 숫자는 무엇일까? 눈치 빠른 사람은 벌써 눈치 챘겠지만 주민등록번호에도 존재하는 숫자이다. 바로 체크 숫자라고 불리는데 이 숫자는 복잡한(?) 수학 공식에 따라 결정이 된다.

이 마지막 체크 숫자는 어떠한 공식에 의해 부여가 되는데 그 공식이 룬 공식(LUHN Formula) 이라고 한다.
이 공식만 알면 우리는 마지막 숫자를 알 수 있게 된다. 그럼 룬 공식이 뭔가? 룬 공식의 규칙을 알아보자.

  1. 카드 번호의 매 홀 수 자리의 숫자마다 2를 곱해서 더한다. 이 때, 나온 숫자가 두 자리 수이면 각자리의 숫자를 더한다.
  2. 앞에서 연산하지 않은 매 짝수 자리는 각 숫자를 더한다.
  3. 1에서 나온 숫자와 2에서 나온 숫자를 더한다.
  4. 마지막으로 나온 값이 10으로 나누어 떨어지도록 체크 숫자를 정하면 된다.

말로는 이해가 안될 수도 있으니 한번 예제를 들어보자. 만약 아래와 같은 번호가 있다고 하자.

4, 7, 1, 6, 1, 0, 8, 9, 5, 6, 3, 5, 4, 5, 9, 9

위의 카드 번호는 테스트 할 수 있는 유효한 카드 번호이다. 근데 실제로 있는건 아니겠지?..
1번을 보면 매 홀 수자리 마다 2를 곱해서 더한다고 했으니 다음과 같다.

(4 × 2) + (1 × 2) + (1 × 2) + (8 × 2) + (5 × 2) + (3 × 2) + (4 × 2) + (9 × 2)

그리고 나서 곱한 수가 두자리 라면 각 자리 수를 더한다.

8 + 2 + 2 + (1 + 6) + (1 + 0) + 6 + 8 + (1 + 8) = 43

위의 소괄호는 알아보기 쉽게 두자리가 나온 숫자들이다. 다 더하면 43이 나온다.
그 다음 마지막을 제외 하고 매 짝수자리를 다 더한다.

7 + 6 + 0 + 9 + 6 + 5 + 5 = 38

위의 두개의 숫자를 더하면 81이 나온다. 그럼 어떤 숫자가 와야지 10으로 딱 떨어지게 되나? 뭐 안봐도 뻔하지만 마지막숫자는 9가 되어야만 10 으로 떨어지게 된다. 한 번 자신의 카드를 꺼내서 확인 해보도록 하자.

여기서 끝내면 조금 아쉽다. 우리는 개발자다. 한번 위의 공식을 코드로 나타내 보자. 뭐 알고리즘이라고 할 것도 없이 너무 간단해서 쉽게 풀 수 있을 것이다.

아래는 필자가 대충 짠 코드가 있긴한데 한번 자신이 짜보도록 하자.

@Test
public void creditCardNumberTest() {
  final int[] list = {4, 7, 1, 6, 1, 0, 8, 9, 5, 6, 3, 5, 4, 5, 9, 9};
  System.out.println(creditCardNumber(list));
}

private boolean isCreditCardNumber(int[] array) {
  int sum = 0;
  for (int i = 0; i < array.length - 1; i++) {
    if ((i - 1) % 2 == 0) {
      sum += array[i];
    } else {
      final int two = array[i] * 2;
      sum += (two / 10 + two % 10);
    }
  }
  sum += array[array.length - 1];
  return sum % 10 == 0;
}

에러 처리나 카드 번호가 꼭 16개인지는 체크 하지 않았다. 그냥 알고리즘만 보면 되어 대충 해놨으니 그냥 참고만 하도록하고 직접 해보자!

또 한 15개의 카드 번호만 입력후에 어떤 값이 체크숫자인지도 출력하는 코드도 함께 작성해보자!. 뭐 이건 위의 코드를 아주 살짝만 건드면 되니.. 대충 이런코드가 되지 않나 싶다.

private int creditCardNumber1(int[] array) {
  int sum = 0;
  for (int i = 0; i < array.length; i++) {
    if ((i - 1) % 2 == 0) {
      sum += array[i];
    } else {
      final int two = array[i] * 2;
      sum += (two / 10 + two % 10);
    }
  }
  return 10 - (sum % 10);
}

아주 간단하게 풀어봤다. 수학카테고리도 종종 이용해야 겠군..
오늘은 이상이다!

1부터 100까지 더해보자

오랜만에 알고리즘 공부를 해보자
아주 간단한 알고리즘이다 1부터 100까지 혹은 n부터 m까지의 더하는 알고리즘이다.
솔직히 아주 간단하다. 하지만 여러 방법으로 접근해보자
그게 목적이다 ㅎㅎㅎ

일단 우리가 흔히 쓰는 1부터 100까지의 합이다 소스를 보자

int sum = 0;
for (int i = 1; i <= 100; i++) {
    sum += i;
}
System.out.println(sum);

흔히 쓰는 방법이라 따로 설명은 생략하겠다.
참고로 자바8에선 더 간단해졌다.

System.out.println(IntStream.rangeClosed(1, 99).sum());

위와 같이 하면 된다.

하지만 여기서는 알고리즘 자체를 생각해보는 시간이기에 생략하겠다.
이번엔 천재수학자 가우스가 발견한 덧셈이다.
누구나 들으면 ‘아하’ 이러겠지만 어렸을때 이방법을 생각해낸 자체가 정말 천재인듯 싶다.
예를 들어 1부터 10까지의 합을 구하고 싶다고 가정하자.
그러면 이런방식으로 할 수 있겠다.
1,2,3,4,5,6,7,8,9,10
1과 10을 더하면 11
2와 9를 더하면 11
3과 8을 더하면 11
4와 7을 더하면 11
5와 6을 더하면 11
그럼 11을 5번 더하면 그게 1부터 10까지의 합이다.
공식으로 보자면
(n + 1) * (n / 2)
위와 같은 공식이 성립할 것이다.
코드로 보자면 아래와 같다

int n = 10;
System.out.println((n + 1) * (n / 2));

근데 여기에선 문제점이 있다. 만약 n이 짝수 일 경우에는 상관없지만 홀수인 경우에는 알고리즘이 성립하지 않는다.

int n = 9;
System.out.println((n + 1) * (n / 2));

실제 1부터 9까지의 합은 45이나 위와 같은 코드를 실행 하였을 경우에는 40이 나온다.
그러면 짝수일 경우에는 위와 같이 하면 되고 홀수 인 경우에는 어떻게 해야 될까
만약 1부터 9까지를 예를 들어보자
1,2,3,4,5,6,7,8,9
그럼 일단 마지막 숫자인 9를 잠시 잊고 있자
1부터 8까지 짝수 알고리즘을 실행하고 나머지 9를 더하면 1부터 9까지 합이 될 것이다.

static int sum(int n){
  if(n % 2 == 0){
    return (n + 1) * (n / 2);
  }else{
    return n * ((n - 1) / 2) + n;
  }
}

위와 같이 n에 1을 빼서 계산하면 된다. ((n + 1) – 1) 은 n이 된다.
좀더 고민을 해보자.
홀수나 짝수나 공식을 똑같다. n에다 1을 빼주고 마지막만 n을 더해주면 되는 것이다.

static int sum(int n){
  if(n % 2 == 0){
    return (n + 1) * (n / 2);
  }else{
    return sum(n - 1) + n;
  }
}

재귀를 이용해서 구했다. 홀수일 경우에는 sum에다 1을 빼주고 n만 더해주면된다.
1부터 n까지의 합이 이렇게 많은 알고리즘이 있다.

마지막으로 우리가 고등학교?때 배운 수열이다.
맞나 고등학교때 배운게… 중고등학교때 수학 공부를 많이 했어야 되는데..
아무튼 수열의합을 이용해서 구해보자
인터넷에 쳐보면 등차수열의합이 자세히 설명 되어있다.
a를 첫째항 d를 공차라 하자. 공차란 두수의 차를 말한다.
공식의 증명은 인터넷으로…
n * {2a + (n – 1) * d} / 2
등차수열의합은 위와 같은 공식을 성립한다.
만약 10까지 합을 구한다하면
10 * {2 + (10 – 1) * 1} / 2
계산을 해보면 10 * 11 / 2 따라서 55가 나온다.
홀수인 1부터 9까지를 해보자
= 9 * {2 + (9 – 1) * 1} / 2
= 9 * 10 / 2
= 45
아주 잘 된다.
소스를 보자

int a = 1;
int n = 10;
System.out.println(n * (2 * a + (n - 1) * 1) / 2);

등차수열의합으로 100부터 200까지의 2배수의합 등 여러가지를 구할 수 있다.
수학은 참 아름답단말야..ㅋㅋㅋㅋ
이렇게 간단하게 1부터 n 혹은 n부터 m까지의 합을 알아봤다.

수학 기호를 어떻게 쓰지…흠

순열이란

순열

  • 서로 다른 n개에서 r개를 택하여 일렬로 배열하는 것을 n개에서 r개를 택하는 순열
  • nPr로 나타낸다.

문제) 1,2,3,4,5의 다섯개 숫자중에서 서로 다른 세 개의 숫자를 사용하여 만들 수 있는 세 자리의 자연수의 개수를 구하여라

  • 5P3 = 5×4×3 = 60

특수한 경우

문제) m,a,t,h의 네 개 문자중 m,t 이웃하도록 배열

  • (mt), a, h를 한덩어리로 본다. 그럼 3!
  • 또한 mt, tm 도 가능하기 때문에 2!
  • 3!× 2!

문제) 1~5 5장 숫자카드중 세자리 짝수의 경우의수는?

  • 조건을 보면 짝수 조건이다.
  • 그럼 마지막의 올 수 있는 카드는 2 또는 4 밖에 올 수 없다. XX2 또는 XX4
  • 그럼 첫번째 자리에 올 수있는 카드의 개수는 4 두번째는 3 그리고 마지막 자리엔 2개
  • 4 × 3 × 2

중복 순열

  • 순열과 마찬가지로 n개중에 r개를 택하는데 중복을 허용하는 순열이다.
  • n∏r로 나타낸다.

문제) 1~5 숫자카드중 세자리 자연수를 만들수있는 개수는? (중복허락)

  • 첫 번째자리에 올 수있는 카드의 개수는 5개 두 번째도 5개 세 번쨰도 5개
  • 5∏3 으로 나태낸다.
  • 5 × 5 × 5 개수이다.

문제) 1 2 두개의 카드중 중복을 허용해서 세자리 자연수로 나타낼수 있는 개수는

  • 첫 번째자리에 2개 두 번째도 2개 세번쨰도 2개
  • 2∏3
  • 2 × 2 × 2

n∏r중에 n은 중복되는 것이 온다.
쉽게 설명에서 n는 집 r은 사람이라 생각하면 된다.

문제) 5명의 유권자중에 2명의 후보에게 투표 방법은?

  • A라는 후보에 5명이 모두 투표 할 수 있다. 이건 A A A A A 라 볼 수 있다.
  • 또는 A에 두명 B엔 3명이 투표를 할 수 있다. 이건 A A B B B 라 볼 수 있다.
  • 그럼 2∏5가 정답이다.

같은 것이 있는 순열

  • n개 중에서 서로 같은 것이 각각 p개,q개 … r개씩 있을 때 이들 n개를 모두 일렬로 배열하는 순열

문제) s, o, c, c, e, r 6개 문자를 일렬로 배열하는 경우의 수

  • 일단 6개 숫자중 같은 것이 없다고 생각하고 배열 6!
  • 그리고 같은 것이 c 두개가 있으므로 2!
  • 두개를 나눠주면 된다.
  • 6!/2!

문제) a,b,c,d,e,f 6개의 문자중 일렬로 배열하는 경우의 수 하지만 b가 d 보다 항상 앞에 있어야 된다.

  • 예로 abcdef 와 adcbef가 배열로 있을 때 두번째는 d가 b보다 앞에 있기 때문에 1개로 취급한다.
  • 1개로 취급 즉 같은 것으로 취급하면 된다.
  • 6!/2!이다.

문제) 숫자 1이 적힌 카드가 3장, 숫자 2가 적힌 카드 2장, 숫자 0이 적힌 카드 1장이 있다. 이 6장의 카드를 일렬로 배열하여 6자리의 자연수를 만들 때, 서로 다른 자연수의 개수는?

  • 일단 0은 맨 앞자리로 못온다.
  • 맨 앞자리에 올수 있는 카드는 1 또는 2
  • 1이 맨 앞에 올 때 올 수 있는 카드는 1 1 2 2 0 5!/2!2! = 30
  • 2가 맨 앞에 올 때 올 수 있는 카드는 1 1 1 2 0 5!/3! = 20
  • 두개를 더하면 된다. 50