[알고리즘] Implementation (구현) - (1)

Implementation (구현)

1. 피지컬로 승부하기

코딩 테스트에서 구현이란 머리속에 있는 알고리즘을 소스코드로 바꾸는 과정 을 뜻한다.

어떤 문제를 풀든 소스코드를 작성하는 과정이 필수이며, 구현 문제 유형은 모든 코딩 테스트 문제 유형을 포함하는 개념으로 볼 수 있다.

1) Problem - Thinking - Solution

흔히 구현 유형의 문제는 풀이를 떠올리는 것은 쉽지만 소스코드로 옮기기 어려운 문제 를 뜻한다.

생각해 낸 문제 풀이를 우리가 원하는 프로그래밍 언어로 정확히 구현해 내야하고, 이를 위해서는 프로그래밍 언어의 문법을 정확히 알고 있어야하고 문제의 요구사항에 어긋나지 않는 답안 코드를 실수없이 작성 해야 한다.

• 구현하기 어려운 문제

  • 알고리즘은 간단한데 코드가 지나칠 만큼 길어지는 문제
  • 특정 소수점까지 출력해야하는 문제
  • 문자열이 입력으로 주어졌을 때 한 문자 단위로 끊어서 리스트에 넣어야하는 (parsing) 문제
    등등
    => 사소한 조건 설정이 많은 경우 코드로 구현하기 까다로움

• 구현 유형에 속하는 알고리즘

  • 완전 탐색 : 모든 경우의 수를 주저 없이 다 계산하는 해결 방법
  • 시뮬레이션 : 문제에서 제시한 알고리즘을 한 단계씩 차례대로 직접 수행해야하는 문제 유형

코딩 테스트에서는 어떤 환경에서 문제를 풀어야 하는 지를 알고, 그 환경에 맞게 프로그래밍 언어를 적절히 사용하여 구현하는 일이 중요하다.

2. 구현 시 고려해야 할 메모리 제약 사항

1) C/C++에서 변수의 표현 범위

전통적으로 프로그래밍 언어에서 정수형을 표현할 때 int 자료형을 사용하고 크기는 4byte이다.

특히 C/C++, java 등의 언어를 사용할 때는 int 자료형을 자주 사용한다.

정수형 종류	자료형 크기	자료형의 범위
int	4 byte	-2,147,483,648 ~ 2,147,438,647
long long	8 byte	-9,223,372,036,854,775,808 ~ 9,223,372,036,854,775,807
BigInteger(클래스)	가변적	제한 없음

위 표를 보면 int 자료형의 범위는 -2,147,483,648 ~ 2,147,438,647 이다. 저 범위를 넘어가는 수를 표현하기 위해서는 long long 자료형을 사용한다.

그러면 long long 자료형으로 다룰 수 있는 범위를 넘어가는 경우는 어떻게 해야할까?

자바의 경우 BigInteger를 표준 라이브러리로 지원하지만, C++의 경우 표준 라이브러리에도 포함되어 있지 않아서 코딩 테스트를 치는 도중에 직접 작성하기는 어려워서 보통 검색을 통해 외부 라이브러리를 그대로 가져와 사용한다.

하지만 이는 검색과 외부 라이브러리를 허용하는 코테의 경우만이 가능한 방법이고, 보통 long long 자료형을 넘어가는 문제는 잘 출제하지 않는다.

2) python

파이썬의 경우, 프로그래머가 직접 자료형을 지정할 필요가 없고, 매우 큰 수의 연산 또한 기본적으로 지원한다.

그래서 파이썬을 사용하는 사람들의 경우 자료형의 표현 범위 제한은 깊게 이해할 필요가 없지만, 실수형 변수는 다른 언어와 마찬가지로 유효 숫자에 따라서 연산 결과가 원하는 값이 안나올 수 있다는 것을 기억해야한다.

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

파이썬에서 여러개의 변수를 사용할 때는 보통 리스트를 사용한다.

파이썬에서 리스트를 사용할 때 고려해야 할 사항은 바로 코테의 메모리 제한 이다.

대체로 코테에서는 128 ~ 512 MB로 메모리를 제한하는데 알고리즘 문제 중 때로는 수백만 개 이상의 데이터를 처리해야 하는 문제가 출제되고는 한다.

이런 경우에는 메모리 제한을 염두에 두고 코딩 을 해야 한다.

- int 자료형 데이터의 개수에 따른 메모리 사용량

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

파이썬에서는 정수 데이터를 사용할 때 int와 같은 별도의 자료형을 명시해 줄 필요가 없지만, 시스템 내부적으로는 위의 표에서 보여주는 것과 유사한 크기만큼 메모리를 차지하는 것을 기억하자.

따라서 크기가 1,000만 이상인 리스트의 경우 메모리 용량 제한으로 문제를 풀 수 없게 되는 경우도 있다.

하지만 이런 문제는 드문데, 메모리 제한 때문이 아닌 수천만 개 이상의 데이터를 입력해야 하면 입출력에 너무 많은 시간이 소요되며 채점 환경에서도 다양한 문제가 발생할 수도 있기 때문이다. ( 입출력 속도는 프로그래밍 언어마다 다르고, 입출력 속도를 빠르게 하기위한 테크닉들이 사용되면 모든 프로그래밍 언어에 대한 입출력 속도까지 고려하여 시간 제한을 설정해야해서 주최측이 힘들어져서)

=> 따라서 일반적인 코딩 테스트 수준에서는 메모리 사용량 제한보다 더 적은 크기의 메모리를 사용해야 한다는 점 정도만 기억하자

4. 채점 환경

문제에서 요구하는 메모리 제한과 실행 시간 제한은 코딩 테스트를 출제하는 기관마다, 문제마다 조금씩 다르다.

출제자가 매루 빠르게 동작하는 프로그램을 원하면 시간 제한은 더욱 짧을 것이고, 보통 코테 환경에서는 채점 시스템의 시간 제한 및 메모리 제한 정보가 적혀있을 것이다.

• 시간 제한 : 1초
• 메모리 제한 : 128MB

파이썬은 C/C++에 비해 동작 속도가 느려서 C/C++에 비해 2배의 수행 시간 제한을 적용하기도 한다.

2020년을 기준으로 python 3.7로 코드를 작성할 때, 자신이 작성한 코드가 1초에 2,000만 번의 연산을 수행한다고 가정하고 문제를 풀면 실행 시간 제한에 안정적이다.(사실 수행 시간을 정확히 측정하려면 채점 시스템의 컴퓨터 사양과 사용하는 알고리즘을 면밀히 분석해야하는데 일반적인 기업 코딩 테스트 환경에서는 그냥 파이썬으로 제출한 코드가 1초에 2,000만 번의 연산을 수행한다고 가정해도 무리가 없다.)

시간 제한이 1초이고, 데이터의 개수가 100만개인 문제가 있다면 일반적으로 시간 복잡도 O(NlogN) 이내의 알고리즘을 사용하여 문제를 풀여야한다.

실제로 N = 1,000,000 일 때, Nlog2(N)은 약 20,000,000이기 때문이다.

따라서 알고리즘 문제를 풀 때는 시간 제한과 데이터의 개수를 먼저 확인한 뒤에 이 문제를 어느 정도의 시간 복잡도의 알고리즘으로 작성해야 풀 수 있을 것인지 예측할 수 있어야 한다.

5. 구현 문제에 접근하는 방법

보통 구현 유형의 문제는 사소한 입력 조건 등을 문제에서 명시해주며 문제의 길이가 꽤 긴 편이다.

문제의 길이는 길지만, 고차원적인 사고력을 요구하는 문제는 나오지 않는 편이라 문법에 익숙하다면 오히려 쉽게 풀 수 있다.

구현 유형의 문제는 C/C++이나 JAVA를 사용할 때 더 어렵다고 한다.

문자열을 처리하거나 큰 정수를 처리하는 문제가 자주 출제되는데, C/C++과 JAVA에서는 문자열 처리가 파이썬에 비해 까다롭고, 큰 정수를 처리하는 라이브러리도 별도로 사용해야하기 때문이다.

반면에 파이썬은 기본 문법만 알아도 상대적으로 구현 유형의 문제를 쉽게 해결할 수 있다.

- 초보자 입장에서 파이썬과 C/C++ 비교

프로그래밍 언어	구현 난이도	프로그램 실행 시간
python	쉬운 편	긴 편
PyPy	쉬운 편	다소 짧은 편
C/C++	어려운 편	짧은 편

실무에서 파이썬을 사용하여 프로그램을 개발할 때는 GPU를 연동하고, 반복적인 행렬 계산을 요구하는 복잡한 수학 문제를 풀 때는 C언어로 작성된 파이썬 코어 소프트웨어가 동작하기 때문에, 파이썬을 사용하면 항상 프로그램의 동작 속도가 느린 것은 아니다. 하지만 코테 환경에서는 GPU를 쓰는 경우가 없기 때문에 그러한 사항은 고려하지 않는다.

PyPy3는 python3의 문법을 그대로 지원하며, 대부분 python3보다 실행 속도가 더 빠르다.

이 말은 코테에서 PyPy3를 선택하면 python3와 동일한 코드를 제출해서 실행 시간을 줄일 수 있다는 의미이다. (삼성 전자 공채에서는 지원자가 python3로 제출하면 기본적으로 PyPy3를 사용하여 채점한다.)

반복문이 많을 수록 PyPy3와 Python3의 속도차가 커지고, C/C++과 견줄만큼 빠르다.

대략 1초에 2,000만 번 ~ 1억 번 정도의 연산을 처리할 수 있다고 기억하자.

=> 코테 환경이 PyPy3도 지원하면 이를 이용하자!