[이것이 코딩테스트다] 구현 - 완전탐색과 시뮬레이션

📚 구현 - 완전탐색, 시뮬레이션

구현(Implementation)이란 머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정.

• 풀이를 떠올리는 것은 쉽지만 소스코드로 옮기기 어려운 문제
• 완전탐색    : 모든 경우의 수를 주저 없이 다 계산하는 해결 방법
• 시뮬레이션 : 문제에서 제시한 알고리즘을 한 단계씩 차례대로 직접 수행해야하는 문제 유형

---

📃 [예제 1] 상하좌우

- 풀이시간 : 13분

 

- 문제풀이

# 1. 나의 풀이

n = int(input())
map = list(map(str, input().upper().split()))
x,y = 1,1

for m in map:
  if m == 'R':
    y = y+1 if y+1 <= n else y
  if m == 'L':
    y = y-1 if y-1 >= 1 else y
  if m == 'U':
    x = x-1 if x-1 >= 1 else x
  if m == 'R':
    x = x+1 if x+1 <= n else x
    
print(x,y)


# 2. 교재 답안

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)

- 시뮬레이션 유형 : 일련의 명령에 따라서 개체를 차례대로 이동시키기 때문에

- 연산 횟수는 이동 횟수에 비례

  이동 횟수가 N번인 경우 시간 복잡도는 O(N) 이다.

 

 문제를 풀이한 과정을 보면  좌, 우, 위, 아래  4가지 이동방향을 List로 만들어서 사용하고 있다.

그리디 유형의 거스름돈 문제에서도 500원, 100원, 50원, 10원의 화폐단위를 List로 만들어서 사용했었는데, 반복적으로 사용하는 값들에 대해서는 리스트에 담아두고 접근하는 방식으로 알고리즘을 작성하는 것이 좀 더 효율적으로 풀 수 있는 것 같다.

'나의 풀이' 처럼 if문으로 접근한다면 이동방향이 사방팔방으로 늘어나는 경우에는 코드가 길어지게 되기 때문에 가독성 측면에서도 좋지 않아 보인다.

---

📃 [예제 2] 시각

- 풀이시간: 12분

 

- 문제풀이

# 1. 나의 풀이

n = int(input())
count = 0

for h in range(n+1):
  for m in range(60):
    for s in range(60):
      time = F'{h}:{m}:{s}'
      if '3' in time: 
        count += 1
print(count)

# 교재 답안

h = int(input())
count = 0

for i in range(h+1):
  for j in range(60):
    for k in range(60):
      # 매 시각 안에 '3'이 포함되어 있다면 카운트 증가
      if '3' in str(i) + str(j) + str(k):
        count += 1
print(count)

- 완전탐색Brute Forcing 유형 : 가능한 경우의 수를 모두 검사

- 모든 시각의 경우를 하나씩 모두 세서 푸는 문제
  전체 시, 분, 초에 대한 경우의 수 : 24 × 60 × 60 

 

일반적으로 완전 탐색 알고리즘은 비효율적인 시간 복잡도를 가지고 있으므로 전체 데이터의 수가 100만 개 이하일 때 완전 탐색을 사용하면 적절하다.

---

⚡ [문제 1] 왕실의 나이트

- 풀이시간: 30분

 

- 문제풀이

# 나의 풀이

n = input()
x = int(n[1])       # 행
y = int(ord(n[0]))  # 열

# 나이트 이동 방향 8가지
steps = [
  (-2, -1), (-2, 1), (2, -1), (2, 1),
  (-1, -2), (1, -2), (-1, 2), (-1, 2)   
        ]

count = 0
for step in steps:
  nx = x + step[0]
  ny = y + step[1]
  # 이동가능하면 count 증가
  if nx >= 0 and nx <= 7 and ny >= 98 and ny <= 105 : 
    count += 1

print(count)

# 교재 풀이

input_data = input()
row    = int(input_data[1])
column = int(ord(input_data[0])) - int(ord('a')) + 1

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

---

⚡ [문제 2] 게임 개발

- 풀이시간: 30분

 

- 문제풀이

# 나의 풀이

n, m =  map(int, input().split())
x, y, direction = map(int, input().split())
map = [list(map(int, input().split())) for _ in range(n)]

map[1][1] = 9
count = 1
turn_step = 0

# 북, 동, 남 서
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]

# 0 은 육지, 1은 바다

def turn_left():
  global direction
  direction -= 1
  if direction == -1:
    direction = 3

while True:
  print(x, y)
  turn_left()
  nx = x + dx[direction]
  ny = y + dy[direction]

  if map[nx][ny] == 0:
    map[nx][ny] = 9
    count += 1
    x, y = nx, ny
    turn_step = 0
    continue
  else: 
    turn_step += 1

  if turn_step == 4:
    nx = x - dx[direction]
    ny = y - dy[direction]
    if map[nx][ny] == 1:
      break
    else: 
      x, y = nx, ny
    turn_step = 0
    
print(count)
  


# 교재 답안

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 = [list(map(int, input().split())) for _ in range(n)]

# 북, 동, 남, 서 방향 정의
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]

# 왼쪽으로 회전
def turn_left():
  global direction
  direction -= 1
  if direction < 0:
    direction = 3

turn_time = 0 # 회전횟수
count = 1     # 방문횟수

while True:
  turn_left()
  nx = x + dx[direction]
  ny = y + dy[direction]
  if array[nx][ny] == 0 and d[nx][ny] == 0:
    d[nx][ny] = 1
    x, y = nx, 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, y = nx, ny
    else:
      break
    turn_time = 0

print(count)

나의 풀이에서는 방문 위치를 저장하는 맵을 생성하지 않고 0의 값을 9 라는 임의의 값으로 업데이트 해서 방문한 것으로 기록했다.

 

---

🐾 정리

완전탐색 유형과 시뮬레이션 유형에 대해 알아봤다. 유형들을 하나씩 익혀가니깐 어떻게 접근해야하는지 조금씩 감이 잡히는 것 같다.

 

 

 

※ 해당 포스팅은「이것이 취업을 위한 코딩테스트다(나동빈 저)」책 내용을 바탕으로 작성하였습니다.