요즘 많은 기업들이 코딩 테스트를 채용 프로세스에 포함시켜 진행한다.
현재 백준에서 1100문제 이상 문제를 풀며 얻은 경험을 바탕으로 문제를 풀 때 도움이 되는 것들을 위주로 정리해보려고 한다. 뛰어난 실력은 절대 아니지만 코테를 준비하며 내가 공부했던 알고리즘에 대한 경험들을 공유해보겠다.
모든 문제는 백준사이트 위주로 공유하겠다.
문제를 어떻게 골라야 할까?
첫번째로는 단계별로 풀어보기이다.
개인차가 있겠지만 DFS/BFS까지는 뚫어야 합격 컷트라인 n솔의 끝자락에라도 걸칠 희망이 생길 것 같다.이제 좀 익숙해졌다면 추천하는 것은 solved.ac 사이트이다.
위 사이트에서는 백준 문제들을 티어별로 볼 수 있으며 각기 다른 기준으로 정렬 가능하다.
실버 2~골드 4문제들을 푼 사람이 많은 순으로 정렬하여 하나씩 풀어보는 것을 추천한다. 모르는 문제가 나오면 구글에 검색을 해서라도 알고 넘어가야 하는데 푼 사람이 적은 문제들은 문제를 풀지 못할 때 검색해도 나오지도 않고 봐도 모르겠고 스트레스만 받는다.
시간복잡도
알고리즘 문제에서는 시간 복잡도가 생명이다. 일단 프로그래머스에서는 정확성과 효율성을 따로 계산하고 백준에서는 그런 것이 따로 없다. 백준에 시간제한이라는 문구가 있으며 여기에는 1초, 2초등의 시간제한을 걸어놓는다. 우리가 작성하는 코드에서 시간복잡도에 가장 큰 비중을 차지하는 게 반복문이다.
반복문이 돌아가는 횟수로 시간 복잡도를 측정하고 N을 대입해 시간 초과를 비교한다.
예를 들어int main(){ int n=100000; //n은 10만 for(int i=0;i<n;i++){ for(int j=0;j<n;j++){ cout<<1<<'\n'; } } } //이중 포문으로 0~(n-1)까지를 n번 돈다.위 코드의 시간 복잡도는 O(n^2)이다.
실제 시간을 계산할 때는 대략 10^8(1억) 번의 반복문을 1초로 근사하게 계산한다.
이러면 이 코드는 n이 10^5이고 n^2번을 돌아 10^10번 연산한다.
대략 100초의 시간이 걸리고 시간제한이 1초라면 시간 초과를 받는다.
Tip) 흔히 그래프에서 BFS/DFS/재귀/DP 등의 시간 복잡도도 마찬가지이다. 결국 방문할 수 있는 노드의 개수가 시간 복잡도가 되고 BFS/DFS의 경우는 중복 방문하지 않으니 노드의 개수만큼이고 DP도 정의해놓은 DP 테이블에서 방문하는 노드의 수가 시간 복잡도가 될 것이다.
dp[100][100]이고 중복 방문이 없다면 기본적으로 100*100 즉 n^2가 되는 것이다.
공간복잡도
공간 복잡도는 백준에서의 메모리 제한과 관련이 있다.
메모리는 오히려 계산하기가 더 쉽다. 내가 선언해놓은 변수들을 계산하면 된다.
우리가 문제를 풀면서 변수를 100개씩 선언하지는 않는다. 100개의 변수를 index로 접근할 배열을 만들고 stl을 사용하거나 하기 때문에 전체 메모리는 이러한 것들에 영향을 받을 것이다.
예를 들어int a[1000000]; int main(){ int n=1000000; vector<int> v(n); } //크기가 10^6인 배열 a와 벡터 v를 선언했다.위 코드의 공간 복잡도는 대략 2000000(int element의 총 갯수)*4(Byte)/1024(KB)/1024(MB)이다.
계산을 하면 약 7MB 정도가 나오고 보통 128MB, 256MB 정도로 주어지기 때문에 넉넉하다.
하지만 이 문제 라면 이야기가 달라진다.
메모리 제한이 4MB밖에 안되기 때문에 접근을 달리해야 한다. 이러한 함정들이 메모리 제한을 신경 써야 하는 이유이다.
Tip) 그래프 문제에서 노드의 개수는 크지만 간선의 개수는 적은 문제들이 있다.(예를 들면 그래프가 알고 보니 트리였다던가) 이러한 문제들에서 인접 배열로 그래프를 모델링 한다면 메모리 초과를 유발할 수 있기 때문에 꼭 인접 리스트로 그래프를 모델링 해야 한다.
구현 및 시뮬레이션
사실 왕도가 없는 영역이다. 많이 풀어보는게 답이라 생각하며 구현력을 늘리기 위해 풀었던 문제집과 태그들을 소개하겠다.
DP
나를 비롯한 많은 사람들이 가장 싫어하고 힘들어하는 분야이다. 가장 큰 문제는 문제가 나왔을 때 DP인지도 모른다는 것 이다. DP문제를 나름 생각해보면 앞서 이용했던 정보를 뒤에서 똑같이 활용할 수 있다면 해당문제는 DP문제이다.즉 똑같은 구조가 반복되어야 한다. 사실 이런것들은 말을해도 무의미하니 열심히 많은 DP를 경험해보기를 바라며 DP의 코드 작성 방법에 대해서 간략하게 설명해보겠다.
//재귀를 이용해 DP를 작성한다면 이런식으로 작성한다. //단적인예이니 참고만 하길 바람 int d[100001]; int n; int solve(int k){ if(k==n) return//기저사례에서 처리해야할 행동들 if(d[k]!=-1) return d[k]; int &val=d[k]; val=0;//d[k]를 초기화 //처리해야 할 logic부분 return val; } int main(){ memset(d,-1,sizeof(d));//d배열을 -1로 초기화 cout<<solve(1); }위 소스를 보면 -1로 초기화를 하고 solve 함수를 호출한다. 그리고 d[k]가 -1이 아니라면 return을 해버린다. 이 말은 d[k]를 한 번 갱신해 주었다면 다시 접근하지 않겠다는 말이다.
대부분의 DP가 이와 같은 원리로 이루어진다.
ex) 이 문제도 위와 같은 방식으로 풀 수 있다. 물론 dp 테이블 설계나 logic 처리 부분은 다르게 진행된다.
- 재귀를 이용하지 않고 bottom-up 방식으로 반복문을 이용해서도 dp를 구현할 수 있다. 반복문으로 하는 방식이 시간적 측면이나 메모리적 측면에서 재귀보다 효율적이다. 하지만 문제가 복잡해질수록 재귀를 이용해야 풀 수 있는 문제들이 있으니 꼭 재귀를 이용한 dp 해결법을 익히자
해싱
코테에 정말 단골로 나오는 문제이다. Java와 Cpp 모두 Map 혹은 Set을 이용해 해싱을 하고 삽입, 삭제, 탐색은 logN으로 정말 빠르다.
하지만 언제 해싱을 써야 할지 모를 수가 있다. 물론 문제를 많이 풀어본다면 느낌이 오겠지만 보통 이런 경우에 사용하니까 느낌만 보자.
비트마스킹
카카오에서 비트 연산을 자주 내고 비트 연산은 사실 필수적으로 해야 하는 부분인 것 같다.
비트 마스킹은 보통 n 제한이 64보다 작은 자연수일 때 쓰인다. 왜냐하면 정수형 변수의 비트가 최대 64자리이기 때문이다. 우리가 문제를 풀 때는 비트 마스킹 문제라 생각하고 들어가면 그나마 비트 마스킹 문제라는 걸 인지하지만 코테를 볼 때는 이야기가 다르다. 이 문제가 어떤 분류의 문제인지 모르기 때문에 난이도가 더 올라간다. 비트 마스킹도 많은 문제를 풀어보며 경험치를 쌓고 핸들링 해야 할 변수의 제한이 작을 때 한번 그쪽으로 생각해 보는 게 정답인 것 같다.(물론 바로 떠오르는 게 베스트다)
- 이 문제는 이동 최대 거리가 50만이고 날마다 이동거리는 2배씩 늘어나기 때문에 이동 가능한 최대 날짜는 20을 넘지 않는다. 이 점을 이용해 bfs를 해주는 문제로 방문 체크를 할 때 비트 마스킹이 사용된다.
마무리
몇 개의 키워드만 정리를 해보았는데 많은 분들에게 도움이 되었으면 한다.
아래 링크를 타고 그룹에 가입신청을 해보는걸 추천한다.
그룹의 문제집에 좋은게 많은 것 같다.
