구현

구현

 

구현은 특별한 알고리즘이 아닌 모든 알고리즘을 통틀어 구현이라고 한다.

 

보통 알고리즘 문제를 풀 때 아이디어는 알겠지만 구현을 하지 못해 풀지 못하는 경우가 상당하다.

 

이는 프로그래밍 언어 문법에 익숙하지 않은 탓이기 때문에 이 또한 그리디 처럼 자주, 많이 풀어보는 방법밖에 없다.

 

그럼에도 불구하고 문제들을 더 효율적으로 풀고 접근해야하는 방법은 정해져 있다.

 

지금부터 그것들을 알아볼 예정이다.

 

1. 메모리

-C나 C++에서는 int나 long long등을 통해 변수에 자료형을 붙여서 메모리를 할당해준다. 문제에서 요구하는 메모리를 보고 거기에 맞춰 변수를 지정하는 것이 중요하다. 

 

2. 파이썬에서의 리스트 크기

-파이썬은 다른 언어와 다르게 변수가 없다. 하지만 메모리 할당은 똑같이 이루어진다. 

보통 데이터의 개수 10,000,000개당 40MB를 할당하게 된다. 일반적으로 문제에서는 128~512MB를 요구하니 이에 맞춰 문제를 접근하기를 바란다.

 

3. 채점 환경

- 문제를 다 풀고 제출하면 시간 제한과 메모리 제한을 검사받게 된다. 이를 초과한다면 오답처리를 받는 것이다. 이것만 기억하자.  "1초에 2000만 번의 연산을 수행해야 한다"