구현 (Implementation)

알고리즘 파트는 책 "이것이 취업을 위한 코딩테스트다 -나동빈" 책을 기반으로 제가 이해한부분을 정리하기 위해 작성되었습니다 .

 

구현  

코테에서 구현이란 '머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정'이다. 즉 어떤 문제든 소스코드를 작성하는 과정은 필수이므로 모든 문제가 구현 문제라고 볼 수 있다. 코딩 테스트에서는 시뮬레이션, 구현, 완전탐색 유형 등 서로 다르게 일컫는다. 

 

완전탐색

일명 브루트포스(brute force) 라고 불리는 방법으로 가능한 모든 경우의 수를 주저 없이 다 계산하여 해결하는 방법이다.  완전 탐색의 시간복잡도는 주로 O(N!), O(2^N)이다. 완전 탐색은 반복문을 이용하는 방법, 재귀 함수를 이용하는 방법이 있는데 보편적으로 사용되는 것은 재귀 함수라고 한다. 반복문의 경우 길이가 변하는 문제를 다룰때 구현이 복잡해진다는 단점이 있다. 초보자의 경우에는 재귀함수가 직관적으로 보이지 않을 수 있지만 경험이 쌓이다 보면 반복문보다 더 직관적으로 보인다고 한다.

 

시뮬레이션

문제에서 제시한 알고리즘을 한 단계씩 차례대로 직접 수행하는 문제 유형. 일련의 명령에 따라서 개체를 차례대로 이동시키는 것. 풀이를 떠올리는 것은 쉽지만 소스코드로 옮기기 어려운 문제이다.