구현

본 글은 '이것이 취업을 위한 코딩 테스트다 with 파이썬' 책을 공부하며 기록합니다.
단, iOS를 공부하고 있기 때문에 swift 언어로 코드를 바꿔보고 있습니다.

구현 문제란?

풀이를 떠올리는 것은 쉽지만 소스코드로 옮기기 어려운 문제로
알고리즘은 간단한데 코드가 지나칠 만큼 길어지는 문제, 특정 소수점 자리까지 출력해야 하는 문제, 문자열 입력으로 주어졌을 때 한 문자 단위로 끊어서 리스트에 넣어야 하는(파싱 해야 하는) 문제들이 있다.

프로그래밍 문법 숙지와 라이브러리 사용 경험이 필요하다
완전 탐색, 시뮬레이션 유형을 구현 문제로 볼 수 있다.

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

구현 문제를 풀 때 유의할 점

다음과 같이 문제에 시간과 메모리 제한 사항들이 있는 경우를 많이 볼 수 있다.

메모리 제약 사항

수백만 개 이상의 데이터를 처리해야하는 문제에서는 메모리 제한을 염두에 둬야한다.

c++에서 int 자료형의 표현 범위 : 약 -20억 ~ 20억
c++에서 int 자료형의 크기 : 4바이트

파이썬 int 자료형 리스트 데이터 개수 1000만개 약 40MB

시간 제한

파이썬 기준 1초에 2000만 번의 연산 수행이면 안정적이다.
데이터가 100만개이면 시간복잡도 $O(NlogN)$ 이내의 알고리즘으로 풀어야 한다.

참고

https://book.naver.com/bookdb/book_detail.nhn?bid=16439154