[실전 알고리즘] 0x00강 - 오리엔테이션_구버전

------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

현재 보고있는 강의는 구버전입니다. 내용에는 문제가 없으나 리뉴얼 중이니 이 게시글을 참고해주세요.

 

리뉴얼한 버전은 [실전 알고리즘] 0x00강 - 오리엔테이션_신버전 에서 확인할 수 있습니다. 리뉴얼 버전으로 보시는 것을 추천드립니다.

------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

 

안녕하세요, BaaaaaaaaarkingDog입니다. 한 1-2개월 전부터 알고리즘 강의를 만들어보고 싶다는 생각을 했는데 시험기간을 거치고 또 종강한 뒤에 쉬엄쉬엄 살다보니 이제야 만들게 됐네요. 최대한 방학 안에 다 만들 수 있도록 노력해보겠습니다.

 

목차는 위와 같습니다.

 

TMI이지만 자기 PR의 시대인만큼 자랑 좀 하고 가겠습니다!! 우선 저는 어렸을 때부터 꽤 수학을 잘하는 편이었는데요, 초5때 소수를 가지고 계차수열을 만들다가 C언어로 만든 프로그램이 소수 목록을 구해준다길래 그 때 처음으로 프로그래밍을 접하게 됐습니다. 하지만 프로그래밍을 엄청 열심히 한건 아니었고, 영재고 준비를 하면서 시간이 남을 때 가끔씩 코딩을 하는 정도였습니다. 영재고에 진학하고 고2가 되어서 알고리즘을 처음으로 알게 되었고 그 때부터 알고리즘 공부를 조금씩 했습니다. 학교 공부를 따라가기도 벅차서 이때도 그다지 열심히 하지는 않았지만요.

 

그리고 IOI(=국제정보올림피아드) 교육생으로 뽑혀 교육을 받았지만 기초가 부족했던 터라 거기서 참교육을 당했습니다. 또 저에게 교육 시스템이 좀 안맞기도 했구요. 그래서 알고리즘은 사실상 고2때 잠깐 하고 그만두게 됐습니다. 그래도 정보올림피아드는 고2, 고3때 둘 다 은상을 받았습니다.

 

사실 고등학교때는 보안과 암호학 공부를 더 많이 했습니다. 고2때 BOB를 했고, 암호 관련 대회에서 상도 몇 개 받았습니다.

 

대학에 진학한 이후 신입생때는 zl젼해커가 되려고 했으나 Return Oriented Programming이라는 큰 벽을 넘지 못하고 시스템 해킹을 접게 됐습니다. 최근에 다시 보니 이해가 가긴 하네요. 2학년 때는 결국 돌아돌아 다시 알고리즘을 하게 됐습니다. 다행히 고등학교때와는 다르게 알고리즘에 재미를 붙일 수 있었고 적혀있는 것 처럼 많은 상들을 쓸어담게 됐습니다. 또 알고리즘을 공부하면서 기른 문제해결능력과 구현력이 비단 알고리즘능력 뿐만 아니라 육목 SW 알고리즘 대회와 같이 다른 분야에서도 큰 도움이 되었습니다.

 

죄다 5등상 투성이인게 좀 아쉽긴 하지만 그래도 이 정도면 어디가서 나 알고리즘 공부 좀 했다고 말하고 다녀도 될 것 같습니다. 물론 저보다 더 잘하는 사람이 수두룩빽빽하지만 알고리즘 강사 중에는 제 실력이나 수상 실적이 월등히 높은 편이니 걱정하지 않으셔도 됩니다. 코드포스 레이팅은 10월부터 오렌지에서 계속 정체되어있는데 레드를 찍을 수 있도록 노력해보겠습니다 ^_____^ 더 자세한 항목은 Resume을 참고하세요!

 

이 강의는 삼성전자 SW Test A형과 B형 중간 수준의 코딩테스트에 나올 수준의 자료구조 및 알고리즘을 알려주고, 실제로 코딩테스트를 잘 넘길 수 있도록 도움을 주기 위한 강의입니다. 이미 코딩테스트를 걱정하지 않으셔도 될 실력을 가지신 분은 굳이 강의를 들으실 필요 없이 그룹에 들어오셔서 문제만 풀어보셔도 됩니다. 다만, 코딩테스트에서 나오지 않을 부분은 다루지 않을 예정이기 때문에 코딩테스트에서는 거의 안나오지만 기술 면접에서는 나올 수 있는 Binary Search Tree, AVL Tree, Linked list, Hash collision 등의 내용은 별도로 공부를 하시는 것을 추천드립니다.

 

모든 강의 내용이 도움이 되기 때문에 완강을 하는 것을 추천드리지만, 만약 삼성 SW역량테스트 A형을 급하게 대비하는 상황이라면 0x09강까지만 들으시면 됩니다. 

 

강의를 따라오기 위해서는 C/C++ 문법을 알고 있으셔야 합니다. 단, 다른 부분은 다 괜찮은데 C++ 클래스와 STL만을 모른다면 둘을 먼저 익히고 강의를 듣는 것 보다는 강의와 함께 C++ 공부를 병행하는 것을 추천드립니다. 만약 지금까지 C++을 모르고 JAVA, Python으로 코딩테스트를 준비했다면 두 언어는 C++에 비해 느리고 자료의 양이 C++에 비해 부족하기 때문에 이 기회에 C++을 배워보는 것을 추천드립니다. 특히 Python은 정말 느리기 때문에 Python만을 알고 계신다면 반드시 C/C++을 공부하셔야 합니다.

 

자료구조 및 알고리즘에 대한 지식은 없어도 괜찮습니다. 해당 지식이 없다고 가정하고 강의를 제작할 예정입니다.

 

이제 알고리즘이 무엇인지 알아보겠습니다. 알고리즘은 주어진 문제를 해결하는 절차 및 방법으로, 입력/출력/명확성/유한성/효율성이라는 요소를 가지고 있지만 저희는 시험 공부를 하고자하는게 아니라 코딩테스트를 준비하기 위해 알고리즘을 공부하므로 정의를 깊게 들어간다거나, 각 조건의 의미를 외운다거나 하는 부분은 생략하겠습니다.

 

알고리즘 문제를 푸는 공부를 PS(=Problem Solving) 혹은 CP(=Competitive Programming)이라고 부르기도 합니다. 코딩테스트는 PS, CP와 같이 주어진 문제를 정해진 시간 제한과 메모리 제한내로 해결할 수 있는 능력을 측정하는 테스트입니다.

 

알고리즘을 잘 한다는 것은 배경지식, 문제해결능력, 구현력 3가지 능력을 모두 갖추고 있다는 의미입니다. 배경지식은 다양한 알고리즘, 자료구조, 기타 테크닉 등과 같이 문제를 해결하기 위해 필요한 지식을 의미합니다. 문제해결능력은 배경지식을 지금 당면한 문제에 맞게 잘 변형해서 적용시키는 능력을 의미합니다. 마지막으로 구현력은 본인이 생각한 알고리즘을 코드로 잘 옮겨낼 수 있는 능력을 의미합니다. (박트리님의 블로그)

 

"알고리즘 그거 잘 해봤자 무슨 의미냐, 그냥 남이 퀵소트 구현해놓은 것을 가져다쓰면 되는거 아니냐" 는 주장은 알고리즘을 단순히 배경지식만으로 착각하기 때문에 나오는 주장입니다. 알고리즘 능력은 주어진 문제를 내가 아는 지식으로 잘 풀어낼 수 있게끔 변형하는 문제해결능력, 그리고 나의 아이디어를 코드로 옮겨내는 구현력을 모두 포함하는 의미이고, 코딩테스트에서 좋은 성과를 내기 위해서는 배경지식, 문제해결능력, 구현력 모두 필요합니다. 

 

강의는 자료구조 및 알고리즘을 설명하고 대표적인 문제 2개 정도를 같이 풀어보는 식으로 진행이 될 것이기 때문에 이 강의를 통해 배경지식과 일부 전형적인 문제에 대한 문제해결능력을 기를 수 있습니다. 그러나 시간이 허락한다면 직접 다양한 문제를 풀어보며 구현력과 문제해결능력을 기르셔야 합니다.

 

강의에서 다루는 문제와 별도로, 주제와 연관이 있어 풀어보면 도움이 될 다양한 문제를 소개해드릴 계획입니다.

 

C++ 컴파일을 위해 사용하는 프로그램은 Visual Studio 2017, Visual Studio Code, Code::Blocks, Dev-C++ 등이 있고 저는 Windows에서 Visual Studio Code + MinGW를 사용하고 있습니다. 코딩 테스트의 채점 서버는 99% GCC를 기반으로 하므로 로컬에서도 GCC를 기준으로 환경을 만들면 환경 불일치로 인한 오답을 방지할 수 있습니다. 아래의 예시는 Visual Studio 2017에서 사용하는 MSVC가 Variable Length Array(가변 길이 배열)를 지원하지 않는 예시이고, 이러한 다른 점들로 인해 남의 코드를 돌릴 때 본인 환경에서 컴파일 에러가 나거나 오동작하는 문제가 발생할 수 있습니다. 그렇기에 GCC로 컴파일 할 수 있도록 환경을 만듭시다.

 

아마 Windows 운영체제를 쓰고 계신다면 대다수가 Visual Studio 2017로 C언어 프로그래밍을 해보셨을테지만, 이번 기회에 Visual Studio Code로 옮겨타는 것을 추천드립니다. 설치법이 조금 복잡한데 인터넷을 찾아가면서 한번 세팅을 해보세요. Code::Blocks, Dev-C++을 써도 상관은 없습니다. 그리고 Baekjoon Online Judge 그룹(링크) 에 가입 신청을 해주세요. 그룹에 문제들을 올릴 예정입니다.

 

사실 알고리즘이 실무에 얼마나 큰 도움이 되는지는 저도 잘 모르겠습니다. 아직 실무다운 실무를 해본 적이 없어서요. 2017년 겨울에 삼성전자에서 인턴을 하긴 했는데, 보안 관련 업무였어서 딱히 개발을 해보지를 않았네요. 그렇기에 현업에 계신 분들이 알고리즘의 중요성을 평가절하하는 것도 일리가 있다고 생각합니다. 또 분야에 따라 알고리즘이 필요한 정도도 차이가 많이 날 것입니다. 그렇지만 앞서 말한 배경지식, 문제해결능력, 구현력이 높아서 나쁠건 없습니다.

 

그리고 아직 알고리즘 능력을 평가하는게 국내에 보편화되어있지 않던 시절, 한국에서 5위 안에 드는 대형 게임회사에서조차 비효율적인 코드를 만들어내는 경우가 비일비재했다는 얘기를 들었습니다. 예를 들어 두 유저리스트에 공통으로 포함된 닉네임을 정렬을 통해 $O((N+M)lgN)$에 찾는게 아니라, $O(NM)$에 찾는다거나 하는 일들을 말합니다.

 

삼성, LG 등의 국내기업 뿐만 아니라 구글, 페이스북에서도 구글 코드잼, 페이스북 해커컵과 같은 대회를 열고, 채용 과정에서 코딩테스트가 포함되어있고, 알고리즘을 잘하는 사람들을 우대하는 것도 코딩테스트를 통과할 수준의 배경지식, 문제해결능력, 구현력을 갖추고 있기를 원하는 것이 아닐까 싶습니다.

 

굳이 따지자면 알고리즘 실력과 현업에서의 능력은 log scale을 따르는 것 같습니다. 알고리즘이 별로 재밌지 않다면 코딩테스트에 합격할 정도의 수준만 만들어놓은 뒤 하고싶은 공부를 하셔도 큰 상관이 없을 것입니다.

 

 

이번 강의에서 다룰 내용은 모두 끝났습니다. 저도 아직 공부를 하는 입장에서 코드포스 레이팅이 수직하강하거나 남들은 다 푸는 문제가 안풀릴 때, 맞왜틀을 반복할 때 굉장히 짜증나고 회의감이 들 때가 있습니다. 그렇지만 폼은 일시적이지만 클라스는 영원하다는 명언처럼 당장의 시련에 일희일비하지말고 힘내서 꾸준하게 열심히 하면 분명 실력이 늘어있을거라 믿어 의심치 않습니다. 저도, 이 강의를 들을 예정인 여러분들도요. 그러니 같이 힘내봅시다!!

 

강의와 관련한 간단한 질문은 블로그 댓글로, 코드를 첨부해야 하는 긴 질문은 BOJ 그룹 게시판으로, 개인적인 질문은 admin@encrypted.gg 로 남겨주세요. 그 어떤 것이든 능력이 되는 한 답을 드릴 것이지만, 문제를 풀다가 생긴 질문은 꼭 저를 통할 필요 없이 BOJ 슬랙이나 카카오톡 오픈채팅방 등에서 질문하시는게 더 빠르게 답을 얻을 수 있는 방법일 것입니다.