_1_ 알고리즘 문제풀이와 코딩테스트는 뭘까
알고리즘문제풀이와 코딩테스트에 대해서 알아봅시다.
알고리즘 문제풀이(PS)는 뭘까
21세기를 살아가는 분들이라면 흔히 유튜브 알고리즘이라는 단어를 들어보셨을 겁니다.
알고리즘의 사전적 정의는 다음과 같습니다.
특히 컴퓨터에 의해 수행되는 계산이나 다른 문제해결 동작에 필요한 절차나 일련의 규칙
이게 대체 뭔말일까요? 저도 모르겠습니다. 사실 알고리즘의 정의는 다양해서 굳이 어떤 것이라고 명확히 설명하긴 힘들지만, Problem Solving(PS) 이라고도 불리는 알고리즘 문제풀이라 함은 다음과 같은 것을 의미합니다.
- 주어진 입력으로 문제에서 원하는 출력을 하는 프로그램을 작성하는 것
- 입력은 문제에서 주어지며 출력을 적절히 할 수 있도록 프로그램을 완성하는 것
- 하지만 우리의 프로그램은 문제에서 제한해놓은 시간 제한과 메모리 제한을 준수해야한다(!?)
예를 들어, 두 숫자를 더하는 문제라고 해봅시다.
- 문제에서는 두 숫자를 입력으로 줄 것입니다.
- 우리는 두 숫자를 더한 값을 함수의 반환값이나 출력으로 내뱉어줘야(?) 합니다.
- 우리가 만든 프로그램은 문제에서 제시한 시간/메모리 제한을 준수해야 합니다. 예를 들어, 문제의 시간 제한이 1초라면 우리의 프로그램이 컴퓨터가 돌릴 때 두 숫자를 더하는데 1초 보다 오래 걸리면 시간 초과(Time Limit Exceeded) 판정을 받게 되어 틀리게됩니다.
코딩테스트는 뭘까
알고리즘 코딩테스트는 근래에 부상한 기업의 채용 프로세스중 하나입니다.
어떤 기업에서는 코딩테스트가 1차가 되어 일단 이것부터 통과한 사람들만 지원서와 2차 테스트 등을 보겠다는 곳도 많고 아니면 지원서를 본 후에 바로 코딩테스트를 실시하는 경우도 있습니다.
코딩테스트의 목적은 말 그대로 언어를 활용할 수 있는 기초적 능력을 보기 위함입니다.
기업에서는 아무리 지원서를 잘 쓰고 스펙/학업 성적이 우수해도 자신의 생각을 코딩으로 옮기는 능력이 없으면 받지 않겠다는 의미일 수도 있고 그냥 지원하는 사람이 너무 많아서 걸러내는 수단으로도 좋을 수도 있습니다.
코딩테스트는 결국 알고리즘 문제풀기입니다.
하지만 같은 수학이여도 수능 수학과 내신 시험의 스타일이 다른 것처럼 흔히 말하는 “코테” 스타일의 문제들이 존재합니다. 이는 보통 기업에 따라서도 꽤 큰 차이를 보입니다.
유명한 삼성의 코딩테스트는 특별한 알고리즘을 사용하지 않고 그저 문제에서 주어진 프로그램을 잘 읽고 잘 구현해내는 능력만 보기도 하고, 카카오의 코딩테스트는 여러 알고리즘을 폭넓게 출제하기도 합니다.
문제를 풀기 위해 Skill(알고리즘)을 쌓자
모든 문제들은 특정한 알고리즘을 사용하는 것으로 분류됩니다.
다음은 국내에서 가장 유명한 PS사이트중 하나인 백준의 알고리즘 분류입니다.
어떤 문제를 풀기위해 단 하나의 알고리즘이 사용될 수도 있고 여러개의 개념들이 혼합되어 사용될 수도 있습니다.
그러면 그 문제를 풀기 위해 익혀야 하는 특정 알고리즘이 존재하겠죠?
이 “알고리즘” 이란 것은 정말 추상적인 개념이여서 대충 ~이런식으로 작동을 하면 XX 라고 이름을 붙이겠다 라고 해서 분류된 걸 수도 있고, 구현법 그자체나 동작하는 방식에 따라 이름을 붙인 것도 있습니다.
그래서 알고리즘에 따라 굉장히 폭넓은 범위를 다룰 수도 있고 좁은 범위에 한정된 개념이 되기도 합니다.
그래서 어떤 알고리즘을 사용해서 풀어야 하는 문제를 겨우 그것 하나 모른다고 못풀까요??
네. 못풉니다. 뭘 기대하셨나요…
알아도 못푸는 경우가 99%입니다.
특정 알고리즘을 익혀서 자신의 것을 100% 만드는 것은 매우 험난한 과정입니다.
우리가 고등수학 목차에 나오는 모든 내용을 알아도 막상 수능에서 모든 문제를 풀 수 있는것이 아니듯이 수많은 응용이 존재합니다.
애초에 문제의 분류를 유추하는것조차 불가능에 가까운 문제들도 많습니다. “아 모르겠다…” 하고 어떤 알고리즘을 써서 푸는건지 문제의 분류를 까보면 전혀 엉뚱한 것이 튀어나올때가 많습니다.
우리는 문제를 꼼꼼히 읽고 분석하여 어떤 알고리즘이 쓰이는 것인지 유추해내고 코딩까지 해서 올바른 답을 도출해야합니다.
문제를 꼼꼼히 읽고 분석하는 능력은 알고리즘 문제풀이에서 가장 중요하게 요구되는 불변의 진리 1항입니다.
앞서 언급했듯이 알고리즘 문제의 구성은 문제 description 그 자체도 있지만 시간 제한, 메모리 제한, 입출력 양식 모든것에 있기 때문에 이 중 하나라도 빼놓고 읽으면 당장 알고리즘세계 랭킹 1위를 데려와도 문제에서 요구하는 것을 제대로 파악하지 못합니다.
이렇게 ~를 구하라라고 설명하는 부분도 중요하지만,
이 부분들도 엄청나게 중요하다는 뜻입니다.
실제로 이 문제와 이 문제는 입력부분에 0 세개만 더 찍혀있을 뿐인데 단순한 수학 문제에서 갑자기 난이도가 17단계가 뛰어버렸으며 술자리에서 해당 문제에 사용되는 알고리즘을 언급하기만 해도 갑분싸가돼서 자동으로 아싸가 되버리기 십상입니다.
이처럼 문제를 꼼꼼히 파악하는 능력은 중요하고 제가 좋아하는 파인만 알고리즘에서도 이는 가장 첫 단계입니다.
WRITE DOWN THE PROBLEM
문제를 정확히 파악만 해도 이미 절반 이상은 푼 것이라고 생각하시면 됩니다.
코딩테스트엔 어떤 수준의 알고리즘이 나올까?
전 문단에서 갑자기 겁을 드려서 죄송합니다.
하지만 코딩테스트에 사용되는 알고리즘들은 술자리에서 얘기해도 골백번 얘기하면 짜증이 날 수 있을 정도이지 아싸가 될 정도는 아닙니다.
코딩테스트를 한두문제만 출제할 수도 있고 긴 시간을 주고 대여섯문제가 출제될 수도 있습니다.
게다가 코딩테스트를 암기해서 볼 수 있다는 말이 괜히 나오는 것이 아니듯이 문제를 보면 코딩테스트의 문제들은 반복되는 경향이 있고 어떤 알고리즘을 써서 풀어야하는지 알고리즘 분류가 쉽게 보이는 경향이 있습니다.
실제로 많이 문제를 푼 사람들은 문제에 있는 그림만 보거나 문제 한 줄만 읽고도 어떻게 푸는 것인지 떠올릴 수 있습니다.
보통 뒤로 갈수록 어려운 문제가 나올 확률이 높지만 코딩테스트에 출제되는 알고리즘들은 절대로 어려운 내용들이 나오지 않습니다.
알고리즘을 응용해서 풀기에 어려운것이지 쓰이는 알고리즘들 그 자체는 절대 난해한 개념들을 집어넣지 않습니다.
갑자기 아무도 모르는 계산기하학문제가 코딩테스트에 출제된다면 제가 기업 정문 앞에서 1인 시위하겠습니다.
차근차근 어떤것들이 나오는지 배워나갈 것입니다.
어떤 언어를 써야할까?
프로그램이 수행되는 것은 공짜가 아닙니다. 무거운 연산이면 무거운대로 시간이 오래걸리고 많은 변수와 함수를 사용한다면 메모리도 많이 사용됩니다.
당연히 언어마다 속도차이도 존재하며 현존 언어 중에 PS에 가장 적합한 언어라고 여겨지는 것은 C++ 입니다. 문법이 다른 언어에 비해 약간 복잡할 수 있어도 압도적으로 빠르고 여러 기능을 잘 지원해주기 때문입니다.
심지어 파이썬은 너무 느려서 실행만 시켜도 환경을 파괴하는 행위를 가장 많이 하게 되는 언어라고 하니 혹시 파이썬을 사용하신다면 꼭 카페에서는 종이 빨대를 사용하시길 바랍니다.
하지만 다른 언어들이 무조건적인 불이익을 받는 것은 아닙니다. 어떤 문제들은 느린 언어라면 그 만큼 문제의 시간 제한을 늘려주기도 하고 애초에 문제를 올바른 방향으로 해결했을 때 언어때문에 못푸는 일은 일어나지 않게 방지합니다.
알고리즘 대회같은 곳에선 시간 제한을 모두 동일하게 걸어버리고 “꼬우면 C++ 쓰든가”(?) 과 같은 문제를 내기도 하지만 코딩테스트에서는 그럴일이 없습니다.
애초에 기업의 코딩테스트에서 해당 언어를 지원해준다는 것은 그 언어로 풀 수 있다는 것을 의미합니다. 그렇지 않다면 같이 시위하러 가시죠.
코딩테스트에서는 파이썬이 가장 유리합니다.
문법도 간결하여 익히기 쉽고 지원해주는 연산도 꽤나 쓸만합니다.
게다가 c++의 int 자료형의 정수 범위가 2³¹-1 이 최대인 반면 파이썬은 그딴거 없습니다. 내부적으로 정수 자료형을 통일하고 큰 수 연산을 구현해두었기 때문입니다.
하지만 파이썬에서도 100만자리 숫자를 곱하는 것과 1자리 숫자를 곱하는 것의 시간차이는 굉장히 크기 때문에 자신의 언어가 어떤식으로 작동하는지 파악하고 익숙해지는 것은 중요합니다.
What’s next?
다음 글부터는 본격적으로 시간복잡도와 공간복잡도의 개념과 입출력에 대해서 알아보도록 하겠습니다.
감사합니다. ⭐️
