구현 (Implementation)

개념

: 머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정

사실, 어떤 문제를 풀든 간에 소스코드 작성은 필수이므로 구현 문제 유형은 모든 범위의 코딩 테스트 문제 유형을 포함하는 개념이다.

완전탐색과 시뮬레이션 문제 또한 '구현' 문제 유형이라고 할 수 있다.

1. 완전 탐색

: 모든 경우의 수를 주저없이 다 계산하는 해결 방법

2. 시뮬레이션

: 문제에서 제시한 알고리즘을 한 단계씩 차례대로 직접 수행해야 하는 해결 방법

문제풀이 Tip

• 데이터 개수에 따른 메모리 사용량 체크
• 테스트 환경이 Pypy3도 지원한다면, Pypy3 이용하기 (실행 속도 빠름)

기본예제

예제 1. 상하좌우

여행가 A는 NxN 크기의 정사각형 공간 위에 서 있다. 이 공간은 1x1 크기의 정사각형으로 나누어져 있다. 여행가 A는 상, 하, 좌, 우 방향으로 이동할 수 있고, 시작 좌표는 항상 (1, 1)이다. 여행가 A가 정사각형 공간을 벗어나는 움직임은 무시된다.
여행계획서에는 L, R, U, D 중 하나의 문자가 반복적으로 적혀있다. 계획서가 주어졌을 때 여행가 A가 최종적으로 도착할 지점의 좌표를 출력하는 프로그램을 작성하시오.

• L : 왼쪽으로 1칸 이동
• R : 오른쪽으로 1칸 이동
• U : 위쪽으로 1칸 이동
• D : 아래쪽으로 1칸 이동

## 내 풀이
n = int(input())
plan = list(input().split())

r, c = 1, 1 # 시작지점
nr, nc = 1, 1 # 이동 후 좌표(초기화)

for i in plan:
	# 네 방향 이동해보기
    if i == 'L' :
        nc = c - 1
    elif i == 'R' :
        nc = c + 1       
    elif i == 'U' :
        nr = r - 1
    elif i == 'D' :
        nr = r + 1

	# 이동 후 좌표가 공간을 벗어나는 경우 반복문 처음으로 돌아가기
    if nr < 1 or nc < 1 or nr > n or nc > n:
        continue
    
    # 이동 후 좌표가 공간 내 있을 경우 실제로 이동시키기
    r, c = nr, nc

print(r, c)

5
R R R U D D

3 4

## 모범답안
n = int(input())
plan = input().split()

r, c = 1, 1 # 시작 지점

# 이동할 네 방향 정의
dr = [0, 0, -1, 1]
dc = [-1, 1, 0, 0]
move = ['L', 'R', 'U', 'D']

for p in plan:
	# 이동 후의 좌표 구하기
	for i in range(len(move)):
    	if p == move[i] :
        	next_r = r + dr[i]
            next_c = c + dc[i]
            
    # 공간을 벗어나는 경우 반복문 처음으로 돌아가기
    if next_r < 1 or next_c < 1 or next_r > n or next_c > c:
    	continue
        
    # 이동 수행하기
    r, c = next_r, next_c
    
print(r, c)

5
R R R U D D

3 4

예제 2. 시각

정수 N이 입력되면 00시 00분 00초부터 N시 59분 59초까지의 모든 시각 중에서 3이 하나라도 포함되는 모든 경우의 수를 구하는 프로그램을 작성하시오.

n = int(input())
cnt = 0

for h in range(n+1):
	for m in range(60):
    	for s in range(60):
        
        	# 시(h), 분(m), 초(s)를 문자화시켜서 이어붙였을 때 그 중 3이 있으면
        	if '3' in str(h) + str(m) + str(s):
            	cnt += 1 # 경우의수 증가
                
print(cnt)

5

11475

---

실습

실전문제 1. 왕실의 나이트

8x8 좌표 평면인 왕실 정원의 특정 한 칸에 나이트가 서 있다. 나이트는 말을 타고 있기 때문에 이동할 때 'L'자 형태로만 이동 가능하며 정원 밖으로는 나갈 수 없다. 나이트는 다음과 같은 2가지 경우로 이동할 수 있다.

1. 수평으로 2칸 이동 후, 수직으로 1칸 이동
2. 수직으로 2칸 이동 후, 수평으로 1칸 이동

이처럼 8x8 좌표 평면상에서 나이트의 위치가 주어졌을 때, 나이트가 이동할 수 있는 경우의 수를 출력하는 프로그램을 작성하시오.
(단, 행 위치는 1부터 8로 표현하며, 열 위치는 a부터 h로 표현한다.)

## 모범답안
rc = input() # 현재위치 입력받기
cnt = 0 # 경우의수

# 행/열 쪼개기
r = int(rc[1]) # 행번호
c = int(ord(rc[0]) - ord('a')) + 1 # 열번호

# 이동가능한 8가지 방향 정의
move = [(-2, -1), (-2, 1), (2, -1), (2, 1), (-1, -2), (1, -2), (-1, 2), (1, 2)]

# 이동 후의 좌표 구하기
for m in move:
    next_r = r + m[0]
    next_c = c + m[1]
    
    # 이동 후의 좌표가 정원 내에 있다면 경우의수 카운트
    if next_r >= 1 and next_r <= 8 and next_c >= 1 and next_c <= 8:
        cnt += 1

print(cnt)

a1

2

📌 ord('문자')
: 하나의 문자를 인자로 받고, 해당 문자의 유니코드 정수를 반환한다.
→ 대표적인 예로, ord('a') 는 97을 반환한다.

실전문제 2. 게임 개발

개발중인 게임에서 게임 캐릭터가 있는 맵은 1x1 크기의 정사각형으로 이루어진 NxM 크기의 직사각형으로, 각각의 칸은 육지 또는 바다이다. 캐릭터는 동/서/남/북 중 한 곳을 바라본다. 맵의 각 칸은 (A, B)로 나타낼 수 있고, A는 북쪽으로부터 떨어진 칸의 개수, B는 서쪽으로부터 떨어진 칸의 개수이다. 캐릭터는 상하좌우로 이동 가능하고, 바다는 갈 수 없다. 캐릭터의 움직임 설정을 위한 메뉴얼은 다음과 같다.

1. 현재 위치에서 현재 방향을 기준으로 왼쪽 방향(반시계방향으로 90도 회전한 방향)부터 차례대로 갈 곳을 정한다.
2. 캐릭터의 바로 왼쪽 방향에 아직 가보지 않은 칸이 있다면, 왼쪽 방향으로 회전한 다음 왼쪽으로 한 칸 전진한다. 가보지 않은 칸이 없다면 왼쪽 방향으로 회전만 수행하고 다시 1단계로 돌아간다.
3. 만약 네 방향 모두 이미 가본 칸이거나 바다로 되어있는 칸인 경우, 바라보는 방향을 유지한 채로 한 칸 뒤로 가고 다시 1단계로 돌아간다. 단, 이때 뒤쪽 방향이 바다라면 움직임을 멈춘다.)

위의 메뉴얼에 따라 캐릭터를 이동시킨 뒤에, 캐릭터가 방문한 칸의 수를 출력하는 프로그램을 만드시오.

💡 풀이 아이디어
이번 문제 풀이의 핵심은 다음과 같다.

1. 방문처리용 리스트(visited[][]) 정의(단, 시작지점부터 방문 처리)
2. 네 가지 방향(da, db) 정의
3. 두가지 변수 "이동 후의 좌표(na, nb)", "실제 이동시킨 현재 좌표(a, b)" 정의
4. 왼쪽으로 회전하는 함수(turn_left)와 회전 횟수(turn_time)를 정의하고 회전할 때 마다 카운팅해서 네 방향을 모두 돌았을 경우를 판단

오랫동안 고민했는데도 불구하고 풀지 못했다. 처음에는 모범답안 이해하는 것도 너무 어려웠었다. 한줄씩 주석달면서 공부하니까 90%는 이해한 것 같다.

## 모범답안
n, m = map(int, input().split())
a, b, direction = map(int, input().split()) # 캐릭터 현재좌표: (a, b), 현재 바라보는 방향: direction(0:북, 1:동, 2:남, 3:서)
gamemap = [list(map(int, input().split())) for _ in range(n)] # 1: 바다, 0: 육지

# 방문한 위치를 저장하기 위한 맵 생성 (0으로 초기화)
visited = [[0] * m for _ in range(n)]
visited[a][b] = 1 # 현재 좌표 방문처리

da = [0, 0, -1, 1]
db = [-1, 1, 0, 0]

# 왼쪽으로 회전시키는 함수
def turn_left():
    global direction # 함수 밖에있는 변수 d를 함수 내에서 쓰기위한 작업
    direction -= 1 # 왼쪽으로 회전
    if direction == -1:
        direction = 3 # 서쪽이 3이기 때문에
        
# 시뮬레이션 시작
cnt = 1 # 방문한 칸 개수 (현재 좌표부터 카운트)
turn_time = 0 # 회전 횟수

while True:
    turn_left() # 왼쪽으로 회전
    
    # 회전 후의 좌표 설정 (앞으로 갈 좌표)
    next_a = a + da[direction]
    next_b = b + db[direction]
    
    # 2-1. 왼쪽 회전 후의 좌표가 아직 방문하지 않은, 육지(0)인 경우
    if visited[next_a][next_b] == 0 and gamemap[next_a][next_b] == 0:
        visited[next_a][next_b] = 1 # 해당 좌표 방문처리
        
        # 실제 회전 (현재좌표)
        a = next_a
        b = next_b
        
        cnt += 1 # 방문한 칸 개수 카운트
        turn_time = 0 # 회전 횟수 초기화
        continue # 반복문 처음으로 돌아가기 (1단계로 돌아가기 : 현재 위치의 왼쪽 방향부터 차례로 갈 곳 정하기)
        
    # 2-2. 왼쪽 회전 후의 좌표가 이미 방문한 상태이거나 바다(1)인 경우
    else:
        turn_time += 1 # 회전 횟수만 추가
        
    # 3. 네 방향으로 왼쪽 회전 후의 좌표가 모두 방문한 상태이거나 바다(1)인 경우
    if turn_time == 4:
        # 앞으로 갈 좌표 = 바라보는 방향을 유지한 채 한칸 뒤로 가기
        next_a = a - da[direction]
        next_b = b - db[direction]
        
        # 3-1. 뒤로 갈 수 있다면(육지인 경우) 실제 이동하기
        if gamemap[next_a][next_b] == 0:
            a = next_a
            b = next_b
            
        # 3-2. 뒤로 갈 수 없다면(바다인 경우) 움직임을 멈추고 프로그램 종료
        else:
            break
            
        turn_time = 0 # 회전 횟수 초기화

# 정답출력
print(cnt)

4 4
1 1 0
1 1 1 1
1 0 0 1
1 1 0 1
1 1 1 1

3

공부하면서 여러 블로그를 찾아보았는데, 책에 적힌 모범답안보다 훨씬 간결하고 왼쪽함수를 따로 정의하지 않은 풀이가 있었다.

## 다른 사람 풀이
n, m = map(int, input().split())
a, b, d = map(int, input().split())
 
input_map = []
 
for i in range(n):
  input_map.append(list(map(int, input().split())))
 
move_steps = [(-1, 0), (0, -1), (1, 0), (0, 1)]
 
result = 1
count = 0
input_map[a][b] = 2
 
while True:
  d = d - 1
  if d == -1:
    d = 3
  next_a = a + move_steps[d][0]
  next_b = b + move_steps[d][1]
  if input_map[next_a][next_b] == 0:
    a = next_a
    b = next_b
    result += 1
    input_map[a][b] = 2
    count = 0
 
  else:
    count += 1
    if count == 4:
      next_a = a + move_steps[d-2][0]
      next_b = b + move_steps[d-2][1]
      if input_map[next_a][next_b] == 1:
        break
      else:
        a = next_a
        b = next_b
        count = 0
 
print(result)

4 4
1 1 0
1 1 1 1
1 0 0 1
1 1 0 1
1 1 1 1

3

방문 처리용 리스트와 왼쪽 회전 함수를 따로 정의하지 않고 해결한 것 같다.
대신 방문한 칸인 경우, 게임 맵 리스트(input_map[][])를 2로 만들어서 방문처리 했다.
또한 왼쪽 회전 함수를 정의하는 대신 반복문 while 안에 왼쪽 회전 코드를 별도로 작성하여 전역변수와 함수를 사용하지 않고 회전할 수 있도록 한 것 같다.

🔗 References

• 이것이 취업을 위한 코딩 테스트다 with 파이썬

• 실전문제 2번 풀이 참고 블로그