[이것이 코딩테스트다] 3일차 - 구현

본문은 [이것이 취업을 위한 코딩테스트다 - 나동빈] 책을 공부하고 작성한 글입니다.

Chapter 4 구현 알고리즘

구현 = 머릿속의 알고리즘을 소스코드로 바꾸는 과정 

구현 유형의 문제 = 풀이를 떠올리는 건 쉽지만 소스코드로 작성하기 어려운 문제

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

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

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

 

모든 문제는 스스로 소스코드를 작성하는 과정을 거치기 때문에 구현은 모든 범위의 코딩 테스트 문제 유형을 포함하는 개념이다

코딩 테스트에서 구현이 중심이 되는 문제가 자주 출제 되므로 연습이 필요하다

 

구현 문제를 잘 풀기 위해서는?

   - 프로그래밍 언어 문법에 능숙해져야 함 (유용한 라이브러리를 알고 사용에 능숙해야 함 )

책에서는 완전 탐색과 시뮬레이션을 구현유형으로 묶어 다룬다

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

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

 

파이썬에서 리스트를 사용할 경우 고려해야 할 사항

코딩테스트 메모리 제한 - 보통 코딩테스트에서는 128~512MB로 메모리를 제한하는데 테스트 케이스로 수백만개 이상의 데이터를 처리해야하는 문제가 출제되곤 하므로 메모리 제한을 염두해 두고 코딩해야 한다.

하지만 이런 문제는 드물게 출제되고 출제자 입장에서도 입출력 속도까지 고려하는 것은 매우 번거로운 작업으로 일반적인 코딩테스트의 경우 메모리 사용량 제한을 고려한다기보다 더 적은 크기의 메모리를 사용하는 코드를 짜도록 노력하는 것이 더 중요하다.

파이썬의 경우 기본적인 문법만 알고있으면 다른 언어들(C/C++, JAVA..)들에 비해 구현 문제를 쉽게 구현할 수 있다

파이썬은 다른 언어에 비해 속도가 느린 단점이 있는데 Pypy3의 경우 파이썬3의 문법을 그대로 지원하지만 속도가 빠른 장점이 있다.

따라서 Pypy3이 지원되는 환경이라면 파이썬보다 이를 선택하여 풀이를 하는 것이 더 유리하므로 이를 선택하도록 하자.

 

Part 2 구현 연습문제는 깃허브에 업로드하였습니다 

GitHub - gymin97/algorithm_study: Solve the algorithm problems (python3)

마지막 게임개발 문제에서 조금 헤매었다.

방향이 있는 문제에서는 이동하는칸의 배열을 만들고 (dx, dy) 이를 현재 위치에 더하거나 빼면서 이동하는것이 효율적임을 배웠다 (짜기도 쉽고 안헷갈림!)

또 왕실의 나이트 경우 if 문을 엄청 써서 풀었는데 이러한 문제 또한 가독성, 효율성을 따져 dx, dy를 만들고 이동하는 연습을 해봐야겠다.