'이것이 코딩 테스트다 with 파이썬(나동빈)' 책과 이코테 유튜브 강의 영상을 기반으로 작성한 글입니다.
👩🏫 구현이란?
코딩테스트에서 구현(Implementation)이란 '머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정'이다. 흔히 문제 해결 분야에서 구현 유형의 문제는 '풀이를 떠올리는 것은 쉽지만 소스 코드로 옮기기 어려운 문제'를 의미한다.
구현하기 어려운 문제로는 이런 것들이 있다.
1. 알고리즘은 간단한데 코드가 지나칠 만큼 길어지는 문제
2. 특정 소수점 자리까지 출력해야 하는 문제
3. 문자열이 입력으로 주어졌을 때 한 문자 단위로 끊어서 리스트에 넣어야 하는(파싱을 해야 하는) 문제
구현에는 완전 탐색 유형과 시뮬레이션 유형이 있다.
완전 탐색은 모든 경우의 수를 주저 없이 다 계산하는 해결 방법을 의미하고, 시뮬레이션은 문제에서 제시한 알고리즘을 한 단계씩 차례대로 직접 수행해야 하는 문제 유형을 의미한다.
또한 라이브러리에 대해 잘 알고 있는 것도 중요하다.
✏️예제1. 상하좌우
- 문제
여행가 A는 N X N 크기의 정사각형 공간 위에 서있다. 이 공간은 1 X 1 크기의 정사각형으로 나누어져 있다. 가장 왼쪽 위 좌표는 (1, 1)이며, 가장 오른쪽 아래 좌표는 (N X N)에 해당한다. 여행가 A는 상, 하, 좌, 우 방향으로 이동할 수 있으며, 시각좌표는 항상 (1, 1)이다. 우리 앞에는 여행가 A가 이동할 계획이 적힌 계획서가 놓여 있다.
계획서에는 하나의 줄에 띄어쓰기를 기준으로 하여 L, R, U, D 중 하나의 문자가 반복적으로 적혀있다. 각 문자의 의미는 다음과 같다.
- L : 왼쪽으로 한 칸 이동
- R : 오른쪽으로 한 칸 이동
- U : 위로 한 칸 이동
- D : 아래로 한 칸 이동
이때 여행가 A가 N X N 크기의 정사각형 공간을 벗어나는 움직임은 무시된다.
계획서가 주어졌을 때 여행가 A가 최종적으로 도착할 지점의 좌표를 출력하는 프로그램을 작성해라.
입력 조건 :
1. 첫째 줄에 공간의 크기를 나타내는 N이 주어진다.(1<=N<=100)
2. 둘째 줄에 여행가 A가 이동할 계획서 내용이 주어진다. (1<=이동횟수<=100)
출력 조건 : 첫째 줄에 여행가 A가 최종적으로 도착할 지점의 좌표(X, Y)를 공백으로 구분하여 출력한다.
입력 예시 : 5 / R R R U D D
출력 예시 : 3 4
- 코드💻
n = int(input())
x, y = 1, 1 #시작 좌표
plans = input().split()
#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)
- 해설📖
이 문제를 요구사항대로 구현하면 연산횟수는 이동횟수에 비례하게 된다. 예를 들어 이동횟수가 N번인 경우 시간복잡도는 O(N)이다. 따라서 이 문제의 시간복잡도는 매우 넉넉한 편이다.
이 문제는 일련의 명령에 따라 개체를 차례대로 이동시킨다는 점에서 시뮬레이션 유형으로 분류되며 구현이 중요한 대표적인 문제 유형이다.
dx = [0, 0, -1, 1]
-> x좌표는 윗칸으로 가면 1씩 감소되고, 아래칸으로 가면 1씩 증가하기 때문. 같은 가로줄 내에서는 변화 없음.
dy = [-1, 1, 0, 0]
-> y좌표는 왼쪽칸으로 가면 1씩 감소되고, 오른쪽칸으로 가면 1씩 증가하기 때문. 같은 세로줄 내에서는 변화 없음.
✏️예제2. 시각
- 문제
정수 N이 입력되면 00시 00분 00초부터 N시 59분 59초까지의 모든 시각 중에서 3이 하나라도 포함되는 모든 경우의 수를 구하는 프로그램을 작성해라.
입력 조건 : 첫째 줄에 정수 N이 입력된다. (0 <= N <= 23)
출력 조건 : 00시 00분 00초부터 N시 59분 59초까지의 모든 시각 중에서 3이 하나라도 포함되는 모든 경우의 수를 출력한다.
입력 예시 : 5
출력 예시 : 11475
- 코드💻
n = int(input())
count = 0
for hour in range(n+1):
for minute in range(60):
for second in range(60):
# 매 시각 안에 '3'이 포함되어 있다면 카운트 증가
# 시분초를 합친 str 내에 '3'이 포함되어 있는지 확인
if '3' in str(hour) + str(minute) + str(second):
count += 1
print(count)- 해설📖
이 문제는 모든 시각의 경우를 하나씩 모두 세서 쉽게 풀 수 있는 문제이다. 왜냐하면 하루는 86,400초로 경우의 수가 86,400가지밖에 존재하지 않기 때문이다. 파이썬에서는 1초에 2천만번 연산이 가능하다고 가정하는 것이 좋다. 그렇기 때문에 시간 제한 내에 풀 수 있다. 따라서 단순히 시각을 1씩 증가시키며 3이 하나라도 포함되어 있는지 확인하면 된다. 전체 시, 분, 초에 대한 경우의 수는 24x60x60이며 3중 반복문을 이용해 계산할 수 있다.
이러한 유형의 문제는 완전 탐색 유형으로 분류된다. 완전탐색 알고리즘은 가능한 경우의 수를 모두 검사해보는 탐색 방법이다. 일반적으로 완전 탐색 알고리즘은 비효율적인 시간 복잡도를 가지고 있으므로 데이터 개수가 큰 경우에 정상적으로 동작하지 않을 수도 있다. 그래서 일반적으로 문제를 풀 때에 확인(탐색)해야 할 전체 데이터의 개수가 100만개 이하일 때 완전 탐색을 사용하면 적절하다.
이 소스 코드에서는 매 시각을 문자열로 바꾼 뒤 문자열에 '3'이 포함됐는지 검사한다. 예를 들어 03시 20분 35초일 때를 확인한다면, 이를 '032035'로 만들어서 '3'이 여기에 포함되었는지를 체크하는 방식을 이용하는 것이다.
📝문제1. 왕실의 나이트
- 문제
P.115 참고
- 나의 코드💻
now = input()
x, y = now[0], now[1]
col = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h']
row = ['1', '2', '3', '4', '5', '6', '7', '8']
move_types = []
while True:
for i in range(len(col)):
if x == col[i]:
x =
if x < col[0] or y < row[0] or x > col[7] or y > row[7]:
continue
print(x, y)-> 실패,,
- 정답 코드💻
now = input()
row = int(now[1])
col = int(ord(now[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] #x
next_col = col + step[1] #y
#해당 위치로 이동이 가능하다면 카운트 증가
if next_row >= 1 and next_row <= 8 and next_col >= 1 and next_col <= 8:
result += 1
print(result)- 비교 분석📖
나이트의 8가지 경로를 하나씩 확인하며 각 위치로 이동이 가능한지 확인한다. 리스트를 이용해 8가지 방향에 대한 방향 벡터를 정의한다.
가능한 8가지 방향에 대해 이해가 잘 안가서 직접 그려보며 이해했다.
col = int(ord(now[0])) - int(ord('a')) + 1
-> ord(a)는 문자의 유니코드 값을 돌려주는 함수이다.
'a'~h'를 1~8의 숫자로 바꿔주는 문장이다.
나는 a~h, 1~8을 각각 리스트에 넣어 문제를 풀려고 했는데 하다보니 뭔가 이상하고, 끝도 없이 길어질 것 같아 중간에 멈췄다,, 풀이를 보니 a~h를 1~8의 수로 대응시키고, 가능한 방향 벡터를 2차원 리스트에 넣는 방법을 사용해 문제를 풀 수 있었다. 이런 방식을 잘 기억해 나중에 문제에 또 적용시켜봐야겠다.
📝문제2. 게임 개발
- 문제
P.118 참고
- 나의 코드💻
코드를 입력하세요- 정답 코드💻
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 == 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)- 비교 분석📖
조금 많이,, 어려웠다. 사실 문제도 이해가 잘 안 가서 여러번 읽어봤다,, 정답 코드를 보며 이해했다,, 사실 아직도 이해가 가지 않는 것 같기도,,?
일반적으로 방향을 설정해서 이동하는 문제 유형에서는 dx, dy라는 별도의 리스트를 만들어 방향을 정하는 것이 효과적이다. 예를 들어 이 답안 예시 코드에서는 현재 캐릭터가 북쪽을 바라보고 있을 때는 북쪽으로 이동하기 위해 x좌표와 y좌표를 각각 dx[0], dy[0]만큼 더한다. 다시 말해 현재 위치에서 (-1, 0)만큼 이동시키는 것이다. 이처럼 코드를 작성하면, 반복문을 이용하여 모든 방향을 차례대로 확인할 수 있다는 점에서 유용하다.
그리고 답안 예시 코드에서는 리스트 컴프리헨션 문법을 사용해 2차원 리스트를 초기화했다. 파이썬에서 2차원 리스트를 선언할 때는 컴프리헨션을 이용하는 것이 효율적이다.
또한 왼쪽으로 회전하는 함수 turn_left()에서 global 키워드를 사용했는데, 이는 정수형 변수인 direction 변수가 함수 바깥에서 선언된 전역변수이기 때문이다.
3개의 댓글
안녕하세요, 김덕우입니다! 제 블로그 댓글 보고 왔는데, 1번에 리스트 만들고 대응시켜서 푼 게 정말 똑같군요!! 저희 어쨌든 풀긴 풀었으니까(?) 코드 개선하는 건 문제 더 풀면서 배워나가요!!! 저도 오늘 너무 어려웠습니다... 너무 고생하셨어요!!!!
안녕하세요 알고리줌입니다 글 잘봤습니다!
저는 벨로그를 시작한지 그래도 꽤 됐는데
최근에 시작하신 웃음님이 저보다 벨로그 활용을 잘하시는것같아 부럽습니다...!
깔끔하게 글 정리 잘해주셔서 저도 많이 참고하고 갑니다
오늘 수고하셨습니다~~~