코딩테스트에서 가장 중요한 것은 꾸준함이 아닐까...?
🔥 코딩테스트의 중요성
신입 개발자 채용의 경우 지원 후 코딩테스트로 일정이 시작되는 경우가 대부분이다.
물론 코딩테스트를 보지 않는 경우도 있겠지만, 선택의 폭이 많이 좁아질 것이다. (신입 기준)
또한 코딩테스트를 합격해야 서류전형이 시작되는 경우도 있고 코딩테스트에 합격해야 면접을 볼 수 있는 기회가 주어지기 때문에,
코딩테스트를 합격하는 것은 취업에 있어서 첫 단추를 끼우는 것과 같다.
👀 그렇다면 어떻게 준비해야 할까?
코딩테스트는 결국 많이 풀어본 사람이 유리하다.
주어진 시간동안 주어진 문제를 요구사항에 맞게 프로그래밍하는 것이기 때문이다.
즉, 문제의 요구사항에 맞게 풀이할 수 있는 자료구조, 알고리즘 등을 선택하여 활용할 수 있는 능력이 중요하다.
해당 유형을 많이 풀어봤으면 같은 유형의 문제를 풀이할 때 더 앞서갈 수 있다.
- 예) 프로그래머스 - 단어 변환
- 이와 같은 문제가 주어지는 경우 DFS/BFS 유형(완탐)의 문제들을 많이 풀어본 사람은 그렇지 않은 사람보다 빠르게 풀이 방법을 떠올릴 수 있다.
방문하지 않은 단어 중에 현재 단어에서 한 알파벳만 변경하여 변환 가능한 단어들로 DFS를 진행하고 목표에 도달한 경우 최소 변환 횟수를 갱신한다.
라는 결론에 빠르게 도달하여 이미 구현해본 DFS로 빠르고 정확하게 풀이할 수 있다.
🤔 그럼 모든 유형을 많이 풀어보면 되겠네?
모든 유형들을 충분히 준비 해놓을 수 있다면 그보다 더 좋은 것은 없을 것이다.
하지만 우리에겐 시간이라는 자원이 한정되어 있고 CS, 언어, 프레임워크, 프로젝트, 자소서, 포트폴리오, 면접 준비 등 준비해야할 것들이 너무나도 많다...
따라서 자주 기출되는, 내가 부족한 유형별로 우선순위를 정하여 준비해보자!
필자가 느끼기에 가장 자주 기출되는 유형은 구현
, 완탐
, DP
이다.
✏️ 코딩테스트 문제 유형 정리
코딩테스트에는 시간 제한(효율성)이 존재하기 때문에 시간복잡도가 매우 중요하다.
만약 문제에서 주어진 N이 10,000 이라면 O(N^3) 풀이 방법으로는 시간 초과가 날 것이다. (대부분의 테스트 환경에서)
반대로 생각하면, 이것은 문제의 힌트와 같다! 시간복잡도를 고려하여 제한 시간내 성공 가능한 알고리즘이 문제의 정답이기 때문이다.
따라서 자료구조, 알고리즘의 시간복잡도는 반드시 알아야 한다.
✨ 해시 테이블
✨ 스택 & 큐
- 많이 사용되긴 하지만 단독으로 사용되는 경우보다 구현하는데 필요한 자료구조 정도로 사용되는 경우가 많다. 예) 스택 : DFS, 큐 : BFS
- 문제에서 선입선출, 후입선출의 단서가 보이면 사용하자!
- 예) 프로그래머스 - 다리를 지나는 트럭
- 다리는 먼저 들어간 차량이 먼저 나옴 -> 선입선출 -> 큐
- 반목문을 돌면서 다리가 버티는 무게를 계산하여 큐에 넣어주고 다 건넜으면 빼줌
✨ 힙
- 우선순위를 고려하는 문제에서 사용된다. 예) 작은 수부터, 큰 수부터
- 보통 Java의 경우
PriorityQueue
로 사용한다. (그렇다고 힙 == PQ는 아님)
PriorityQueue
의 경우 개선된 다익스트라의 구현에 사용된다.
- 예) 프로그래머스 - 더 맵게
- 스코빌 지수가 K이상이 될 때까지 반복문을 돌며 우선순위 큐에서 2개를 빼고 섞은 뒤 다시 넣음
✨ 구현
✨브루트 포스(완전탐색)
- 코딩테스트 필수 of 필수일 만큼 자주 출제되는 유형으로 완탐이라고 줄여 부르기도 한다.
- DFS, BFS, 백트래킹(완탐은 아니긴 하다)을 공부하자.
- 이름 그대로 모든 경우를 탐색해야 할 경우에 사용된다. (미로찾기 등)
- 무작정 모든 경우를 탐색하면 효율이 낮으므로, 시간 제한에서 실패하면 다른 풀이를 생각해보거나 문제 조건에 따라 탐색을 최소한으로 만들어야 한다.
- 예) 2020 KAKAO BLIND RECRUITMENT - 양궁대회
- 라이언이 쏠 수 있는 모든 경우의 수를 구하기 위해 DFS 사용하면 시간 초과가 뜸
- 어피치가 쏜 과녁 횟수의 + 1 이상이어야 라이언이 득점하므로 이 조건을 DFS에 추가하면 성공
✨ 다이나믹 프로그래밍
- 복잡한 문제를 한 번에 해결하는 것이 아닌, 조금씩 점차적으로 풀이하는 유형이다. (점화식을 떠올리면 이해하기 쉬움)
- 개인적으로 어려운 유형이라고 생각한다.
- 다른 유형도 그렇겠지만, 특히 DP는 여러 문제를 풀어보면서 감을 익혀보자.
- bottom-up, top-down 을 모두 공부하자. (필자는 bottom-up 접근이 편하다고 생각)
- 한 문제를 bottom-up, top-down 두 방법으로 각각 풀이해보는 것도 좋다.
- 예) 프로그래머스 - 정수 삼각형
- 산보다 나무를 본다는 마음으로 가장 작은 삼각형 부터 시작
- 가장 위부터 0번째 인덱스라고 하면 1번째 인덱스의 solution은 10, 15
- 마찬가지로 2번째 인덱스의 solution은 18, 16, 15
- 그 다음으로 3번째 인덱스는... 반복하다보면 점화식이 보임
✨ 그리디
- 부분적인 최적해가 전체적인 최적해가 되는 문제에서 사용한다.
- 어렵게 출제되면 풀이를 쉽게 떠올리기 힘드니, 문제를 많이 풀어보면서 풀이 방법을 기억하자.
- 정렬, 우선순위 큐를 활용하는 경우가 많다.
- 예) 프로그래머스 - 큰 수 만들기
- 숫자가 증가할 때 까지 제거하다 숫자가 내려가면 가장 큰 수 keep 을 k 개 제거할 때 까지 반복
✨ 이분 탐색
- 순차적인 배열 탐색으로는 시간 초과가 나는 문제에서 사용한다.
- 시간 복잡도 : O(logN)로 그냥 순회하는 O(N)보다 빠르다.
- 이분 탐색 + 다익스트라 등 다른 유형과 연계되는 문제가 출제될 수 있다.
- 예) 2019 카카오 개발자 겨울 인턴십 - 징검다리 건너기
- 건널 수 있는 친구의 수를 1부터 최대 200000까지 구하면 비 효율적
- 따라서 1~ 200000 중앙 값부터 모두 건널 수 있는지 이분 탐색 시작
- 건널 수 없으면 중앙 값에서 좌측 절반, 건널 수 있으면 중앙 값에서 우측 절반 이동
✨ 트리
- 트리의 경우 DFS를 활용한 전/중/후위 순회, 루트노드, 서브트리, 높이, 너비, 그래프에서 트리의 수 찾기 등 다양하게 출제할 수 있다.
- 따라서 트리를 활용한 다양한 문제의 유형을 풀어보는 것이 좋다.
- 바킹독 트리 문제집의 문제들을 풀어보는 것을 추천한다.
✨ 그래프
- 최단 경로를 구하는 문제가 많이 출제된다.
- 최단 경로를 구할 때는 다익스트라, 벨만-포드, BFS, 플로이드-워셜 알고리즘들을 사용하자.
- 그래프 순회에는 DFS / BFS를 사용하자.
- 추가로 학습하면 좋은 알고리즘으로는 위상정렬이 있다.
- 예) 2021 KAKAO BLIND RECRUITMENT - 합승 택시 요금
- 문제가 너무 길어서 사진만...
- S에서 함께 출발하거나 따로 택시 타서 A, B에 각각 내리면 됨
- 즉, 어떤 정점(자신 포함)으로 까지의 최단 거리 + 해당 정점에서 A 최단 거리 + 해당 정점에서 B 최단 거리 3가지를 합친 것의 최소를 구하면 됨
✨ 투 포인터, 슬라이딩 윈도우
- 배열에서 인덱스 2개를 사용해야 할때 평범하게 for 문 2번으로 풀이하면 시간 초과가 발생하는 경우 생각해볼 수 있다.
- 인덱스 2개를 while 문 한번으로 사용하면서 문제를 해결할 수 있다.
- 구간 합도 공부하자.
- 예) 백준 - 2230번 수 고르기
- 투 포인터를 사용해서 두 수의 차이가 주어진 값보다 작으면 포인터 이동
- 주어진 값보다 크거나 같으면 최소 값 갱신
✨ 유니온 파인드
- 최근 자주 기출되는 유형이다.
- 노드를 집합에 속하게 하는 Union 연산과 노드의 루트 노드를 찾는 Find 연산으로 이루어진다.
- 노드들을 루트 노드를 기준으로 하는 어떠한 집합으로 묶는다고 생각하면 이해하기 편하다.
- 예) 백준 - 1717번 집합의 표현
- 입력 값이 0인 경우 Union, 1일 경우 Find하여 루트 노드를 확인
✨ 최소 신장 트리
- 최소 신장 트리를 만드는데 필요한 비용을 구하는 유형이다.
- 자주 기출되지는 않지만, 사용되는 알고리즘이 어렵지 않으니 익혀두자.
- 크루스칼, 프림 알고리즘을 공부하자.
- 예) 백준 - 1368 물대기
- 우물을 하나의 노드라고 생각하고 MST 만드는 비용을 계산
✨ 비트마스킹
- 문제에서 0, 1로 표현할 수 있는 경우 비트마스크를 사용하여 효율적으로 풀이할 수 있다.
- 비트마스크를 사용하면 수행시간, 메모리에서 이점을 가진다.
- 비트 연산자를 사용하므로 AND, OR, XOR, NOT, Shift 를 공부하자.
- 예) 백준 - 11723 집합
- 비트를 해당 값의 유무(있으면 1, 없으면 0)로 사용하여 풀이
- 집합에 x를 추가하거나 있으면 무시하기 위해선
bitmask |= 0b1 << x
맛있게 보고갑니다~