🐢 알고리즘 강의

유튜브 바킹독의 실전 알고리즘 강의를 듣고 내용을 정리합니다.

🍀 참조자(Reference)

C언어에서 swap 함수를 만들 때 원본 값을 바꾸는 방법은 swap2 함수처럼 포인터를 보내서 두 변수의 값을 바꾸는 것이다.

그런데 C++에서는 해결법이 한 개 더 있는데, 바로 참조자(reference)이다.

swap3 함수를 보면 함수 인자인 a와 b의 type이 int가 아니고, int 뒤에 &가 붙어있는 것을 볼 수 있다.

여기서 a와 b는 int reference이다. 저렇게 a와 b를 참조자로 만들면 함수 내의 코드에서는 그냥 int를 쓰듯이 tmp에 a를 대입하고, a에 b를 대입하는데, 이것이 다 원본의 값을 바꿔주는 것이다.

✔️ 왜 포인터 대신 참조자를 쓸까?

참조자는 C에서의 포인터랑 거의 비슷한 기능을 하지만, 포인터에서 Null pointer에 값을 넣는다거나 type이 다른걸 마음대로 캐스팅하는 등의 문제들을 덜 할 수 있게 하는 패러다임이다.

🍀 STL(Standard Template Library)과 함수 인자

C++에는 미리 다양한 알고리즘과 자료구조가 STL에 구현되어 있어서 우리는 필요한 자료구조를 직접 구현할 필요가 없이 그냥 STL에서 가져다 써서 사용할 수 있다. 대표적으로 vector가 있다.

✔️ vector에 대한 간단한 설명

C++에서는 배열을 선언할 때 크기를 명시해야 하고 무조건 해당 크기 안에서만 사용을 해야 한다. 그런데 vector는 일종의 가변배열로 크기를 마음대로 늘렸다 줄였다 할 수 있다. vector는 vector 헤더에 선언되어 있다. 인덱스 접근이 가능하다.

✔️ STL을 함수 인자로 넘기면 어떤 일이 생길까?

vector로 예시를 들어보자.

STL도 구조체랑 비슷하게 함수 인자로 실어 보내면 원본이 아닌 복사본을 만들어서 보내기 때문에 func1 함수에서 바꾼건 원본에 영향을 주지 않는다.

다음으로 이것을 보자.

두 vector를 인자로 넘겨받아 idx번째 원소의 값을 비교한 결과를 반환하는 함수이다.

두 vector의 크기가 N이라고 할 때 이 함수의 시간복잡도는 얼마일까?

시간복잡도는 충격적이게도 O(N)이다. 함수 안에 연산을 딱 1번만 하는데도 시간복잡도가 O(N)인 이유는 vector 인자를 받는 과정에서 복사가 일어나기 때문이다.
v1, v2의 크기가 N이니까 N개의 원소들을 하나하나 복사하는 과정은 O(N)이 들기 때문에, 이 함수는 의도하지 않게 시간복잡도가 O(N)이 된다.

그렇다면 의도한대로 시간복잡도를 줄여주려면 코드를 어떻게 짜야할까?

이럴 때 참조자를 이용하면 된다.

cmp2 함수에서는 v1, v2의 type을 vector의 reference로 만들었기 때문에, cmp2가 호출될 때 복사본을 따로 만들어내지 않고 참조 대상의 주소 정보만 넘어간다.
이렇게 되면 시간복잡도는 의도한대로 O(1)이 된다.

🍀 표준 입출력

코딩테스트에서 입력과 출력은 표준 입출력을 사용한다.

• C : scanf/printf로 입력과 출력을 처리
• C++ : cin/cout으로 입력과 출력을 처리

✔️ scanf, cin 모두 공백을 포함한 문자열을 입력받을 때 주의점

둘 다 공백 앞까지만 입력을 받기 때문에 출력이 원하는 대로 나오지 않을 수 있다.

ex)

string s;
cin >> s;
cout << "s is " << s;

입력 : hi hello
원하는 출력 : s is hi hello
실제 출력 : s is hi (hi 뒤의 공백으로 인해 hi까지만 입력을 받음)

해결책 3가지

1. scanf에서 줄바꿈(\n)이 나오기 전 까지 입력을 받는다는걸 명시하는 방식. 외우기 힘들기 때문에 비추천

2. gets 함수를 사용하기. 하지만 이 함수는 보안상의 이유로 C++14 이상에서는 제거됨. 비추천

3. getline을 이용하기. 이게 제일 깔끔! 추천! 대신 이건 type이 C++ string이어야 함.

기억하자! 공백이 포함된 문자열을 받아야 할 때 단순히 scanf나 cin을 쓰면 안된다!

✔️ ios::sync_with_stdio(0), cin.tie(0)

scanf/printf와 다르게 cin/cout은 입출력으로 인한 시간초과를 막기 위해서
ios::sync_with_stdio(0), cin.tie(0)이라는 두 명령을 실행시켜야 한다.

ios::sync_with_stdio(0)

기본적으로 scanf/printf 등에서 쓰는 C stream과 cin/cout 등에서 쓰는 C++ stream은 분리가 되어있다.

코드의 흐름(ex. 사용자의 입력 순서)과 실제 출력(ex.입력한 순서대로 출력)이 동일하기 위해서 기본적으로 프로그램에서는 C++ stream과 C stream을 동기화하고 있다.

그런데 C++ stream만 쓸거면 굳이 두 stream을 동기화하고 있을 필요가 없다. 동기화를 하면 시간 낭비일 뿐이다. 그렇기 때문에 C++ stream만 쓸거면 동기화를 끊어버려서 프로그램 수행 시간에서 이득을 챙길 수 있고, 동기화를 끊는 명령이 바로 sync_with_stdio(0)이다. sync_with_stdio(false)로 써도 된다.

❗ 주의할 점 : 대신 동기화를 끊었으면 절대 cout과 printf를 섞어쓰면 안된다. 섞어쓰면 출력 순서가 꼬이게 된다.

cf) Visual Studio 2017/2019에서는 sync_with_stdio를 그냥 무시하고 무조건 동기화를 유지하고 있어서 섞어써도 출력 순서가 원하는대로 된다. 하지만 채점 서버는 gcc이기 때문에 분명히 차이가 있다.

cin.tie(0)

화면에 아무 글자나 출력을 하는걸 생각해보면, 우리는 별 생각 없이 cout으로 출력을 찍으면 찍을 때마다 바로바로 출력된다고 생각하지만 사실은 그렇지 않고 출력 버퍼라는 곳에 문자가 임시로 저장되었다가 버퍼가 비워지면서 화면에 보인다.

출력에서 버퍼가 있는 것 처럼, 입력에서도 버퍼가 있어서 키보드로 받은 입력을 바로바로 넘겨주지 않고 버퍼에서 어느 정도 모았다가 준다.

그런데 입력과 출력이 번갈아나오고 그게 한 화면에서 다 보여질 경우, 버퍼의 존재로 인해서 순서가 꼬여버릴 수도 있다.

이 코드는 3번에 걸쳐 두 수를 입력받고 바로 합을 출력해주는 코드이다.

우리는 당연히 첫 번째 결과처럼 순서에 맞게 콘솔에 나타나기를 원한다.

그런데 예를 들어 6번 줄에서 "118\n"이란 출력을 하라고 했을 때, 바로 출력이 되지 않고 버퍼에 들어있다가 "2 5"를 입력한 후에야 출력이 되면 순서가 꼬일 것이다. 두 번째 결과처럼 말이다.

이런 현상을 막기 위해 C++에서는 기본적으로는 cin 명령을 수행하기 전에 cout 버퍼를 비워준다. 버퍼를 비우면 자연스럽게 "2 5" 입력이 들어오기 전에 118이 출력되어 순서가 꼬이지 않게 된다.

❗ 그런데 온라인 저지 사이트에서는 채점을 할 때 그냥 출력 글자만 확인을 한다(맨 오른쪽 결과 참고). 그렇기 때문에 입력, 출력의 순서가 꼬인다고 해도 채점에 아무런 영향을 주지 않고 두 경우 모두 다 정답 처리가 됩니다. 그러면 굳이 cin 명령을 수행하기 전에 cout 버퍼를 비울 필요가 없다는 것을 알 수 있다.

그래서 cin 명령을 수행하기 전에 cout 버퍼를 비우지 않도록 하는 코드가 cin.tie(0)인 것이다. cin.tie(nullptr)로 써도 된다.

✔️ endl

endl : 개행문자("\n")를 출력하고 출력 버퍼를 비우라는 명령

❗ 절대 쓰지말자. 줄바꿈이 필요하면 endl 말고 그냥 개행문자를 출력하자!

어차피 저지는 프로그램이 종료될 때 출력이 어떻게 생겼는지를 가지고 채점을 진행하니까 중간 중간 버퍼를 비우라고 명령을 줄 필요가 전혀 없다!

🍀 코드 작성 팁

✔️ 코딩테스트와 개발은 다르다.

코딩테스트의 목표는 남이 알아볼 수 있는 클린코드를 작성하는게 아니다. 어떻게든 제한된 시간 안에 정답을 받아야한다. 그렇기 때문에 코드를 거의 책에 예제로 실어도 될 정도로 깔끔하게 만들기 위해 노력하기 보다는, 좀 더럽더라도 내가 빠르게 짤 수 있는 방식으로 빠르게 구현하는게 훨씬 더 중요하다.

✔️ 공백과 줄바꿈 출력

코딩테스트에서 출력 맨 마지막에 공백 혹은 줄바꿈이 추가로 있어도 상관이 정답 처리가 된다. 그래서 이 부분을 별도로 예외처리를 할 필요가 없습니다.

✔️ 디버거는 굳이 사용하지 않아도 된다.

구현을 끝냈는데 예제에 대해 답이 올바르게 나오지 않을 때 코드의 어디가 잘못됐는지 알고 싶어서 디버거를 이용하는 경우가 간혹 있는데, 사실 코딩테스트의 코드는 끽해야 100줄 전후 길이일 것이다.

그럴 때 디버거를 켜면 뭔가 꼬이고 늪에 빠져드는 것과 같은 느낌을 받을 때가 있어서 차라리 중간 변수를 보고 싶으면 cout이나 printf로 출력을 찍어서 확인하고 디버거는 굳이 사용을 안하는 것을 권장한다.

참고 링크

바킹독 블로그