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

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

카드 앞쪽에는 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까지의 합을 알아봤다.

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

퀵 정렬 (quick sort)

퀵정렬 (quick sort)

이번엔 퀵정렬을 알아 보겠다.
퀵 정렬은 n개의 데이터를 정렬할 때, 최악의 경우에는 O(n2)번의 비교를 수행하고, 평균적으로 O(n log n)번의 비교를 수행한다.
위키출처

이라고 한다.
말그대로 빠른 정렬 방식이다.
quicksort
위키 출처

일단 설명을 해보자

만약

6, 3, 8, 7, 9, 2, 1, 5

이런 리스트가 있다고 가정하자!
그럼 일단 왼쪽에 있는걸 피벗으로 잡자
6을 피벗으로 잡는다.
그리고 또한 left도 6 이라고 정하고 맨 오른쪽에 있는걸 right라 정하자
그럼 이런 형식이 될거다

6, 3, 8, 7, 9, 2, 1, 5
P                    R
L

P: 피벗 L: left R: right

그리고 나서 left 는 피벗보다 큰 값이 나올때 까지 오른쪽으로 이동하고 rigth는 피벗보다 작은 값이 나올때까지 왼쪽으로 이동한다.

6, 3, 8, 7, 9, 2, 1, 5
P     L              R

이렇게 됐다. 이동한 후에 두개를 교환한다.

6, 3, 5, 7, 9, 2, 1, 8
P     L              R

계속 이동해야된다.

6, 3, 5, 7, 9, 2, 1, 8
P        L        R   

7은 6보다 큰값이나 정지! 1은 6보다 작은값이니 정지! 다시 교환

6, 3, 5, 1, 9, 2, 7, 8
P        L        R   

아직 더 가야된다. 고고!

6, 3, 5, 1, 9, 2, 7, 8
P           L  R         

또 교환해야된다.

6, 3, 5, 1, 2, 9, 7, 8
P           L  R         

이제 왔다 left가 한번더 가고 right더 한번더가면 곂친다. right 더 앞서 있다.

6, 3, 5, 1, 2, 9, 7, 8
P           R  L         

그럼 이제 피벗이랑 right랑 교환해야된다.
두개가 만났다면 left는 0번째 2이고 rigth는 rigth – 1 즉 배열의4번째요소 1이 된다. 현재 right의 요소를 알고 있어야된다.

2, 3, 5, 1, 6, 9, 7, 8
P  L     R           

그래서 다시 이번엔 피벗을 2로 잡고 left는 처음으로 rigth는 왼쪽으로 이동한다.
3은 2보다 크기 때문에 정지 1은 1보다 작기때문에 정지 교환하자

2, 1, 5, 3, 6, 9, 7, 8
P  L     R           

다시 이동하면 left 5는 2보다 크기 때문에 정지 ! right 5는 2보다 크기 때문에 다시 이동 1보다 작기때문에 정지!

2, 1, 5, 3, 6, 9, 7, 8
P  R  L             

이렇게 모양이 나왔다 다시 R은 L보다 앞에 있기때문에 R과 피벗과 교환한다 그리고 다시 돌아온다.
right는 위에서 기억하고 있던 4번째 left는 위의 right + 1 즉 배열의요소 2번째가 된다.

1, 2, 5, 3, 6, 9, 7, 8
      L  R           
      P

그리고 다시 작업을 한다. 교환을 한다. 그러면 왼쪽 정렬은 끝났다. 오른쪽도 마찬가지로 정렬을 하면된다.

1, 2, 3, 5, 6, 9, 7, 8
         P     L     R

교환하자

1, 2, 3, 5, 6, 8, 7, 9
               L  R   
               P
1, 2, 3, 5, 6, 7, 8, 9

정렬이 완료 되었다.
그럼 소스를 한번 보자!
요즘 스칼라를 공부중이랑 스칼라로 해봤다. 그래봤자 문법을 잘 몰라서 인지 그냥 자바다…
어차피 뭐 알고리즘이라는게 언어에 종속적인게 아니니까..

def partition(arr: Array[Int], left: Int, right: Int): Int = {
  var high = right
  var low = left
  val pivot = arr(left)

  while (high > low) {

    while (high > low && pivot >= arr(low)) {
      low += 1
    }
    while (pivot < arr(high)) {
      high -= 1
    }
    if (high > low){
      swap(arr, low, high)
    }

  }
  swap(arr, high, left)
  high
}

def swap(arr: Array[Int], left: Int, right: Int) = {
  val temp = arr(left)
  arr(left) = arr(right)
  arr(right) = temp
}

def quick(arr: Array[Int], left: Int, right: Int): Unit = {
  if (right > left) {
    val partitionIndex = partition(arr, left, right)
    quick(arr, left, partitionIndex - 1)
    quick(arr, partitionIndex + 1, right)
  }
}
def main(args: Array[String]) {
  val list = Array(6, 3, 8, 7, 9, 2, 1, 5)
  quick(list, 0, list.length - 1)
}

내 소스가 틀릴수도..있으니..흠