2. [Algorithm] 구현(시뮬레이션, 완전탐색)

구현

• 나의 생각을 소스코드로 바꾸는 과정이다.
• 코딩 테스트를 풀기 위해서는 소스코드를 작성하는 과정은 필수 → 구현 문제는 모든 범위의 코딩 테스트 문제 유형을 포함하는 개념.
• 생각해낸 문제 해결 방법을 내가 원하는 프로그래밍 언어로 정확히 구현했을 때 비로소 정답 처리를 받을 수 있다. 이를 위해서는 해당 언어의 문법과 문제의 요구사항을 정확히 알고있어야 한다.
• 완전 탐색(Brute Force), 시뮬레이션 유형을 모두 구현 유형으로 묶어서 다루고 있다.(이코테 도서)
  • 완전 탐색(Brute Force) : 모든 경우의 수를 주저 없이 다 계산하는 방법
  • 시뮬레이션 : 문제에서 제시한 알고리즘을 한 단계씩 차례대로 직접 수행하여 해결하는 방법

 

그렇다면, 어떠한 문제 유형이 구현하는데 까다로울까?

 

ex)

• 알고리즘은 간단하나 코드가 매우 길어지는 문제
• 특정 소수점까지 출력해야 하는 문제
• 문자열이 입력으로 주어졌을 때 한 문자 단위로 끊어서 리스트에 넣어서(파싱) 해결해야 하는 문제 

등이 있다.

 

구현 시 고려해야 할 메모리 제약

위 표를 제외한 더 큰수를 처리하려면 JAVA의 경우 BigInteger를 표준 라이브러리로 지원하지만, C++의 경우 표준 라이브러리에도 포함되어 있지 않다.

반면에 Python에서는 프로그래머가 자료형을 직접 지정할 필요가 없고 매우 큰 수의 연산 또한 기본으로 지원한다.(Python에서의 실수형 변수는 다른 언어와 마찬가지로 유효숫자에 따라서 연산 결과가 원하는 값이 나오지 않을 수 있다.)

 

---

 

대체로 코딩 테스트에서는 128 ~512MB로 메모리를 제한한다. 알고리즘 문제 중 때로는 수백만 개 이상의 데이터를 처리해야 하는 문제가 출제되곤 한다. → 이 경우 메모리 제한을 염두해두고 문제를 해결해야 한다.

데이터의 개수(리스트의 길이) || 메모리 사용량
1,000 (천) || 약 4KB
1,000,000 (백만) || 약 4MB
10,000.000 (천만) || 약 40MB

Python의 경우 다른 언어에 비해 구현상의 복잡함은 적지만 데이터 처리량이 많을 때는 꼭 메모리 제한을 고려해야 한다. (드물지만 리스트 크기가 1,000만 이상인 리스트는 메모리 제한으로 인해 문제를 풀 수 없는 경우가 있다.)

또한, Python은 C/C++에 비해 동작 속도가 느리다. 보통 일반적인 기업 코딩 테스트 환경에서는 Python으로 코드를 작성할 때 1초에 2,000만 번의 연산(O(N))을 수행한다고 가정하면 실행 시간 제한에 안정적이라고 보면 된다.