구현 Implementation

코딩 테스트에서 구현이란 머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정이다. 어떤 문제를 풀든 간에 소스코드를 작성하는 과정을 필수이므로 구현 문제 유형은 모든 범위의 코딩 테스트 문제 유형을 포함하는 개념이다. 

그런 의미에서 알고리즘 교재에서는 대부분 구현을 별도의 유형으로 다루지 않는다. 하지만 취업을 목표로 하는 코딩 테스트에서는 구현이 중심이 되는 문제가 자주 출제되기에 다른 알고리즘을 배우기 전에 먼저 다루고자 한다. 

 

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

 

완전 탐색: 모든 경우의 수를 주저 없이 다 계산하는 방법

시뮬레이션: 문제에서 제시한 알고리즘을 한 단계씩 차례대로 직접 수행해야 하는 문제 유형. 

이 둘은 구현이 핵심이 되는 경우가 많다.

 

1. 상하좌우 문제

여행가가 N x N 크기의 정사각형 공간 위에 서 있다. 가장 왼쪽 위 좌표가 (1, 1)이며 가장 오른쪽 아래가 (N, N)이다. 상화좌우로 이동할 수 있는 4종류의 명령이 주어질 때, 여행가가 최종적으로 위치하게 되는 좌표를 출력하는 프로그램을 작성하시오. (정사각형 공간을 벗어나는 움직임은 무시된다.)

 

	n = int(input())
	plans = input().split()
	a = 1
	b = 1
	for i in plans:
	if i == "R" and b < n:
	b += 1
	if i == "L" and b > 1:
	b-= 1
	if i == "U" and a > 1:
	a -= 1
	if i == "D" and a < n:
	a += 1
	print('(', a, ', ', b, ')')

view raw 상하좌우 문제 - 본인 버전 hosted with ❤ by GitHub

이러한 유형은 일련의 명령을 따라서 개체를 차례대로 이동시킨다는 점에서 시뮬레이션 유형으로 분류되며 구현이 중요한 대표적인 문제 유형이다. 

 

2. 시각

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

 

	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)

view raw 동빈님 코드 hosted with ❤ by GitHub

	n = int(input())
	count = 0
	sec = 0
	minute = 0
	hour = 0
	while True:
	sec += 1
	if sec == 60:
	sec = 0
	minute += 1
	if minute == 60:
	minute = 0
	hour += 1
	if hour > n:
	break
	if "3" in str(sec) + str(minute) + str(hour): # 시, 분, 초를 문자열로 만들어 합친 뒤 3이 있으면 카운트
	count += 1
	print(count)

view raw 시각 문제 hosted with ❤ by GitHub

이러한 유형은 완전 탐색 유형으로 분류되기도 한다. 완전 탐색 알고리즘은 가능한 경우의 수를 모두 검사해보는 탐색 방법이다. 일반적으로 완전 탐색 유형은 비효율적인 시간 복잡도를 가지고 있으므로 데이터 개수가 큰 경우에 정상적으로 작동하지 않을 수 있다. 때문에 주로 데이터가 100만개 이하일 때 완전 탐색을 이용한다.

 

 

3. 왕실의 나이트

8x8 좌표 평면의 정원의 한 칸에 나이트가 서 있다. 나이트는 다음과 같이 2가지 방법으로만 움직일 수 있다. 

1. 수평으로 2칸 이동한 뒤 수직으로 한 칸 이동

2. 수직으로 2칸 이동한 뒤 수평으로 한 칸 이동

나이트의 위치가 주어졌을 때 나이트가 이동할 수 있는 경우의 수를 출력하는 프로그램을 작성하시오

입력 예시: a1

 

	input_data = input()
	row = int(input_data[1])
	column = ord(input_data[0]) - 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)

view raw 왕실의 나이트 - 동빈님 버전 hosted with ❤ by GitHub

	loc = input()
	a = []
	a.append(loc[0])
	if a[0] == 'a':
	a[0] = '1'
	elif a[0] == 'b':
	a[0] = '2'
	elif loc[0] == 'c':
	a[0] = '3'
	elif a[0] == 'd':
	a[0] = '4'
	elif loc[0] == 'e':
	a[0] = '5'
	elif a[0] == 'f':
	a[0] = '6'
	elif a[0] == 'g':
	a[0] = '7'
	elif a[0] == 'h':
	a[0] = '8'
	count = 0
	if int(a[0]) + 2 < 9 and int(loc[1]) + 1 < 9:
	count += 1
	if int(a[0]) + 2 < 9 and int(loc[1]) - 1 > 0:
	count += 1
	if int(a[0]) + 1 < 9 and int(loc[1]) + 2 < 9:
	count += 1
	if int(a[0]) -1 > 0 and int(loc[1]) + 2 < 9:
	count += 1
	if int(a[0]) - 2 > 0 and int(loc[1]) + 1 < 9:
	count += 1
	if int(a[0]) - 2 > 0 and int(loc[1]) - 1 > 0:
	count += 1
	if int(a[0]) + 1 < 9 and int(loc[1]) - 2 > 0:
	count += 1
	if int(a[0]) - 1 > 0 and int(loc[1]) - 2 > 0:
	count += 1
	print(count)

view raw 왕실의 나이트 - 본인 버전 hosted with ❤ by GitHub

ord() :  특정 문자를 아슽키코드로 변환

 

4. 게임 개발

* map() 함수는 map 클래스를 리턴하므로 list()로 캐스팅해줘야 한다.

*global = 전역변수 선언

*[[0] * m for _ in range(n)] = 리스트 내포 또는 리스트 컴프리헨션

맵:  N행 x M열

1. 현태 위치에서 현재 방향을 기준으로 왼쪽 방향부터 차례대로 갈 곳을 정한다. 

2. 캐릭터의 바로 왼쪽 방향에 아직 가보지 않은 칸이 존재한다면, 왼쪽 방향으로 회전한 다음 왼쪽으로 한 칸 전진. 왼쪽 방향에 가보지 않은 칸이 없다면 회전만 하고 1단계로 되돌아감.

3. 만약 네 방향 모두 이미 가본 칸이거나 바다인 경우 방향을 유지한 채로 뒤로 1칸 이동. 이때 뒤쪽 방향이 바다인 경우 움직임을 멈춘다. 

이때 캐릭터가 방문한 칸의 수를 출력하시오

 

	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 #현재 위치 방문 처리, x가 행, y가 열
	#전체 맵 정보 입력받기
	array = []
	for i in range(n):
	array.append(list(map(int, input().split())))
	# 북, 동, 남, 서 방향 정의. 방향 번호와 인덱스 번호 일치시킴
	dx = [-1, 0, 1, 0]
	dy = [0, 1, 0, -1]
	#왼쪽으로 회전. 북-서-남-동 0 3 2 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 == 4: # 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)

view raw 게임 개발 - 동빈님 버전 hosted with ❤ by GitHub