C++로 알고리즘 풀기 - 1주차 과외내용 정리

안녕하세요? 이화입니다. 최근 국민대 알고리즘 대회를 준비하고 있어요! 그래서 지인 분께 알고리즘 과외를 받으면서 C++ 공부를 하고 있습니다. 매일은 아니지만, 일주일에 두 번(과외 받은 거 정리 / 숙제 정리)이상은 이렇게 글로 정리해 보려고 해요! 과외 시간에 알고리즘 파트와 언어 파트로 나눠서 가르쳐 주시기 때문에, 아마 글 내용도 두 부분으로 나뉘겠네요. 오늘의 내용은 다음과 같습니다.

• 알고리즘 파트에서는 수학적 귀납법을 배웠습니다.
• 문법 파트에서는 C++의 입출력, 벡터, 스트링에 대해서 배웠습니다.

 

여담으로, 42 서울 라 피신은 다리 부상으로...(이렇게 이야기하니까 라 피신이 육상 경기 같아 보이지만, 전혀 아닙니다) 중간에 멈추게 되었습니다. 그래도 재미있는 경험이였어요. 

오늘은 수학 이야기를 좀 할 텐데, 수학 전공하는 사람이 보면 좀 나이브하게 보일지도 몰라요. 그런 부분에 대해서 조언해주시면 저는 매우 감사합니다. 자. 시작해 볼게요.

0. 토카이 테이오

토카이 테이오는 일본의 경주마입니다. 사츠키상, 일본 더비 등에서 1착을 거둔 유명한 말이지만, 부상이 잦았습니다. 특히 92년 아리마 기념에서 근육 부상으로 11착을 기록한 뒤로 재기가 어렵다는 이야기가 있었지만, 1년의 요양 끝에 93년 아리마 기념에서 저번에 소개한 비와 하야히데를 이기고 1착을 기록하고 은퇴한 일이 유명합니다.

물론, 오늘 내용과는 전혀 상관이 없습니다.

1.  수학적 귀납법

제일 먼저, 테스트 몇 가지를 거친 뒤 수학적 귀납법에 대해서 배웠습니다. 수학적 귀납법은 고등학교 교과서에 살짝 나와 있던 개념이고, 고등학교 때 수학 선생님이 시험에도 안 나오는 거 넘겨! 하는 분이 아니셨기 때문에 기초적인 개념이 어느정도 머릿속에 남아있던 거 같아서 생각보다 배우는 데 오래 걸리진 않았던 거 같아요.

사족은 이쯤 하고, 수학적 귀납법에 대해서 이야기해 봅시다. 수학적 귀납법은 "모든 자연수(또는 어떤 자연수보다 큰 자연수)가 어떤 성질을 만족시킨다" 라는 명제를 증명하기 위한 방법입니다. 그리고 이 증명 과정은 두 개의 명제를 통해 이루어집니다. "P(1)이 성립한다." 그리고 "어떤 자연수 N에 대해 P(N)^[각주:1]이 성립하면, P(N+1)도 성립한다." 가 그것입니다. 이 두 명제를 모두 증명할 수 있다면, "모든 자연수 N에 대해 P(N)이 성립한다."를 증명한 것과 같습니다. 

왜 그럴까요? 한번 간단히 이해해 봅시다.^[각주:2] 만약 P(1)이 성립하고 P(N)이 성립할 때 P(N+1)도 성립한다면, 둘을 합치면 P(2)가 성립함을 알 수 있습니다. 이제 P(2)가 성립한다는 걸 두 번째 명제에 넣으면, P(3), P(4)...간단히 감이 잡히시나요?

과외 중에 이걸로 가우스 공식(그래요! 가우스! 이 이름이 생각이 안 나서 찾아봤어요!)이라고 흔히 불리는 등차수열의 합 공식을 증명해 보고, Z, ㄴ타일 깔기 의 풀이에 대해서 이야기해 보았는데, 등차수열의 합 공식에 대해서는 분량상 생략하고, 나머지 둘의 풀이에 대해서는 숙제를 풀면서 자세히 설명해 보도록 하겠습니다.

 

2. C++의 입출력

C++에서는 C와 다르게, 입출력에 cin과 cout을 사용합니다. 사용법은 다음과 같습니다.

#include <iostream> 
// iostream을 include해서 cin, cout를 쓸 수 있게 합니다.

using namespace std; // std 네임스페이스를 사용하기로 합니다. 이게 없으면 std::cin처럼 써야 해요.

int	main(){
	int	i;
    
	cin >> i;
	cout << "Hello World! " << i << '/n';
	return (0);
}

 

간단하지 않나요? printf scanf처럼 이것저것 복잡하게 쓸 필요 없이, <<과  >>을 사용해서 변수와 입출력을 이어주는 것만으로도 출력과 입력을 모두 할 수 있습니다. 타입도 알아서 잘 해 줘요!

 

하지만, 이대로는 printf scanf보다 느리기 때문에, 다음 코드를 main에 추가해 주세요!

	ios::sync_with_stdio(false);
	cin.tie(0);
   //간단히 설명하자면, printf/scanf문과 링크를 끊는 역할을 하는 코드입니다.
   //이 코드와 printf/scanf문을 동시에 쓰지 마세요!

3.  C++의 벡터

우리는 C에서 배열을 통해서 list 형태의 자료를 저장했습니다. 하지만 C++에선, list 데이터를 저장하기 위한 더 좋은 수단이 있습니다. 바로 벡터입니다. 벡터는 다음과 같이 사용합니다.

#include <iostream>
#include <vector>
//vector을 include해서 vector을 사용할 수 있도록 합니다.
using namespace std;

int	main()
{
	vector<int>	a; //선언이 특이하죠? 아래에서 알아봅시다
	a.push_back(1);
	a.push_back(2);
	a.push_back(3); //push_back을 통해 vector의 맨 뒤에 요소를 추가할 수 있습니다. 
	a[2] == 3; //true입니다. 인덱스 연산자[]를 사용할 수 있어요.
    a.size == 3; //역시 true입니다. size를 측정할 수 있네요.
}

4.  C++의 스트링 

#include <iostream>
#include <string>
using namespace std;

int main()
{
	string S; // string을 통해 선언합니다.
	cin >> S; // 입력받을 수 있습니다.
    
    return (0);
}

5. 오늘의 알고리즘 헤더는 뭘까~용

reverse 반복자를 입력받아 거꾸로 뒤집습니다.

min / max 두 값을 입력받아 작은/큰 값을 반환합니다.

swap 다들 아는 그것!

 

요새 바빠서 글 오래 붙들고 있기가 힘드네용. 용두사미 같은 글이지만 공부 내용 정리일 뿐이니까 이해해주실거죠?

1. P(N)은 술어를 간단히 표기한 것입니다. 술어는 변수가 포함된 명제인데, 예를 들어서 P(A)은 "A는 자연수이다." 라는 표현이라고 하면, P(1)은 "1이 자연수이다." 라는 표현이 됩니다. [본문으로]
2. 제대로 "증명"하려면 대학 수학이 필요한 거 같아요. [본문으로]