구현
구현(implementation)이란 '머리속에 있는 알고리즘을 소스코드로 바꾸는 과정'
이 책에서는 구현은 모든 범위의 코딩 테스트 문제 유형을 포함한다고 한다.
구현이 어려운 문제는?
알고리즘은 간단한데 코드가 지나치게 길어지는 문제
특정 소수점 자리까지 출력해야 하는 문제
문자열이 입력으로 주어졌을 때 한 문자 단위로 끊어서 리스트에 넣어야하는(파싱을 해야하는) 문제 등등
파이썬에서 리스트의 크기
코딩 테스트의 메모리 제한.
대체로 코테에서는 128~512MB로 메모리를 제한하는데 가끔 수백만개 이상의 데이터를 처리해야 하는 문제가 출제된곤 한다. 이때는 메모리 제한을 염두해야된다.
1000개의 데이터 - 약 4kb의 메모리 사용량
1,000,000 - 약 4MB
10,000,000 - 약 40MB
리스트를 여러 개 선언하고 그중에 크기가 1000만 이상인 리스트가 있다면 메모리 용량 제한으로 문제를 풀 수 없게 되는 경우도 있다. !! (이런 문제가 드물긴하다)
상하좌우 문제
여행가는 A는 N x N 크기의 정사각형 공간위에 있다. 이 공간은 1 x 1크기의 정사각형으로 나누어져 있다. 가장 왼쪽위 좌표는(1,1) 가장 오른쪽 아래 좌표는 (N,N) A는 상,하,좌,우 ㅏㅇ향으로 이동할 수 있다.
시작 좌표는 항상(1,1)
L: 왼쪽으로 한칸
R: 오른쪽으로 한칸
U: 위로 한 칸
D: 아래로 한칸
계획서가 주저였을때 여행가가 최종적으로 도착할 지점의 좌표를 출력!
a = int(input())
x, y = 1, 1
plans = input().split()
dx = [0, 0, -1, 1]
dy = [-1, 1, 0, 0]
move_type = ['L', 'R', 'U', 'D']
for plan in plans:
for i in range(len(move_type)):
if plan == move_type[i]:
nx = x + dx[i]
ny = y + dy[i]
if nx < 1 or ny < 1 or nx > n or ny > n:
continue
x, y = nx, ny
print(x, y)
위와 같이 풀면 된다.
list에다가 x좌표 이동과 y좌표 이동을 L R U D 와 같은 순서로 지정해놓아서 index값으로 쉽게 얼마나 이동하는지 구현할 수 있다.
시각 문제
정수 N이 입력되면 00시 00분 00초 부터 N시 59분 59초 까지의 모든 시각 중에서 3이 하나라도 포함되는 모든 경우의 수를 구하는 프로그램을 작성하시오.
첫밴째 줄에 정수 N이 입력된다.
n = int(input())
count = 0
for i in range(n + 1):
for j in range(60):
for k in range(60):
if '3' in str(i) + str(j) + str(k):
count += 1
print(count)
위와 같이 3중 for문을 이용해서 문제를 푼다.
0시 부터 23시 59분 59초까지 86400가지만 존해 하기때문에 경우의 수가 100,000가지가 되지않기때문에 일일이 확인해봐도 된다. aka - 완전탐색 (brute force)
왕실의 나이트
8x8 좌표 평면의 체스판이 있다. 나이트는 이동할때 L자 형태로만 이동가능. 체스판 밖으로는 이동 불가능.
1. 수평으로 두 칸 이동한 뒤에 수직으로 한칸 이동
2. 수직으로 두 칸 이동한 뒤에 수평으로 한 칸 이동
행을 1부터 8로 열을 a부터 h로 표현 맨좌측 맨위 가 a1이다.
나이트의 위치를 입력했을때 이동할 수 있는 경우의수를 구하시오.
n = input()
row = int(n[1])
column = int(ord(n[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_column = column+step[1]
if (1<=next_row<=8) and (1<=next_column<=8):
result +=1
print(result)
나이트가 이동할 수 있는 8가지 방향을 미리 list형태로 정의해놓는다. 그리고 행을 숫자로 열을 숫자로 바꾸어서 입력받은 위치에서 steps를 전부 시도해봐서 체스판안으로 이동될때만 result을 +1 해준다.
ord - 문자의 유니코드값을 return
게임 개발 문제
캐릭터가 맵 안에 움직이는 시스템 개발중
캐릭터가 있는 장소는 1 x 1크기의 정사각형으로 이뤄진 N x M 크기의 직사각형으로, 각각의 칸은 육지 or 바다이다.
맵의 각 칸은 (A,B)로 나타낼 수 있고, A는 북쪽으로 떨어진 칸의 개수, B는 서쪽으로 떨어진 칸의 개수, 캐릭터는 상하좌우로 이동가능, 바다로는 못간다.
문제설명 생략
n, m = map(int, input().split())
x, y, direction = map(int, input().split())
d = [[0] * m for _ in range(n)]
d[x][y] = 1
array = []
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]
count = 0
for i in range(n):
array.append(list(map(int, input().split())))
def turn_left():
global direction
direction -= 1
if direction == -1:
direction = 3
count = 1
turn_time = 0
while True:
turn_left()
nx = x + dx[direction]
ny = y - dy[direction]
if d[nx][ny] == 0 and array[nx][ny] == 0:
d[nx][ny] = 1
x = nx
y = ny
count += 1
turn_time = 0
continue
else:
turn_time += 1
if turn_time == 4:
nx = x - dx[direction]
ny = y - dy[direction]
if array[nx][ny] == 0:
x = nx
y = ny
else:
break
turn_time = 0
print(count)방향별 북동남서 순으로 x좌표와 y좌표 이동을 설정해놓고
while문으로 시물레이션을 시작하고
규칙에 따라 시작하면 왼쪽으로 회전한다.
회전하구 정면에 가보지 않은 칸이 있으면 그곳으로 이동하고 정면에 가보지 않은 칸이 없거나 못가는 칸이면 회전한다.
4번회전했는데 모두 못가면 turn_time ==4 일때
뒤로 갈수있다면 뒤로 가고 뒤로 못가면(바다면) while문을 끝낸다.
