17. Basic Algorithms Intro

코딩 문제를 풀 때 사용되는 다양한 알고리즘을 배우기 위해서는 기본적인 문제 해결 방법에 대해 알아야 한다. 기본적인 문제 해결 방법으로 다음과 같은 것들을 생각할 수 있다.

 

• 구현(Implementation)은 문제에서 요구하는 것을 직접 실행하는 것이다. 보통 구현 문제라고 하면 코딩이 문제 해결의 대부분을 차지하는 문제를 의미한다.
• 완전 탐색(Brute Force)은 문제의 조건에 맞는 가능한 모든 경우를 다 확인하면서 답을 구하는 것이다. 입력의 범위가 작은 경우 이 방법으로 문제를 풀 수 있는 경우가 많이 존재한다.
• 시뮬레이션(Simulation)은 문제의 상황이 시간에 따라 변하는 경우 이 변화를 직접 구현해서 문제를 해결하는 데 이용하는 것이다. 구현의 한 종류로 볼 수도 있다.
• 그리디(Greedy)는 이후의 상황을 고려하지 않고 현재 상황에서 최선인 선택을 하는 방법이다. 이 방법이 모든 문제에서 최적해를 찾지는 못하지만, 일부 문제는 이런 방법으로도 풀 수 있다.
• 재귀(Recursion)는 재귀호출을 이용하여 문제를 해결하는 방법이다. 문제를 해결하는 데 점화식이 이용되는 경우 이 점화식을 재귀함수로 구현할 수 있는 경우가 많다.
• 퇴각 검색(Backtracking)은 제한된 조건을 가진 문제를 푸는 방법의 하나로 각각의 방법을 확인하면서 답이 될 수 없는 경우 이전 단계로 되돌아가는 방식으로 문제를 해결한다.
• 동적 계획법(Dynamic Programming)은 문제를 여러 개의 하위 문제로 나누어 각각의 하위 문제에 대한 답을 구하고 그것을 바탕으로 문제를 해결하는 방법이다. 이 방법은 메모이제이션(Memoization)을 바탕으로 하고 있는데, 이것은 계산 과정에서 같은 문제가 여러 번 등장할 경우 한 번만 계산해서 성능을 향상시키는 것이다.
• 분할 정복(Divide and Conquer)은 문제를 여러 개의 부분 문제로 나누어 각각의 부분 문제에 대한 답을 구하고 그것을 바탕으로 문제를 해결하는 방법이다.
• 비트마스킹(Bitmasks)은 비트 단위의 값을 자료 구조로 이용하거나 비트 연산 자체를 이용해서 문제를 해결하는 방법이다. 입력의 범위가 매우 작을 경우 이 방법을 이용해서 완전 탐색, 동적 계획법 등을 효율적으로 수행할 수 있다.

그밖의 기본적인 문제 해결 방법으로 주어진 데이터를 특정 기준에 따라 나열하는 정렬(Sorting)과 주어진 데이터에서 원하는 값을 찾는 탐색(Search)이 있다. (정렬과 탐색은 따로 분류했고 동적 계획법 역시 종류가 다양한 관계로 따로 분류했다.) 이런 방법들이 기본적인 것이긴 하지만 응용 범위가 굉장히 넓어서 매우 어려운 문제에도 이 방법들이 자주 사용된다. 카테고리 B에서는 위에서 제시한 $9$가지 문제 해결 방법을 차례로 살펴볼 것이다.