아래의 내용은 조금 어렵기 때문에 지금 이해하기 어렵다면 건너 띄어도 좋다.

그리고 이 내용을 증명하기 위해서는 아직 모르는 개념을 몇개 간략히 소개해야하는데

그걸 소개하기 위해서는 시간이 좀 걸리기 때문에 소개를 생략하겠다.

다만 어떤 개념을 추가적으로 알아야되는지는 설명할테니 나중에 추후 포스팅을 참조하자.

우리가 이번에 알게될 용어는 비트(Bit), 바이트(byte), 무부호 타입(Unsigned), 자연수(Natural Number), 정수(Integer Number), 보수(Complement Number), 부동 소수점(Floating Point), 실수(Real Number) 이다.

여러분이 앞으로 C언어를 얼마나 쓰게될진 모르겠지만 C언어 같은 언어가 중요한게아니라

실제로 내부에 데이터가 저장되는 방식을 알아야 한다.

왜냐하면 저장 하는 방식은 모두 동일하기 때문이다. 

컴퓨터는 실제 사람들이 쓰는 숫자를 알아먹지 못한다.

마치 한국어를 외국인이 못알아 먹듯이 말이다.

그래서 기계가 읽을 수 있게 번역되서 저장된다고 생각하면된다.

착한 사람인 우리들이 기계가 뭐라고 기억하는지 이해할 필요가 있고 그 이야기를 할 것이다.

저번에도 말했지만 C언어의 데이터형은 크게 4종류로 나뉠 수 있다.

무부호 타입(0을 포함한 자연수, 0을 포함한 양의 정수), 정수, 실수(소수), 진리값

이 순서대로 설명을 듣도록 하자.

중요한건 컴퓨터는 오직 1,0밖에 모른다, 즉 우리가 보는 모든 자료는 사실 2진수이다.

우리가 정수 10을 지정한게 컴퓨터에 정수 10으로 저장되는게 아니며,

실수 3.14를 지정한게 컴퓨터에 실수 3.14로 저장되는것도 아니다.

사실 컴퓨터는 해당 메모리의 값이 얼마인지 모른다.

바보기 때문이다. 그래서 우리는 해당 변수(메모리)가

크기(바이트)는 얼마이며, 타입은 무엇이다라고 알려주어야 그제서야 의미를 가진다는 것이다.

반대로 이야기하자면 메모리의 크기와 타입을 만약 속일 수 있다면

컴퓨터는 전혀 다른 값으로 인식되게 할 수 있다.

이를 이해해야만 앞으로 변수에 대해서 다룰 수 있다.

비트와 바이트에 대한 개념은 아주 쉽지만 간략하게 설명하도록 하겠다.

이제 무부호타입(0을 포함한 자연수)에 대해 알아보도록 하자.

무부호 타입이라는 것은 말그대로 부호가 없다는 뜻이다.

정확히 말하자면 모든 부호가 양수라는 뜻이다.

C언어에서 unsigned가 붙은 모든 정수를 의미한다.

프로그래밍에서(C언어에서가 아니다) 자연수를 지원하는 언어와 지원하지 않는 언어가 있다.

아니 그럼 자연수를 지원하지 않는다면 정수만 지원한다는 것이냐? 라는 것인데...

그렇다. 사실 필자도 자연수가 있어야하는지는 잘 모르겠지만...

관점의 차이, 혹은 필요의 차이라고 할 수 있다.

사실 default가 정수의 변형이 자연수이지만 자연스러운 흐름을 위해서

자연수부터 설명하려고 한다.

위에서 메모리는 무조건 1과 0으로만 저장된다고 하였다.

그래서 우리는 1과 0으로만 생각해야한다.

그래서 어떤 프로그래밍 언어던 모든 숫자는 2진수로 저장된다.

컴퓨터가 숫자를 읽는 방식은 (메모리와 데이터타입과 읽는 방식)의 조합이다.

여기서 말하는 데이터 타입은 자료형을 의미하고 읽는 방식은 서식일 것이다.

그러면 어떻게 저장하느냐?

먼저 숫자를 2진수로 바꾸는 방법부터 알아야할 것이다.

가장 간단한 방법은 계산기를 쓰는것이지만... 근데 계산기만 써도 될거 같은데?

여튼 우리가 학창시절에 배우던(혹은 지금 학창시절이거나) 2진수 변환을 보도록하자.

177을 계속 거듭 2로 나누고 나머지를 기록해둔다음 이를 역순으로 쓰면 2진수가 된다.

다만 나머지만 기록하는게 아니라 마지막 결과값 부터 시작해야한다.

즉 빨간색 값을 포함해야하면 이를 시작으로해서 나머지를 역순으로 올라가면 결과 값이 나온다.

그래서 최종적으로 값이 1011,0001이 된다.

우리는 실제로 변수를 255 같은 형태로 적지만 컴퓨터는 1111,1111로 받아들인다.

그리고 다시 읽을 때 타입이 없다면 그냥 1111,1111일 뿐이다.

그래서 우리는 이를 자연수라고 명시적으로 알려주면 컴퓨터는 이를 인식해서

255라고생각하고 거기에 맞춰서 작업을 수행하게된다.

여기서 unsinged char형은 1바이트라고 했다.

1바이트는 8비트이기 때문에 2진수 8자리를 나타낼 수 있다.

부족한자리는 0을 넣게된다.(아무작업을 하지 않는게 아니다.)

이러한 것을 zero pedding이라고 한다.

문제는 넘쳐날 경우이다.

윗그림에서 290은 2진수로 나타냈을 표현하려면 9비트가 필요하다.

그런데 unsigned char형은 8비트밖에 표현할 수 없다.

1바이트는 8비트이다.

이렇게 데이터 형만큼이 넘쳐난다면 데이터를 잘라버린다.

이러한 것을... 뭐라하는지 모르겠다. 뭐라부르지?

여튼 넘쳐나는건 잘라버리기 때문에 290을

unsigned char에 저장하면 이론상 34가된다.

정말로 그럴까? 한번 테스트 해서 한번 알아보자.

#include <stdio.h>

int main() {
	char num = 290;
	printf("%hhd",num);
	return 0;
}

그만 알아보자.

우리는 수많은 0을 포함한 자연수,

즉 unsigned형이 어떻게 저장되는지 배웠다.

정수도 근본적으로는 unsinged와 같다.

하지만 생각해야할 점이 있다.

바로 음수를 어떻게 저장하는가이다.

컴퓨터는 0과 1밖에 못읽는데 음수를표기하려면

+, -를 표시해야한다는 근본적인 문제점이 생긴다.

이 문제점을 해결하기 위해서 등장한 것이 바로 보수표기법이다.

가령 10진법 체계에서 2의 10보수는 8이고 13의 10보수는 87이다.

반연 10진법 체계에서 2의 9보수는 7이고 13의 9보수는 86이다.

2진법 체계에도 당연히 2의 보수와 1의 보수가 있다.

컴퓨터는 2의 보수를 체택한다.

보수를 구하는 방법은 아주 아주 아주 쉽다.

제일 먼저 현재 적혀있는 숫자의 1과 0을 맞바꾼다.

가령 144의 보수는 110,0000인데 이는 원래 144의 0과 1을 바꾸면 나오는 수를 1의 보수라고한다.

그 다음에 거기서 1을 더하면 2의 보수가 된다.

보수가 왜 중요하냐면 컴퓨터는 각 자료형의 제일 상위의 1비트를 부호비트로 판단한다.

만약 이게 0이라면 양수로, 1이면 음수로 판단한다.

그래서 최상위가 1이다? 그러면 이 수가 "보수로 저장"되어있다고 판단하고

최상위 1비트를 제외하고 나머지 수를 재보수화 시킨다.

그 다음 -를 붙혀서 마무리한다.

조금더 세분화 해서 보도록 하자.

위의 숫자들을 우리가 입력하게되면 컴퓨터는 당연히 이를 2진수전환한다.

이 때 부호는 상관하지 않고 일단 2진수로 변환한다.

그 다음 이를2진수 전환한 다음 이를 char형 크기로 맞춰준다. 

부족하면 0 패딩을, 넘치면 잘라버린다.

char형 크기로 맞춘다음 음수만 2의 보수화를 진행한다.

당연하지만 음수만 보수화 과정을 진행하며 양수와 0은 진행하지 않는다.

결국 이 값이 최종값이 된다.

우리가 다시 읽어 낼때는 이를 역과정을 한다고 생각하면된다.

또한 알아야 할점이 -255와 -257은 서로 다른 값이 나왔다는 것이다.

255는 unsigned char형은 표현이 가능한 범위였다.

이유는 8비트로 표현할 수 있는 마지막 수였기 때문이다.

하지만 -255는 보면 알겠지만 8비트만으로 표현할 수 없다.

왜냐하면 마지막 비트로 음수를 사용하기 때문이다.

그래서 char의 범위는 -128 부터 127 까지이다.

이를 저장할 경우 완전 다른 수가 출력되게 된다.

항상 음수의 표현범위가 하나 더 많은데 그 이유는 0 때문이다.

0은 부호가 +로 표현된다. 그래서 양수가 표현가능한 숫자를 하나 까먹게된다.

이제 왜 컴퓨터가 정수와, 자연수를 처리하는 방식이 다른걸 알겠는가?

그러면 이제 실수는 어떻게 표현하는 거지? 라는 궁금증이 스멀스멀 올라와야한다.

실수를 표현하는 방법도 알아보도록 하자.

실수를 표현하는 방법은 크게 고정소수점과 부동소수점이 있다.

부동소수점을 영어로 floating point라고 하며

변수 이름이 float이였던 이유도 바로 이 때문이다.

솔직히 이름은 조금 센스가 부족하다.

고정이나 부동이나 똑같이 움직이지 않는 것이라 생각할 확률이 농후하기 때문이다.

그런데 여기서 말하는 부동의 부는 부유하다, 즉 떠있다는 뜻이다.

부유해서 움직이므로 소수점이 움직인다는 뜻이다.

누가 이러한 네이밍 센스를 했는진 모르겠지만 개발자이니 그러려니하자.

부동소수점을 표현하기 위해서 3개의 부분을 사용한다.

부동 소수점을 나타내는 방식은 살작 복잡하다.

먼저 소수를 2진법으로 바꾸는 방법을 간략히 알아보자.

일단 2의 각승의 값이 뭔지 알아야 한다.

뭐 모르는 사람은 없겠지만 잠시 보고 머리좀 식히자.

그러면 어떻게 수를 표현해야할지 감이 잡히...나?

0.8125를  소수로 변환하는 예제는 위와 같다.

정수를 바꿀 때는 2로 나누었지만 소수를 바꿀때는 2를 곱해야한다.

그래서 0.8125는 1101로 변환된다는걸 알 수 있다.

그러면  예를 들어 이제 -118.625가 어떻게 저장되는지 보도록 하자.

부호부, 지수부, 가수부에 할당된 크기는 위와 같다.

float의 4바이트는 32비트이고 그 값들이 위처럼 알뜰 살뜰하게 나눠져 있다.

double의 8바이트는 64비트이고 그 값들이 위처럼 나눠져 있는걸 확인할 수 있다.

-118.625

먼저 -118.625에서 음수를 제거 한다 그리고 부호부는 1이된다.

118.625

나머지 118.625를 2진법 변환하면 1110110.101이 된다.

1110110.101

여기서 소수점을 맨앞의 1만남을때까지 이동시킨다.

1.110110101 * 2^6 

여기서 앞에 구한 숫자의 소수는 가수부가 된다.(110110101)

가수부 - 110110101

여기서 지수부 6은 바로 지수부가 되지 않고 가중치와 연산을 한다.

왜냐하면 지수의 음수를 표현해야해서 그렇다. -100승을 어떻게 표현하나?

그래서 만약 지수부가 140이면 여기서 가중치인 127을 빼서 23승으로 인식한다.

가중치는 해당 자료형의 지수부 크기를 n이라고 하면 2^n/2이다.

float은 127이고 double은 1023이다.

지수부 - 10000101

그래서 6의 지수부는 6 + 127 = 133 이된다.

가수부는 나머지 부분은 0 패딩을 한다.

그래서 float에 저장할 경우 위처럼 저장되게 된다.

C언어에서 참과 거짓, 즉 진실과 거짓을 저장하는 값을 진리값이라고 한다.

true와 false로 나타내지며 당연히 true는 진실, false는 거짓이다.

C언어에서 숫자1은 진실로 판단된다. 즉 만약 진리값이 필요한 자리에

값 1에 해당하는 녀석을 넣으면 컴퓨터는 이 녀석을 진실이라고 판단한다.

그러면 가짜는 무엇인가?? 통념상으로 0이라고 생각하는데 이는 뭐 엄밀히 말하면은 아니다.

C언어에서는 1을 제외한 모든 녀석을 0이라고 판단한다.

저번에 printf라는 함수에 대해서 배웠다.

사실 저번 시간에서 배운 것의 전부라고 할 수 있다.

그 때 이야기했던 것을 복기해보면 printf의 역활은 "" 내부의 내용을 출력하는 것이라고 하였다.

그렇기 때문에 여러분은 조금만 이를 수정하면 여러분이 원하는 것을 출력할 수 있다.

이런것을 알렴련 여러분은 변수를 알아야한다.

이번 시간에 배울 것은 변수(Variable), 자료형(Data Type), 서식 지정자(Format Specifier), 제어 문자(Escape Sequence)에 대해서 배울 것이다.

그리고 변수(Variable), 자료형(Data Type), 서식(Format), 서식 지정자(Format Specifier), 제어 문자(Escape Sequence), 접두사(Prefix), 접미사(Suffix)라는 용어를 새로 듣게 될 것이다.

#include <stdio.h>

int main() {
    printf("나는 오늘 밥을 먹었다. 맛있었다.");
    return 0;
}

위처럼 코드를 작성한다면 우리는 밥을 먹었다는 출력값을 볼 수 있다.

하지만 사실 필자는 밥보다는 고기가 좋다.

그래서 고기로 출력해보고 싶다.

#include <stdio.h>

int main() {
    printf("나는 오늘 고기를 먹었다. 맛있었다.");
    return 0;
}

기특하게도 여러분은 고기로 수정할 수 있다.

사실 여러분도 고기가 더 좋을테니 틀린말이 아닐 것이다.

문제는 여기서 발생한다.

만약 고기가 아니라 존재하진 않겠지만 야채라면?

콜라라면? 약이라면? 플라스틱이라면?

이렇게 바뀐다면 여러분은 계속해서 printf의 내용을 수정해줘야한다.

이는 솔직히 말해서 귀찮다.

코드가 적으면 귀찮다라는 아주 심플한 말로 끝나지만

좀 많아진다면 귀찮다는 가벼운말로 정할수 없게 된다.

그래서 우리는 한번 정해서 쓸 수 있는 변수라는걸 프로그래밍에 도입하게된다.

변수는 우리가 흔히 수학에 아는 변수와 똑같다고 생각하면된다.

변수를 설명할때는 뭔가를 담는 그릇이나 박스라고 설명하는 경우가 많다.

그런데 오랫동안 이렇게 식상하게 설명하니까 카멜레온을 예시로 들겠다.

변수는 카멜레온같은 녀석이다.

카멜레온이 색을 변경할 수 있듯이 변수는 값을 바꿀 수 있다.

아래는 변수를 사용하고 이를 출력하는 예제이다.

#include <stdio.h>

int main() {
    int num = 27;
    printf("나의 나이는 %d다!", num);
    return 0;
}

여기서 모르는 개념이 추가되었는데 나눠서 보자.

int num = 27;

int라는 것은 integer의 줄임말이다.

integer의 뜻은 정수라는 뜻이다.

말그대로 정수 값만 집어넣을 수 있기 때문에 소수형태의 값은 저장할 수 없다.

위의 코드 한줄 짜리를 해석해보면

"정수 변수 num이 있는데 값은 27이다."라는 뜻이다.

만약 소수 형태로 저장을 시도한다면 소수점을 날려버리고 정수만 취하게 된다.

위의 예시는 선언과 동시에 초기화를 한 것이다.

변수는 위같은 방식이 아니라

아래처럼 사용도 가능하다.

int num; // - (1)
num = 27; // - (2)

여기서 1번의 int num은 값을 집어넣지 않았다.

이런경우를 변수의 선언이라고 한다.

2번의 경우는 선언을 한 후 초기화를 한 것이다.

여기서 중요한것은 만약 초기화를 하지 않았다면 어떻게 되느냐일 것이다.

백문이 불여일견이니 한번 코드를 수정해서 실행해보자.

#include <stdio.h>

int main() {
    int num;
    printf("나의 나이는 %d다!", num);
    return 0;
}

비주얼 스튜디오 2019에서는 빌드를 거부한다.

어떻게든 빌드를 시킬 수는 있지만 그 방법을 여기서 논하지는 않겠다.

필자가 해본 결과, 에러를 무시하고 빌드할 경우(공식적으로는 아직 에러가 아니다.)

저 자리에 0이 출력되는걸 확인할 수 있었다.

하지만 기본적으로는 0이 출력되는게 아니다.

위는 맥에서 실행한 화면이며 아래에는 결과값을 볼 수 있다.

비주얼 스튜디오도 옜날버전은 위처럼 동작하므로 위를 기준으로 설명하겠다.

일단 두가지의 문제가 있는데 num을 초기화 하지 않아도 프로그램이 정상작동을 하게된다는점.

두번째로는 num의 값을 특정지을 수 없다는 점이다.

그 이유를 설명하려면 복잡한데 어쨋든 결과만 간단히 말하자면

num은 초기화를 하지 않았지만 이상한 값을 가지고 있게 된다.

이러한 값은 아무런 의미가 없다. 이러한 값을 쓰레기(Garbage, 가비지)라고 부른다.

이는 아무 의미 없는 값이지만 사용자 입장에서는 이게 의미 있는 값인지 없는 값인지 모른다.

가령 여러분이 위의 예제에서 num이 194842661 이런수가 나왔다면

의미 없는 수라고 생각하겠지만 실제로 194842661라는 숫자를 쓸수도 있지 않은가.

그래서 여러분이 변수를 사용할 때는 항상 초기화 작업을 해주어야한다.

위에서 변수를 한번 지정하고 나면 타입은 바뀌지 않는다.

예를 들어서 카멜레온이 색은 변할 수 있어도 다른 종류의 카멜레온은 될 수 없는것 처럼 말이다.

그래서 다른 언어에서는 변수는 마치 메타몽 처럼 타입도 바꿀 수 있지만

C언어에서는 메타몽 보다는 카멜레온에 더 가깝다고 볼 수있다.

변수를 printf에서 사용하는 예시는 아래와 같다.

printf("나의 나이는 %d다!", num);

이 코드는 고작 몇개가 바뀌었지만 여러분의 프로그래밍 인생에서 엄청난 변화가 있을 것이다.

바로 변수를 사용하는 법을 알게 된것이다.

%d라는 것은 서식 지정자(Format Specifier)라는 것이다.

이러한 서식 지정자는 %와 알파뱃의 조합으로 이루어진다.

위의 d는 Decimal, 즉 십진수 출력을 의미한다.

%d라는 녀석이 붙어있다면 그 뒤에 변수가 선언되어있는지를 확인해서 없다면 쓰레기 값이 출력된다.

#include <stdio.h>

int main() {
    int num = 27;
    printf("나의 나이는 %d다!");
    return 0;
}

이 경우에도 %d자리에 쓰레기 값이 출력하게된다.

또한 변수를 여러개나 혹은 서식 지정자를 여러개 사용할 수 있다.

#include <stdio.h>

int main() {
    int num1 = 27;
    int num2 = 2018;
    printf("나의 나이는 %d다! %d!", num1, num1);
    printf("나의 나이는 %d년 현재 %d다!", num2, num1);
    return 0;
}

이 경우 %d라는 서식 지정자가 한 printf함수에서 두개씩 존재한다.

결과를 보면 각각에 매칭되는걸 알 수 있다.

위의 printf는 같은 변수를 두번 사용하였고 아래의 printf는 다른 변수를 각각 한번씩 사용하였다.

사용할 변수들은 사용된 서식 지정자의 숫자와 맞추어주어야한다.

위를 출력해보면 알겠지만 printf를 각각 나눠쓰더라도 두 문장은 붙혀서 출력이 될 것이다.

그 이유는 두 printf의 문장 사이에 공백을 입력해주는 문자를 넣지 않아서다.

우리의 목표가 공백을 출력하지 않는거라면 뭐 상관없지만 공백을 출력해야한다면 이는 문제가된다.

그런데 공백을 도대체 어떻게 표현해야할까?

이러한 특수한 문자들을 출력하기 위 무언가가 필요하다는걸 직감적으로 알 수 있다.

#include <stdio.h>

int main() {
    int num1 = 27;
    int num2 = 2018;
    printf("나의 나이는 %d다! %d!\n", num1, num1);
    printf("나의 나이는 %d년 현재 %d다!", num2, num1);
    return 0;
}

그래서 이를 출력하기 위해서 제어 문자라는 것을 쓴다. 영칭인 이스케이프 시퀀스라고도 많이 부른다.

이를 사용해서 우리는 "한칸 띄우고"라는 의미를 출력할 수 있다.

이제 붙혀서 출력하지 않고 따로 출력하게 될 것이다.

제어 문자도 여러종류가 있는데 여기서 설명하기는 좀 길기 때문에 추후에 언급하겠다.

일단 사용한 부분만 설명하자면 \도 %때와 마찬가지로 알파벳의 조합으로 이루어진다.

\n은 Line Feed(보통 줄여서 LF라 한다.)라는 의미를 담고 있는데

한국에서 말하는 Line Feed는 강제 개행이라는 의미를 담고있다.

강제 개행은 줄바꿈이라는 뜻이기 때문에 줄이 바뀌어 지게된다.

지금 까지 변수, 자료형, 서식 지정자에 대해서 알았다.

여기서 우리가 사용한 변수의 자료형은 10진수였고 서식 지정자는 %d를 사용하였다.

그러면 다른 종류도 있느냐고 반문할 수 있다.

당연히 있다!

우리는 정수만 다뤘는데 정수 말고도 다른 타입이 존재하면 심지어 정수도 여러가지의 타입이 존재한다.

이에 대해서 다... 알아보기에는 너무 서면이 길어지기에 추가 포스팅으로 언급하겠다.

이번에는 정수말고 실수를 쓰는 법을 보도록하자.

#include <stdio.h>

int main() {
    float f1 = .1f;
    float f2 = 4.14f;
    printf("너랑 나랑 사귈 확률? %f야!\n", f1);
    printf("원의 원주율? 그것도 모르냐? %f지!", f2);
    return 0;
}

처음으로 실수라는 개념을 배우게 되겠지만 보통 실수라고 하진 않고 소수라고 하는 경향이 있다.

C에서 사용하는 실수(소수)는 부동소수점이라는 방식을 채택하는데 여기서 설명하기엔 길어지므로 생략하겠다.

c에서의 실수형 float은 특이한 성질이 몇가지 있다.

첫번째로 접미사(Suffix)가 붙는다는 점이다.

우리가 int를 정의할때 접미사는 없었지만 float을 정의할 때는 접미사가 필요하다.

또한 만약 값에 정수부가 0이라면 0.은 생략할 수 있다.

써도 상관없고 안 써도 상관없다. 이건 정말 스타일 대로라서 어떤사람들은 칼같이 안쓰는 반면

어떤 사람들은 0.을 붙혀주는 경우도 많다.

당연하지만 정수부가 0이아니라면 무조건 정의해줘야한다.

이제 데이터 타입에 대하여 int와 float을 배웠다.

그럼 이 두놈만 있느냐? 이 또한 당연히 아니다.

아래는 다른 변수들이다.

몇가지 주의해야할 점이 있기에 짚고 넘어가겠다.

현재는 별로 안중요할 수 있는 내용이지만 크기에 대해서 잠시 논하려고한다.

1. 문자 타입이란건 사실 없다
- 아직 문자를 배우지는 않았지만 실제로 문자 타입이라는건 존재하지않는다. char에 문자 타입이라고 적은건 그냥 여러분들이 앞으로 하면서 배우기 쉽게하려고 한 말이다. 그러나 아직까지는 문자 타입이라고 생각하는게 편하다.

2. 크기는 고정되어 있지 않다
- 위의 크기(byte)를 적어두었지만 사실 크기가 정확히 정해진건 char뿐이고 나머지는 상대 크기로 언제든지 바뀔 수 있다. 다만 현재 C표준에서는 가급적 크기를 위와 같이 맞추려는 경향이 있을 뿐이다. 머신에 따라서 조금씩 차이는 있다.

3. 진리값은 그냥 쓸 수 없다
- 아직 진리값을 배우지 않았지만 진리 값은 그냥 쓸 수 없다. 상단에 #include<stdbool.h>를 추가해야 사용할 수 있다.

4. 서식 지정자는 사실 고정이 아니다
- 서식 지정자의 대응을 적어뒀지만 사실 고정이 아니며 저렇게 복잡하게 쓰는 사람이 오히려 드물 것이다. 하지만 이도 추후에 논하도록 하겠다.

5. 접미사는 대소문자를 가리지 않는다
- 말그대로 가리지 않기 때문에 4.3f나 4.3F나 동일하다

이번 시간에 아주 많은 것을 배웠는데 사실 축약해보면 많지 않다.

다음 시간에는 5장인 입력과 출력으로 넘어갈 것이다.

다만 4장에서 추가적인 부록으로 1, 2 편을 준비했으니 시간남으면 읽어보길 바란다.

이제 C언어에 대해서 별로 궁금하진 않았을것 같지만 여러 궁금증을 해결했으니

C언어 프로젝트를 만들고 첫 프로그램을 만들기로 해보자.

우리는 C언어를 하기에 앞서서 세가지 가정을 해줄 것이다.

1. 우리는 C언어를 학습한다.

2. 운영체제는 윈도우이다.

3. 개발환경은 Visual Studio를 사용한다.

일단 1번 가정은 왜 필요한지 궁금할 수 있다.

그 이유는 Visual Studio의 기본 세팅이 C++인데 학교에서 그냥 가르치는 경우가 많다.

일반적으로 C는 C++의 부분집합으로 간주되기 때문에

그렇게 교육을 해도 상관이 없으나 두가지의 문제가 있는데

첫번째로 C와 C++문법은 완전하게 일치하지 않는다는 점,

두번째로는 코딩하다보면 C++문법과 C문법을 헷갈려서 C++문법을 잘못 적는 경우가 생긴다는 것이다.

그래서 사과는 사과맛이 난다와 비슷한 느낌의 글을 적었지만 사실 의미는 있다.

나머지 2번과 3번은 처음 배우는 입장에서는 가급적이면 환경을 고정시켜주는게 좋다.

그 이유는 여러 상황을 가변적이게 대처할 능력이 되지 않아서 에러에 취약하기 때문이다.

필자가 사용한 버전은 Visual Studio 2019이다.

이전 버전과 활용방법은 약간 다르지만 거의 똑같으니 큰 문제가 없으리라 믿는다.

"저는 다른 운영체제인데 어떻게 하나요?"

근데 다른 운영체제 쓰는 사람이 이걸 보나?

맥이나 리눅스를 쓰는 사람들은 혼자서도 잘 하잖아.

그러니까 별 필요없을거 같은데... 아닌가?

리눅스를 하는 사람중에서 초보는 없을테니 맥에서는 어떻게 하는지 짤막하게 설명하도록 하겠다.

먼저 당연하지만 Visual Studio를 실행시켜준다.

그 다음 새 프로젝트 만들기를 눌러주면된다.

안에는 여러가지 목록이 있다.

콘솔 앱을 눌러주자.

빈 프로젝트를 해도 되지만 설정을 좀 더 해줘야한다.

그 다음 프로젝트의 이름을 정한다.

그러면 프로젝트가 완성되고 코드가 적혀있다.

여기서 좌측의 소스 파일을 눌러보자.

확장자가 cpp로 되어있는데 이 파일은 C++파일이라는 뜻이다.

정확하게 하기위해서 우리는 이 파일을 C파일로 바꿔주기 위해서 확장자를 c로 직접 고쳐주자.

또한 이 코드는 C++의 코드이므로 몽땅 지워준다.

#include<stdio.h>

int main() {
	printf("Hello, World!");
	return 0;
}

다 지우면 위와 같이 코드를 작성해준다.

아직 뜻은 몰라도 되니 시키는데로 적어보자.

바꾸고 나면 옆에처럼 C파일을 제대로 인식하지 못하는 경우가 있다.

보면 코드의 색깔이 맥아리 없이 이상한 색으로 되있는걸 확인할 수 있다.

이런 경우 껏다 켜주면된다.

코드를 다 작성해주면 실행을 해야하지 않는가?

위의 동그라미친 초록 버튼을 눌러주면된다.

이는 단축키로 ctrl+F5를 누르면 재빨리 시행할 수 있다.

그러면 시행이 되고 Hello, World가 출력되는걸 확인할 수 있다.

재빨리 달려 왔으니 이제코드에 대한 해석을 해보도록 하자.

코드를 길게 썼지만 모두 다 설명하는건 비효율 적이다.

여러분이 알아야 하는것은 저 빨간색 영역을 제외한 영역,

즉 printf만 알면된다.

그러니 나머지는 일단 항상 써놓는것!이라고 외우고 넘어가도록하자.

printf같은 것을 C언어에서는 함수라고 부른다.

우리가 아는 수학 함수와는 좀 다른데 왜 함수라고 부르는 지는 나중에 알려주겠다.

어쨋든 이 printf의 역활은 간략히 말하면 "화면에 뿌려줘라"라는 뜻이다.

그러면 우리는 화면에 ""로 감싼 부분을 화면에 뿌려주게된다.

그로 인해서 우리는 Hello, World!라는 글자가 화면에 뿌려지게된다.

나는 그래도 저게 각각이 뭐가 의미하는지 꼭 알고싶어!

그런 분들을 위해서 간략히 해석을 붙혀놨으니 참조하자.

지금 까지 배운 개념으로는 알수 없으니 맛보기로 느껴보기만 하도록 하자.

많은 예제가 Hello, World!로 시작을 하니 그 유래를 간략히 말하고 넘어가겠다.

Hello, World라는 글자는 별 뜻이 없는게 아니라 의미가 있다.

그 이유는 C언어를 만든 데니스 리치와 켄 톰슨이 만든 책인 TCPL의 첫 예제이기 때문이다.

그래서 프로그래밍에서 첫 예제는 보통 Hello, World를 출력하는 예제를 하게된다.

맥에서 C를 하는 법을 보도록하자.

맥에는 Visual Studio가 되긴 되는데 제약이 크다.

그래서 보통의 경우 Xcode로 하게된다.

Xcode를 설치한후 따라와주길 바란다.

Create a new Xcode project를 눌러준다.

macOS를 눌러준다.

Command Line Tool을 눌러준다.

프로젝트 이름을 적고 Language를 C로 바꿔준다.

저장할 위치를 정해준다.

그러면 프로젝트가 완성이 됬는데 좌측 상단으 재생 버튼을 눌러주면 실행할 수 있다.

실행해서 결과가 안보일 수 있는데 그 경우 우측 상단의 동그라미 친부분을 눌러준다.

그러면 보이는걸 확인할 수 있다.

C언어를 배운다면 C언어에 대해서도 알고 있는 것이 좋다.

그래서 C언어가 대체 뭔지에 대해서 알아보도록 하는 시간을 가져보자.

C언어는 하버드 대학교 물리학도인 데니스리치가 1972년 벨 연구소에서 만들었다.

이유는 UNIX를 만들기 위해서였다.

당 대에는 프로그래밍 언어는 어셈블리어로 만들었었는데

어셈블리어로 코딩하는것은 매우 난이도가 있는 일이였다.

어셈블리어는 기계어와 1대1 대응인데 이 말인 즉슨 "나도 컴퓨터와 똑같이 생각해야한다"였다.

과거 프로그래밍 언어들은 메모리를 직접관리하려고하지는 않았고

그게 필요하다면 어셈블리어를 사용했었다.

그런데 데니스 리치는 메모리를 효과적으로 관리하는 고수준의 언어를 원했다.

이러한 상황을 타파하기위해 만들어진 것이 바로 ALGOL계 언어이다.

위는 ALGOL계 언어 중 하나인 ALGOL68이다.

차차 개량버전인 CPL, BCPL, B로 진화하기에 이른다.

마지막에 B언어를 만든 켄 톰슨과 함께 C언어를 만들게 된다.

이 C언어는 곧 업계의 표준이 되어서 굉장히 많이 쓰게된다.

후기에 많은 언어들의 원형이 됬는데 이렇게 C언어의 영향을 받은 언어를 C-likes언어라고 부른다.

C언어는 언어계의 라틴어와 같은 위치에 존재하게된다.

그래서 프로그래밍 입문으로 C를 배우는 경우가 많다.

현재는 여러 분야에서 메인으로 쓰이지는 않지만 부분부분은 C언어로 작성하는 경우가 많다.

하지만 주요분야는 임베디드이다.

C언어의 장점은 성능 하나는 끝내준다는 것이다.

현실적으로 C언어보다 성능을 좋게 만드려면 어셈블리어 밖에 없다.

즉 성능의 끝판왕이다.

단점은 성능 좋은거 빼고 전부 다...

잘못 짜게 되면 오히려 성능이 하락할 수도 있다.

C는 코딩하기에는 꽤 난해한 면이 있다.

문법은 쉬워도 활용하기는 어렵다는 이야기이다.

현재는 이러한 C언어의 코딩의 난해함을 해결하기 위해서 여러가지 언어가 추가적으로 출범한 상태이다.

Rust나 Go등이 이렇게 C의 대처를 자처하며 등장하였다. 이러한 언어들이 C를 대체할지는 지켜봐야 알 것이다.

사실 이 C언어 강의를 보는 사람들 중에서 C언어를 좀 진지하게 하려는 사람은 없을 것이다.

그 이유는 C언어를 배우는 사람의 거의 대부분은 어쩔 수 없이 학교에서 하니까 배우기 때문이다.

따라서 C언어를 배우는 이유에 대해서 말하는게 큰 의미는 없을 것이다.

그러나 그래도 이왕 배우는거 C언어를 도대체 왜 배워야하는지에 아는 것이 좋을 것이다.

그래서 이번 포스팅에서는 C언어를 배우는 이유에 대해서 몇가지를 이야기 해보도록하자.

C언어를 처음 배우는 이유는 관습적인 측면이 크긴하지만 납득 못할만한 이유는 아니다.

C언어를 배움으로 컴퓨터의 기본 동작원리에 대해서 이해하게 된다. 

요즘에는 C언어를 배우는게 필수가 아니라고 생각하거나 

다른 방법, 혹은 설명으로 충분히 알려줄 수 있다고 생각하는 사람들도 있다. 

그래서 이러한 사람들은 C언어를 제일 처음 배우는게 아니라 

파이썬 혹은 Java등을 처음 가르치는 경우도 있다. 

그래서 C언어를 처음 배울 때 얻는 장점과 단점들을 알아보도록 하자. 

C언어에서는 배열이나 포인터등을 직접다루며 메모리가 어떻게 배치되는지 보게된다. 

그리고 이게 더 심도깊게 배울 경우 버퍼에는 어떻게 적재되고 어떻게 처리하는지 알게된다. 

메모리 동적할당 및 구조체, 공용체, 배열등의 메모리 활용에 대해서 배우게 된다. 

따라서 이러한 메모리 관리에 대해서 보는 눈이 생긴다. 

C언어는 성능에 충실한 언어이다. 

성능을 올리려면 C언어에서 썼던 활용테크닉을 떠올리게 되기에 성능에 대해서 생각하게 된다. 

문자열이 내부에서 어떻게 관리하는지 확인하게 된다. 

물론 C언어에서 배우는 문자 스타일은 다른 언어와 일치하지는 않지만 

적어도 문자들이 어떻게 문자열을 이루게 되고 관리되는지에 대해서는 알 수 있다. 

배열,구조체,공용체,포인터 등이 어떻게 메모리에 배치되며 

이게 어떻게 성능에 영향을 미치는지 알 수 있다. 

요즘 모든 언어들이 탑재중인 클래스라는 개념이 없고 메모리를 완전 수동관리한다. 

C언어로 객체지향 코딩을 하지 못하는건 아니지만 객체지향을 지원해주는 언어는 아니다. 

그래서 C로 코딩을 배울 때 절차적 코딩을 하게되는 경우가 많은데 이는 다른 언어를 배울 때 단점이된다. 

입문자는 코딩 패러다임에 적응하는데 엄청난 시간과 리소스가 투자되는걸 잊어서는 안된다. 

필자가 생각하는 가장 큰 문제점이다. 

C언어는 문법이 쉽지만 이 쉬운 문법으로 어려운 작업들을 해나가야해서 생산성이 떨어진다. 

필연적으로 활용법을 많이 알아야하며 사실 활용법을 포함한다면 C언어는 쉬운 언어가 아니라 

아주아주아주 어려운 언어이다. 그런데 입문용으로 배우는 사람에게는 간단한 일밖에 시킬 수 없다. 

게다가 활용을 하기위해서 매우 많은 부분에 대해서 이해를 시켜야하며 그럴 경우 다른 언어보다 학습량이 많다. 

현재 한국의 구인 시장에서의 분야중 이직이 잘되는 분야는 프론트엔드, 서버, 안드로이드, ios등이고 

거기에 머신러닝, 빅데이터, 임베디드 분야가 있다. 

그런데 임베디드를 제외하고 나머지 분야에서 C를 잘 사용하지 않는다. 

물론 입문 입장에서는 아직 취직이 먼 이야기이기 때문에 상관없지만 

비전공자들이나 4학년 등의 취준생들에게는 좋은 언어라고 보기 어렵다. 

모두 단순히 의견일 뿐이므로 여러분들도 깊게 생각할 필요가 없다.

어짜피 이거 보는 사람들은 학부생들이지 않는가?

억지로 하는거기 때문에 그냥 하면 되지만 장단점을 알아두는게 도움은 될 것이다.

https://www.acmicpc.net/problem/7569

이 문제는 BFS문제 중에서는 기초적인 문제이지만 조금 더러운 문제중 하나이기도하다.

그 이유는 이 문제에서는 여러가지 해결법이 다 통하는 문제는 아니기 때문이다.

이 문제의 의도는 "정석 BFS로 풀어라!"라는 문제이다.

그 이유는 풀면서 설명하겠다.

가로 M, 세로 N, 높이는 H이다.

그리고 하나의 토마토가 익게되면 주위의 토마토도 같이 익게된다.

이 때 익은 토마토는 1, 안 익은 토마토는 0, 토마토가 없는 칸은 -1이 된다.

이 문제는 DFS와 BFS모두 접근은 가능한데 실제로는 DFS로는 거의 못푸는 문제이다.

그 이유는 DFS로 풀게되면 엄청나게 반복을 하기 때문이다.

즉 시간을 미친듯이 잡아먹는다. 그래서 BFS로 푸는것이 좋다.

첫 예제로 보도록하자.

1)
0 -1 0 0 0
-1 -1 0 1 1
0 0 0 1 1

2)
0 -1 0 1 1
-1 -1 1 1 1
0 0 1 1 1

3)
0 -1 1 1 1
-1 -1 1 1 1
0 1 1 1 1

4)
0 -1 1 1 1
-1 -1 1 1 1
1 1 1 1 1

실패

첫 예제를 보면 0이 결국 하나 남기 때문에 모두 익히지 못한다.

그래서 -1이 출력된다.

두번 째예제를 보자.

1)
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
-
0 0 0 0 0
0 0 1 0 0
0 0 0 0 0

2)
0 0 0 0 0
0 0 1 0 0
0 0 0 0 0
-
0 0 1 0 0
0 1 1 1 0
0 0 1 0 0

3)
0 0 1 0 0
0 1 1 1 0
0 0 1 0 0
-
0 1 1 1 0
1 1 1 1 1
0 1 1 1 0

4)
0 1 1 1 0
1 1 1 1 1
0 1 1 1 0
-
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1

5)
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
-
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1

4번만에 성공

두번째는 총 4번만에 성공하게된다.

BFS로만 구현하면 되므로 난이도 자체는 높지는 않다.

문제는 BFS를 아느냐 모르느냐겠지만.

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>

using namespace std;

class Point {
public:
    int m;
    int n;
    int h;

    Point(int m, int n, int h) : m(m), n(n), h(h) {}

    Point() : m(0), n(0), h(0) {}
};

ostream &operator<<(ostream &o, Point p) {
    o << "m:" << p.m << ", n:" << p.n << ", h:" << p.h;
    return o;
}

int M, N, H;
vector<vector<vector<int>>> map;
queue<Point> q;
int tmp;
Point tp;
int result = 1;
int remain = 0;
bool sw;

void print() {
    for (int h = 1; h <= H; h++) {
        for (int n = 1; n <= N; n++) {
            for (int m = 1; m <= M; m++) {
                cout << map[m][n][h] << " ";
            }
            cout << endl;
        }
    }
}

int main() {
    //init
    {
        cin >> M >> N >> H;
        map.resize(M + 1, vector<vector<int>>(N + 1, vector<int>(H + 1, 0)));
        for (int h = 1; h <= H; h++) {
            for (int n = 1; n <= N; n++) {
                for (int m = 1; m <= M; m++) {
                    cin >> tmp;
                    map[m][n][h] = tmp;
                    if (tmp == 1) {
                        q.push(Point(m, n, h));
                    } else if (tmp == 0) {
                        remain++;
                    }
                }
            }
        }
    }

    //logic
    {
        while (!q.empty()) {
            tp = q.front();
            q.pop();
            sw = false;
            if (0 < tp.m - 1 && map[tp.m - 1][tp.n][tp.h] == 0) {
                q.push(Point(tp.m - 1, tp.n, tp.h));
                map[tp.m - 1][tp.n][tp.h] = map[tp.m][tp.n][tp.h] + 1;
                sw = true;
                remain--;
            }
            if (tp.m + 1 <= M && map[tp.m + 1][tp.n][tp.h] == 0) {
                q.push(Point(tp.m + 1, tp.n, tp.h));
                map[tp.m + 1][tp.n][tp.h] = map[tp.m][tp.n][tp.h] + 1;
                sw = true;
                remain--;
            }
            if (0 < tp.n - 1 && map[tp.m][tp.n - 1][tp.h] == 0) {
                q.push(Point(tp.m, tp.n - 1, tp.h));
                map[tp.m][tp.n - 1][tp.h] = map[tp.m][tp.n][tp.h] + 1;
                sw = true;
                remain--;
            }
            if (tp.n + 1 <= N && map[tp.m][tp.n + 1][tp.h] == 0) {
                q.push(Point(tp.m, tp.n + 1, tp.h));
                map[tp.m][tp.n + 1][tp.h] = map[tp.m][tp.n][tp.h] + 1;
                sw = true;
                remain--;
            }
            if (0 < tp.h - 1 && map[tp.m][tp.n][tp.h - 1] == 0) {
                q.push(Point(tp.m, tp.n, tp.h - 1));
                map[tp.m][tp.n][tp.h - 1] = map[tp.m][tp.n][tp.h] + 1;
                sw = true;
                remain--;
            }
            if (tp.h + 1 <= H && map[tp.m][tp.n][tp.h + 1] == 0) {
                q.push(Point(tp.m, tp.n, tp.h + 1));
                map[tp.m][tp.n][tp.h + 1] = map[tp.m][tp.n][tp.h] + 1;
                sw = true;
                remain--;
            }
            result = sw ? max(result, map[tp.m][tp.n][tp.h] + 1) : result;
        }
    }

    //output
    {
        if (remain == 0) {
            cout << result - 1 << endl;
        } else {
            cout << -1 << endl;
        }
    }
    return 0;
}

코드를 보면 간단하다.

여기서 디버깅용 로직들을 제외하면 다음과 같다.

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>

using namespace std;

class Point {
public:
    int m;
    int n;
    int h;

    Point(int m, int n, int h) : m(m), n(n), h(h) {}

    Point() : m(0), n(0), h(0) {}
};

int M, N, H;
vector<vector<vector<int>>> map;
queue<Point> q;
int tmp;
Point tp;
int result = 1;
int remain = 0;
bool sw;

int main() {
    //init
    {
        cin >> M >> N >> H;
        map.resize(M + 1, vector<vector<int>>(N + 1, vector<int>(H + 1, 0)));
        for (int h = 1; h <= H; h++) {
            for (int n = 1; n <= N; n++) {
                for (int m = 1; m <= M; m++) {
                    cin >> tmp;
                    map[m][n][h] = tmp;
                    if (tmp == 1) {
                        q.push(Point(m, n, h));
                    } else if (tmp == 0) {
                        remain++;
                    }
                }
            }
        }
    }

    //logic
    {
        while (!q.empty()) {
            tp = q.front();
            q.pop();
            sw = false;
            if (0 < tp.m - 1 && map[tp.m - 1][tp.n][tp.h] == 0) {
                q.push(Point(tp.m - 1, tp.n, tp.h));
                map[tp.m - 1][tp.n][tp.h] = map[tp.m][tp.n][tp.h] + 1;
                sw = true;
                remain--;
            }
            if (tp.m + 1 <= M && map[tp.m + 1][tp.n][tp.h] == 0) {
                q.push(Point(tp.m + 1, tp.n, tp.h));
                map[tp.m + 1][tp.n][tp.h] = map[tp.m][tp.n][tp.h] + 1;
                sw = true;
                remain--;
            }
            if (0 < tp.n - 1 && map[tp.m][tp.n - 1][tp.h] == 0) {
                q.push(Point(tp.m, tp.n - 1, tp.h));
                map[tp.m][tp.n - 1][tp.h] = map[tp.m][tp.n][tp.h] + 1;
                sw = true;
                remain--;
            }
            if (tp.n + 1 <= N && map[tp.m][tp.n + 1][tp.h] == 0) {
                q.push(Point(tp.m, tp.n + 1, tp.h));
                map[tp.m][tp.n + 1][tp.h] = map[tp.m][tp.n][tp.h] + 1;
                sw = true;
                remain--;
            }
            if (0 < tp.h - 1 && map[tp.m][tp.n][tp.h - 1] == 0) {
                q.push(Point(tp.m, tp.n, tp.h - 1));
                map[tp.m][tp.n][tp.h - 1] = map[tp.m][tp.n][tp.h] + 1;
                sw = true;
                remain--;
            }
            if (tp.h + 1 <= H && map[tp.m][tp.n][tp.h + 1] == 0) {
                q.push(Point(tp.m, tp.n, tp.h + 1));
                map[tp.m][tp.n][tp.h + 1] = map[tp.m][tp.n][tp.h] + 1;
                sw = true;
                remain--;
            }
            result = sw ? max(result, map[tp.m][tp.n][tp.h] + 1) : result;
        }
    }

    //output
    {
        if (remain == 0) {
            cout << result - 1 << endl;
        } else {
            cout << -1 << endl;
        }
    }
    return 0;
}

그럼 설명을 시작하겠다.

class Point {
public:
    int m;
    int n;
    int h;

    Point(int m, int n, int h) : m(m), n(n), h(h) {}

    Point() : m(0), n(0), h(0) {}
};

먼저 큐에 좌표의 정보를 담아야하니까 클래스를 만들어준다.

물론 클래스를 만들지 않아도 되지만 개인적으론 안만드는게 더 힘들 거 같다.

//init
    {
        cin >> M >> N >> H;
        map.resize(M + 1, vector<vector<int>>(N + 1, vector<int>(H + 1, 0)));
        for (int h = 1; h <= H; h++) {
            for (int n = 1; n <= N; n++) {
                for (int m = 1; m <= M; m++) {
                    cin >> tmp;
                    map[m][n][h] = tmp;
                    if (tmp == 1) {
                        q.push(Point(m, n, h));
                    } else if (tmp == 0) {
                        remain++;
                    }
                }
            }
        }
    }

초기화 로직도 중요한데

다른게 아니라 바로 remain이라는 변수의 존재이다.

우리는 성공했을 때와 실패했을 때를 구별해야한다.

즉 모든 BFS를 돌았을 때 0이 남지 않아야한다.

0이 남으면 실패한것인데 이걸 해결할 수 있는 방법은 2가지가 있다.

하나는 이렇게 미리 0의 갯수를 새고 익은녀석마다 0의 갯수를 지우는 것,

또다른 것은 BFS가 끝나고 마지막에 0의 갯수를 새는 것이다.

물론 시간복잡도는 똑같으니 뭘해도 상관없지만 깔끔하게 하고싶다면 위 방법을 추천한다.

bool chkAll() {
    bool result = true;
    for (int h = 1; h <= H; h++) {
        for (int n = 1; n <= N; n++) {
            for (int m = 1; m <= M; m++) {
                if (map[m][n][h] == 0) {
                    result = false;
                }
            }
        }
    }
    return result;
}

만약 마지막에 0의 갯수를 새고 싶다면 위처럼 사용해주면 된다.

//logic
    {
        while (!q.empty()) {
            tp = q.front();
            q.pop();
            sw = false;
            if (0 < tp.m - 1 && map[tp.m - 1][tp.n][tp.h] == 0) {
                q.push(Point(tp.m - 1, tp.n, tp.h));
                map[tp.m - 1][tp.n][tp.h] = map[tp.m][tp.n][tp.h] + 1;
                sw = true;
                remain--;
            }
            if (tp.m + 1 <= M && map[tp.m + 1][tp.n][tp.h] == 0) {
                q.push(Point(tp.m + 1, tp.n, tp.h));
                map[tp.m + 1][tp.n][tp.h] = map[tp.m][tp.n][tp.h] + 1;
                sw = true;
                remain--;
            }
            if (0 < tp.n - 1 && map[tp.m][tp.n - 1][tp.h] == 0) {
                q.push(Point(tp.m, tp.n - 1, tp.h));
                map[tp.m][tp.n - 1][tp.h] = map[tp.m][tp.n][tp.h] + 1;
                sw = true;
                remain--;
            }
            if (tp.n + 1 <= N && map[tp.m][tp.n + 1][tp.h] == 0) {
                q.push(Point(tp.m, tp.n + 1, tp.h));
                map[tp.m][tp.n + 1][tp.h] = map[tp.m][tp.n][tp.h] + 1;
                sw = true;
                remain--;
            }
            if (0 < tp.h - 1 && map[tp.m][tp.n][tp.h - 1] == 0) {
                q.push(Point(tp.m, tp.n, tp.h - 1));
                map[tp.m][tp.n][tp.h - 1] = map[tp.m][tp.n][tp.h] + 1;
                sw = true;
                remain--;
            }
            if (tp.h + 1 <= H && map[tp.m][tp.n][tp.h + 1] == 0) {
                q.push(Point(tp.m, tp.n, tp.h + 1));
                map[tp.m][tp.n][tp.h + 1] = map[tp.m][tp.n][tp.h] + 1;
                sw = true;
                remain--;
            }
            result = sw ? max(result, map[tp.m][tp.n][tp.h] + 1) : result;
        }
    }

로직은 길어 보이지만 간단하다.

그냥 BFS를 돌리는 로직이며 마지막에 result는 현재 level이 최고 level보다 크다면 갱신시켜주는 작업이다.

보통 BFS를 돌릴 때 level정보는 저장하는 방법이 두가지가 있다.

하나는 좌표(Graph나 map)에 직접 적는 방법과 클래스(위의 경우 Point)에 레벨 변수를 두고 넣는 방법이다.

이 문제가 더러운 이유는 레벨 변수를 둘 수가 없기 때문이다.

그래서 좌표에 직접 써야한다.

따라서 위의 경우 익으면 1이 아니라 익으면 1 이상이 들어가게 로직이 짜져있다.

if (0 < tp.h - 1 && map[tp.m][tp.n][tp.h - 1] == 0) {
    q.push(Point(tp.m, tp.n, tp.h - 1));
    //map[tp.m][tp.n][tp.h - 1] = 1;
    map[tp.m][tp.n][tp.h - 1] = map[tp.m][tp.n][tp.h] + 1;
    sw = true;
}

가령 하나를 예를 들어서 3번째 줄을 보면 위의 코드는 만약 현재 탐색하려는 좌표가 빈공간이면

지금 좌표의 값에 1을 더해주는 로직이다.

원래라면 주석처리한것 처럼 해도 되지만 이 경우 현재 레벨에 대한 정보는 소실된다.

즉 지금 일어난 루프가 몇번째 레벨인지를 알 도리가 없다.

이 경우 클래스에 저장해 두는데 이게 메모리 제한으로 막아놨다.

그래서 우리는 현재 레벨에 대한 정보를 좌표에 저장해둔다(위의 예제는 변수 map).

//output
    {
        if (remain == 0) {
            cout << result - 1 << endl;
        } else {
            cout << -1 << endl;
        }
    }

그래서 마지막에 결과에서 1을 뺀다.

왜냐하면 기존 토마토가 존재한다는걸 좌표에서 1로 표현,

그 다음은 1씩 증가하게 되는데 결과 값에서 기존의 값 1이 최대값이므로 1을 빼줘야하기 때문이다.

https://www.acmicpc.net/problem/9095

이 문제는 백준 DP중 가장 많이 푼 문제이며 한편으론 DP로 풀지 않아도 되는 이상한 문제이다.

일단 이 문제는 초보자가 풀기에는 딱 좋은 문제인데 어떻게 푸는지 보도록 하자.

특정 정수 N을 만들기 위해서 0에서 붙어 1혹은 2혹은 3을 더하는 문제이다.

즉 1혹은 2혹은 3을 더하여 N을 만들 수 있는 경우의 수를 모두 찾는 것이다.

이 문제는 모든 경우의 수를 계산하는 완전탐색(브루트포스)를 이용하여 풀 수 있다.

다만 원래라면 시간 제한에 걸리게되는데 여기서는 N의 상한선이 11밖에 되지 않는다.

4를 구하는 방법

1+1+1+1
1+1+2
1+2+1
2+1+1
2+2
1+3
3+1

총 7가지

모든 경우의 수를 나열하는 문제는 트리를 그려가면서 보면 위처럼 나온다.

위는 4를 구하는 방법인데 총 7가지가 나오는걸 알 수 있다.

시간 복잡도는 일반적으로 계산하면 O(3^N)이 나오게된다.

하지만 실제로 계산해보면 3^N보다는 월등히 적게 계산하는데 그 이유는 안하는 경우의 수가 매우 많기 때문이다.

다 계산해야 실제 시간복잡도를 알 수 있지만 여기서는 패스하겠다.

어쨋든 일반적인 완전탐색을 사용할경우 어마어마한 시간을 사용하는걸 알 수 있다.

완전탐색을 하는 방법은 재귀함수를 이용하는 방식(메모이제이션)과 for문을 이용한 방식(타뷸레이션)이 있다.

여기서는 메모이제이션을 이용한 방식으로 푸는 법을 알아보자.

void f(int n) {
    if (n == N) {
        cnt++;
    }

    if (n + 3 <= N) {
        f(n + 3);
    }
    if (n + 2 <= N) {
        f(n + 2);
    }
    if (n + 1 <= N) {
        f(n + 1);
    }
}

재귀함수를 짜본적이 없다면 지금부터라도 익숙해 져야한다.

재귀를 짜려면 종료되야하는 지점인 배이스 케이스를 먼저 작성해야한다.

이 모든 경우의 수를 구하는 재귀 함수 f는 0부터 시작해서 특정한 수 N을 완성해 나갈것이다.

그리고 그 N이 되면 더이상 함수를 실행하지 않고 종료를 할것이다.

그리고 마지막 경우에 도달했다면 cnt를 늘려준다.

#include <iostream>
#include <vector>

using namespace std;

int T;
int N;
vector<int> ARR;
vector<int> results;
int cnt;
int tmp;

void f(int n) {
    if (n == N) {
        cnt++;
    }

    if (n + 3 <= N) {
        f(n + 3);
    }
    if (n + 2 <= N) {
        f(n + 2);
    }
    if (n + 1 <= N) {
        f(n + 1);
    }
}

int main() {
    //init
    {
        cin >> T;
        ARR.push_back(0);
        results.push_back(0);
        for (int t = 1; t <= T; t++) {
            cin >> tmp;
            ARR.push_back(tmp);
        }
    }

    //logic
    {
        for(int t=1;t<=T;t++){
            cnt = 0;
            N = ARR[t];
            f(0);
            results.push_back(cnt);
        }
    }

    //output
    {
        for(int t=1;t<=T;t++){
            cout << results[t] << endl;
        }
    }
    return 0;
}

이 코드를 사용해서 문제를 풀면 두가지의 문제점이 있다.

먼저 시간복잡도가 O(3^N)으로 매우 높다는점, 그리고 큰 수를 사용할 수 없다는 점이다.

하지만 이 문제로 백준에 넣어도 통과는 되는데 그 이유는 11까지 밖에 연산하지 않기 때문이다.

11까지 연산량은 필자가 직접해본결과 1104번 밖에 돌지 않는데 이는 1초도 걸리지 않기 때문에 충분한 시간이다.

그래서 사실 이 문제는 DP를 도입하지않고 완전탐색만으로 풀 수 있는 쉬운 문제이다.

괜히 정답률이 60%대가 아니라는 이야기이다.

#include <iostream>
#include <vector>
#define ll long long

using namespace std;

int T;
int N;
ll cnt;
vector<ll> memo;

ll f(int n) {
    if (n == N) {
        return 1;
    } else {
        ll result = 0;
        if (n + 3 <= N) {
            if (memo[n + 3] == 0) {
                memo[n + 3] = f(n + 3);
            }
            result += memo[n + 3];
        }
        if (n + 2 <= N) {
            if (memo[n + 2] == 0) {
                memo[n + 2] = f(n + 2);
            }
            result += memo[n + 2];
        }
        if (n + 1 <= N) {
            if (memo[n + 1] == 0) {
                memo[n + 1] = f(n + 1);
            }
            result += memo[n + 1];
        }
        return result;
    }
}

int main() {
    //init
    {
        cin >> T;
    }

    //repeat
    for (int t = 1; t <= T; t++) {
        //init
        {
            cin >> N;
            cnt = 0;
            memo.clear();
            memo.resize(N + 1, 0);
        }

        //logic
        {
            cnt = f(0);
        }

        //output
        {
            cout << cnt << endl;
        }
    }
    return 0;
}

그럼 메모이제이션을 도입하고 숫자를 큰 숫자도 가능하게 하려면 위처럼 코드를 짜면된다.

실제 여러분의 코드는 30이상부터 엄청나게 오랜시간동안 연산을 하게 될것이다.

또한 40이상의 수는 오버플로우로 제대로 표현 못할것이다.

문제 조건상 11이하의 수가 들어가므로 위의 처리를 안해줘도 무방하지만,

여러분이 DP를 배우는 입장에서 메모이제이션은 익히는게 좋다.

if (n + 3 <= N) {
    result += f(n + 3);
}

메모이제이션이 뭔지 알려면위의 코드를 보자.

우리는 f(n+3)의 결과값을 구하고싶다.

하지만 이는 중복계산될 수 있다.

f(n+3)이 여러번 호출될 가능성이 있다.

문제는 f(n+3)은 또다시 f(n+3+1),f(n+3+2),f(n+3+3)을 호출할 가능성이 생긴다.

물론 아래의 녀석들도 자식들을 3개씩 더 호출할 수 있다.

이렇게 중복 호출을 막으려면 이 때의 값을 저장해 놓는 것이다.

이를 메모이제이션이라고한다.

if (n + 3 <= N) {
    if (memo[n + 3] == 0) {
        memo[n + 3] = f(n + 3);
    }
    result += memo[n + 3];
}

이렇게 memo[n+3]이 있는지 확인하고(0이 아닌지확인하고) 0이라면 함수를 계산해서 값을 넣는다.

만약에 0이 아니라면 이미 구했던 것이므로 메모의 값을 넣는다.

#include <iostream>
#include <vector>

using namespace std;

int T;
int N;
vector<int> ARR;
vector<int> memo;
vector<int> results;
int tmp;
int result;

int main() {
    //init
    {
        cin >> T;
        ARR.push_back(0);
        results.push_back(0);
    }

    //repeat
    for (int t = 1; t <= T; t++) {
        //init
        {
            cin >> tmp;
            ARR.push_back(tmp);
            N = ARR[t];
            memo.clear();
            memo.resize(N + 1, 0);
            memo[0] = 1;
        }

        //logic
        {
            for (int n = 1; n <= N; n++) {
                result = 0;
                if (n - 1 >= 0) {
                    result += memo[n - 1];
                }
                if (n - 2 >= 0) {
                    result += memo[n - 2];
                }
                if (n - 3 >= 0) {
                    result += memo[n - 3];
                }
                memo[n] = result;
            }
            results.push_back(memo[N]);
        }

        //output
        {
            cout << results[t] << endl;
        }
    }

    return 0;
}

만약 나는 재귀함수가 아닌 for문을  쓰고싶다면 for문을 써도 무방하다.

같은 로직을 for문으로 짠 것이다.

여기서도 memo에 넣는데 for문과 재귀의 차이점은

재귀는 필요한 것만 계산하고(모두를 계산하지는 않음)

for문은 필요하건 안하건 모두를 계산하게된다.

모두를 구하지 않는다면 재귀가 시간이 더 빠르게 된다.

다만 보통 알고리즘 테스트에서는 모두를 다 구하게 하므로 for문을 쓰는 방법 역시 유효하다.

이렇게 미리 모든 값을 다 구하는 것은 메모이제이션이라고 하지 않고 타뷸레이션이라고 한다.

메모이제이션이나 타뷸레이션이나 둘다 메모이제이션이라고 부르는 경향이 있어서 적당히 알아들으면된다.

https://www.acmicpc.net/problem/1463

이 문제는 백준에서 동적계획법(다이나믹 프로그래밍)문제 중에서는 가장 위에 있는 문제이며 가장 유명한 문제이다.

난이도는 동적계획법중에서 가장 쉬운 편이기에 초보자들에게 많이 추천받는 문제이기도 하다.

시간 제한은 2초로 널널한편, 동적계획법만 효율적이게 작동한다면 무조건적으로 해결되는 시간이다.

또한 메모리제한도 256메가는 아니지만 신경쓸 정도는 아니다. 정답률은 32퍼로 동적계획법이라는점, 사람들이 많이푼다는점.

두개를 종합해 봤을 때 정답률 역시 높은 편이라고 볼 수 있다.(단 일반적으로 32퍼는 낮은 확률에 속한다.)

1.X가 3으로 나누어 떨어지면, 3으로 나눈다.
2. X가 2로 나누어 떨어지면, 2로 나눈다.
3. 1을 뺀다.

이 문제는 위의 세가지 경우를 반복한다.

즉 어떤 수 X가 주어졌을 때 위의 위의 연산을 통해서 1을 만드는데 그중에서 최솟값을 출력하면된다.

7을 예시로 들어보자.

괄호안의 숫자는 아래를 뜻한다

1 - 3으로 나눔

2 - 2로 나눔

3 - 1로 뺌

7->(1)불가능
7->(2)불가능
7->(3)6->(1)2->(1)불가능
7->(3)6->(2)3->(1)1
7->(3)6->(3)5->(1)불가능
7->(3)6->(3)5->(2)불가능
7->(3)6->(3)5->(3)4->(1)불가능
7->(3)6->(3)5->(3)4->(2)2->(1)불가능
7->(3)6->(3)5->(3)4->(2)2->(2)1
7->(3)6->(3)5->(3)4->(2)2->(3)1
7->(3)6->(3)5->(3)4->(3)3->(1)1
7->(3)6->(3)5->(3)4->(3)3->(2)불가능
7->(3)6->(3)5->(3)4->(3)3->(3)2->(1)불가능
7->(3)6->(3)5->(3)4->(3)3->(3)2->(2)1
7->(3)6->(3)5->(3)4->(3)3->(3)2->(3)1

7이 가능한 경우의 수를 한번 보도록하자.

불가능한 경우를 도달한것을 센다면 7의 경우15가지, 불가능한 경우를 도달한 것을  뺀다면 6가지의 경우의 수 이다.

시간복잡도는 항상 최악으로 계산하는데 보면 알겠지만 3^7개까지의 경우의 수를 나열하므로

시간복잡도 계산시에는 O(3^n)로 계산하게 된다.

다만 실제로는 저 시간복잡도에 한참 못미치는데 그 이유는 실제 숫자가 2나 3으로 안나눠지는 경우가 아주 많기 때문에

기하 급수적으로 경우의 수가 줄어들긴 한다.

일단 중요한건 그냥 완전탐색(브루트포스로)문제를 풀줄 알아야한다.

그러면 위의 시간복잡도로 풀 수 있다.

그러면 우리는 공간복잡도를 이용해서 시간 복잡도를 줄 일 수 있다.
어떻게 시간을 줄이냐면 "중복된 계산"을 저장한 후 나중에 함수 호출해야할 경우 함수를 호출안하고 계산된 값을 주는 것이다.

즉 일종의 캐싱전략이고 이를 메모이제이션이라고 부른다.

아래 예시를 보자

괄호안의 숫자는 아래를 뜻한다

1 - 3으로 나눔

2 - 2로 나눔

3 - 1로 뺌

대괄호안의 숫자는 체크해야할 이전 값이다.

7을 예시로 생각하면 문제는 아래처럼 생각할 수 있다.

1이라면 최소값이 0이다.
-(1)은 불가능
-(2)은 불가능
-(3)은 불가능

2의 경우 최소값은 1이다.
-(1)은 불가능
-(2)의 결과값[1] : 0
-(3)의 결과값[1] : 0
-최소 값은 [1]의 0이므로 여기서 +1 해준다.

3의 경우 최소값은 1이다.
-(1)의 결과값[1] : 0
-(2)는 불가능
-(3)의 결과값[2] : 1
-최소 값은 [1]의 0이므로 여기서 +1 해준다.

4의 경우 최소값은 2이다.
-(1)은 불가능
-(2)의 결과값[2] : 1
-(3)의 결과값[3] : 1
-최소 값은 [2]나 [3]의 1이므로 여기서 +1 해준다.

5의 경우 최소값은 3이다.
-(1)은 불가능
-(2)는 불가능
-(3)의 결과값[4] : 2
-최소 값은 [4]의 2이므로 여기서 +1 해준다.

6의 경우 최소값은 2이다.
-(1)의 결과값[2] : 1
-(2)의 결과값[3] : 1
-(3)의  결과값[5] : 3
-최소 값은 [2]나 [3]의 1이므로 여기서 +1 해준다.

7의 경우 최소값은 3이다.
-(1)은 불가능
-(2)는 불가능
-(3)의 결과값[6] : 2
-최소값은 [6]의 2이므로 여기서 +1 해준다.

여러분은 분할정복기법으로 이 문제를 접근할 수 있어야한다.

7의 결과를 아는 것은 6의 최소값을 아는   것과 동일한 문제다.

6의 결과값을 아는 것은 5의 최소값을 아는 것과 동일한 문제이다.

이렇게 1까지 내려가면된다.

이를 코드로 구현하는 방법은 재귀와 for문이 있다.

마술 같게도 DP를 도입하면 시간복잡도는 O(n)이된다. 단 공간복잡도는 O(n)으로 늘어나게 된다.

#include <iostream>
#include <vector>

#define INF 0x7fffffff
using namespace std;

int N;
vector<int> memo;
int result;

int mi(int x, int y) {
    return x < y ? x : y;
}

int f(int n) {
    if (n == 1) {
        return 0;
    } else {
        int min_val = INF;
        if (n % 3 == 0) {
            if (memo[n / 3] == -1) {
                memo[n / 3] = f(n / 3);
            }
            min_val = mi(min_val, memo[n / 3]);
        }
        if (n % 2 == 0) {
            if (memo[n / 2] == -1) {
                memo[n / 2] = f( n / 2);
            }
            min_val = mi(min_val, memo[n / 2]);
        }
        if (n - 1 >= 1) {
            if (memo[n - 1] == -1) {
                memo[n - 1] = f(n - 1);
            }
            min_val = mi(min_val, memo[n - 1]);
        }
        return min_val + 1;
    }
}

int main() {
    //init
    {
        cin >> N;
        memo.resize(N + 1, -1);
    }

    //logic
    {
        result = f(N);
    }

    //output
    {
        cout << result << endl;
    }

    return 0;
}

재귀로 푸는 방법은 위와 같다.

#include <iostream>
#include <vector>

#define INF 0x7fffffff
using namespace std;

int N;
vector<int> memo;
int result;

int mi(int x, int y) {
    return x < y ? x : y;
}

int main() {
    //init
    {
        cin >> N;
        memo.resize(N + 1, -1);
        memo[1] = 0;
    }

    //logic
    {
        for (int n = 2; n <= N; n++) {
            result = INF;
            if (n % 3 == 0) {
                result = mi(result, memo[n / 3]);
            }
            if (n % 2 == 0) {
                result = mi(result, memo[n / 2]);
            }
            if (n - 1 >= 1) {
                result = mi(result, memo[n - 1]);
            }
            memo[n] = result + 1;
        }

    }

    //output
    {
        cout << memo[N] << endl;
    }

    return 0;
}

for문을 이용해서 푸는 방법은 위와 같다.