구현
머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정
코딩테스트에 자주 출제됨, 완전 탐색과 시뮬레이션 유형을 같이 공부함
완전 탐색은 모든 경우의 수를 주저 없이 다 계산하는 방법을 말하고,
시뮬레이션은 문제에서 제시한 알고리즘을 한 단계씩 차례대로 직접 수행해야하는 문제 유형을 말한다.
구현 시 고려해야 할 메모리 제약 사항
파이썬에서는 리스트 크기를 고려해야 한다.
대체로 코딩 테스트에서는 128~51MB로 메모리를 제한하는데 알고리즘 문제 중 때로는 수백만 개 이상의 데이터를 처리해야 하는 문제가 출제되곤 한다.
int 자료형 데이터의 개수에 따른 메모리 사용량
데이터의 개수 (리스트의 길이) 메모리 사용량
| 1,000 | 약 4KB |
| 1,000,000 | 약 4MB |
| 10,000,000 | 약 40MB |
리스트 크기가 1,000만 이상인 리스트가 있다면 메모리 용량 제한으로 문제를 풀 수 없게 되는 경우도 있지만 드물다. 일반적인 코딩 테스트 수준에서는 메모리 사용양 제한보다 더 적은 크기의 메모리를 사용하려고 해야함
구현 문제에 접근하는 방법
문제의 길이가 꽤 긴편이나 , 고차원적인 사고력을 요구하는 문제는 나오지 않는 편이라 문법에 익숙하면 쉽게 풀 수 있다.
예제 4-1 상하좌우
문제
여행가 A는 NN 크기의 정사각형 공간 위에 서 있다. 이 공간은 11 크기의 정사각형으로 나누어져 있다. 가장 왼쪽 위 좌표는 (1,1)이며 가장 오른쪽 아래 좌표는 (N,N)에 해당한다. 여행가 A는 상,하,좌,우 방향으로 이동할 수 잇으며 시작 좌표는 항상 (1,1)이다. 명령대로 움직였을 때 도착할 지점의 좌표를 출력하시오
나의 답안
- N 크기를 입력 받는다.
- 시작점 위치를 (1,1)로 세팅해야 한다
- 현재 좌표를 나타낼 변수를 정함
- 방향대로 좌표를 이동한다dx = [-1,+1,0,0] , 만약 이동한 좌표가 1보다 작으면 무시한다
- dy = [0,0,-1,+1]
- 방향 = [왼쪽,오른쪽,위,아래]
n = int(input())
plan = list(map(str,input().split()))
# 현재 위치
x=1
y=1
#방향 = [왼쪽,오른쪽,위,아래]
dx = [-1,+1,0,0]
dy = [0,0,-1,+1]
ind = -1
for p in plan:
if p == "L":
ind = 0
elif p == "R":
ind = 1
elif p == "U":
ind = 2
else:
ind = 3
px = x + dx[ind]
py = y + dy[ind]
if px < 1 or py <1 or px>n or py>n:
continue
x = px
y= py
print(py,px)
ㅇㅖ제 4-2 시각
정수 N이 입력되면 00시 00분 00초부터 N시 59분 59초까지의 모든 시각 중에서 3이 하나라도 포함되는 모든 경우의 수를 구하는 프로그램을 작성하시오
정답
N = int(input())
count = 0
for h in range(N+1):
for m in range(60):
for s in range(60):
if '3' in str(h)+str(m)+str(s) :
count +=1
print(count)
예제 4-3 왕실의 나이트
8*8 좌표 평면 체스판에서 나이트의 이동 경로를 구하라
p = input()
row = int(p[1])
col = int(ord(p[0])) - int(ord('a'))+1
steps = [(-2,-1),(-1,-2),(1,-2),(2,-1),(2,1),(1,2),(-1,2),(-2,1)]
result = 0
for step in steps:
next_row = row +step[0]
next_col = col+step[1]
if next_row >= 1 and next_col <= 8 and next_col >=1 and next_col <= 8:
result +=1
print(result)