[실전 알고리즘] 0x02강 - 기초 코드 작성 요령 II

 

안녕하세요, 바킹독입니다. 이전 단원에서 오지고 지리게 고통받으셨을텐데 이번에는 훨씬 쉬우니까 걱정을 덜어내시고 마음 편하게 보시면 됩니다. 저 아직 0x18살이니까 급식체 써도 되는거 인정하는 부분이죠 ㅇㅈ? ㅇㅇㅈ

 

대신 이제 기초 코드 작성 요령을 끝낸 기념으로 백준 그룹에 문제 폭탄을 뒀으니 온라인 저지 사이트가 익숙해질 때 까지 쭉 풀어보세요.

 

이전 단원에서는 이론적인 내용을 주로 다뤘는데 이번에는 실제로 코드를 짤 때 주의해야 하는 점들을 많이 뒀습니다.

 

첫 번째로 C언어 공부를 제대로 하셨는지 점검을 한 번 해보겠습니다. 3개의 코드를 보고 출력을 예측해보세요. 일단 3개의 코드가 어떤 부분에 대한걸 물어보는건지는 알겠죠? 함수의 인자로 int / int 배열 / 구조체를 실어보내서 값을 바꿨을 때 원본의 값이 바뀌는지를 물어보는 것입니다.

 

답은 바로 0, 10, 0입니다. 세 번째 코드는 헷갈렸을 수도 있을 것 같은데 첫 번째나 두 번째에서 틀리셨다면 좀 맴찢이네요ㅜㅜ

 

첫 번째는 진짜 당연한 얘긴데, int를 함수 인자로 보내면 값이 복사돼서 넘어갑니다. 그러니까 함수에서 값을 바꾸더라도 main의 변수 t에는 아무런 영향을 주지 않습니다.

 

두 번째는 arr[0]이 바뀌게 되는데, func에 int 배열 arr를 인자로 주는게 arr의 주소를 넘겨주는 것이니 arr[0]을 func 함수에서 바꾸면 원본의 값도 자연스럽게 바뀌게 됩니다.

 

마지막으로 구조체의 경우에는 int랑 비슷하게 그냥 값이 다 복사되기 때문에 func 함수에서 값을 바꿔도 원본에는 영향을 주지 않습니다.

 

당연히 사람은 망각의 동물이니까 헷갈릴 수는 있지만 지금 제가 써놓은 저 설명 자체가 이해가 안간다고 하면 C언어의 함수 인자와 포인터 부분을 따로 복습을 좀 하실 필요가 있습니다.

 

C언어를 배울 때 관련된 얘기를 하면서 두 변수를 swap하는 함수를 만드는 방법도 아마 배웠을 것입니다. 기억을 꺼내보면 일단 swap1 함수는 제대로 동작하지 않는걸 알 수 있을 것입니다. 원본 2개를 바꾸고 싶은데 복사된 2개를 바꾼다한들 의미가 없습니다.

 

그래서 swap2 함수처럼 포인터를 보내서 두 변수의 값을 바꿀 수가 있습니다. 그런데 C++에서는 해결법이 한 개 더 있는데, 바로 참조자(reference)입니다. swap3 함수를 보면 함수 인자인 a와 b의 type이 int가 아니고, int 뒤에 &가 붙어있는 것을 볼 수 있습니다. 그러니까 a와 b는 int reference인 것입니다.

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

 

참조자는 C에서의 포인터랑 거의 비슷한 기능을 하지만 포인터에서 Null pointer에 값을 넣는다거나 type이 다른걸 마음대로 캐스팅한다거나 하는 문제들을 덜 할 수 있게 하는 패러다임인거고, 지금이 C++ 시간은 아니니까 이 정도로만 다루고 넘어가겠습니다.

 

그 다음으로는 STL을 좀 다뤄볼까 합니다. STL은 C++에서 제공되는 라이브러리로, C++을 입문한지 얼마 안되셨다고 해도 STL이라는 단어 자체는 들어보셨을 것입니다.

복잡한 얘기는 생략하고, C++에는 미리 다양한 알고리즘과 자료구조가 STL에 구현되어 있어서 우리는 필요한 자료구조를 직접 구현할 필요가 없이 그냥 STL에서 가져다 써서 사용할 수 있습니다.

 

종류도 굉장히 다양한데 각 STL들은 나중에 대응되는 자료구조를 배운 후에 소개하고 일단 지금은 배열과 비슷한 기능을 수행하는 vector STL만 소개하겠습니다.

 

원래 C++에서는 배열을 선언할 때 크기를 명시해야 하고 무조건 해당 크기 안에서만 사용을 해야 합니다. 그런데 vector는 일종의 가변배열로 크기를 마음대로 늘렸다 줄였다 할 수 있습니다. 자세한 기능은 0x03강에서 알려드릴거고 지금은 간단하게만 익혀보겠습니다. 참고로 vector는 vector 헤더에 선언되어있습니다.

 

01번째 줄같이 선언하면 type이 int이고 0으로 초기화된 100칸짜리 가변배열 v가 선언되고, 02, 03번째 줄처럼 그냥 일반적인 배열을 쓰듯이 인덱스에 접근해서 값을 바꿀 수 있습니다.

 

자 이제 우리가 살펴볼 것은 STL을 함수 인자로 넘길 때 어떤 일이 생기는지에 대한 것입니다. 언젠가 코딩테스트 특강을 할 때 이걸 질문하고 정답이 무엇인지 물었는데, 절반 넘게 오답을 말씀하셨습니다. 

 

코드를 보시면 100칸짜리 0으로 초기화된 vector v를 선언하고 func1을 호출합니다. func1에서는 v[10]을 7로 바꿉니다. 그 다음에 v[10]을 출력하는데 과연 값이 0일지 7일지 알아맞춰봅시다.

 

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

 

그냥 STL을 쌩으로 함수 인자에 넣으면 복사해서 보낸다는걸 꼭 유의하셔야 합니다. 이 사실을 머릿속에 넣어두고 cmp1 함수를 한 번 확인해봅시다.

 

이 함수가 뭐하는 함수인지 쉽게 알 수 있을 것 같은데, 두 vector를 인자로 넘겨받아 idx번째 원소의 값을 비교한 결과를 반환하는 함수입니다. 두 vector의 크기가 N이라고 할 때 이 함수의 시간복잡도는 얼마일까요?

 

시간복잡도는 충격적이게도 O(N)이 됩니다. 아니 함수 안에 연산을 딱 1번만 하는데 O(N)이라는게 무슨 말도 안되는 소리냐라고 생각이 들 수 있지만 v1, v2를 인자로 실어서 보낼 때 원본으로부터 복사본을 만드는 비용을 생각하지 못하고 계신 것입니다. v1, v2의 크기가 N이니까 N개의 원소들을 하나하나 복사하는 과정은 O(N)이 듭니다. 그래서 이 함수는 의도하지 않게 시간복잡도가 O(N)이 됩니다.

 

그런데 저희는 그냥 idx번째 원소의 값만 비교하고 싶은데 매번 vector를 복사하는건 정말 말이 안되는 일입니다. 이럴 때 참조자를 이용하면 됩니다. cmp2를 확인해보세요.

 

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

 

지금 다룬 이 내용들이 헷갈려버리면 코드의 시간복잡도를 착각해버리거나 함수에서 복사본의 값을 바꿔서 원본은 변함이 없는데 원본이 바뀐다고 잘못 생각해서 분명 답이 이상하게 나오는데 원인을 못찾는다거나 할 수 있기 때문에 참조자와 함수 인자 부분은 기억을 해두는 것을 추천드립니다.

 

이번에는 표준 입출력에 대해 다루겠습니다. 코딩테스트에서 입력과 출력은 표준 입출력을 사용합니다. C에서는 scanf/printf로 입력과 출력을 처리하고 C++에서는 cin/cout을 사용하는데, 기능에 별 차이가 없어서 어느 것을 쓰셔도 상관이 없습니다. 참고로 저는 cin/cout을 사용하긴 합니다.

 

scanf/printf에서 단 한 가지 아쉬운 점이라고 한다면, C++ string을 처리할 수가 없습니다. 아시다시피 C에서는 char*으로 문자열을 다루는데 사실 char*보다 C++ string이 월등하게 편합니다. 그래서 scanf/printf를 쓰면서도 C++ string을 활용하고 싶으면 일단 char*으로 입력을 받고 string으로 형 변환을 해서 원하는 작업을 다 끝낸 후에 c_str() 메소드를 이용해 출력하면 됩니다. 코드를 한 번 확인해보세요.

 

그리고 scanf를 쓰든 cin을 쓰든 주의해야 할 것이 있는데, scanf와 cin 모두 공백을 포함한 문자열을 입력받을 때 굉장히 껄끄럽습니다. 코드를 보시면 알겠지만 둘 다 공백 앞까지만 입력을 받기 때문입니다.

 

해결책으로는 3가지 방법이 있는데, 첫 번째는 scanf에서 줄바꿈(\n)이 나오기 전 까지 입력을 받는다는걸 명시하는 방식입니다. 그런데 솔직히 저건 너무 외우기가 힘들 것 같습니다.

 

두 번째는 gets 함수를 사용하는건데, 문제는 저 함수가 보안상의 이유로 C++14 이상에서는 제거되었습니다. 그래서 이것도 별로입니다. 

 세 번째는 getline을 이용하는건데 이게 제일 깔끔해보입니다. 대신 이건 type이 C++ string이어야 합니다.

 

두 번째는 환경에 따라 사용하지 못할 수도 있으니 아예 제껴두고, 선택지가 첫 번째나 세 번째인데 제 눈에는 getline이 더 좋아보이긴 합니다.

 

아무튼 공백이 포함된 문자열을 받아야 할 때 단순히 scanf나 cin을 쓰면 안된다는걸 꼭 기억해주셔야 합니다.

 

앞서 말했듯 scanf/printf를 쓰든 cin/cout을 쓰든 아무 상관이 없지만, scanf/printf에서는 신경을 안 써도 되는데 cin/cout에서는 꼭 주의할게 있습니다.

 

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

이걸 안해두면 입/출력의 양이 많을 때 시간초과가 날 수 있습니다. 두 명령이 뭐하는 명령인지 몰라도 상관은 없지만 그래도 알아서 나쁠건 없으니 알려드리겠습니다.

 

기본적으로 scanf/printf 등에서 쓰는 C stream과 cin/cout 등에서 쓰는 C++ stream은 분리가 되어있습니다. 그런데 지금 코드처럼 printf와 cout을 번갈아하며 사용하는 상황을 생각해보면 사용자 입장에서는 C stream과 C++ stream이 분리되어있고 어쩌고 하는 내용이 다 알 바가 아니고 그냥 11111, 22222, 33333이 차례대로 나오는게 정상일 것입니다.

 

이렇게 코드의 흐름과 실제 출력이 동일하기 위해서 기본적으로 프로그램에서는 C++ stream과 C stream을 동기화하고 있습니다. 그런데 내가 C++ stream만 쓸거면 굳이 두 stream을 동기화하고 있을 필요가 없게 됩니다. 쓸데 없이 시간만 잡아먹으니까요.

 

그렇기 때문에 C++ stream만 쓸거면 동기화를 끊어버려서 프로그램 수행 시간에서 이득을 챙길 수 있고, 동기화를 끊는 명령이 sync_with_stdio(0)입니다. 엄밀히 말해 인자가 bool type이라 sync_with_stdio(false)가 더 맞긴 한데 false보다 0이 더 짧으니 그냥 0으로 하겠습니다.

 

대신 동기화를 끊었으면 절대 cout과 printf를 섞어쓰면 안됩니다. 섞어쓰면 지금 코드 출력 결과처럼 순서가 꼬이게 됩니다.  

 

참고로 Visual Studio 2017/2019에서는 sync_with_stdio를 그냥 무시하고 무조건 동기화를 유지하고 있어서 혹시 실습을 VS 2017/2019에서 진행한다면 오른쪽 코드도 그냥 11111 22222 33333으로 출력이 나올 것입니다. 하지만 채점 서버는 gcc이기 때문에 분명히 차이가 있습니다.

 

두 번째 명령인 cin.tie(0)을 이해하려면 버퍼라는 개념을 이해해야 합니다. 그런데 버퍼가 각 잡고 강의하면 거의 30분은 들여서 설명해야 할 개념이어서 아쉽지만 좀 간략하고 두리뭉실하게 설명을 해야할 것 같습니다.

 

일단 저희가 화면에 아무 글자나 출력을 하는걸 생각해보면, 저희는 별 생각 없이 cout으로 출력을 찍지만 사실은 위와 같이 한 글자 한 글자가 바로 화면에 보이는게 아닙니다.

 

그렇지 않고 출력 버퍼라는 곳에 문자가 임시로 저장되었다가 버퍼가 비워지면서 화면에 보입니다.

 

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

 

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

지금 이 코드를 보면 3번에 걸쳐 두 수를 입력받고 합을 출력하는데 우리는 당연히 순서에 맞게 콘솔에 나타나기를 원합니다. 그런데 예를 들어 6번 줄에서 "118\n"이란 출력을 하라고 했을 때, 바로 출력이 되지 않고 버퍼에 들어있다가 "2 5"를 입력한 후에야 출력이 되면 순서가 꼬일 것입니다.

 

이런 현상을 막으려고 기본적으로는 cin 명령을 수행하기 전에 cout 버퍼를 비워줍니다. 버퍼를 비우면 자연스럽게 "2 5" 입력이 들어오기 전에 118이 출력될거고 또 "94 542" 입력이 들어오기 전에 7이 출력되어서 순서가 꼬이지 않게 됩니다. 

 

그런데 온라인 저지 사이트에서는 채점을 할 때 그냥 출력 글자만 확인을 합니다. 그렇기 때문에 콘솔 창에서 입력 글자와 출력 글자 사이에 순서가 설령 꼬인다고 해도 채점에 아무런 영향을 주지 않고 두 경우 모두 다 정답 처리가 됩니다.

 

그러면 굳이 cin 명령을 수행하기 전에 cout 버퍼를 비울 필요가 없다는걸 알 수 있습니다. 그래서 cin 명령을 수행하기 전에 cout 버퍼를 비우지 않도록 하는 코드가 cin.tie(nullptr)인거고, 엄밀히는 type을 지켜서 nullptr로 쓰는게 좋지만 그냥 타이핑도 아낄겸 0으로 쓰겠습니다.

 

sync_with_stdio, cin.tie 명령에 대해 설명을 드렸는데 잘 이해가 안가면 cin/cout을 쓸 땐 반드시 저 두 명령을 넣어줘야한다고만 받아들이고 넘어가도 됩니다. 그리고 sync_with_stdio를 쓴 이후로는 무조건 cin/cout만 쓰고 printf/scanf를 쓰면 안된다는 것도 꼭 기억하셔야 합니다.

 

endl은 긴 말 안하겠습니다. 절대절대절대절대절대절대절대 쓰면 안됩니다. 진지하니까 궁서체로 썼습니다. 그냥 endl은 잊어버리시고 절대절대 쓰면 안됩니다.

 

endl은 개행문자("\n")를 출력하고 출력 버퍼를 비워라는 명령입니다. 앞에서도 얘기했지만 어차피 저지는 프로그램이 종료될 때 출력이 어떻게 생겼는지를 가지고 채점을 진행하니까 중간 중간 버퍼를 비우라고 명령을 줄 필요가 전혀 없습니다.

 

줄바꿈이 필요하면 endl 말고 그냥 개행문자를 출력하시면 됩니다.

 

그냥 코드만 작성하면 땡인줄 알았는데 알아야할게 너무 많습니다. 그래도 나중에 풀다가 원인 모를 이유로 틀린 다음에 한참 헤매는 것 보다는 미리 다 알아두는게 좋을 것 같아서 싹 다 알려드렸습니다.

 

이제 여러분이 코딩테스트를 볼 때 도움이 많이 될 코드 작성 팁을 알려드리겠습니다. 첫 번째로 코딩테스트와 개발은 다르다는 것을 꼭 기억하셔야 합니다. BOJ 10871번 : X보다 작은 수 문제를 통해서 표현의 의미를 한 번 이해해보겠습니다. 문제로 들어가셔서 직접 풀어보시면 좋겠습니다. 혹시 폰으로 보고 계시면 코딩을 할 수가 없을텐데, 그렇더라도 일단 문제는 한 번 보고 오세요.

 

앞으로라도 지금 군대에서 이 강의를 보신다거나 출퇴근 시간을 힘들게 쪼개서 이동 중에 보고 계시면 어쩔 수 없이 쌓아뒀다가 컴퓨터를 쓸 수 있을 때 다 짜보시고, 가능하면 컴퓨터 앞에서 직접 실습을 같이하면서 진행하는게 더 좋을 것 같습니다.

 

조금 다른 얘기지만 저는 옛날에 인턴할 때 출퇴근 시간에 지하철을 타면 사람에 치여서 정신을 못차리겠더라구요. 그래서 그냥 음악이나 들으면서 시간을 죽였는데, 지금 이직이나 자기계발을 위해 없는 시간 쪼개어서 출퇴근 중에 보고 계신 분이 있다면 정말 존경합니다. 열심히 하셔서 꼭 좋은 결과가 있길 바라겠습니다.

 

아무튼 문제를 보시면 N개의 정수를 입력받아서 싸바싸바 해야 하는데 실제 개발을 오래 하셨던 분들은 코드를 아주 정교하게 짜시는 경우가 더러 있습니다.

 

대충 왼쪽 코드와 같은 방식인데, 일단 필요한 헤더만 include 했고, 딱 크기에 맞게 n칸짜리 배열을 잡은 후에 해제까지 합니다. 아주 깔끔하죠.

 

그런데 코딩테스트에서는 내가 헷갈리지 않는 범위 안에서 어떻게든 타이핑을 아끼는게 최고입니다. 그래서 저는 오른쪽 위와 같이 짤 것입니다.

 

왼쪽같은 코드를 선호하시는 분들은 기겁을 하실 수도 있습니다. 또 현업이었다면 코드리뷰에서 대차게 까일 것입니다. "아니 cin/cout만 쓰면서 온갖 헤더를 다 include할거야?", "sync_with_stdio는 bool 자료형을 인자로 받는데 왜 0을 넣어?", " 왜 전역에 다 때려박아?", "배열 크기는 왜 5를 더 크게 받았어?" 등등...

 

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

 

그리고 사실 문제 상황을 보면 배열 자체가 필요없기 때문에 저는 더 줄여서 오른쪽 아래와 같이 짤 것입니다.

 

그리고 이건 굉장히 구체적인 팁인데 출력 맨 마지막에 공백 혹은 줄바꿈이 추가로 있어도 상관이 없습니다. 당장 앞의 문제도 엄밀하게 말을 하면 답이 1 4 2 3일 때 3 다음에 공백 1개가 추가로 출력되었습니다. 그래도 아무 문제 없이 정답 처리가 됐습니다.

 

공백이랑 비슷하게 줄바꿈 또한 출력 맨 마지막에 추가로 있어도 정답 처리가 됩니다. 그래서 이 부분을 별도로 예외처리를 할 필요가 없습니다.

 

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

 

그럴 때 디버거를 켜면 뭔가 꼬이고 늪에 빠져드는 것과 같은 느낌을 받을 때가 있어서 차라리 중간 변수를 보고 싶으면 cout이나 printf로 출력을 찍어서 확인하고 디버거는 굳이 사용을 안하는 것을 권장합니다. 하지만 이건 권장일 뿐이고 아무리 생각해도 디버거를 쓰는게 낫다 싶으면 쓰셔도 상관은 없습니다.

 

오늘 강의는 좀 순한 맛이었습니다. 지금까지 한게 롤로 따지면 이제 막 튜토리얼을 마치고 인게임에서 도란링과 포션 2개를 산 상황입니다. 갈 길이 까마득하게 멀지만 그래도 조금씩 하다보면 분명 발전이 있을거니까 당장 지금부터 백준 그룹 내의 문제들을 계속 풀어보세요.

 

풀다가 잘 모르겠는게 있으면 검색하셔서 풀이를 적극적으로 찾아보는 것을 추천합니다. 적어도 알고리즘 공부에서만큼은 어떻게 푸는건지 잘 모르겠다고 할 때 풀이를 찾아보는게 나쁘다고 생각하지 않습니다. 한 30분 정도 고민했는데도 전혀 실마리가 잡히지 않으면 네이버나 구글 같은 곳에 문제 번호로 검색해서 다른 사람의 코드를 보고 배워가시면 됩니다.