해당 기능을 함수를 작성한다고 생각해 봅시다. 작성한 코드가 -2147483647 ~ 2147483647 까지는 정상동작을 합니다. 그런데 -2147483648 에서는 에러가 납니다. 오버플로우가 발생한 것으로 보입니다. 이 코드는 완전한 코드일까요? 네. 당연히 완전한 코드가 아닙니다.

제가 사용하고자 하는 완전한 코드의 의미는 정상적인 입력에서 오류가 나지 않고, 예상하는 바를 수행하는 코드를 의미합니다. 역시나 피신때의 코드를 활용해서 이야기를 이어나가 보겠습니다.

사실 완벽과 완전이란 표현이 올바라 보이진 않습니다.

3. 기억하나요? 나예요 union

union은 두 개의 문자열 s1과 s2를 입력받아 s1부터 s2까지 앞에서부터 차례로 출력하되, 하나의 문자가 여러번 출력하는 경우가 없도록 요구합니다. 어떻게 구현할 수 있을까요?

3.1 이전 출력 모두 보는 기본 코드

우선 차근히 문제의 지시사항을 따라가 봅시다.

이전에 출력된 문자는 출력하지 않습니다. 그대로 s1과 s2의 앞부터 글자 하나를 출력할지 말지 결정하기 위해 이전의 모든 문자들을 하나씩 순회 해야합니다.

이때 s1의 문자들을 출력할때에는 s1중에서 현재 출력하고자 하는 문자열의 위치 이전까지 탐색하고,

s2의 문자들을 출력할때에는 s1 문자열 전체와 s2중에서 현재 출력하고자 하는 문자열의 위치 이전까지 탐색해야 합니다.

코드를 구현한다면 아래와 같이 구현할 수 있을겁니다.

기본 코드

이제는 좀 더 간결한 코드, 혹은 효율적인 코드를 짤 수 없을지 고민해 봅시다.

먼저 기본 코드의 작동을 간단한 예시와 함께 살펴봅시다.

먼저 문자열 s1 = “aaaaa”와 s2 = “aaaaa”를 출력하고자 합니다.

모든 문자가 a로 동일해서, 각 문자는 s1의 첫번째 문자 a만을 보고서 출력하지 않아도 됨을 알수 있습니다.

다음으로 문자열 s1 =”1234567890"와 s2 = “abcdefghij" 를 출력하고자 합니다.

겹치는 문자가 존재하지 않아, s1과 s2 그대로 출력하면 됩니다.

이때 s2의 마지막 문자 j 를 출력해야할지 결정하는 과정에서 총 19개의 문자를 검색해야합니다.

꼭 이렇게 모든 문자를 검색해야 할까요? 이전에 출력된 문자는 출력하지 않는다….. 이전에 출력된 문자들을 기록해두면 되지 않을까요?

3.2 이전 출력을 기록해두기

이전 출력들을 기록하는 방식으로 먼저 set 을 떠올려 봅시다. c에서 set을 써본적이 없어… 파이썬 코드로 얼렁뚱땅 살펴봅시다.

python의 set은 이론적으로 O(1) 에 포함 여부를 알 수 있으므로, 간단한 방법으로 매우 효율적으로 union함수를 구현할 수 있습니다.

def	union(s1, s2):
	printed = set()
	for c in s1:
		if c not in printed:
			printed.add(c)
			print(c)
	for c in s2:
		if c not in printed:
			printed.add(c)
			print(c)
C
복사

그렇다면 c에서는 어떻게 할 수 있을까요? set이 아닌 유사한 방법으로, 피신때 exam에서 나오는 코드인 만큼 피신에서 배운 지식안에서 해결할 수 있는 방법은 아래와 같습니다.

void	printed_init(char *printed)
{
	int	i;

	i = -1;
	while (i++ < 255)
		printed[i] = 0;
}

void	ft_union_memorization(char *s1, char *s2)
{
	char	printed[256];

	printed_init(printed);
	while (*s1)
	{
		if (printed[*s1] == 0)
		{
			printed[*s1] = 1;
			while (1, s1, 1);
		}
		s1++;
	}
	while (*s2)
	{
		if (printed[*s2] == 0)
		{
			printed[*s2] = 1;
			while (1, s2, 1);
		}
		s2++;
	}
}
C
복사

이전에 각 문자가 출력 되었는지 여부를 저장하기 위해 정적 배열 printed를 256의 크기로 생성했습니다.

넉넉한 사이즈로 생성했지만, 그것이 문제에 유의미한 영향을 주진 않습니다.

오히려 여기서 강조할 것은 256의 크기를 가진 정적 배열 printed를 포함하는 본 코드가 완전한 코드라는 것입니다. 왜 완전할 수 있을까요?

char의 크기가 255인것은 맞지만, 범위가 -128 ~ 127이고, 음수에 해당하는 값이 인덱스로 들어오면 에러가 남이 자명하지만!!!!

문제에서 출력될 수 있는 문자란 조건이 붙어있었고, 그래서 문자열의 각 문자의 값은 32 ~ 127 로 확실합니다.할 수 있습니다. (물론 그외 문자도 들어오는 상황이라면 unsigned int 로 모두들 형변환 해야겠죠?)

그래서 위의 코드가 (적어도 제가 아는 수준에서는) 완전한 코드라는 의미를 부여하고 싶습니다.

4. 좀 더 살펴보자. Rush-02

Rush-02는 123456를 “십이만 삼천 이백 오십 육" 으로 표현하는 과제입니다.

(본 포스팅에서는 우리말 수사를 사용해 살펴보겠습니다.)

void my_login(char *number)
{
	// number를 어떻게 다루실 것인가요?
}

int main(int ac, char **av)
{
	if (ac == 2)
		my_logic(av[1]);
}
JavaScript
복사

number를 어떻게 다룰 것인가요? int? long? long long?

여러분이 선택한 그 type은 무량수

10^{68}

를 감당할 능력이 있나요?

없다면 여러분의 코드는 완전한 코드가 아닙니다.

실제 rush 당시 저의 팀의 구현도 계산 과정에서 숫자로의 변환이 필요한 과정이 존재하여, 특정한 경우에 오류를 내어 완전한 코드는 아니였습니다.

하지만 일찍이 엄청 큰 숫자도 다루는 부분에 대해서도 고려했기에, number를 지수부와 가수부로 나누어 (수사 포함) 다루는 방식을 활용했던 것입니다. 이로써 좀 더 많은 범위를 커버하고, 무량수를 당연히 표현할 수 있으며, 더 나아가 만약 지수부가 1인 수사만을 고려한다면 (불필요하게 숫자로 변환하는 코드만 다시 바꾼다면) 완전한 코드로서 동작할 수 있습니다.

5. 마무리

Rush 00 기억하시나요? 음수에 대해서 0에 대해서 핸들링 안 하셔서 0점 받진 않으셨나요?

물론 파고 파고 또 파면 뚤리지 않을 코드가 어디있을까 싶지만, 주어진 과제를 잘 분석하고, 정상적인 상황과 (고려하지 않아도 되는) 비정상적인 상황을 잘 구별하여, 정상적인 상황에서의 모든 경우에 대해서 올바른 핸들링을 통해 완전한 코드를 앞으로도 구현하려 노력해야만 합니다. 그게 좋은 개발자가 되는 길 중 하나라 의심치 않습니다.

6. 진짜 마무리 양궁대회 문제

어떤 동작을 수행할때 이전까지의 모든 동작을 고려하는 코드를 적용하는 예시로 삼고자 합니다.

6.1 문제 분석

먼저 문제를 분석해 봅시다.

입력

•

n : 남은 화살수

•

info : 상대방이 각 과녁에 맞힌 화살 갯수

출력(정답)

•

승리 불가능시 : [-1]

•

가장 큰 점수 차이 (여러 경우 시, 가장 낮은 점수를 더 많이 맞힌 경우) : [각 과녁에 맞힌 화살 갯수]

6.2 어떤 동작을 수행할때 이전까지의 모든 동작을 고려하는 코드 적용

10점부터 0점으로 차례로 과녁을 맞추는 과정에 적용할 수 있을 것 같습니다.

•

어떤 동작 : k 점 과녁에  a 개 맞추기

•

이전까지의 모든 동작 고려

◦

초기 n개에서 시작해 k점 과녁을 조준하는 현재 화살 갯수

◦

현재 k점 과녁에 상대방이 이미 맞힌 화살 갯수 b개

◦

현재까지 상대방이 획득한 점수 & 내가 획득한 점수

6.3 예시 살펴보기

6.3.1 k점 과녁에 상대방이 b(≥1)개 맞춘 상황

나의 행동에 따른 결과 분기

•

0개 맞추기 : 상대방 그대로 k점 보유, 나는 0점 획득, 화살 세이브

•

1 ~ b 개 맞추기 : 위 조건에서 화살만 추가 소비

•

b+1 개 맞추기 : 상대방의 k점을 빼앗고, 나는 k점 획득, 화살은 b+1소비

•

b+2 ~ 개 맞추기 : 위 조건에서 화살만 추가 소비

6.3.2 k점 과녁에 상대방이 0개 맞춘 상황

나의 행동에 따른 결과 분기

•

0개 맞추기 : 상대방 그대로 0점, 나도 0점 획득, 화살 세이브

•

1개 맞추기: 상대방 그대로 0점, 나는 k점 획득, 화살 1개 소비

•

1 ~ 개 맞추기: 위 조건에서 화살만 추가 소비

6.3.2 최적의 행동은?

•

0개 맞추기 || b+1개 맞추기

•

나머지 과녁의 상황 & 남은 화살의 상황에 따라 최적의 경우가 달라지기에, 딱 하나의 최적의 행동만 존재하지 않는다.

6.4 코드에 적용하기

6.4.1 매 과녁에서

•

현재 과녁의 점수는 k

•

상대방이 획득한 점수는 k || 0

•

상대방이 맞춘 화살 갯수는 b || 0

•

내가 취할 최선의 행동은

◦

0개 맞추기 ⇒ 점수 그대로 유지

◦

if (k > b) b + 1개 맞추기 ⇒ 나는 점수 획득 & 상대방 점수 유지 || 감소

6.4.2 종말 단계에서

•

점수의 차이 최댓값이 갱신되는 순간

◦

최댓값 갱신

◦

각 과녁당 화살 수 갱신

•

점수의 차이 최댓값과 동일한 경우

◦

낮은 과녁에 맞춘 쪽의 화살 수로 유지 or 갱신

•

점수의 차이 최댓값보다 낮을 경우

◦

패스

그렇게 단계를 하나씩 적용해 코드로 적용하면 너도 카카오 면접을 경험할 수 있다! (후… 하지만 난 42에 오게 되었지…..)