[Hive Helsinki / Piscine] C01
Exercise 00: ft_ft
Create a function that takes a pointer to int as a parameter, and sets the value "42" to that int.
Allowed Function: None
해당 문제는 포인터의 아주 기본적인 이해를 묻는 문제이다. 코드도, 해답도 너무 간단해서 오히려 이게 정말 맞는 거냐는 질문을 3일 동안 다양한 사람들에게 받았던 것 같다. 포인터는 변수 선언 후에 * 표시 없이 사용하면 주소값을 reassign 하는 것이고, * 표시와 함께 사용하면, 해당 메모리 주소에 저장된 value 값을 바꾸겠다는 뜻이다. 따라서 아래와 같이 간단한 코드로 nbr 포인터에 저장된 value 값을 42로 변경할 수 있다.
void ft_ft(int *nbr)
{
*nbr = 42;
}
Exercise 01: ft_ultimate_ft
Create a function that takes a pointer to pointer to pointer to pointer to pointer to pointer to pointer to pointer to pointer to int as a parameter and sets the value "42" to that int.
Allowed Function: None
해당 문제 역시 포인터에 관한 간단한 이해를 묻는 문제이다. 포인터가 무식하게 많이 붙어있을 뿐 앞선 문제와 동일하다.
void ft_ultimate_ft(int *********nbr)
{
*********nbr = 42;
}
Exercise 02: ft_swap
Create a function that swaps the value of two integers whose addresses are entered as parameters.
Allowed Function: None
해당 문제는 포인터로 받은 인자 두 개의 value를 서로 바꿔주면 되는 문제이다. 앞서 말했듯 point가 가리키는 메모리 주소 내 value 값에 접근하려면 *표시와 함께 사용해주면 안 된다. 이 문제를 풀면서 *a = *b / *b = *a를 쓰면 안 되냐는 질문을 많이 받았는데, c언어가 아니라도 코딩을 해본 사람들은 당연하게 생각하는 질문이겠지만 첫 번째 *a = *b로 인해 *a는 이미 본연의 값을 잃었기 때문에 *b에는 다시 같은 *b 값이 최종적으로 assign 된다. 따라서 임시적으로 변수 하나를 선언하여 *a의 value를 미리 보관해 준 후 값을 swap 해줘야 한다.
void ft_swap(int *a, int *b)
{
int temp;
temp = *a;
*a = *b;
*b = temp;
}
Exercise 03: ft_div_mod
Create a function ft_div_mod divides parameters a by b and stores the result in the int pointed by div. It also stores the remainder of the division of a by b in the int pointed by mod
Allowed Function: None
해당 문제 역시 간단한 포인터 문제이다. 이제 포인터에 값을 어떻게 저장하는지를 알았으니 아주 약간의 응용을 더한 문제이다. 나누기 연산자가 '/'이고 나머지 연산자가 '%'라는 것만 알면 어려울 것이 없는 문제이다.
void ft_div_mod(int a, int b, int *div, int *mod)
{
*div = a / b;
*mod = a % b;
}
Exercise 04: ft_ultimate_div_mod
Create a function ft_ultimate_div_mod divides parameters a by b. The result of this division is stored in the int pointed by a. The remainder of the division is stored in the int pointed by b.
Allowed Function: None
해당 문제는 이전 문제와 동일하지만, 나누기와 나머지 연산의 결과를 저장할 변수가 따로 주어지지 않고 a와 b의 값을 변경해야 하는 문제이다. ex03과 ex02의 약간의 혼합이라고 보면 되겠다. 임시 변수를 하나만 지정해서 사용하면 변수 갯수도 줄이고, 코드도 더 짧게 쓸 수 있지만, 그리 긴 코드가 아니라서 굳이 가독성을 해치면서 변수 개수를 줄이고 싶지는 않았다.
void ft_ultimate_div_mod(int *a, int *b)
{
int div;
int mod;
div = *a / *b;
mod = *a % *b;
*a = div;
*b = mod;
}
Exercise 05: ft_putstr
Create a function that displays a string of characters on the standard output.
Allowed Function: write
해당 문제는 string의 특징 몇가지만 기억하면 쉽게 해결 가능한 문제이다. c언어에는 따로 string type이 없기 때문에 char 배열을 이용한다. 따라서 string이 주어지면 char 배열 첫 글자의 주소값이라고 생각해 주면 된다. 그리고 string의 끝을 표시해 주기 위해 끝에 null character('\0', ascii code 0)를 추가해 준다. 따라서 배열 첫 글자의 주소값을 받아, 배열이 끝에 nuill character에 다다를 때까지 출력해 주다 null character를 만난다면 출력을 멈추면 된다.
아래 코드에 대해서 부연설명을 덧붙이자면, null character의 아스키코드가 0이고, 대부분 언어에서 0은 false처럼 작동하므로, while문 안에 *str만 넣어주면 *str이 null character에 도달했을 때 자동으로 while (false)처럼 되어 while loop가 멈추가 된다. 그리고 ++는 증가연산자로, str을 출력한 후, 다음 character의 주소값으로 이동시킨다. ++str로 작성하면 증가시킨 후 출력하는 것이므로 ++의 위치를 함부로 바꿔서는 안 된다.
#include <unistd.h>
void ft_putstr(char *str)
{
while (*str)
write(1, str++, 1);
}
Exercise 06: ft_strlen
Create a function that counts and returns the number of characters in a string.
Allowed Function: None
해당 문제 역시 string에 대한 기본적 이해를 묻는 문제이다. 위 문제와 기본적으로 유사하다.
int ft_strlen(char *str)
{
int len;
len = 0;
while (str[len])
len++;
return (len);
}
하지만 이 문제에 대해서 유독 다른 peer들의 질문을 많이 받았었는데, 크게 두가지 질문이 있었다.
1. *str를 사용하고 str++;를 하는 것과 str[len]을 사용하고 len++를 하는 것의 차이
일단 이 질문에 대해서는 주어진 주소값을 직접 옮기냐, 변수를 설정해서 주소값에 더해가며 다음 주소값에 접근하냐의 차이라고 설명했다. 이렇게는 잘 이해가 되지 않아서 주로 그림이나 엑셀을 사용해서 설명하곤 했어서 그림 설명을 첨부한다. 아래는 포인터 변수에 "apple"이라는 string을 넣은 예시이다. 파란색 글씨의 첫 줄이 str 주소값을 직접 움직여 각 character에 접근하는 방식이고, 두 번째 줄이 index를 설정한, 즉 변수를 따로 설정해 특정 주소값에 접근하는 방식이다. 각각 용도에 따라 장단이 있다. 해당 문제에서는 length를 파악해야 하므로, 따로 length를 파악할 변수를 설정해 글자를 하나씩 세는 것이 더 효율적일 것이다. 하지만 이전 문제에서는 그냥 터미널에 한 글자씩 프린트하면 되는 것이므로, 주소값을 직접 옮겨 코드나 변수를 줄이는 것이 더 효율적일 것이다.
2. return 값이 대체 뭔지, 왜 있어야 하는지
아무래도 처음에 함수를 사용할 때, 리턴 값을 void로 설정하고 함수 내에서 출력하는 방식을 사용하다 보니, 많은 peer들이 리턴값에 대해서 이해를 잘 하지 못했다.
인자들이 함수의 input 값이라면 return 값은 output이라고 생각하면 된다. 예를 들어 add라는 함수를 만든다고 가정하면, 우리는 두 개의 숫자를 주고, 그 두 개의 덧셈 연산 결괏값인 하나의 숫자를 결과로 받을 것이다. 여기서 우리가 함수에 주는 두 개의 숫자가 인자, 즉 argument이고, 하나의 결괏값이 return 값이 될 것이다.
쉽게 코드로 예를 들면 아래와 같다.
아래 코드는 add라는 함수를 정의해서 a, b 두개의 정수를 인자로 준다. 그리고 그 두 숫자를 더한 결괏값을 출력한다. 이렇게 하게 되면 main 함수 내에 result 변수에는 8 값이 입력되게 된다. add 함수 앞에 'int'라고 표기되어 있기 때문에 리턴값은 int type이어야 한다.
int add(int a, int b)
{
return (a + b);
}
int main(void)
{
int result;
result = add(3, 5);
return (0);
}
또 여기서 왜 main 함수의 return type이 int인지 궁금할 수 있는데, 보통 main 함수가 정상 작동하면 0을 리턴하고 아니면 1을 리턴해서 오류가 발생했음을 알린다. 추후 오류처리를 하다 보면 사용할 일이 많이 생긴다.
Exercise 07: ft_rev_int_tab
Create a function which reverses a given array of integer (first goes last, etc)
Allowed Function: None
해당 문제는 int type의 배열과 그 크기를 인자로 받아, 배열을 역순으로 재배열하는 함수를 만드는 문제이다. string의 경우 끝에 null character가 있어 따로 size를 알지 못하더라도 끝을 알 수 있지만, 다른 형태의 배열은 불가능하기 때문에 저렇게 size를 따로 명시받아야 한다.
아래 코드는 start 변수를 배열의 첫번째 인덱스인 0으로, end 변수를 배열의 마지막 인덱스인 size-1로 각각 설정하고, start와 end가 가리키는 배열 element를 swap해준 후 start는 하나 증가시키고, end는 하나 감소시키는 과정을 반복하며 진행된다. 이 과정은 start가 end보다 작을 때까지만 반복하므로, 배열의 원소가 0개이거나 하나만 남았을 때 반복을 멈춘다.
void ft_rev_int_tab(int *tab, int size)
{
int start;
int end;
int temp;
start = 0;
end = size - 1;
while (start < end)
{
temp = tab[start];
tab[start] = tab[end];
tab[end] = temp;
start++;
end--;
}
}
Exercise 08: ft_sort_int_tab
Create a function which sorts an array of integers by ascending order.
Allowed Function: None
해당 문제는 int type의 배열과 그 크기를 인자로 받아, 배열을 오름차순으로 재배열하는 함수를 만드는 문제이다. 나는 해당 문제에서 quick sort를 이용했는데, 다른 peer들을 평가하다 보니 대체로 bubble sort를 사용했다. quick sort가 시간복잡도 측면에서는 유리한 것이 사실이지만, 딱히 system이 timeout을 줄 만큼 큰 경우를 체크하지는 않는 것으로 보인다. 그리고 bubble sort를 사용하면 코드가 획기적으로 짧아진다. 따라서 나도 이 문제 이후 sort를 요하는 문제에서는 대체로 bubble sort나 더 짧은 코드를 가진 다른 방법들을 사용했다.
quick sort의 대략적인 방법은 pivot을 하나 설정하고 privot 왼쪽 부분은 pivot보다 작은 값으로, 오른쪽 부분은 pivot보다 큰 값으로 채워준 후 다시 pivot의 왼쪽과 오른쪽 부분 각각에 해당 과정을 반복하는 것이다.
위 알고리즘을 recursive로 구현했는데, 첫번째부터 세 번째 그림까지의 과정을 하나의 함수로 만들어서 4번째 과정을 왼쪽 부분과 오른쪽 부분으로 나눠 다시 함수를 사용하여 정렬해 나가는 방식이다.
편의를 위해 swap 함수를 따로 구현해줬고, check condition 함수는 42 시스템의 함수 하나당 25줄 제한 때문에 그저 따로 빼둔 것이다. high 가 low보다 작거나 같으면 배열 내 원소가 없거나 하나만 있다는 뜻이므로 이후 일련의 과정을 진행할 필요가 없다. 따라서, 함수를 terminate 해준다. high-low가 1이면 배열 내 element가 2개뿐이라는 뜻이므로, 둘의 크기만 비교하여 swap 해야 하는 경우만 swap해준 후 함수를 terminate 해준다.
check condition에서 확인한 경우가 아니라면, while문을 통해 첫번째 두 번째 그림의 과정을 반복해 주고, 이후 while문을 빠져나와 pivot을 high 위치 element와 swap 해준다. 그리고 recursive function으로 왼쪽파트와 오른쪽 파트에 각각 quick sort를 다시 반복해 준다.
void swap(int *num1, int *num2)
{
int temp;
temp = *num1;
*num1 = *num2;
*num2 = temp;
}
int check_condition(int high, int low, int *nums)
{
if (high <= low)
return (1);
else if ((high - low) == 1)
{
if (nums[low] > nums[high])
swap(&nums[low], &nums[high]);
return (1);
}
return (0);
}
void quick_sort(int *nums, int low, int high)
{
int pivot;
int inith;
if (check_condition(high, low, nums) == 1)
return ;
pivot = low++;
inith = high;
while (low < high)
{
while ((nums[low] <= nums[pivot]) && (low <= high))
low++;
while ((nums[high] >= nums[pivot]) && (low <= high))
high--;
if (low >= high)
break ;
swap(&nums[low], &nums[high]);
low++;
high--;
}
swap(&nums[high], &nums[pivot]);
quick_sort(nums, pivot, high - 1);
quick_sort(nums, high + 1, inith);
}
void ft_sort_int_tab(int *tab, int size)
{
quick_sort(tab, 0, size - 1);
}