홈 [Algorithm] 코딩테스트 알고리즘 06 - 구현
포스트
취소

[Algorithm] 코딩테스트 알고리즘 06 - 구현

게시 2022-03-20 업데이트 2022-10-16
By 19tak

본 포스팅은 “이것이 취업을 위한 코딩테스트다 with 파이썬” - (한빛미디어, 나동빈 지음)을 바탕으로 공부한 내용을 정리한 것입니다.

  1. 구현 유형
  2. 예제 1
  3. 예제 2
  4. 실전 문제 1
    • 왕실의 나이트
  5. 실전 문제 2
    • 게임 개발

1. 구현 유형

코딩 테스트에서 구현 (Implementation)은 머릿 속에 있는 알고리즘을 소스코드로 바꾸는 과정이다.

보통 풀이를 떠올리는 것은 쉽지만 소스코드로 옮기기 어려운 문제를 의미한다.

현재 상황에서 지금 당장 좋은 것만 고르는 방법을 의미한다.

  • 표준 라이브러리를 활용해 쉽게 짜는 방법도 있지만, 프로그래밍 언어의 문법을 정확히 알고 있어야 하며 문제의 요구사항에 어긋나지 않는 답안 코드를 실수 없이 작성해야 한다.

  • 보통 구현 유형의 문제는 사소한 입력 조건 등을 문제에서 명시해주며 문제의 길이가 꽤 긴 편이다.

시뮬레이션 유형, 구현 유형, 완전 탐색 유형은 서로 유사한 점이 많다.

2. 예제 1

시뮬레이션 유형

여행가 A는 N x N 크기의 정사각형 공간 위에 서 있다.

이 공간은 1 X 1 크기의 정사각형으로 나누어져 있다.

가장 왼쪽 위 좌표는 (1,1)이며, 가장 오른쪽 아래 좌표는 (N,N)에 해당한다.

여행가 A는 상, 하, 좌, 우 방향으로 이동할 수 있으며, 시작 좌표는 항상 (1,1)이다.

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

A가 N x N 크기의 정사각형 공간을 벗어나는 움직임은 무시된다.

계획서가 주어졌을 때 A가 최종적으로 도착할 지점의 좌표를 출력하는 프로그램을 작성하시오.

  • 첫째 줄에 공간의 크기를 나타내는 N이 주어진다. (1 <= N <= 100)
  • 둘째 줄에 여행가 A가 이동할 계획서 내용이 주어진다. (1 <= 이동 횟수 <= 100)
  • 첫째 줄에 여행가 A가 최종적으로 도착할 지점의 좌표 (X, Y)를 공백으로 구분하여 출력한다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

n = int(input()) # 5 입력
x, y = 1, 1
plans = input().split() # R R R U D D 입력

# 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)

3. 예제 2

완전 탐색 유형

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

  • 첫째 줄에 정수 N이 입력된다. (0 <= N <= 23)
  • 00시 00분 00초부터 N시 59분 59초까지의 모든 시각 중에서 3이 하나라도 포함되는 모든 경우의 수를 출력한다.
1
2
3
4
5
6
7
8
9
10

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)

4. 실전 문제 1

왕실의 나이트

행복 왕국의 왕실 정원은 체스판과 같은 8 x 8 좌표 평면이다.

왕실 정원의 특정한 한 칸에 나이트가 서 있다. 나이트는 말을 타고 있기 때문에 이동을 할 때는 L자 형태로만 이동할 수 있으며, 정원 밖으로는 나갈 수 없다. 나이트는 특정한 위치에서 다음과 같은 2가지 경우로 이동할 수 있다.

    1. 수평으로 두 칸 이동한 뒤에 수직으로 한 칸 이동하기
    1. 수직으로 두 칸 이동한 뒤에 수평으로 한 칸 이동하기

행 위치를 표현할 때는 1부터 8, 열은 a부터 h로 표현한다.

  • 첫째 줄에 8 x 8 좌표 평면상에서 현재 나이트가 위치한 곳의 좌표를 나타내는 두 문자로 구성된 문자열이 입력된다. 입력 문자는 a1처럼 열과 행으로 이뤄진다.
  • 나이트가 이동할 수 있는 경우의 수를 출력하시오.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

# 현재 나이트의 위치 입력받기
input_data = input()
row = int(input_data[1])
column = int(ord(input_data[0])) - int(ord('a')) + 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)

예제 1에서는 리스트를 선언하여 이동할 방향을 기록할 수 있도록 했다.

실전 문제 1에서는 steps 변수가 동일 기능을 대신하여 수행한다. 두가지 모두 자주 사용된다.

5. 실전 문제 2

시뮬레이션 유형

일반적으로 방향을 설정해서 이동하는 문제 유형에서는 dx, dy 라는 별도의 리스트를 만들어 방향을 정하는 것이 효과적이다.

게임 개발

게임 캐릭터가 맵 안에서 움직이는 시스템을 개발 중이다.

캐릭터가 있는 장소는 1 x 1 크기의 정사각형으로 이뤄진 N x M 크기의 직사각형으로, 각각의 칸은 육지 또는 바다이다. 캐릭터는 동서남북 중 한곳을 바라본다.

맵의 각 칸은 (A,B)로 나타낼 수 있고, A는 북쪽으로부터 떨어진 칸의 개수, B는 서쪽으로부터 떨어진 칸의 개수이다. 캐릭터는 상하좌우로 움직일 수 있고, 바다는 못 간다.

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

캐릭터가 방문한 칸의 수를 출력하는 프로그램을 만드시오.

  • 첫째 줄에 맵의 세로 크기 N과 가로 크기 M을 공백으로 구분하여 입력한다. (N >= 3, M <= 50)
  • 둘째 줄에 게임 캐릭터가 있는 칸의 좌표 (A,B)와 바라보는 방향 d가 각각 서로 공백으로 구분 입력.0 북쪽 / 1 동쪽 / 2 남쪽 / 3 서쪽
  • 셋째 줄부터 맵이 육지인지 바다인지 입력한다. N개의 줄에 맵의 상태가 북쪽부터 남쪽 순서대로, 각 줄의 데이터는 서쪽부터 동쪽 순서대로 주어진다. 맵의 외곽은 항상 바다로 되어있다. 0 육지 / 1 바다
  • 처음에 게임 캐릭터가 위치한 칸의 상태는 항상 육지이다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57

# N, M을 공백으로 구분하여 입력받기
n, m = map(int, input().split())

# 방문한 위치를 저장하기 위한 맵을 생성하여 0으로 초기화
d = [[0] * m for _ in range(n)]
# 현재 캐릭터의 X 좌표, Y 좌표, 방향을 입력받기
x, y, direction = map(int,input().split())
d[x][y] = 1 # 현재 좌표 방문 처리

# 전체 맵 정보를 입력받기
array = []
for i in range(n):
	array.append(list(map(int, input().split())))

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

# 왼쪽으로 회전
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 += 1:
		nx = x - dx[direction]
		ny = y - dy[direction]
		# 뒤로 갈 수 있다면 이동하기
		if array[nx][ny] == 0:
			x = nx
			y = ny
		# 뒤가 바다로 막혀있는 경우
		else:
			break
		turn_time = 0
print(count)

참고

“이것이 취업을 위한 코딩테스트다 with 파이썬” - (한빛미디어, 나동빈 지음)

Study, Algorithm
Python Algorithm
이 기사는 저작권자의 CC BY 4.0 라이센스를 따릅니다.
최근 업데이트
바로가기