[CH4 구현] 아이디어를 코드로 바꾸는 구현 1

머릿속에 있는 알고리즘을 정확하고 빠르게 프로그램으로 작성하기

---

피지컬로 승부하기

• 코딩 테스트에서 구현(Implementation)이란 '머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정'이다

• 

  귀여워,,//

• 흔히 문제 해결 분야에서 구현 유형의 문제는 '풀이를 떠올리는 것은 쉽지만 소스코드로 옮기기 어려운 문제'를 의미한다
• 흔히 개발할 때 프로그래밍 언어의 문법에 능숙하고 코드 작성 속도(타자 속도)가 빠른 사람을 보고 '피지컬이 좋다'고 하는데 이런 의미에서 구현 유형은 '피지컬을 요구하는 문제'라고 할 수 있겠다
• 구현하기 어려운 문제는 아래와 같다
  1. 알고리즘은 간단한데 코드가 지나칠 만큼 길어지는 문제
  2. 특정 소수점 자리까지 출력해야 하는 문제
  3. 문자열이 입력으로 주어졌을 때 한 문자 단위로 끊어서 리스트에 넣어야 하는(파싱을 해야하는) 문제
• 피지컬이 좋아지려면 언어의 문법을 잘 이해하고 경험이 있어야만 바로 떠올릴 수 있게 된다!
• 여기서는 완전 탐색, 시뮬레이션 유형을 모두 '구현' 유형으로 묶어서 다루고 있다
• 완전 탐색은 모든 경우의 수를 주저 없이 다 계산하는 해결 방법을 의미하고, 시뮬레이션은 문제에서 제시한 알고리즘을 한 단계씩 차례대로 직접 수행해야 하는 문제 유형을 의미한다
• 코테에서는 어떤 환경에서 문제를 풀어야 하는지르 ㄹ알고 그 환경에 맞게 프로그래밍 언어를 적절히 사용하여 구현하는 일이 중요하므로, 먼저 코테 채점 시스템의 제약에 대해 알아보자

---

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

 

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

• C/C++에서는 정수는 주로 int를 사용하며, 이보다 큰 수를 다룰 때는 long long을 사용한다
• 만약 이보다 더 큰 수를 쓴다면 외부 라이브러리 BigInteger를 사용하는데, 이는 코테에서는 거의 사용되지 않는다

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

• 반면 파이썬에서는 직접 자료형을 지정할 필요가 없으며 매우 큰 수의 연산 또한 기본적으로 지원한다
• 따라서 파이썬에서는 정수형 변수의 연산 때문에 고민할 일은 거의 없으나, 실수형 변수는 다른 언어와 마찬가지로 유효숫자에 따라서 연산 결과가 원하는 값이 나오지 않을 수 있다

 

파이썬에서 리스트 크기

• 파이썬에서 여러 개의 변수를 사용할 때는 리스트를 이용한다
• 파이썬에서 리스트를 이용할 때는 코테의 메모리 제한을 조심해야 한다
• 앞서 다룬 int 자료형의 데이터 개수에 따른 메모리 사용량을 확인해 보자
• 파이썬에서는 정수 데이터를 사용할 때 int와 같은 별도의 자료형을 명시해줄 필요가 없지만, 시스템 내부적으로는 아래와 같은 크기만큼 메모리를 차지한다

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

• 파이썬은 다른 언어에 비해 구현은 쉽지만, 데이터 처리량이 많은 경우에는 꼭 메모리 제한을 고려하자
• 하지만, 메모리 용량 제한으로 못 풀 문제도 드물기 때문에 코테 수준에서는 메모리 사용량 제한보다 더 작은 크기의 메모리를 사용해야 한다는 점 정도만 기억하면 된다

 

 

채점 환경

• 파이썬은 C/C++에 비해 동작 속도가 느리다
• 일반적인 기업 코테 환경에서는 파이썬으로 제출한 코드가 1초에 2,000만 번의 연산을 수행한다고 가정하면 크게 무리가 없다는 점만 기억하자
• 알고리즘 문제를 풀 때는 시간 제한과 데이터의 개수를 먼저 확인한 뒤에 이 문제를 어느 정도의 시간 복잡도의 알고리즘으로 작성해야 풀 수 있을 것인지 예측할 수 있어야 한다

 

 

구현 문제에 접근하는 방법

• 보통 구현 유형의 문제는 사소한 입력 조건 등을 문제에서 명시해주며 문제의 길이가 꽤 길다
• 이 때 문제의 길이를 보고 지레 겁을 먹는데, 문법에 익숙하다면 오히려 쉽게 풀 수 있다
• 구현 유형의 문제는 C/C++로 풀 때 더 어렵게 다가온다
• 문자열을 처리하거나 큰 정수를 처리하는 문제가 많은데, C/C++은 파이썬에 비해 문자열 처리가 까다롭고 큰 정수를 처리하는 라이브러리를 별도로 사용해야 하기 때문에 보다 까다롭다
• 실무에서 파이썬으로 프로그램을 개발할 때는 GPU를 연동하며, 반복적인 행렬 계산을 요구하는 복잡한 수학 문제를 풀 때는 C언어로 작성된 파이썬 코어 소프트웨어가 동작하기 때문에 파이썬을 쓴다고 항상 동작 속도가 느린 건 아니다
• 하지만 코테에서는 그런 사항은 고려하지 않는다
• 요즘 코테 환경에서는 Pypy3을 지원하는 곳이 늘고 있는데, Pypy3은 파이썬 3의 문법을 그대로 지원하며, 파이썬3보다 실행 속도가 빠르고 이는 C/C++에 견줄 만큼 빠르다!
• 따라서 Pypy3을 지원한다면 이를 이용하도록 하자!
• API 개발 문제 또한 구현 유형과 상당히 맞닿아 있다
• C/C++은 웹 서버나 데이터 분석에 대한 기초 지식이 필요한데, 파이썬을 사용하면 상대적으로 무난하게 대처가 가능하다

---

내일은 구현 알고리즘의 대표적인 예시인 '상하좌우' 문제와 '시각' 문제를 풀어볼 것이다!

오늘은 시험기간이니까 여기까지만 하자..!

빠잉><