[알고리즘] '이것이 코딩테스트다' Chapter 4 구현

❇️이 글은 '이것이 코딩테스트다' 교재를 학습하며 작성했습니다.

구현 문제는 '머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정'이다.

 

이 책에서는 모든 경우의 수를 주저없이 다 계산하는 해결방법인 '완전 탐색'과, 문제에서 제시한 알고리즘을 한 단계씩 차례대로 직접 수행해야 하는 '시뮬레이션' 문제를 구현 문제로 포함하고 있다.

 

파이썬에서 int 자료형 데이터의 개수에 따른 메모리 사용량

데이터의 개수(리스트의 길이)	메모리 사용량
1,000	약 4KB
1,000,000	약 4MB
10,000,000	약 40MB

 

예제 4-1 상화좌우

N = int(input())
x, y = 1, 1
plans = input().split()

# L, R, U, D에 따른 이동 방향
dx = [0, 0, -1, 1]
dy = [-1, 1, 0, 0]
move_types = ['L', 'R', 'U', 'D']

# 이동 계획을 하나씩 확인
for plan in plans:
    # 이동 후 좌표 구하기
    for i in range(len(move_types)):
        if plan == move_types[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)

 

예제 4-2 시각

 

#예제 4-2(완전탐색)
hour = int(input())

count = 0
for i in range(hour+1):
  for j in range(60):
    for k in range(60):
      #매 시각 3이 포함되어 있으면 count++
      if '3' in str(i) + str(j) + str(k):
        count+=1
print(count)

 

실전문제 - 왕실의 나이트

상하좌우 문제와 유사하다.

 

#실전! 왕실의 나이트

#현재 나이트의 위치 입력받기
input_data = input()
row = int(input_data[1])
column = int(ord(input_data[0])) - int(ord('a'))+1 #a면 97-97+1 = 1

#나이트가 이동할 수 있는 8가지 방향 정의
steps = [(-2,-1), (-1,-2), (1,-2), (2,-1), (2,1), (1,2), (-1,2),(-2,1)]

#8가지 방향에 대하여 각 위치로 이동이 가능한지 확인
result = 0
for step in steps:
  #이동하고자 하는 위치 확인
  next_row = row+step[0]
  next_column = column+step[1]
  #해당 위치로 이동이 가능하다면 카운트 증가
  if next_row>=1 and next_row <=8 and next_column >=1 and next_column <=8:
    result+=1
print(result)

 

실전문제 - 게임 개발

#실전2 게임개발
#시뮬레이션 문제 
n, m = map(int, input().split())
a, b, d = map(int, input().split())
data = [list(map(int, input().split())) for _ in range(n)]

visited = [[0 for _  in range(n)] for _ in range(m)]
visited[a][b] = 1

dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]

# 왼쪽으로 도는 함수
def turn_left(direction):
  direction -= 1
  if direction == -1:
    direction = 3
  
  return direction

x, y = a, b
result = 1
count = 0

# 시뮬레이션 시작
while True:
  d = turn_left(d)
  nx = x + dx[d]
  ny = y + dy[d]
  
  if data[nx][ny] == 0 and visited[nx][ny] == 0:
    x = nx
    y = ny
    visited[x][y] = 1
    result += 1 
    count = 0
    continue
  else:
    count += 1
  
  # 네 방향 모두 갈 수 없는 경우
  if count == 4:
    nx = x - dx[d] 
    ny = y - dy[d]
    
    if data[nx][ny] == 1:
      break
    else:
      x = nx
      y = ny
      count = 0 
      
print(result)