[Algorithm] 구현 문제란?

학습 목표

· 구현 문제란?

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

· 채점 환경

· 구현 문제에 접근하는 방법

---

구현 문제란?

코딩 테스트에서 구현

· 머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정

 

구현 문제

·  풀이를 떠올리는 것은 쉽지만 소스코드로 옮기기 어려운 문제

   - 코딩 테스트에서는 구현이 중심이 되는 문제가 자주 출제된다.

   - ex) 완전 탐색, 시뮬레이션 유형

      ▶ 완전 탐색: 모든 경우의 수를 주저 없이 다 계산하는 해결 방법

      ▶ 시뮬레이션: 문제에서 제시한 알고리즘을 한 단계씩 차례대로 직접 수행해야 하는 문제 

 

구현하기 어려운 문제란?

1. 알고리즘은 간단한데 코드가 치나칠 만큼 길어지는 문제

2. 특정 소수점 자리까지 출력해야 하는 문제

3. 문자열이 입력으로 주어졌을 때 한 문자 단위로 끊어서 리스트에 파싱 해야 하는 문제

 

·  대체로 사소한 조건 설정이 많은 문제일수록 코드로 구현하기 까다롭다.

 

구현 문제를 풀기 위한 선행 조건

1. 프로그래밍 문법의 정확한 숙지

2. 라이브러리 사용 경험

 

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

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

·  전통적으로 프로그래밍 언어에서 정수형을 표현할 때는 int 자료형을 주로 사용하며, 이 자료형의 크기는 4바이트

·  기본 int 자료형의 표현 범위: -2,147,483,648 ~ 2,147,438,647

 

기본 int 자료형 보다 큰 범위를 표현하는 방법

· 크기가 8바이트 long long과 같은 자료형을 사용

   - -9,224,372,036,854,775,808 ~ 9,224,372,036,854,775,807(약 92경)까지 표현 가능

· 이 보다 큰 수를 처리하려면 자료형 범위의 제현이 없는 BigInteger클래스(표준 라이브러리)를 구현하거나 이용한다.

 

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

   - 따라서 파이썬을 이용하면, 표현 범위 제한에 대해 깊게 이해하지 않아도 된다. 

   - 단, 실수형 변수는 다른 언어와 마찬가지로 유효숫자에 따라 연산 결과가 원하는 값이 나오지 않을 수 있다.

 

파이썬에서 리스트 크기

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

· 파이썬에서 리스트를 이용할 때는 코딩 테스트의 메모리 제한과 입출력 속도를 고려해야한다. 

   - 리스트를 잘못 사용하면 메모리 제한과 입출력 속도(시간 제한)로 인해 채점 환경에서 문제가 발생할 수 있다.  

   - 대체로 코딩 테스트에서는 128 ~ 512MB로 메모리를 제한하며, 수백만 개 이상의 데이터를 처리해야 하는 문제가 출제될 수 있다.

 

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

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

 

 

채점 환경

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

· 일반적인 코딩 테스트 환경에는 다음과 같은 채점 시스템의 시간 제한 및 메모리 제한 정보가 적혀 있다.

 

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

 

· 파이썬은 C/C++에 비해 동작 속도가 느리므로, 파이썬을 선택했을 때 C/C++에 비해 2배의 수행 시간 제한을 적용하기도 한다.

· 2020년 기준 파이썬 3.7로 코드를 작성할 때, 코드가 1초에 2,000만 번 연산을 수행한다고 가정하고 문제를 풀면

  실행 시간 제한에 안정적이다.

 

· 시간 제한이 1초이고, 데이터의 개수가 100만 개인 문제가 있다면 일반적으로

  시간 복잡도는 O(NlogN) 이내의 알고리즘을 이용하여 문제를 풀어야 한다.

   - N = 1,000,00일 때 Nlog₂N은 약 20,000,000이기 때문이다.

   - 즉,  알고리즘 문제를 풀때 시간 제한과 데이터의 개수를 먼저 확인한 뒤 이 문제를

     어느 정도의 시간 복잡도의 알고리즘으로 작성해야 풀 수 있을 것인지 예측할 수 있어야 한다.

 

구현 문제에 접근하는 방법

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

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

 

·  C/C++/Java에서 구현 유형 문제가 더 어렵게 다가온다.

   - 문자열을 처리하거나 큰 정수를 처리하는 문제가 출제되는 경우가 많은데 C/C++/JAVA에서는

     문자열 처리가 파이썬에 비하여 까다롭고, 큰 정수를 처리하는 라이브러리를 별도로 사용하기 때문이다.

   - 자신만의 코드 노트를 잘 활용하여 이를 보완할 수 있다.