구현
구현이란, 머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정이다.
•
풀이를 떠올리는 것은 쉽지만 소스코드로 옮기기 어려운 문제를 지칭한다.
예시
◦
알고리즘은 간단한데 코드가 지나칠 만큼 길어지는 문제
◦
실수 연산을 다루고, 특정 소수점 자리까지 출력해야 하는 문제
◦
문자열을 특정한 기준에 따라서 끊어 처리해야 하는 문제
◦
적절한 라이브러리를 찾아서 사용해야 하는 문제
•
일반적으로 알고리즘 문제에서의 2차원 공간은 행렬의 의미로 사용되며, 시뮬레이션 및 완전 탐색 문제에서는 2차원 공간에서의 방향 벡터가 자주 활용된다.
◦
완전탐색 : 모든 경우의 수를 주저 없이 다 계산하는 해결 방법
◦
시뮬레이션 : 문제에서 제시한 알고리즘을 한 단계씩 차례대로 직접 수행해야 하는 문제 유형을 의미한다.
•
파이썬에서 리스트 크기
◦
파이썬에서 여러 개의 변수를 사용할 때는 리스트를 이용한다. 이때 코딩 테스트의 메모리 제한을 고려해야 한다. 대체로 코딩 테스트 에서는 128 ~ 512 MB 로 메모리를 제한한다.
int 자료형 데이터의 개수에 따른 메모리 사용량
데이터의 개수(리스트의 길이) | 메모리 사용량 |
1000 | 약 4 KB |
1000000 | 약 4 MB |
10000000 | 약 40 MB |
◦
파이썬은 다른 언어에 비해서 구현상의 복잡함이 적은 편이지만 데이터 처리량이 많을 때에는 꼭 메모리 제한을 고려하도록 하자. 리스트를 여러 개 선언하고, 그 중에서 크기가 1000 만 이상인 리스트가 있다면 메모리 용량 제한으로 문제를 풀 수 없게 되는 경우도 있다는 점을 기억하자. (하지만, 이런문제 또한 드물다)
예제 4-1 상하좌우
일련의 명령에 따라서 개체를 차례대로 이동시킨다는 점에서 시뮬레이션 유형으로도분류 되며 구현이 중요한 대표적인 문제 유형이다.
예제 4-2 시각
if '3' in str(hour) + str(min) + str(sec): 을 이용해 여러곳을 한꺼번에 관찰실전문제 왕실의 나이트
char → 아스키 코드값ord() : 문자의 아스키코드를 알려주는 메서드
아스키 코드값 → char
char() : () 안의 아스키코드값에 해당하는 문자를 반환하는 메서드
실전문제 게임 개발
필요한 것들과 구현의 순서를 정해놓고 코딩을 시작해보자•
필요한 것들
◦
가로 * 세로 입력
◦
행, 열 방향 입력
◦
북, 동, 남, 서 정의
◦
전체 맵 정보
◦
방문한 위치를 저장하기 위한 행렬 (0 으로 초기화 후, 방문하면 1 증가) 과 입력받은 위치 방문처리
◦
왼쪽으로 회전할 시의 함수
•
구현순서
while True :
# 왼쪽으로 회전
# 이동 했을 시의 새로운 위치 구하는 식
if
# 회전 한 이후 정면에 가보지 않은 칸이 존재한다면 이동
continue
else
# 회전 한 이후 정면에 가보지 않은 칸이 없거나 바다인 경우
# 회전만 한다.
# 네 방향 모두 갈 수 없는 경우
if # 4 번 회전했겠지
# 뒤로 갈 수 있다면 한 칸 뒤로 이동하지만
else
# 뒤가 바다로 막혀있어서 이동할수 없다면
break
# 회전 횟수는 0 으로 초기화 해주기
# 결과 출력
Python
복사