[바킹독의 실전 알고리즘] 0x02강 - 기초 코드 작성 요령 2

0x02강 - 기초 코드 작성 요령 2

- STL 함수 인자 -

기초적인 내용을 확인해보자.

위 코드들은 각각 함수 인자로  int, int 배열, 구조체를 보내 값을 바꿨을 때 원본의 값이 바뀌는 지를 확인하는 코드이다.

 

첫 번째 코드처럼 int를 함수 인자로 보내면 원본이 아니라 복사된 값이 보내진다.

때문에 함수에서 값을 바꾸더라도 main의 변수 t에는 아무런 영향을 주지 않는다.

 

두 번째로 int 배열인 arr를 보내는 것은 함수 인자로 arr의 주소를 넘기는 것이다.

따라서 func 함수에서 arr[0] 값을 바꾸면 원본에서도 자연스럽게 바뀌게 된다.

 

마지막으로 구조체 tmp는 int 변수와 마찬가지로 값이 다 복사되기 때문에 원본이 영향을 받지 않는다.

 

두 변수의 값을 바꿔주는 swap 함수를 작성하는 방법에 대해서도 알아보자.

swap1함수의 경우, 원본이 아니라 복사된 두 값을 바꿔주는 잘못된 코드이다.

제대로 동작하게 하려면 swap2 함수처럼 포인터를 보내서 두 변수의 값을 바꿔야 한다.

 

C++에서는 참조자(Reference)를 이용해 포인터 없이도 원본을 변형할 수 있다.

swap3 함수를 보면 변수 a, b의 타입이 int가 아니고 int&라고 쓰여있는 것을 볼 수 있다.

이렇게 a와 b를 참조자(int reference)로 만들면 함수 내에서 원본을 쉽게 바꿀 수 있다.

참조자는 C의 포인터와 비슷하게 동작하지만 포인터에서 Null pointer에 값을 넣는다거나 type이 다른 것을 마음대로 캐스팅한다거나 하는 문제들을 덜 할 수 있도록 해준다. (포인터와 참조자의 차이에 대해서 나중에 자세히 공부해봐야겠다.)

---

C++ 에는 미리 다양한 알고리즘과 자료구조가 STL(Standard Template Library)에 구현되어 있어서 우리는 필요한 자료구조를 직접 구현할 필요가 없다.  배열과 비슷한 기능을 수행하는 vector STL에 대해 알아보자.

 

원래 C++에서는 배열을 선언할 때 크기를 명시해야 하고 무조건 해당 크기 안에서만 사용을 해야 한다.

그런데 vector은 가변 배열로 마음대로 크기를 늘렸다 줄일 수 있다. 참고로 vector는 vector 헤더 안에 선언되어 있다.

 

01번째 줄처럼 vector를 선언하면 type이 int이고 값이 모두 0으로 초기화된 100칸짜리 가변 배열 v가 선언된다.

02, 03 번째 줄에서 볼 수 있듯이, 일반 배열처럼 인덱스에 접근해 값을 바꿀 수 있다. 

 

위 코드에서는 vector v를 func1의 함수 인자로 보내서 v[10]의 값을 바꾸려고 하고 있다.

하지만 STL을 함수 인자로 넘기게 되면 구조체와 마찬가지로 원본이 아닌 복사된 값이 전달되기 때문에 원본의 값은 변형되지 않고, v[10]을 출력했을 때 0이 나오게 된다.

 

첫 번째 코드에서 함수 cmp1은 vector v1과 vector v2를 인자로 받아 idx번째 인덱스에 해당하는 값을 비교하고 있다.

cmp1의 시간 복잡도는 O(1)처럼 보일 수 있지만 사실 O(n)의 시간 복잡도를 갖는다.

함수 인자로 vector v1과 v2를 보낼 때 각 vector마다 N개의 원소들을 복사해서 보내야 하기 때문이다.

이렇게 원본에서 복사본을 만드는 비용을 고려하지 않으면 시간 복잡도를 잘못 계산할 수 있다.

 

idx번째 원소의 값만 비교하고 싶을 뿐인데 vector 전체를 복사해서 보내는 것은 비효율적이다.

이럴 때 참조자를 이용하면 된다. 함수 cmp2를 보면 v1, v2의 타입을 vector<int>의 reference로 만들었다.

cmp2가 호출될 때 vector들의 복사본을 따로 만들지 않고 참조 대상의 주소 정보를 보내주게 된다.

그리고 시간 복잡도는 의도한 대로 O(1)이 된다.

 

- 표준 입출력 -

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

C에서는 scanf/printf로 입력과 출력을 처리하고, C++에서는 cin/cout을 사용하는데 기능에는 큰 차이가 없어서 어떤 것을 사용해도 상관이 없다.

 

scanf/printf에서 한 가지 아쉬운 점은 C++ string을 처리할 수 없다는 것이다.

C에서는 char*로 문자열을 다루는데, char*보다 C++ 이 월등하게 편리하다. 그래서 만약 scanf/printf를 쓰면서도 C++ string을 활용하고 싶다면 일단 char*으로 입력을 받고 형 변환을 해서 원하는 작업을 다 끝낸 후에 c_str() 메소드를 활용해 출력해야 한다.

 

scanf를 쓰든 cin을 쓰든 주의해야 할 것은, 공백을 포함한 문자열을 입력받기가 까다롭다는 것이다.

왼쪽 코드들을 보면 둘 다 공백 앞까지만 입력을 받고 있다.

 

이에 대해 3가지의 해결책이 존재한다.

일단 첫 번째는 scanf에서 줄 바꿈이 나오기 전까지 입력을 받는다는 것을 명시하는 방식이고 두 번째는 gets 함수를 사용하는 것이다. 첫 번째 방법은 사용이 불편해 보이고 두 번째 방법은 보안상의 이유로 c++14 이상에서는 제거되었다.

마지막 방법은 getline 함수를 이용하는 것인데 가장 깔끔한 방식이다. 대신 type이 C++ string일 때만 사용할 수 있다.

cin/cout을 사용할 때만 주의해야 하는 것도 있다.

scanf/printf와 다르게 cin/cout은 입출력으로 인한 시간 초과를 막기 위해서 ios::sync_with_stdio(0), cin.tie(0)라는 두 명령을 실행시켜야 한다. 이걸 해두지 않으면 입출력의 양이 많을 때 시간 초과가 날 수 있기 때문이다.

 

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

왼쪽 코드처럼 printf와 cout을 번갈아 사용하는 상황을 생각해보면 코드의 흐름과 실제 출력이 동일하기 위해서 기본적으로 프로그램에서는 두 stream을 동기화시키고 있다.

하지만 내가 C++ stream만 쓸 거라면 굳이 두 stream을 동기화하고 있을 필요가 없다.

ios::sync_with_stdio(false) 명령을 실행해 동기화를 끊어버리면 프로그램 수행 시간에서 이득을 챙길 수 있다.

(false 대신 0을 넣어도 정상적으로 작동한다.)

 

동기화를 끊었다면 절대 scanf와 cout을 섞어 쓰면 안 된다. 그렇게 되면 입출력 순서가 꼬이게 된다.

참고로 Visual Studio 2017/2019에서는 sync_with_stdio를 무시하고 무조건 동기화를 유지하고 있다.

 

cout이 문자열을 출력할 때 바로 화면에 출력되는 것이 아니라, 출력 버퍼라는 곳에 문자가 임시로 저장되었다가 버퍼가 비워지면서 화면에 보인다. 입력에서도 버퍼가 있어서 키보드에서 받은 입력을 바로바로 넘겨주지 않고 버퍼에서 어느 정도 모았다가 넘어간다.

그런데 입력과 출력이 번갈아 가면서 나올 때는 버퍼의 존재로 인해 순서가 꼬일 수 있다.

이런 현상을 막기 위해 보통 cin 입력이 들어오기 전에 cout 버퍼를 비워준다.

버퍼를 비워주면 입력이 들어오기 전에 출력 버퍼에 있던 글자들이 출력되기 때문에 입출력이 꼬이지 않는다.

 

하지만 온라인 저지 사이트에서는 출력 글자만 확인하기 때문에 콘솔 창에서 순서가 꼬인다고 해도 모두 정답 처리가 된다.

그렇다면 굳이 cin 명령을 수행하기 전에 cout 버퍼를 비울 필요가 없다. 그래서 cin.tie(nullptr) 명령을 실행해 cin 명령 전에 cout 버퍼를 비우지 않도록 만든다. (nullptr 대신 0을 넣어도 정상적으로 작동한다.)

 

cin/cout을 쓸 때에는 반드시 이 두 명령어를 넣어주는 것이 좋다!

 

+ endl은 절대 쓰지 않기!!

endl은 개행 문자('\n')를 출력하고 출력 버퍼를 비우라는 명령어이다.

하지만 코딩 테스트에서는 중간에 출력 버퍼를 비울 이유가 전혀 없기 때문에 줄 바꿈을 하고 싶을 때에는 endl를 사용하지 말고 개행 문자를 직접 출력하자.

 

- 코드 작성 팁 -

1. 코딩 테스트와 개발은 다르다. 효율적인 코드보다 빠르고 짧게 작성할 수 있는 코드를 짜기!

2. 가장 마지막 출력에서 공백 혹은 줄 바꿈이 추가로 있어도 상관없다.

3. 디버거는 굳이 사용하지 않아도 된다. 차라리 중간 변수를 보고 싶으면 cout을 활용하는 것을 권장한다.

 

 

🐶 바킹독의 실전 알고리즘 강의를 듣고 정리한 내용을 기록한 글입니다