[C] 난수의 활용과 기수 변환 프로그램 구현

자료구조와 알고리즘 시작

오늘부터 자료구조와 알고리즘 공부를 하면서 정리한 내용들을 기록할 것이다.

학습을 위해 내 블로그를 본다면 앞으로의 글은 동적할당, 포인터, 배열에 대한 개념을 이해하고 읽기를 추천한다.

이 포스트에서는 배열 파트를 학습하며 정리한 내용과 더불어 난수를 활용해보고 배열을 사용해 기수를 변환시키는 프로그램을 만드는 내용까지 담아보겠다.

자료구조란 ?

데이터 단위와 데이터 사이의 물리적 또는 논리적인 관계

쉽게 말해 자료를 효율적으로 사용할 수 있도록 컴퓨터에 저장하는 방법

배열의 요소 개수 구하기

sizeof(a) / sizeof(a[0]) 

전체 배열 크기를 첫 요소 크기로 나눈 몫이 요소의 개수가 된다.

NULL이란

NULL은 '값 0을 갖는 모든 정수, 상수 또는 상수식을 void* 형으로 변환한 식'이다.

이는 많은 라이브러리에서 다음과 같이 정의 되어 있다.

#define NULL ((void*)0)

이는 C에서 <stddef.h>헤더에 정의되어 있는데, <locale.h>, <stdio.h>, <stdlib.h>, <time.h> 가운데 어느 헤더를 포함해도 선언한 것과 마찬가지로 동작한다.

함수의 매개변수에 배열 넣기

int maxof(const int a[], int n){
  int max = a[0];
  for(int i = 1; i<n; i++) {
    if (a[i] > max) max = a[i];
  }
  return max;
}

여기서 매개변수의 선언에서 [ ]는 배열이 아니라 포인터를 선언하는 것과 같다.
즉 const int a[ ]는 const int *a로 해석된다.

이때 const는 그 인수가 가리키는 배열의 요소에 접근할 수 없도록 한다. 이로 인해 maxof 함수에서 배열은 읽기 전용으로 바뀌여 읽기는 가능하지만 수정은 불가능하게 된다.

난수 사용하기

난수로 배열의 요솟값 설정하기

#include <stdio.h>
#include <time.h>
#include <stdlib.h>

int maxof(const int a[], int n){
  int max = a[0];
  for(int i = 1; i < n; i++){
    if(a[i] > max){
      max = a[i];
    }
    return max;
  }
}

void main(){
  int number;
  printf("몇 명인가요 ? : ");
  scanf("%d", &number);
  int *height = calloc(number, sizeof(int));
  srand(time(NULL));
  for(int i = 0; i < number; i++){
    height[i] = 150 + rand() % 40; 
    printf("height[%d] = %d\n", i, height[i]);
  }
  printf("최대값은 %d 입니다.\n", maxof(height, number));
  free(height);
}

난수에 대해 설명하기 전 난수를 생성하는 과정을 요약해보겠다.

1. rand 함수, srand 함수가 포함된 <stdlib.h>과 time 함수가 포함된 <time.h> 헤더를 포함시킨다.
   
   
2. 난수의 시드를 현재 시간을 기준으로 초기화하기 위해 srand 함수를 호출한다.
   
   
3. rand 함수를 호출하여 난수를 생성한다.

이 과정에서 rand 함수가 반환하는 값은 0 이상 RAND_MAX 이하의 값인데 RAND_MAX 값은 컴퓨터 환경에 따라 다르고 최소 32,767이다.

rand() 함수만으로 난수 만들기

#include <stdio.h>
#include <time.h>
#include <stdlib.h>

void main(){
  int x = rand();
  int y = rand();
  printf("x = %d이고 y = %d", x, y);
}

-------------------------------------
4번 실행한 결과 
x = 1804289383이고 y = 846930886
x = 1804289383이고 y = 846930886
x = 1804289383이고 y = 846930886
x = 1804289383이고 y = 846930886

위와 같이 rand 함수가 값을 반환할때는 시드를 사용하여 난수를 생성하기 때문에 시드가 일정할 경우에 매번 같은 순서의 난수를 생성하게 된다.

매번 같은 순서의 난수가 생성된다면 이는 난수라고 보기 어려울 것이다. 이 문제를 해결하고자 시드 값을 변경하는 srand 함수를 사용한다.

이때 srand(50); 과 같이 시드를 변경할 수도 있지만, 결국엔 시드가 50일때의 순서로 같은 순서의 난수가 계속 등장할 것이다.

그러하여 주로 사용하는 방법은 srand 함수에 현재 시간의 값을 주는 방법이다.

앞의 예제에서 사용했듯 srand(time(NULL)); 를 통해 시간이 지날때마다 난수가 바뀌도록 무작위로 난수를 생성할 수 있다.

의사 난수

여기서 rand 함수처럼 난수처럼 보이지만 일정한 규칙에 따라 생성되는 수를 의사 난수라고 부른다.

이와 같은 의사 난수들은 한번 난수를 생성하면 다음에 생성할 난수를 예측할 수 있다.

난수 활용 연습하기 - 배열 a의 모든 요소의 순서를 뒤섞는 shuffle() 함수

#include <stdio.h>
#include <time.h>
#include <stdlib.h>

int shuffle(int a[], int n){
  srand(time(NULL));
  int temp;
  int rn;
  for(int i = 0; i < n; i++){
    rn = rand() % n;
    temp = a[i];
    a[i] = a[rn];
    a[rn] = temp;
  }
}

rand 함수를 사용할땐 나머지를 활용하면 쉽게 쓸 수 있다는 점을 잘 기억해야겠다.

배열 요소를 역순으로 정렬하기

int a[7] = {1, 2, 3, 4, 5, 6, 7};

위와 같은 배열을 역순으로 {7, 6, 5, 4, 3, 2, 1} 처럼 정렬하려면 a[0]과 a[7]의 자리를 바꾸고 a[1]과 a[6]의 자리를 바꾸는 식으로 중앙을 기준으로 양쪽 값의 위치를 바꾸면 될 것이다.

이때 유의할 점은 x와 y의 값을 교환할때 원래의 값을 잃지않도록 임시로 x 값을 보관해줄 추가적인 변수 temp가 필요하다는 점이다.

이 원리로 n개 요소가 있는 배열에서 순서를 바꾸는 코드를 간단하게 짜보겠다.

for(int i = 0; i < n/2; i++){
  int temp = a[i];
  a[i] = a[n-i-1];
  a[n-i-1] = temp;
}

이와 같은 기능들은 자주쓰여 x와 y값을 바꾸는 함수 형식 매크로로도 구현해놓으면 좋을 것이다.

#define swap(type, x, y) do{type t = x; x = y; y = t ;} while(0)

while(0)은 거짓이므로 한번만 실행하라는 뜻이고

굳이 do while 문을 사용한 이유는 while(0) 뒤에 세미콜론을 안 붙인상태로 치환함으로써 사용할때 함수처럼 swap(); 형태로 사용하기 위해서이다.

do while 없이 치환한다면 사용 시에 swap(int, a[i], a[n-i-1]) 형태로 세미콜론 없이 사용해야해므로 이상하게 느껴질 것이다.

이 지식을 기반으로 10진수를 n진수로 만드는(기수 변환) 프로그램을 만들어 볼 것이다.

기수 변환을 수행하는 프로그램

숫자를 n으로 나눈 몫이 0이 될때까지 나머지를 자리에 대입하며 나누기를 반복하는 방법을 이용한 알고리즘이다.

#include <stdio.h>

#define swap(type, x, y) do{type t = x; x = y; y = t ;} while(0)

void convert_decimal(unsigned int x, int n, char result[]){ //x를 n진수로 바꾸어 result[]에 저장
  char letter[] = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";
  int digits = 0; //변환 후 자릿 수
  if(x == 0) {
    result[digits++] = letter[0];
  }else{
    while(x){ //x가 0이 될때까지 반복
      result[digits++] = letter[x % n]; //나머지를 대입
      x /= n; //몫을 저장
    }
  }
  for(int i = 0; i < digits/2; i++){ //digits/2 즉 짝수일 경우에는 전부 교체 홀수일 경우엔 중앙값만 나두고 교체
    swap(char, result[i], result[digits - i - 1]); 
  }
}

int main(){
  int retry;
  unsigned int unchanged_number;
  int n;
  char changed_number[512];
  do{
    printf("\n10진수를 입력하세요 : ");
    scanf("%d", &unchanged_number);
    printf("\n몇 진수로 변경할까요 ? : ");
    scanf("%d", &n);
    if(n != 0){
      convert_decimal(unchanged_number, n, changed_number);
      printf("\n%d에서 %d진수로 변경한 결과 : %s\n\n", unchanged_number, n, changed_number);
      printf("계속 하려면 (1) 그만두려면 (0) : ");
      scanf("%d", &retry);
    }else{
      printf("\n0으로 나눌 수 없습니다\n");
      retry = 1; 
    }
  }while(retry == 1);
}

나머지값을 배열에 앞에서부터 대입하고 역순으로 정렬함으로써 간단하게 n진수로 변환할 수 있는 프로그램이다.

배열에 대해선 여러 언어에서 오랫동안 다뤄서 비교적 쉬웠지만, shuffle 함수를 구현할 때 되게 쉬운 함수임에도 생각을 꽤나 해야만 했다.

그래도 생각을 곰곰히 해보고 직접 코드를 손으로 치며 공부하고, 벨로그를 작성하며 복습까지 하니 확실히 시간은 오래걸려도 개발 능력이 점차 좋아지는 것 같다.

다음 포스트에서는 소수를 나열하는 프로그램을 짜고 알고리즘을 개선시키는 과정을 다뤄보겠다.