[Algorithm] 구현 문제 (Implementation) with 방향 이동(dx, dy)

 

구현 문제

: 문제 해결 분야에서 구현 문제는 '풀이를 떠올리기 쉽지만 소스로 작성하기는 어려운 문제'를 말한다!

예) 코드가 지나치게 길어지는 문제, 특정 소수점까지 출력하는 문제, 문자열을 문자 단위로 끊어서 리스트에 넣는(파싱하는) 문제 등

- 사소한 조건 설정이 많을 수록 구현하기 어렵다

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

    * 완전 탐색 : 모든 경우의 수를 다 계산하는 방법

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

 

 

 

파이썬에서의 구현

> 자료형

- 파이썬에서는 프로그래머가 직접 자료형을 지정할 필요가 없다

- 매우 큰 수의 연산도 기본적으로 지원한다

- 실수형 변수는 유효숫자에 따라 원하는 값이 나오지 않을 수 있다

 

> 리스트

- 보통 코딩 테스트에서는 128 ~ 512MB로 메모리를 제한한다

- 리스트가 여러 개 이고, 그 중 크기가 1,000만 이상인 리스트가 있다면 메모리 용량 제한으로 문제를 풀 수 없는 경우가 있다

 

 

 

구현 문제에 접근하는 방법

- Pypy3을 지원한다면, 선택하자!  👉  파이썬3와 동일한 코드로 실행 시간을 줄일 수 있다

- 알고리즘 문제를 풀 때는 시간 제한과 데이터 개수를 확인하고, 어떤 시간 복잡도의 알고리즘을 선택해야 할지 결정할 수 있어야 한다

    * 완전 탐색 알고리즘은 비효율적인 시간 복잡도를 가지기 때문에, 전체 데이터 수가 100만 개 이하일 때 사용한다

- 코딩 테스트에서 난이도가 낮은 1 ~ 2번 문제는 대부분 그리디 알고리즘이나 구현 문제이다.

 

 

 

방향 이동 문제

- x, y좌표 상에서 방향을 설정하여 이동하는 문제

- 시뮬레이션 문제에서 게임 캐릭터의 이동 등으로 자주 등장한다

 

- dx, dy라는 리스트를 만들어 방향을 정하는 것이 효과적이다

    * 위(북)쪽으로 이동하기 위해, x와 y좌표에 dx[0], dy[0]을 더할 수 있다

dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]
# 위, 오른, 왼, 아래
# 북,  동,  남,  서

 

 

 

 

 

📚 참고서적 : 이것이 코딩테스트다 with 파이썬