[이것이 취업을 위한 코딩 테스트다] 구현(Implementation)
구현(Implementation)
- 머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정
특징
- 문제 길이가 길지만, 고차원적인 사고력을 요구하는 문제는 아님
- 표준 라이브러리를 숙지하고 있으면 부분적으로 코드를 쉽게 작성할 수 있음
- 두 가지 유형
- 완전 탐색 : 모든 경우의 수를 주저 없이 다 계산하는 해결 방법
- 시뮬레이션 : 문제에서 제시한 알고리즘을 한 단계씩 차례대로 직접 수행해야 하는 문제 유형
- 구현 시 채점 시스템의 제약사항을 고려하여 작성해야 함(대부분 시간제한 1초, 메모리 제한 128MB)
- 파이썬은 1초에 2,000만 번의 연산을 수행한다고 가정하여 시간 계산
- 예 : N이 1,000,000 일 때, 시간 복잡도가 O(NlogN)이면 약 2,000만번의 연산을 수행함
-
리스트 사용 시 메모리 사용량을 확인해야 함
데이터의 개수(리스트 길이) 메모리 사용량 1,000 4KB 1,000,000 4MB 10,000,000 40MB 32,000,000 128MB
- 파이썬은 1초에 2,000만 번의 연산을 수행한다고 가정하여 시간 계산
1. 연습문제
상하 좌우(시뮬레이션 유형)
여행가 A는 N X N 크기의 정사각형 공간 위에 서 있다. 이 공간은 1 X 1 크기의 정사각형으로 나누어져 있다. 가장 왼쪽 위 좌표는 (1, 1)이며, 가장 오른쪽 아래 좌표는 (N, N)에 해당한다. 여행가 A는 상, 하, 좌, 우 방향으로 이동할 수 있으며, 시작 좌표는 항상 (1, 1)이다. 우리 앞에는 여행가 A가 이동할 계획이 적힌 계획서가 놓여 있다.
계획서에는 하나의 줄에 띄어쓰기를 기준으 하여 L(왼쪽으로 한 칸), R(오른쪽으로 한 칸), U(위로 한 칸), D(아래로 한 칸) 중 하나의 문자가 반복적으로 적혀 있다.
여행가 A가 N X N 크기의 정사각형 공간을 벗어나는 움직임은 무시된다.
계획서가 주어졌을 때 여행가 A가 최종적으로 도착할 지점의 좌표를 출력하는 프로그램을 작성하시오.
- 시간 제한 : 1초
- 메모리 제한 : 128MB
- 입력 조건
- 1 <= N <= 100
- 1 <= 이동 횟수 <= 100
-> 이동 시 위치 계산을 위한 ‘좌표’를 리스트로 구현하여 하나의 반복문에서 계산하는 것이 핵심
def solution():
n = int(input())
x, y = 1, 1
plans = input().split()
dx = [0, 0, -1, 1] # (0, -1) : 왼쪽으로 한칸(y축 방향으로 한 칸)
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
return str(x) + " " + str(y)
# test case
# 5
# R R R U D D
print(solution())
# 3 4
시각(완전 탐색)
정수 N이 입력되면 00시 00분 00초부터 N시 59분 59초까지의 모든 시각 중에서 3이 하나라도 포함되는 모든 경우의 수를 구하는 프로그램을 작성하시오. 예를 들어 1을 입력했을 때 다음은 3이 하나라도 포함되어 있으므로 세어야 하는 시각이다.
- 00시 00분 03초
- 00시 13분 30초
반면에 다음은 3이 하나도 포함되어 있지 않으므로 세면 안 되는 시각이다.
- 00시 02분 55초
-
01시 27분 45초
- 시간 제한 : 2초
- 메모리 제한 : 128MB
- 입력 조건 : 0 < = N <= 23
-> 시간 복잡도가 O(N^3) = 86,400(24 X 60 X 60) 이므로 시간 제한 2초 내에 연산이 가능하다(2초 내 4천만 번의 연산을 수행할 수 있음) 3중 반복문으로 원소들을 문자열로 만들어 문자열 내 글자 포함여부를 체크하는 방법으로 푸는 것이 핵심
def solution():
h = int(input())
count = 0
for i in range(h + 1):
for j in range(60):
for k in range(60):
if '3' in str(i) + str(j) + str(k):
count += 1
return count
# test case
# 5
print(solution())
# 11475
2. 실전 문제
왕실의 나이트
행복 왕국의 왕실 정원은 체스판과 같은 8 X 8 좌표 평면이다. 왕실 정원의 특정한 한 칸에 나이트가 서 있다. 나이트는 매우 충성스러운 신하로서 매일 무술을 연마한다. 나이트는 말을 타고 있기 때문에 이동을 할 때에는 L자 형태로만 이동할 수 있으며 정원 밖으로는 나갈 수 없다. 나이트는 특정한 위치에서 다음과 같은 2가지 경우로 이동할 수 있다.
- 수평으로 두 간 이동한 뒤에 수직으로 한 칸 이동하기
- 수직으로 두 간 이동한 뒤에 수평으로 한 칸 이동하기
이처럼 8 X 8 좌표 평면상에서 나이트의 위치가 주어졌을 때 나이트가 이동할 수 있는 경우의 수를 출력하는 프로그램을 작성하시오. 이때 왕실의 정원에서 행 위치를 표현할 때는 1부터 8로 표현하며, 열 위치를 표현할 때는 a부터 h로 표현한다.
예를 들어 만약 나이트가 a1에 있을 때 이동할 수 있는 경우의 수는 다음과 같은 2가지이다. a1의 위치는 좌표 평면에서 구석의 위치에 해당하며 나이트는 정원의 밖으로는 나갈 수 없기 때문이다.
- 오른쪽으로는 두 칸 이동 후 아래로 한 칸 이동하기 (c2)
- 아래로 두 칸 이동 후 오른쪽으로 한 칸 이동하기 (b3)
나이트가 이동할 수 있는 경우의 수를 출력하시오.
- 시간 제한 : 1초
- 메모리 제한 : 128MB
- 입력 조건 : 두 문자(예 : a1)
-> 상하 좌우 문제와 마찬가지로 좌표를 이용한 다른 유형의 문제로, 좌표를 계산하는 것이 핵
def solution():
input_data = input()
row = int(input_data[1])
column = int(ord(input_data[0])) - int(ord('a')) + 1 # ord('a') = 97
steps = [(-2, -1), (-1, -2), (1, -2), (2, -1), (2, 1), (1, 2), (-1, 2), (-2, 1)]
result = 0
for step in steps:
next_row = row + step[0]
next_column = column + step[1]
if 1 <= next_row <= 8 and 1 <= next_column <= 8: # 범위를 벗어나지 않았을 때만 카운트
result += 1
return result
# test case
# a1
print(solution())
# 2
게임 개발(삼성전자 코딩 테스트에서 자주 출제되는 시뮬레이션 유형)
현민이는 게임 캐릭터가 맵 안에서 움직이는 시스템을 개발 중이다. 캐릭터가 있는 장소는 1 X 1 크기의 정사각형으로 이뤄진 N X M 크기의 직사각형으로, 각각의 칸은 육지 또는 바다이다. 캐릭터는 동서남북 중 한 곳을 바라본다.
맵의 각 칸은 (A, B)로 나타낼 수 있고, A는 북쪽으로부터 떨어진 칸의 개수, B는 서쪽으로부터 떨어진 칸의 개수이다. 캐릭터는 상하좌우로 움직일 수 있고, 바다로 되어 있는 공간에는 갈 수 없다. 캐릭터의 움직임을 설정하기 위해 정해 놓은 매뉴얼은 이러하다.
현재 위치에서 현재 방향을 기준으로 왼쪽 방향(반시계 방향으로 90도 회전한 방향)부터 차례대로 갈 곳을 정한다.
캐릭터의 바로 왼쪽 방향에 아직 가보지 않은 칸이 존재한다면, 왼쪽 방향으로 횐전한 다음 왼쪽으로 한 칸을 전진한다. 왼쪽 방향에 가보지 않은 칸이 없다면, 왼쪽 방향으로 회전만 수행하고 1단계로 돌아간다.
만약 네 방향 모두 이미 가본 칸이거나 바다로 되어 있는 칸인 경우에는, 바라보는 방향을 유지한 채로 한 칸 뒤로 가고 1단계로 돌아간다. 단, 이때 뒤쪽 방향이 바다인 칸이라 뒤로 갈 수 없는 경우에는 움직임을 멈춘다.
현민이는 위 과정을 반복적으로 수행하면서 캐릭터의 움직임에 이상이 있는지 테스트하려고 한다. 메뉴얼에 따라 캐릭터를 이동시킨 뒤에, 캐릭터가 방문한 칸의 수를 출력하는 프로그램을 만드시오.
이동을 마친 후 캐릭터가 방문한 칸의 수를 출력하라.
- 시간 제한 : 1초
- 메모리 제한 : 128MB
- 입력 조건
- 첫째 줄에 맵의 세로 크기 N과 가로 크기 M을 공백으로 구분하여 입력한다. (3 <= N, M <= 50)
-
둘째 줄에 게임 캐릭터가 있는 칸의 좌표 (A, B)와 바라보는 방햔 d가 각각 서로 공백으로 구분하여 주어진다. 방향 d의 값으로는 다음과 같이 4가지가 존재한다.
0 : 북쪽 1 : 동쪽 2 : 남쪽 3 : 서쪽
-
셋째 줄부터 맵이 육지인지 바다인지에 대한 정보가 주어진다. N개의 줄에 맵의 상태가 북쪽부터 남쪽 순서대로, 각 줄의 데이터는 서쪽부터 동쪽 순서대로 주어진다. 맵의 외각은 항상 바다로 되어 있다.
0 : 육지 1 : 바다
- 처음에 게임 캐릭터가 위치한 칸의 상태는 항상 육지이다.
-> 이전 문제들에 구체적으로 제한된 맵, 캐릭터가 회전하는 등의 룰이 추가 되었다. 게임을 개발한다고 생각하고, 손으로 그려가며 문제를 해결하는 것이 핵심
def solution():
n, m = map(int, input().split())
d = [[0] * m for _ in range(n)] # 방문 기록 행렬, 1 : 방문
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] # 북, 동, 남, 서
# 북쪽으로 1칸 = x 방향으로 -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: # 방문하지 않은 곳이라면, 현재 위치 Update
x = nx
y = ny
else:
break
turn_time = 0 # 회전 횟수 초기화
return count
# test case
# 4 4
# 1 1 0
# 1 1 1 1
# 1 0 0 1
# 1 1 0 1
# 1 1 1 1
print(solution())
# 3
Leave a comment