코딩 테스트 준비 전 모르면 큰일나는 알고리즘 문제 유형 파악 및 꿀팁 정리

들어가기에 앞서

필요성: 나는 과연 효율적으로 공부하는 사람일까?

어떤 시험을 준비한다면, 상위권 성적을 얻기 위해 가장 중요하고 기본적인 것은 시험 문제 유형 분류와 파악이라고 생각한다. 얼마나 많은 유형을 커버할 수 있는지에 따라 최상위권이 될 수도 있다. 이 본질에 충실하다면 결국 시간을 갈아넣을수록 유리해지는 것이 당연하다고 볼 수 있다.

(1) 시험에 출제되는 문제들의 유형을 분류해둔다.
(2) 각 문제 유형의 풀이법을 파악하고 연습해둔다.
(3) 문제가 주어졌을 때 어떤 유형인지 빠르게 파악한다.

그런데, 필자의 학창시절에는 책상에 앉아있는 시간이 필자보다 더욱 길지만 성적이 잘 나오지 않는 친구들이 많았다. 위 세 가지를 수행하는 개개인의 역량 차이라고 생각할 수도 있다. 하지만, 필자가 과외를 통해 다양한 학생들과 얘기해본 결과, 놀랍게도 중하위권의 친구들은 애초에 위의 과정 중 (1)과 (3)이 부족한 경우가 많았다. 교과서나 문제집에서 단원 별로 나눠진 내용을 통해 (1)이 자연스럽게 달성됨에도 불구하고, 학생들에게 책을 덮고 시험에 나올 수 있는 유형들을 나열해보라고 하면 대답을 못하는 경우가 태반이었다. 또한, 각 단원에 예제로 나와있는 문제들은 잘 풀지만, 시험지에 나와있는 유사한 문제는 잘 풀지 못하는 경우가 많았다. 시험지에서는 문제가 어떤 유형인지 알려주지 않기 때문이다.

공부를 효율적으로 하지 못하는 사람들은 개념서나 문제집의 문제들을 무작정 풀면서 (2)만 연습하는 꼴이라고 할 수 있다. 개념서나 문제집의 문제들은 (1)과 (3)이 이미 되어있는 상태로 나오기 때문에, (1)과 (3)을 연습할 수 있는 기회를 놓치기 쉽다.

그래서, "실전" 문제들을 풀어야 한다는 말이 나오는 것 같다. 시험이라는 것은 주어진 문제의 풀이법을 익히는 것, 즉, (2)의 능력 뿐만 아니라, 주어진 문제가 어떤 유형인지 파악하는 (3)의 능력과 최대한 많은 유형들을 숙지해두는 (1)의 능력을 종합적으로 보는 무대인 것이다.

코딩 테스트도 마찬가지다. 보통 개발자로의 취업이나 이직 준비를 위해 LeetCode같은 사이트에서 유형 별로 정리된 문제들을 무작정 푸는 것은 (2)의 능력만 키우는 것이라고 볼 수 있다. 잠시 "아묻따" 문제풀이를 멈추자. 차분히 앉아서 문제 유형들을 나열해보고, 문제가 어떤 유형인지 파악하는 방법을 먼저 숙지할 필요가 있다.

대상 독자

필자는 알고리즘 대회에 출전해본 경험도 없고, 평소에 알고리즘을 꾸준히 공부한다거나 주기적으로 알고리즘 문제를 풀지도 않는다. 코딩 테스트를 준비하기 위한 시간 투자를 최소화하고 있다. 사실 실제 개발 활동을 하다보면 코딩 테스트에 필요한 지식들이 실무와 직접적으로 연관되는 경우가 많지는 않다고 생각하기 때문이다.

그럼에도 웬만한 IT회사들의 코딩 테스트에서는 자신감을 잃지 않고 있다. 코테 단계에서 탈락의 고배를 마셨던 경험은 많이 없는 것 같다. 필자가 알고리즘 문제풀이를 잘하는 사람일까? 그것은 확실히 아니라고 말할 수 있다. 아마 알고리즘 대회에 출전하면 예선에서 광탈할 것이 뻔하다.

알고리즘 대회에 출전하거나 알고리즘 자체에 흥미를 느껴서 깊이있게 탐구하고자 하는 것이 아니라면, IT회사 입사를 위한 코딩 테스트는 "효율적"으로 공부하는 것만으로도 충분하다는 것을 말하고 싶다. 따라서, 이 글은 개발자 취업이나 이직을 준비하는 단계에서 코딩 테스트를 위해 (2)를 멈추고 최소한의 시간을 들여서 (1)과 (3)을 훑어보고싶은 사람들에게 바치는 글이다.

이 글의 목적

이 글의 목적은 문제 풀이 방법보다는 짧은 기간 내에 코딩 테스트 준비를 효율적으로 할 수 있도록 가이드를 제공하는 것이다. 대략 어떤 문제들이 나오는지 빠르게 훑어보고, 상대적으로 중요하지 않은 것과 중요한 것을 가려내는 벼락치기 쪽집게에 가깝다.

중요한 유형의 문제들이 무엇인지 범위를 좁힌 뒤에, 시험에 출제된 문제들이 해당 유형의 문제가 맞는지 판별하는 방법에 대해 알아보자. 그리고, 문제 풀이에 사용되는 기본적인 접근 방법에 대한 아이디어와 팁들도 일부 다루어보겠다.

코딩 테스트 문제 대분류

코딩 테스트 문제 종류

코딩 테스트에 출제되는 문제들을 먼저 대분류로 나눠보면 다음과 같이 대략 세 가지라고 볼 수 있다. 공식적인 것은 아니고 편의를 위해 필자가 임의로 나눈 것이다. 각 유형끼리는 서로 그레이존이 존재하기 때문에 모든 유형을 엄격하게 구분하여 학습할 필요는 없다.

• 자료구조 문제
• 알고리즘 문제 (이 글의 타겟)
• 기타 문제

자료구조 문제 유형

자료구조 문제는 특정 자료구조에 대한 지식을 묻는 문제이다. Stack, queue, tree, heap, graph, hash map 등 다양한 자료구조에 대한 이해를 바탕으로 해당 자료구조를 직접 구현하거나 활용해서 문제를 해결하는 유형이다. 경험상 자료구조를 직접 구현하는 문제는 만나기 어렵다. 물론, 유니온 파인드처럼 직접 자료구조를 구현해야 하는 경우도 있지만, 보통 프로그래밍 언어에서 기본적으로 제공하는 자료구조들에 대한 이해가 있다면 어렵지 않게 풀 수 있는 문제들이 대부분이다. 이 "자료구조 문제"에 해당하는 유형은 다른 글에서 자세히 다루도록 하겠다.

알고리즘 문제 유형

알고리즘 문제는 보통 "문제 해결 패러다임 네 가지"라고 알려져 있는 유형의 문제이다. 코딩 테스트의 꽃이라고 할 수 있을 정도로 무조건 출제되는 유형이다. 알고리즘 문제의 대표라고 할 수 있는 동적 계획법(다이나믹 프로그래밍)도 이 유형에 속한다. DFS, BFS, 백트래킹, 탐욕법, 분할 정복, binary search, DP 등 익숙한 이름들이 많이 등장한다. 복잡한 문제의 조건에 비해 비교적 코드는 간결한 경우가 많아서 출제하기에 가장 편한 유형이기도 하다. 다시 말해서, 문제 유형 파악 방법 숙지만으로도 가장 큰 이득을 볼 수 있는 영역이다. 뒤에서 중점적으로 다루겠다.

기타 문제 유형

기타 문제에는 단순한 문자열 처리나, 최소공배수와 최대공약수 등 기본적인 수학적 지식에 대해 묻는 문제, 그리고 앞선 유형들에 해당하지 않는 "창의적인 문제"들이 속한다. 알고리즘 대회가 아닌 이상 단순 문자열 처리 외에는 잘 등장하지 않는 것 같다. 이 글에서는 다루지 않겠다.

예상 출제 범위

코딩 테스트에 3문제 정도가 나온다면 가장 쉬운 문제는 보통 "기타 문제" 유형에 해당하는 간단한 문자열 처리 정도가 나온다. 그리고 중간 난이도나 가장 어려운 문제로 "알고리즘 문제" 유형에 해당하는 문제들이 출제되는 경우가 많은 듯 하다. 가끔 "자료구조 문제" 유형 중에서도 가장 까다로운 그래프 관련 문제가 가장 어려운 문제로 출제되기도 하지만, 아직까지 만나본 경험은 없다. 보통 그래프 문제들은 사람 이름이 붙은 복잡한 알고리즘들에 대한 지식이 필요한 경우가 많다. 비전공자들을 공평(?)하게 배려하는 차원에서 출제가 잘 안되는 것이 아닐까 예상해본다.

그래프 문제가 출제되더라도 대부분 최단 경로 탐색이나 MST 등 간단한 문제들만 나오는 것 같다. 이 문제들은 "알고리즘 문제" 유형에서 등장하는 DP, 탐욕법으로도 충분히 커버가 되기 때문에 그래프 유형 자체에 대해 깊게 탐구하기 위해 시간을 투자할 필요까지는 없다고 생각한다. 조금 더 냉정하게 얘기한다면, 복잡한 그래프 문제가 나왔을 때 그냥 다른 문제를 다 풀고 남은 시간에 풀이에 도전해보거나 깔끔하게 포기하면 된다.

알고리즘 문제 중분류

문제 해결 패러다임 종류

문제 해결 패러다임에는 다음과 같이 네 가지 유형이 있다.

• 완전 탐색: BFS, DFS, backtracking
• 분할 정복: binary search
• 탐욕법: greedy search
• 동적 계획법: N차원 DP

각 유형에는 어떤 문제들이 포함되는지 살펴보고, 문제 해결을 위한 팁들을 알아보자.

완전 탐색

완전 탐색(complete search)은 보통 brute force라고 불리는 "무식한" 방법을 뜻한다. 코딩 테스트에서 가장 쉬운 난이도인 첫 문제로 등장하는 경우가 많다. 보통 이중, 삼중 루프를 돌거나 재귀 함수를 통해 자료구조의 모든 (또는 일부) 요소들을 탐색하는 작업을 구현하면 된다. 경우에 따라서는 stack이나 queue를 활용하여 DFS와 BFS를 구현해야 하는 경우도 있다.

보통 특수한 조건없이 완전 탐색 코드를 요구하는 경우는 쉬운 난이도 문제에 해당한다. 출제 의도는 프로그래밍 언어를 기초 수준 정도는 쓸 수 있는지 검증하기 위함이라고 할 수 있다. 또는 stack이나 queue를 활용하여 BFS와 DFS를 구현할 수 있는지 검증하기 위함이다.

탐색에서 특수한 제약조건, 즉, 일명 "가지치기"를 요구한다면 중간 난이도 이상의 문제가 되기도 한다. 특정 시점 및 조건에서는 방문할 수 없는 지점이 있다는 조건이 있는 경우 적절한 조건문을 통해 가지치기를 해야 한다. 이 과정에서 이미 방문했던 요소는 다시 방문하지 않도록 마킹해두거나 방문을 취소하는 작업도 필요하기 때문에 코드가 복잡해질 수 있다. 가지치기로 인해 막힌 지점은 더이상 진행하지 않고, 다시 이전으로 돌아가서 다른 지점으로 나아가야 한다.

보통 이런 과정을 재귀적 퇴각 검색(recursive backtracking), 또는 단순히 백트래킹이라고 부른다. 말이 어렵지만, 결국 DFS를 조건문과 함께 잘 짜라는 소리이다. 문제풀이를 위한 코드를 작성할 때는 다음과 같은 팁을 기억하고 있으면 뼈가 되고 살이 된다.

• BFS는 queue와 루프로 구현한다.
• DFS는 재귀 함수로 구현한다. (Stack X)

구현할 때 루프를 사용할지 재귀 함수를 사용할지 고민될 때는 다음을 고려해보면 좋다. 먼저, 루프를 사용하면 좋은 경우는 다음과 같다.

• 방문을 위한 상태를 인덱스를 포함한 점화식으로 간단하게 정의할 수 있는 경우
• 거의 모든 상태를 확인해봐야 하는 경우
• 모든 순열을 생성해야 하는 경우

반대로, 재귀 함수를 사용하면 좋은 경우는 다음과 같다.

• 상태를 인덱스를 포함한 점화식으로 도출하는 것이 어려운 경우
• 탐색 공간의 상태를 많이 가지치기해야 하는 경우
• 특정 시점에 방문할 수 없다는 제약조건이 있는 경우

완전 탐색 문제의 경우, brute force에 가깝기 때문에 자칫 잘못하면 탐색 공간이 너무 커서 TLE 판정을 겪는 경우가 많다. 완전 탐색 문제인 것은 분명하지만 아무리 생각해도 탐색 공간이 너무 큰 것 같다면 추가적으로 창의적인 사고를 통해 해결해야 한다. 대부분의 경우 두 가지 기법 중 하나를 적용하면 탐색 공간이 급격히 줄어들어서 난이도가 쉬워지는 경험을 할 수 있다.

• 대칭성 활용하기
• 거꾸로 생각하기

이는 문제마다 특수한 영역이기 때문에 글을 통해 정확히 설명하기는 어렵다. 예를 들자면, 대칭성 활용하기는 2차원 행렬에서 대각선의 원소에 대칭성이 발견되는 경우 탐색을 skip하는 것이다. 그리고 거꾸로 생각한다는 것은 문제에서 "탐색의 대상"이라고 설명하는 것에 매몰되지 않고, 문제에 숨겨진 다른 대상을 탐색해보는 것을 뜻한다. 이는 창의력과 관련된 부분이라서 미리 대비하는 것이 매우 어렵다. 많은 문제를 경험해보거나, 자신의 창의력을 믿거나, 아니면 깔끔하게 포기하거나 셋 중 하나다! 다행인 것은 제한 시간이 다소 짧은 코딩 테스트에서 이러한 창의력을 요구하는 문제는 잘 나오지 않는다는 것이다. 틀리더라도 합격에는 문제 없을 것이다!

분할 정복

분할 정복(divide and conquer)은 문제를 작은 단위로 쪼개어 단순한 문제로 만든 후 단순한 문제의 답들을 모아 최종 답을 내놓는 풀이 방식이다. 부분 문제들이 서로 독립적이어야 분할 정복 유형에 해당한다. 쉽게 말해서, 쪼개진 부분 문제를 이미 풀었다면 해당 부분은 더이상 다시 확인해보지 않고 다른 부분 문제만 풀어도 무방해야 한다는 것이다. 만약 "부분 문제의 독립"이 성립되지 않는다면, 뒤에서 살펴볼 DP 문제에 해당할 수도 있다.

분할 정복 접근 방식의 대표적인 예시는 머지 소트와 이진 탐색이 있다. 보통 머지 소트를 직접 구현하는 문제는 출제되지 않기 때문에, 사실상 분할 정복 유형의 문제는 대부분 이진 탐색을 적용하는 문제라고 볼 수 있다. 실제로, Steven Halim과 Felix Halim의 저서 <알고리즘 트레이닝>에서도 다음과 같이 언급하고 있다.

우리는 이진 탐색의 범주에 속하지 않는 분할 정복 문제가 얼마 없음을 알 수 있었다.

특히, 주어진 자료구조 내에서 무언가를 "탐색"하라는 문제가 나온다면 십중팔구 binary search 문제일 가능성이 높다. 잠시 정렬된 배열에 대한 탐색 방법 별 시간복잡도를 상기해보자.

- 완전 탐색: O(N)
- 이진 탐색: O(logN)
- 해시: O(1)

이진 탐색을 적용하려면 정렬이 되어있어야 하기 때문에 최대 O(NlogN)의 시간복잡도일 수도 있다. 이는 정렬이 필요없는 완전 탐색에 비해 느리다. 그런데, 만약 문제가 동일한 자료구조에 대해 여러 번의 탐색을 요구하는 경우에는 위와 같은 시간복잡도가 성립되기 때문에 이진 탐색이 훨씬 유리하다. 해시를 사용해야 하는 문제의 경우 사실 python의 dict같은 빌트인 자료구조를 사용하면 허무하게 해결되기 때문에, 따로 시간을 내어 준비할 필요도 없으며 출제되는 경우도 거의 없다고 보면 된다. 따라서, 탐색 문제에 대해서는 이진 탐색부터 시도해보는 습관을 갖는 것도 좋다. 이진 탐색 구현에 대해서는 이 글을 읽어보는 것을 추천한다.

탐욕법

탐욕법(greedy search)은 전체 탐색공간의 지역적인 최적해가 전역 최적해에 포함되는 경우에 적용할 수 있는 풀이 방식이다. 이를 어려운 말로 "최적 부분 구조"를 갖춰야 한다고 표현한다. 쉽게 말하면, 알고리즘의 특정 단계에서 배열의 일부분에 해당하는 정답이라고 생각하는 값을 찾았을 때 해당 답을 의심하지 않아도 된다는 뜻이다. 이후 단계에서 이전에 미리 찾아둔 답이 정말 맞는지 다시 검증할 필요가 없는 것이다.

문제에서 "최적값"을 찾으라는 신호가 있다면 탐욕법 문제 후보이다. 그런데, 보통 이 탐욕법을 적용할 수 있는 문제는 많지 않다. 탐욕법이 적용 가능한지 판단하려면 최적 부분 구조의 유무를 증명할 수 있어야 하는데, 코딩 테스트에서 주어지는 짧은 시간 동안 이를 증명해내는 것은 매우 어렵다. <알고리즘 트레이닝>에서도 다음과 같이 설명하고 있다.

탐욕적 풀이를 찾아내는 것은 일종의 예술이며, 이는 완전 탐색 풀이를 찾아내기 위해서 창의력이 필요한 것과 마찬가지이다.

따라서, 코딩 테스트에서는 보통 다음의 탐욕법의 두 가지 고전적인 문제 외에는 만날 확률이 없다고 생각하면 된다. 창의적인 탐욕법 문제가 나왔다면 깔끔하게 포기하자. 사실, 해당 문제가 탐욕법 문제였는지도 모르고 시험이 끝나는 경우가 대부분이겠지만 말이다.

• 균형 맞추기 문제
• 구간 덮기 문제

이 "고전적인 탐욕법 문제"를 판별하는 방법은 무엇일까? 문제에서 풍기는 냄새가 있다. 우선 크기나 양이 다른 재료들이 등장한다. 예를 들어, 금액이 다른 동전이나, 범위가 다른 폭탄이나, 양이 다른 용액 등이 나온다. 이때, 각 재료를 특정 위치에 배치하였을 때의 "불균형을 최소화"해야 한다면 균형 맞추기 문제가 된다. 만약 재료들을 사용하여 특정 값이나 범위를 채우기 위해 필요한 재료의 "최소 개수"에 대해 묻는다면 구간 덮기 문제에 해당한다.

그런데, 앞서 언급했듯이 주어진 문제가 탐욕법 문제가 맞는지 판단하는 것은 어렵다. 고전적인 문제의 경우에도 문제의 제약조건에 따라 완전 탐색이나 DP 문제가 되기도 한다. 따라서, 탐욕법 풀이를 고민하는 것은 가장 후순위로 낮추는 것을 권장한다. 우선 완전 탐색이나 DP를 고려해봤을 때 충분히 주어진 시간 내에 해결된다면 탐욕법을 적용할 필요가 없다. 탐욕법은 최후의 보루로 남겨두자. 탐욕법을 고민하는 단계까지 왔지만 풀이가 떠오르지 않는다면 어쩔 수 없다!

동적 계획법

동적 계획법(dynamic programming)은 최적화 문제나 경우의 수 문제를 풀 때 사용되는 기법이다. 복잡하고 어려운 문제 설명에 비해 풀이 코드는 몇 줄 안되는 경우가 많아서 코딩 테스트에서 가장 높은 확률로 출제된다. 따라서, DP 문제임을 판별하는 방법을 반드시 숙지해둬야 한다.

문제에서 "제한된 자원"이라는 constraint가 등장하고, 어떤 값을 "최소화" 또는 "최대화"하라는 주문이 있거나 특정 조건을 만족하는 "경우의 수"를 구하라는 요구사항이 있다면 높은 확률로 DP 문제다. 대부분의 경우 최적해를 요구하지 않고 최적값 또는 경우의 수까지만 요구한다. 다시 말해서, "~를 만족하는 최소값을 구하라"가 보통이지, "~를 만족하는 최소값과 그 때의 재료의 구성을 출력하라"고까지 요구하지는 않는다는 뜻이다.

DP 문제 풀이를 적용하려면 "최적 부분 구조", "중복되는 부분 문제"라는 두 가지 조건이 필요하다. 예를 들어, 제한된 예산이 M일 때 특정 재료를 선택하여 발생한 비용을 price[i]라고 해보자. 그렇다면 i 번째 재료를 한 개 선택한 상태는 남아있는 예산인 M-price[i]에서 다시 동일한 문제를 푸는 것이라고 처리할 수 있어야 한다. 해당 상태의 값은 한 번 계산해두고 다른 상태의 답을 구할 때 반복 계산 없이 재활용이 가능해야 한다.

쉬운 DP 문제들은 상태의 차원이 1차원 또는 2차원이며 최적값만을 요구한다. 어려운 DP 문제들은 상태의 차원이 3차원 이상이거나 최적값과 더불어 최적해까지 요구한다. 최적해까지 구해야 한다면 매번 최적값을 구하는 과정을 기록해두고 백트래킹을 통해 답을 재구성하는 과정이 추가로 구현되어야 한다.

DP는 문제에 숨겨진 "상태"와 "전이"를 빠르게 파악하는 것이 관건이라고 할 수 있다. 쉽게 말해서, 문제를 DAG 형태로 만들면 끝이다! 각 노드가 상태를 나타내고, 각 노드를 이어주는 간선이 상태 전이를 나타내는 그래프 말이다.

상태와 전이는 인덱스를 포함한 간단한 점화식으로 표현이 가능해야 한다. 예를 들어, 다음의 점화식을 살펴보자. 상태의 차원은 1차원이며, 특정 상태는 한 단계 이전의 상태와 두 단계 이전의 상태를 활용하여 정의된다. 익숙한 피보나치 수열의 점화식이다.

S(i) = S(i - 1) + S(i - 2)

사실 피보나치 수열처럼 1차원의 상태만으로도 해결되는 문제는 거의 나오지 않는 것 같다. 최소한 2차원 이상의 상태를 정의하는 경우가 대부분이다. 경험적으로 상태를 정의할 때는 보통 "남은 예산"과 "선택지"를 포함하여 2차원으로 구성하는 것이 일반적인 틀이라고 생각한다. 문제를 읽고 상태를 빠르게 정의하는 것이 익숙하지 않다면 우선 이 방식대로 상태를 정의해두고 생각을 시작하는 것이 편하다. 다음과 같은 과정을 통해 DP 문제를 간단하게 구현할 수 있다. 흔히 bottom-up 방식이라고 알려져 있는 구현 방식이다. 이 정도는 기억해두면 좋을 것이다.

• N차원 상태 정의 (남은 예산, 선택지를 상태에 포함)
• Base line 구해두기
• N중 루프 안에 점화식 구현하기 (+ 선택 내역 기록)

앞서 언급했듯이 만약 문제에서 최적해까지 요구한다면, N중 루프 내에서 특정 상태를 업데이트할 때 해당 단계에서 선택되는 재료를 별도의 "선택된 자들의 배열"에 저장해두면 된다. 루프가 종료된 뒤에, 정답에 해당하는 최종 상태부터 시작하여 최초의 상태에 이르기까지 "선택된 자들의 배열"을 역추적하며 최적해를 재구성하는 코드를 추가하면 끝이다.

알고리즘 문제 풀이에 어느정도 감각이 있는 사람이라면, 급한 경우 이러한 기본적인 아이디어만 알아두고 시험에 임해도 충분하다고 생각한다. 만약 좀 더 큰 자신감을 얻은 상태로 코딩 테스트에 응시하고 싶다면 잘 알려진 DP의 고전적인 문제 유형들에 대해 알아두면 좋다. 모두 다루기에는 분량이 방대해지므로, 각 문제에 대한 설명과 해설은 다른 글에서 자세히 소개하도록 하겠다. 필자는 다음 10가지 유형의 문제의 상태 정의를 거의 암기하다시피 숙지하고 있다.

• 가성비 옷 선택 문제
• 1차원 최대 구간합 문제 (1D-RSQ)
• 2차원 최대 구간합 문제 (2D-RSQ)
• 최대 증가 부분 수열 문제 (LIS)
• 0-1 배낭 문제 (부분집합의 합)
• 동전 교환 최적화 문제
• 동전 교환 경우의 수 문제
• 여행하는 외판원 문제
• 막대기 자르기 문제
• K개의 자연수의 합으로 N을 만드는 경우의 수

사실 DP를 구현하는 방식에는 top-down 방식과 bottom-up 방식이 있다. 두 구현 방식의 장단점이 존재하지만, 앞선 설명에서는 bottom-up 방식만 언급했다. 보통 코딩 테스트에서는 DP 문제를 해결하는 것 자체가 목적이지, 구현 방식에 따라 정답 유무가 갈릴 정도의 최적화를 요구하진 않기 때문이다. 실수를 줄이기 위해 두 방식 중 하나를 패턴화하여 익숙해지는 연습을 하자.

마찬가지로, bottom-up 방식 자체도 배열의 크기를 줄여서 공간복잡도를 줄이는 기법 등 최적화 트릭들이 존재하지만, 코딩 테스트에서는 공간복잡도까지 섬세하게 요구하진 않는다. 문제가 주어졌을 때 DP 문제임을 파악하고 빠르게 상태와 전이를 도출해내는 연습에 집중하자!

결론 요약

• 자료구조 문제나 기타 문제는 보통 쉽게 나온다. 어렵게 나왔다면 다음을 기약하자.
• 알고리즘 문제에 해당하는 문제들은 대부분 완전 탐색이나 DP 문제인 경우가 많다.
• 완전 탐색이나 DP로 풀리지 않는 경우에만 탐욕법 적용을 고려해보자.
• 분할 정복은 이진 탐색 문제가 대부분이다.
• 준비 기간이 부족하다면 DP를 중점적으로 연습해야 한다.
• DP는 상태와 전이를 빠르게 정의하는 능력이 핵심이다.
• 재능이 없다면 고전적인 DP 문제 유형들 정도는 숙지하고 시험에 응하자.