구현이란?
- 코딩 테스트에서 구현이란 '머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정'
- 사실상 어떤 문제를 풀든 간에 소스코드를 작성하는 과정은 필수이므로, 구현 문제 유형은 모든 범위의 문제 유형을 포함하는 개념이라고 할 수 있음
- 따라서 흔히 말하는 구현문제는 '풀이는 떠올렸지만 소스코드로 옮기기는 어려운 문제를 뜻함'!
ex) 알고리즘은 간단하나, 소스코드가 지나칠만큼 길어지는 문제
- 특정 소수점 자리까지 출력해야하는 문제
- 문자열이 입력으로 주어졌을 대 한 문자 단위로 끊어서 리스트에 넣어야 하는(파싱을 해야하는) 문제 등 ... - 대체로 사소한 조건이 많을수록, 코드로 구현하기가 까다로움
- 대표적으로 구현 내에는 완전 탐색이나, 시뮬레이션 유형을 구현 유형으로 포함하기도 함
✔ 완전 탐색: 모든 경우의 수를 주저 없이 다 계산하는 해결 방법
✔ 시뮬레이션: 문제에서 제시한 알고리즘을 한 단계씩 차례대로 직접 수행해야 하는 유형
예제 1번 ✏ 상하좌우
여행가 A는 N×N 크기의 정사각형 공간 위에 서있다. 이 공간은 1×1 크기의 정사각형으로 나누어져 있다. 가장 왼쪽 위 좌표는 (1, 1)이며, 가장 오른쪽 아래 좌표는 (N, N)에 해당한다. 여행가 A는 상, 하, 좌, 우 방향으로 이동할 수 있으며, 시작 좌표는 항상 (1, 1)이다. 우리 앞에는 여행가 A가 이동할 계획이 적힌 계획서가 놓여 있다.
계획서에는 여행가가 움직일 방향이 적혀있고, L(Left) / R(Right) / U(Up) / D(Down) 총 4가지 방향으로 1칸씩 움직일 수 있다. 하지만 여행가가 N×N 크기의 정사각형 공간을 벗어나는 움직임은 무시된다. 전체 공간의 크기인 N과 계획서가 주어졌을 때, 여행가 A가 최종적으로 도착할 지점의 좌표를 출력하는 프로그램을 작성하시오.
[입력 예시]
5
R R R U D D
[출력 예시]
3 4
def checkBoundary(N, dir, pos):
if dir == 'R':
if pos[1] < N:
return [0, 1]
elif dir == 'L':
if pos[1] > 1:
return [0, -1]
elif dir == "U":
if pos[0] > 1:
return [-1, 0]
elif dir == 'D':
if pos[0] < N:
return [1, 0]
return [0, 0]
N = int(input())
plan = list(map(str, input().split()))
pos = [1, 1] # starting point
for dir in plan:
result = checkBoundary(N, dir, pos)
pos = [a+b for a,b in zip(pos, result)]
print(pos[0], pos[1])- 본 문제는 문제에서 지시한 대로 구현하면 풀리는 '시뮬레이션' 유형에 포함된다
- 또한 이동 횟수가 N일 경우 시간복잡도 또한 O(N)으로, 시간복잡도도 넉넉한 편에 속한다
- 이러한 난이도가 낮은 문제는 오히려 모두가 맞추는 문제이기 때문에, 합격을 좌우하는 중요한 문제이기도 하다
예제 2번 ✏ 시각
정수 N이 입력되면 00시 00분 00초부터 N시 59분 59초까지 모든 시각 중에서 3이 하나라도 포함되는 모든 경우의 수를 구하는 프로그램을 작성하시오
[입력 예시]
5
[출력 예시]
11475
N = int(input())
cnt = 0
for h in range(N+1):
for m in range(60):
for s in range(60):
if '3' in str(h)+str(m)+str(s):
cnt +=1
print(cnt)- 본 문제는 모든 시각의 경우를 하나씩 모두 세서 쉽게 풀 수 있는 문제이다
- 수학적으로 풀려고 하는 것도 좋으나, 자칫하면 오류가 발생할 수도 있기 때문에, 문제 그대로 구현하고 추후에 시간이 남을 때 시간복잡도를 개선하기 위해 수학식을 기반으로 한 코드로 바꾸는 것이 좋다
- 위 문제는 완전 탐색 유형으로 분류된다
→ 그러나 완전 탐색 유형은 시간 복잡도가 비효율적이므로, 탐색해야 하는 데이터 개수가 100만개 이하일 때 완전 탐색을 이용하는 것이 적절하다
예제 3번 ✏ 왕실의 나이트
8×8 체스판에서 나이트 말이 이동 가능한 경로의 수를 구하시오. 단 나이트는 체스판 위를 벗어날 수 없으며, 나이트가 처음 배치된 위치는 문자로 주어진다 (열 정보 a~h, 행 정보 1~8)
※ 나이트는 { 수평 2칸 이동 뒤 수직 1칸 이동 } 혹은 { 수직 2칸 이동 뒤 수평 1칸 이동 } 가능
[입력 예시]
a1
[출력 예시]
2
order = input()
# directions of knights
dir_list = [[1, 2],
[-1, 2],
[1, -2],
[-1, -2],
[2, 1],
[2, -1],
[-2, 1],
[-2, -1]]
# translate str position info to int info
order_table = order.maketrans('abcdefgh', '12345678')
order = order.translate(order_table)
order = [int(i) for i in order]
# calculate possible moving dir
cnt = 0
for dir in dir_list:
expect_pos = [a+b for a, b in zip(order, dir)]
if expect_pos[0] >= 1 and expect_pos[0] <= 8 and expect_pos[1] >= 1 and expect_pos[1] <= 8:
cnt += 1
print(cnt)- 본 문제는 위의 예제 1번 - 상하좌우와 유사하다.
- 이 또한 문제에서 제안하는 조건을 그대로 구현하여, 움직일 수 있는 공간을 직접 세보는 시뮬레이션 유형에 속한다고 할 수 있다
- 우선 나이트가 이동 가능한 경로를 모두 리스트에 저장해둔다
- 그리고 입력받은 현재 위치를 숫자 좌표값으로 변환한 뒤, 이동 가능한 방향을 모두 더해 이동할 위치값을 계산한다
- 이동할 위치값이 체스판 내에 있다면 카운트를 증가시키고, 그렇지 않으면 넘어가도록 한다.
예제 4번 ✏ 게임 개발
문제 내용이 상당히 길기 때문에, 문제 내용과 조건을 상세하게 잘 써주신 다른 블로거 분의 포스트 링크를 첨부해놓겠습니다! 멜론님 감사합니다 :) https://melon-is-jy.tistory.com/14
[이것이 코딩 테스트다] 구현 <3. 게임 개발>
📚[실전 문제] [문제] 현민이는 게임 캐릭터가 맵 안에서 움직이는 시스템을 개발 중이다. 캐릭터가 있는 장소는 1 X 1 크기의 정사각형으로 이뤄진 N X M 크기의 직사각형으로, 각각의 칸은 육지
melon-is-jy.tistory.com
[입력 예시]
4 4
1 1 0
1 1 1 1
1 0 0 1
1 1 0 1
1 1 1 1
[출력 예시]
3
# get base info
N, M = map(int, input().split()) # N is ver and M is hor
x, y, dir = map(int, input().split())
# make map base on N, M input
game_map = []
for i in range(N):
row = list(map(int, input().split()))
game_map.append(row)
cur_pos = [x, y]
dic_list = [0, 3, 2, 1]
dic = {
0: [-1, 0], # north
1: [0, 1], # east
2: [1, 0], # south
3: [0, -1] # west
}
def turn_left(dir):
left = dir
if left == 0:
left = 3
else:
left -= 1
return left
def get_backdir(dir):
if dir == 0:
return 2
elif dir == 2:
return 0
elif dir == 1:
return 3
elif dir == 3:
return 1
else:
print("Not proper value for backdir")
# starting point
print("[START]:", cur_pos)
game_map[cur_pos[0]][cur_pos[1]] = 2 # already gone
count = 1
while True:
before = cur_pos
# check the way and move
for _ in range(4):
dir = turn_left(dir)
expect = [a + b for a, b in zip(cur_pos, dic[dir])]
if game_map[expect[0]][expect[1]] == 1:
print("sea", expect)
elif game_map[expect[0]][expect[1]] == 2:
print("already gone", expect)
else:
print("[MOVE]: land", expect)
game_map[expect[0]][expect[1]] = 2
cur_pos = expect
count += 1
break
# if there's no way to move - check the backward
if before == cur_pos:
back = [a + b for a, b in zip(cur_pos, dic[get_backdir(dir)])]
if game_map[back[0]][back[1]] == 1: # can't move - END
print("[END]")
break
else: # move to backward
print("[BACK]:", cur_pos, "to", back)
cur_pos = back
print("end:", cur_pos)
print("count:", count)
※ 위 코드들은 제가 풀이한 것으로 모든 상황에 대해서 정답이 나오지 않을 수도 있습니다! ※
본 포스트는 '이것이 취업을 위한 코딩테스트다 with 파이썬' 책 내용을 토대로 작성되었습니다
