[Hive Helsinki / Piscine] C05
Exercise 00: ft_iterative_factorial
Create an iterated function that returns a number. This number is the result of a factorial operation based on the number given as a parameter.
Allowed Function: None
C05에서는 iterative와 recursive에 대한 문제가 주를 이룬다. 특히 recursive의 개념을 익히기 위한 프로젝트라는 생각이 든다. 이 문제는 iterative를 적용한 문제인데, factorial을 iterative로 구현하는 것이다. iterative는 반복문을 이용하여 반복하는 방식이고, recursive는 함수 자체를 해당 함수 내에서 다시 사용해서 반복하는 방식이다. 따라서 이 문제에서는 반복문을 활용해서 팩토리얼을 계산하는 함수를 구현하면 된다.
우선 factorial의 정의 자체가 0!이 1이기 때문에 이를 예외적으로 처리해주었다. (팩토리얼의 정의가 그런 건데, 왜 그렇냐는 질문에 설명해 주느라 애먹었던 기억이 있다.) 그리고 invalid한 값을 인자로 받으면 0을 리턴해야 하기 때문에, nb가 0보다 작은 경우를 다시 예외처리해 줬다. 그 이후에는 while문에서 nb를 하나씩 줄여가며 res값에 하나씩 곱해준다. 사실 끝까지 보면 nb가 0인 경우를 굳이 예외처리해 줄 필요가 없다는 것을 알 수 있다. 어차피 res의 초기값이 1이고, while문은 nb가 0보다 커야 실행되기 때문에 결국 nb가 0이면 1이 리턴된다. 하지만 뒤에 나올 recursive에서 어차피 필요한 조건이기 때문에 추가해 줬다.
int ft_iterative_factorial(int nb)
{
int res;
if (nb == 0)
return (1);
if (nb < 0)
return (0);
res = 1;
while (nb > 0)
{
res *= nb;
nb--;
}
return (res);
}
Exercise 01: ft_recursive_factorial
Create a recursive function that returns the factorial of the number given as a parameter.
Allowed Function: None
이 문제는 앞선 exercise00을 recursive로 바꿔서 구현하면 된다. if문에 나오는 조건은 모두 같고, 반복을 어떻게 수행하는지만 다르다. return에서 바로 nb 자신에 함수 자신에 nb-1을 넣은 결괏값을 곱하면 된다.
int ft_recursive_factorial(int nb)
{
if (nb == 0)
return (1);
if (nb < 0)
return (0);
return (nb * ft_recursive_factorial(nb - 1));
}
나는 항상 좀 복잡한 recursive 코드를 짤 때, 적어보면서 이해하려 하는데, 이 문제는 복잡하진 않지만 설명을 위해 recursive의 과정을 적어보았다. recursive를 처음 접하는 분들이 이해하는데 도움이 되길 바란다. 설명을 덧붙이자면, 마지막 recursvie_factorail() 함수가 if문을 만나 1을 return하게 되기 때문에, 하나씩 리턴하면서 원하는 곱셈 연산을 만들 수 있게 되는 것이다.
Exercise 02: ft_iterative_power
Create an iterated function that returns the value of a power applied to a number. An power lower than 0 returns 0. Overflows must not be handled.
Allowed Function: None
이 문제는 제곱을 계산하는 iterative 함수를 만드는 문제이다. nb의 power 제곱을 구해 return하는 것이 목표이다. 원래는 <math.h> 헤더에 있는 pow() 함수를 사용하면 되지만, 해당 함수 사용이 불가능하므로 직접 제곱을 구현해야 한다. 어려운 개념이나 알고리즘이 아니므로 바로 코드로 넘어가려 한다.
함수의 처음에 정의된 res 변수는 결과를 저장하려 return하기 위한 변수이다. 그리고 함수 초반에 여러 조건들이 나오는데, 예외적인 상황을 처리하기 위한 조건이다. 우선 power가 0 미만인 경우 invalid한 input이라고 판단하여 0을 리턴한다. 그리고 power가 0인 경우는 nb 값에 상관없이 결과가 1이 되므로 1을 리턴해준다. 마지막으로 power가 0인 경우를 제외하고 nb가 0이면 결과는 0이 되기 때문에 0을 리턴한다.
이 외의 경우에는 power번 nb를 반복해서 곱해주면 된다. 그래서 res의 초기값을 1로 설정하고, power를 하나씩 줄여가며 res에 nb를 곱해준다. 마지막으로 res를 리턴하면 함수는 마무리된다.
int ft_iterative_power(int nb, int power)
{
int res;
if (power < 0)
return (0);
if (power == 0)
return (1);
if (nb == 0)
return (0);
res = 1;
while (power-- > 0)
res *= nb;
return (res);
}
Exercise 03: ft_recursive_power
Create a recursive function that returns the value of a power applied to a number. Overflows must not be handled, the function return will be undefined.
Allowed Function: None
이 문제는 제곱을 recursive로 계산하는 문제이다. 지난 문제와 조건이 다 동일한데, 하나만 추가되었다. nb가 1일 때의 조건이 추가된 것인데, 사실 없어도 power가 0이 되면 1이 리턴되어 1이 한 번 곱해지는 것이므로, 결과가 크게 달라지지는 않지만 제곱의 정의를 보다 엄밀하게 따르기 위해 추가한 조건이다.
int ft_recursive_power(int nb, int power)
{
if (power < 0)
return (0);
if (power == 0)
return (1);
if (nb == 0)
return (0);
if (power == 1)
return (nb);
return (nb * ft_recursive_power(nb, --power));
}
Exercise 04: ft_fibonacci
Create a function ft_fibonacci that returns the n-th element of the Fibonacci sequence, the first element being at the 0 index. We’ll consider that the Fibonacci sequence starts like this: 0, 1, 1, 2.
Allowed Function: None
이 문제는 피보나치 수열의 n번째 숫자를 구하는 함수를 만드는 문제이다. 그리고 recursive로 만들어야 하는 것이 조건이다.
함수를 시작할 때, 문제에 index가 0보다 작으면 -1을 리턴해야 하는 조건이 있으므로, 예외처리 해주고, 만약 index가 0이나 1이면 그 자체가 결과이기 때문에 index 자체를 리턴해준다. 그 외의 경우에는 recursive로 ft_fibonacci() 함수 자체에 index - 2와 index - 1을 넣은 것을 더한 값을 리턴해주면 된다.
int ft_fibonacci(int index)
{
if (index < 0)
return (-1);
if (index <= 1)
return (index);
return (ft_fibonacci(index - 2) + ft_fibonacci(index - 1));
}
Exercise 05: ft_sqrt
Create a function that returns the square root of a number (if it exists), or 0 if the square root is an irrational number.
Allowed Function: None
이 문제는 인자로 주어진 nb의 제곱근을 구하는 함수를 만드는 문제이다. 보통은 <math.h> 헤더에 있는 sqrt() 함수를 사용하나, 여기서는 직접 구현하는 것을 요구했다.
기본적인 방법을 설명하면, 제곱했을 때 딱 nb값이 되는 '어떠한 수'를 찾는 것이 목표가 된다. 따라서 while문을 통해서 제곱했을 때 nb가 되는 값을 찾아서 리턴하면 된다. 하지만 nb가 0보다 작은 경우는 제곱근 값이 존재하지 않으므로 0을 리턴해주고, nb가 0이나 1인 경우는 그 자체가 제곱근이므로 nb 자체를 리턴해준다. 이런 예외 경우를 제외하고는 temp 변수에 현재 탐색 중인 res 값을 제곱한 값을 저장해 비교하고 만약 nb와 같다면 해당 res값을 리턴하면 된다. 하지만 temp값이 nb보다 커지거나 res값이 nb보다 커진 경우는 제곱근이 존재하지 않는다는 뜻이므로 0을 리턴해주면 된다. 여기서 굳이 temp라는 변수를 하나 더 만들어서 res의 제곱을 저장해 준 이유는 반복문에서는 반복문 내 계산과정을 최대한 줄이는 것이 코드의 효율을 높이는 방법인데, 만약 temp 변수가 없다면 비교를 위해 곱셈을 세 번 수행해야 하기 때문이다.
그리고 temp 변수의 type을 long long int로 설정해준 이유는 int type 변수인 res를 제곱한 값이 들어가기 때문에 overflow가 발생할 수 있기 때문이다.
int ft_sqrt(int nb)
{
int res;
long long int temp;
if (nb < 0)
return (0);
if (nb <= 1)
return (nb);
temp = 1;
res = 1;
while (res < nb)
{
temp = res * res;
if (temp > nb)
return (0);
if (temp == nb)
return (res);
res++;
}
return (0);
}
Exercise 06: ft_is_prime
Create a function that returns 1 if the number given as a parameter is a prime number, and 0 if it isn’t.
Allowed Function: None
이 문제는 인자로 주어진 nb가 prime number, 즉 소수인지 아닌지를 판별하는 함수를 만드는 것이 목표이다. nb가 prime number라면 1을, 아니라면 0을 리턴하는 함수를 만들면 된다.
코드를 보면, 우선 처음에 조건문으로 예외적이거나 간단한 경우들을 먼저 처리해 줬다. nb가 1보다 작거나 같으면 무조건적으로 소수가 아니므로 0을 리턴해주면 된다. (음수와 0은 약수가 아님, 1의 경우 학계에서 주장이 갈린다고는 하지만 1과 자기 자신 즉 보통 2개의 수에 의해 나누어 떨어지는 소수의 특성과 다르므로 소수가 아니라고 처리함. 실제로 1을 소수로 처리한 코드가 시스템에 의해 통과하지 못하는 것을 확인한 적이 있음.) 이후 nb가 2이거나 3인 경우 소수이고, 간단한 경우이기 때문에 1을 리턴해주고 넘어간다.
그 이후 while문을 통해 2부터 nb보다 작은 값들이 nb를 나머지 없이 나눌 수 있는지를 체크한다. 나머지 없이 나눌 수 있는 수를 만나는 순간 소수가 아니라고 판단하여 0을 리턴하면 되고, 끝까지 나머지 없이 나눌 수 있는 수를 찾지 못한다면 반복문이 리턴 없이 종료될 것이므로, 반복문 종료 후 1을 리턴해주면 된다.
int ft_is_prime(int nb)
{
int n;
if (nb <= 1)
return (0);
if (nb <= 3)
return (1);
n = 2;
while (n < nb)
{
if ((nb % n) == 0)
return (0);
n++;
}
return (1);
}
Exercise 07: ft_find_next_prime
Create a function that returns the next prime number greater or equal to the number given as argument.
Allowed Function: None
이 문제는 주어진 인자보다 크거나 같은 prime number를 구하는 문제이다. 앞서 작성한 ft_is_prime() 함수를 그냥 사용하면 되는 것이 통상적인 생각이지만, 계속 시스템에서 Time out을 줘서 효율성을 극대화해서 다시 만든 is_prime() 함수를 사용했다.
새로 만든 is_prime() 함수에 대해서 먼저 이야기를 해보자면, 다른 부분은 다 같지만 while문 내에 조건이 바뀐 것을 알 수 있다. 이전 문제에서 만든 ft_is_prime() 함수에서는 while (n < nb)로 사용했지만, 이 문제에서는 while ((n * n) < nb)로 조건문을 설정하여 반복 횟수를 획기적으로 줄였는데, 이것이 가능한 이유는 제곱 이상의 약수는 이미 그전에 나왔던 어떤 수들의 배수로 확인되었기 때문에 더 확인하지 않아도 된다. 예를 들어 60의 약수를 찾아보면 1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30, 60이 있다. 여기서 5까지는 앞서 나온 수들의 배수가 아니지만, 6부터는 앞서 나온 수들의 배수에 해당한다. 60의 제곱근은 약 7.7이므로, 약수 중 확인해야 하는 최댓값인 5가 이보다 작은 것을 알 수 있다. 다른 수들을 확인해 봐도 이와 같은 규칙이 적용된다. 따라서 while문에서 이를 활용하여 효율성을 극대화할 수 있는 것이다.
다음 우리가 만들어야 하는 주된 함수인 ft_find_next_prime() 함수를 보면 nb부터 int의 최대값(제시된 프로토타입에서 return type이 int로 설정되었기 때문에 해당 값까지만 확인하면 되는 것으로 판단했다.)까지 순회하면서 is_prime() 함수를 통해 prime number인 점이 확인되면 바로 그 값을 리턴해주는 방식으로 next prime을 찾는다.
int is_prime(int nb)
{
int n;
if (nb <= 1)
return (0);
if (nb <= 3)
return (1);
n = 2;
while ((n * n) < nb)
{
if ((nb % n) == 0)
return (0);
n++;
}
return (1);
}
int ft_find_next_prime(int nb)
{
int res;
if (nb <= 2)
return (2);
res = nb;
while (res <= 2147483647)
{
if (res == 2147483647)
return (res);
if (is_prime(res))
return (res);
res++;
}
return (0);
}
Exercise 08: ft_ten_queens_puzzle
Create a function that displays all possible placements of the ten queens on a chessboard which would contain ten columns and ten lines, without them being able to reach each other in a single move, and returns the number of possibilities.
Allowed Function: None
이 문제는 10x10 크기의 체스판에 10개의 queen을 올바르게 배치하는 함수를 만드는 문제이다. 여기서 올바르게 배치한다는 것은 queen이 한 번에 갈 수 있는 위치에 다른 queen이 있으면 안 된다는 규칙을 지켜 배치하는 것이다. 답을 출력하는 방식은 각 row 별로 queen이 배치된 column의 위치를 나열해서 한 케이스당 10개의 숫자를 한 줄에 출력하면 된다. 즉 예시 출력 첫 번째 경우인 0257948136은 아래 사진과 같이 배치되어 있는 것을 표현한 것이다.
처음에는 체스룰을 잘 몰라서 문제가 이해가 잘 안됐는데, 체스에서 queen의 위치나 이동 범위에 대해서 알고 나니 풀기에 수월했다. 퀸은 가로 세로 그리고 대각선 방향이라면 몇 칸인지에 관계없이 한 번에 갈 수 있다. 즉 아래 사진의 동그라미 위치에 퀸을 하나 배치하고 나면 X로 표시한 위치에는 다른 퀸을 놓지 못한다는 것이다.
복잡해 보여서 그런지 주변에서 많이 도전을 안하고 넘기던데, 사실 위에 나온 내용만 알고 나면 코드 짜는 것이 그렇게 까다로운 편은 아니다. 나는 재귀함수를 이용해서 문제를 해결했다. 대략적인 방법을 설명하자면, 하나의 문자열에 첫 번째 문자부터 0에서 9까지의 값을 차례로 체크하면서 조건에 맞는다면, 재귀를 통해 다음 문자 위치로 이동하여 다시 0에서 9까지의 값을 체크하는 과정을 마지막 문자까지 거치고, 결국 마지막 문자까지 채워지면 문자열을 출력하는 방식이다. 백트래킹(backtraking) 알고리즘을 사용했다고 생각하면 편하다. 백트래킹 알고리즘은 rush 과제 중에서도 활용하게 되는데, 브루트포스(brute force) 알고리즘이 모든 경우의 수를 다 체크하여 맞는 경우를 찾는 알고리즘이라면 백트레킹은 해당 경우가 아닌 것이 판명 나는 순간 더 나아가는 것을 포기하여 경우의 수를 줄이는 알고리즘이다. 즉, 여기서는 예를 들어 첫 번째 열에 첫 번째 행에 queen을 놓았다면 다음 열에서는 첫 번째 행이나 두 번째 행에는 queen을 배치하지 못한다. 그러므로 첫 번째 행이나 두 번째 행은 배제하고 세 번째 행에 놓는 경우부터 다시 체크를 시작하는 것이다. 이렇게 경우를 쳐가면서 나아가는 알고리즘이기 때문에 가지치기(pruning)이라고도 불리며, tree형태의 자료구조에 적합한 알고리즘이다.
코드를 자세히 보면 3개의 함수를 사용해서 구현했다. 첫 번째 함수인 check() 함수는 helper function으로 사용된 함수로, 현재 위치에 해당 숫자가 가능한지를 판별한다. 즉, 현재 확인하고 있는 위치가 앞서 배치해둔 퀸이 한 번에 이동할 수 있는 위치인지를 체크해 주는 함수인 것이다. 현재 위치에 퀸을 배치하는 것이 가능하다면 1을 리턴하고, 그렇지 않다면 0을 리턴한다. 확인하는 방식은 현재 확인하고 있는 열 전까지의 열에 퀸이 배치된 행이 현재 배치하고자 하는 행과 같은지, 혹은 대각선 위치에 있는지를 while문을 통해 이전 열들을 순회하며 확인하는 방식이다. 대각선 방향은 현재 확인하고 있는 행 위치인 cur와 이전 열의 행 위치인 pre의 차가 각각의 열 위치의 차와 같은지를 확인하여 체크한다.
두 번째 함수인 queens_puzzle()은 재귀함수이다. 우선 재귀함수의 중단 조건을 설정해줘야 하므로, 함수 처음에 if문을 통해 idx가 10이 되면 퀸을 배치하는 하나의 경우가 완성되었다는 뜻이므로 경우의 수를 세는 count에 1을 더하고 완성된 문자열을 출력해 준 후 재귀를 마무리한다. 10이 아닌 경우는 아직 문자열이 다 채워지지 않았다는 뜻이므로 while문을 통해 0부터 9까지 순회하며 현재 열에서 들어갈 수 있는 행 위치를 찾는다. 앞서 만든 check() 함수를 통해 현재 확인하고 있는 행 위치가 적절한지 확인하고, 적절하다면 재귀를 통해 다음 열 위치로 이동하여 문자열 채우기를 계속한다.
마지막으로 우리가 만들어야 하는 주함수인 ft_ten_queens_puzzle()에서는 우선 각각의 경우를 담을 크기 11의 문자열을 만들어준다. 10개의 문자만 담으면 되지만 크기를 11으로 한 이유는 마지막에 new line character를 추가하여 추후 출력 시 따로 출력하지 않아도 되게 하기 위함이다. 그리고 처음에는 크기를 12로 하여 마지막에 null character까지 추가했었는데, write 함수에서 출력 크기를 정해주기 때문에 문자열이라고 해도 굳이 null character가 필요하지 않고, null character를 포함해서 출력하게 되면 시스템에서 체크할 때 순서가 달라져서 답이 맞아도 fail을 받을 수 있으므로 주의해야 한다. (시스템에서 sort 함수를 확인하여 체크하는데, 첫 번째로 사용한 이후로는 null character가 문자열 처음으로 가서 sort를 사용했을 때의 순서가 뒤바뀐다.) count 변수를 정의하여 리턴할 경우의 수를 센다. 이후 만들어 둔 재귀함수를 idx 0을 초기값으로 시작해 준다.
#include <unistd.h>
int check(char *res, int idx, char cur)
{
char pre;
int j;
if (idx < 0)
return (1);
j = 0;
while (j < idx)
{
pre = res[j];
if (cur == pre)
return (0);
if ((cur - pre) == (idx - j))
return (0);
if ((cur - pre) == (j - idx))
return (0);
j++;
}
return (1);
}
void queens_puzzle(char *res, int idx, int *count)
{
char i;
if (idx == 10)
{
write(1, res, 11);
++(*count);
return ;
}
i = '0';
while (i <= '9')
{
if (check(res, idx, i) == 1)
{
res[idx] = i;
queens_puzzle(res, idx + 1, count);
}
i++;
}
}
int ft_ten_queens_puzzle(void)
{
int count;
char res[11];
res[10] = '\n';
count = 0;
queens_puzzle(res, 0, &count);
return (count);
}