Implementation (완전 탐색, 시뮬레이션)

Implementation

알고리즘 문제를 푼다는 것은, 내가 생각한 문제 해결 과정을 컴퓨팅 사고로 변환해 코드로 구현한다는 것과 같습니다. 

• 데이터를 정렬할 수 있는가?
• 데이터를 효율적으로 탐색할 수 있는가?
• 데이터를 조합할 수 있는가? ...etc

카테고리를 분류한다고 해도 내가 생각한 로직을 '코드로 구현'한다는 건 전부 공통적인 속성입니다. 이러한 문제 해결을 코드로 풀어낼 때, 정확하고 빠를 수록 구현 능력이 좋다고 말합니다.

구현 능력이 좋은 개발자를 선발할 의도로 구현 능력을 직접 평가하기도 합니다. 정해진 시간 안에 빠르게 문제를 해결하는 능력을 보기 위함입니다. 머리로 이해하고 있어도 코드로 작성하지 않거나 시간 부족으로 못한다면 정답이 될 수 없기 때문입니다. 본인이 선택한 프로그래밍 언어의 문법을 정확히 알고 있어야 하며, 문제의 조건에 전부 부합하는 코드를 실수 없이 빠르게 작성하는 것을 목표로 두는 것을 구현 문제, 구현 유형이라고 통칭할 수 있습니다.

 

보통 이러한 문제들은 구현하는 것 자체를 굉장히 까다롭게 만듭니다. 지문을 매우 길게 작성하거나, 까다로운 조건이나 상황을 붙인다거나, 로직은 쉽지만 구현하려는 코드가 굉장히 길어지게 되는 문제들이 대다수입니다. 그렇기 때문에 깊은 집중력과 끈기가 필요합니다.

 

구현 능력을 보는 대표적인 사례에는 완전 탐색(brute force)과 시뮬레이션(simulation)이 있습니다.

완전 탐색

모든 문제는 완전 탐색으로 풀 수 있습니다. 굉장히 단순하고 무식하지만 답이 무조건 있다는 강력함이 있습니다.

예를 들어, 양의 정수 1부터 100까지의 임의의 요소가 오름차순으로 하나씩 담긴 배열 중, 원하는 값 N을 찾기 위해서는 배열의 첫 요소부터 마지막 요소까지 전부 확인을 한다면 최대 100 번의 탐색 끝에 원하는 값을 찾을 수 있습니다.

그렇지만, 문제 해결을 할 때엔 기본적으로 두 가지 규칙이 붙습니다.

• 문제를 해결할 수 있는가?
• 효율적으로 동작하는가?

완전 탐색은 첫 번째 규칙을 만족시킬 수 있는 강력한 무기이지만 두 번째 규칙은 만족할 수 없는 경우가 있습니다

완전 탐색은 단순히 모든 경우의 수를 탐색하는 모든 경우를 통칭합니다.

완전히 탐색하는 방법에는 brute Force(조건/반복을 사용하여 해결), 재귀, 순열, DFS/BFS 등 여러 가지가 있습니다.

Brute Force (무차별 대입)

문제를 풀 때, 반복문이 아닌 배열을 전부 순회하는 메서드를 사용한다거나 간결한 코드를 위한 문법을 사용한다고 하더라도 배열을 전부 탐색하여 값을 도출한다는 것엔 변함이 없습니다.

시뮬레이션

시뮬레이션은 모든 과정과 조건이 제시되어, 그 과정을 거친 결과가 무엇인지 확인하는 유형입니다.

문제 해결을 떠올리는 것 자체는 쉬울 수 있으나 길고 자세하여 코드로 옮기는 작업이 까다로울 수 있습니다.

 

문제에 대한 이해를 바탕으로 제시하는 조건을 하나도 빠짐없이 처리해야 정답을 받을 수 있습니다.

하나라도 놓친다면 통과할 수 없게 되고, 길어진 코드 때문에 헷갈릴 수도 있으니 주의해야 합니다.