2-1. 구현 개념 & 실전 문제

Speedwell🍀·2022년 3월 15일

코딩테스트

이것이 코딩 테스트다

목록 보기

3/15

구현 (implementation)

: 머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정

문제 해결 분야에서 구현 유형의 문제는

풀이를 떠올리는 것은 쉽지만 소스코드로 옮기기 어려운 문제
피지컬(언어 문법에 능숙, 빠른 타자)을 요구하는 문제

어떤 문제가 구현하기 어려운 문제?

알고리즘은 간단한데 코드가 지나칠 만큼 길어지는 문제
특정 소수점 자리까지 출력해야 하는 문제
문자열이 입력으로 주어졌을 때 한 문자 단위로 끊어서 리스트에 넣어야 하는(파싱을 해야 하는) 문제

등등

➡️ 사소한 조건 설정이 많은 문제일수록 까다로움

📌라이브러리를 잘 사용할 수 있어야 함

예) N개의 원소가 들어 있는 리스트에서 R개의 원소를 뽑아 한 줄로 세우는 모든 경우(순열)를 구해야 하는 문제 ➡️ itertools와 같은 표준 라이브러리 사용하면 쉽게 할 수 있다!

이 책에서 '구현' 유형은 완전 탐색, 시뮬레이션을 포함한다.

완전 탐색 (Brute Forcing)

: 모든 경우의 수를 주저 없이 다 계산하는 해결 방법

시뮬레이션

: 문제에서 제시한 알고리즘을 한 단계씩 차례대로 직접 수행

구현 시 고려해야 할 제약 사항

파이썬을 사용하면 자료형의 표현 범위 제한에 대해 깊게 이해하지 않아도 괜찮다.

📌 하지만, 실수형 변수는 다른 언어와 마찬가지로 유효숫자에 따라서 연산 결과가 원하는 값이 나오지 않을 수 있다는 점을 기억하자!

메모리, 시간 제한

대체로 코딩 테스트에서는 메모리를 128~512MB로 제한한다.

파이썬은 C/C++에 비해 동작 속도가 느리다. ➡️ 1초에 2,000만 번의 연산을 수행한다고 가정하고 풀면 실행 시간 제한에 안정적이다.

구현 문제에 접근하는 방법

실무에서 파이썬으로 프로그램을 개발할 때는 GPU를 연동하며, 반복적인 행렬 계산을 요구하는 복잡한 수학 문제를 풀 때는 C 언어로 작성된 파이썬 코어 소프트웨어가 동작한다. ➡️ 파이썬을 사용한 프로그램이 항상 동작 속도가 느린 것은 아니다!

하지만 알고리즘 코딩 테스트 환경에서는 GPU 연산을 쓰는 경우가 ❌

API 개발 문제 또한 구현 유형과 상당히 맞닿아 있다.

예시) 카카오 공채 때, 카카오 문제 풀이 서버와 통신하는 프로그램 모듈을 작성하는 API 개발 문제가 출제되었었다. ➡️ 파이썬에 있는 매우 간결하고 직관적인 코드의 라이브러리 사용하면 유리

Pypy3

파이썬3 문법을 그대로 지원
대부분 파이썬3보다 실행 속도가 ⬆️
- 반복문이 많을수록 Pypy3와 파이썬3의 속도 차이 ⬆️
- 대략 1초에 2,000만 번~1억 번 정도의 연산 처리 가능

📌 코딩 테스트 환경에서 Pypy3을 지원한다면 이를 이용하도록 하자!!

삼성전자 공채에서는 코딩 테스트 채점에 Pypy3 이용! 지원자가 파이썬3로 제출하면 기본으로 Pypy3을 이용해서 채점한다.

예제

1) 상하좌우

난이도: ⭐
풀이 시간: 15분
시간 제한: 1초
메모리 제한: 128MB

여행가 A는 N x N 크기의 정사각형 공간 위에 서 있다. 이 공간은 1x1 크기의 정사각형으로 나누어져 있다. 가장 왼쪽 위 좌표는 (1,1)이며, 가장 오른쪽 아래 좌표는 (N,N)에 해당한다. 여행가 A는 상,하,좌,우 방향으로 이동할 수 있으며, 시작 좌표는 항상 (1,1)이다. 우리 앞에는 여행가 A가 이동할 계획이 적힌 계획서가 놓여 있다.

계획서에는 하나의 줄에 띄어쓰기를 기준으로 하여 L, R, U, D 중 하나의 문자가 반복적으로 적혀있다.

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

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

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

입력 조건

첫째 줄에 공간의 크기를 나타내는 N이 주어진다. (1<=N<=100)
둘째 줄에 여행가 A가 이동할 계획서 내용이 주어진다. (1<=이동횟수<=100)

출력 조건

첫째 줄에 여행가 A가 최종적으로 도착할 지점의 좌표 (X, Y)를 공백으로 구분하여 출력한다.

# 입력 예시
5
R R R U D D # U는 공간을 벗어나는 움직임이므로 무시
# 출력 예시
3 4

<해설>

연산 횟수는 이동 횟수에 비례
시뮬레이션 유형
- 일련의 명령에 따라서 개체를 차례대로 이동시키기 때문
- 교재나 사이트마다 다르게 일컬을 수 있다. - 코딩 테스트에서의 시뮬레이션/구현/완전 탐색 유형은 서로 유사한 점이 많다는 정도로만 기억하기.

# N을 입력받기
n = int(input())
x, y = 1, 1
plans = input().split()

# L, R, U, D에 따른 이동 방향
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
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)

2) 시각

난이도: ⭐
풀이 시간: 15분
시간 제한: 2초
메모리 제한: 128MB

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

입력 조건

첫째 줄에 정수 N이 입력된다. (0<=N<=23)

출력 조건

00시 00분 00초부터 N시 59분 59초까지의 모든 시각 중에서 3이 하나라도 포함되는 모든 경우의 수를 출력한다.

<해설>

모든 시각의 경우를 하나씩 모두 세서 쉽게 풀 수 있는 문제
➡️ 단순히 시각을 1씩 증가시키면서 3이 하나라도 포함되어 있는지 확인하면 된다.
➡️ 3중 반복문 (24 x 60 x 60)

이 문제는 완전 탐색(Brute Forcing) 유형

가능한 경우의 수를 모두 검사해보는 탐색 방법
비효율적인 시간 복잡도
- 데이터 개수가 큰 경우에 정상적으로 작동하지 않을 수 있음
- 확인/탐색해야 할 전체 데이터의 개수가 100만 개 이하일 때 사용해야 적절

📌매 시각을 문자열로 바꾼 다음 문자열에 '3'이 포함됐는지 검사

예를 들어 03시 20분 35초일 때를 확인한다면, 이를 '032035'로 만들어서 3이 포함되어 있는지 체크

# H를 입력받기
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)

실전 문제

1) 왕실의 나이트

난이도: ⭐
풀이 시간: 20분
시간 제한: 1초
메모리 제한: 128MB

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

수평으로 두 칸 이동한 뒤에 수직으로 한 칸 이동
수직으로 두 칸 이동한 뒤에 수평으로 한 칸 이동

이처럼 8x8 좌표 평면상에서 나이트의 위치가 주어졌을 때 나이트가 이동할 수 있는 경우의 수를 출력하는 프로그램을 작성하시오. 이때 왕실의 정원에서 행 위치를 표현할 때는 1부터 8로 표현하며, 열 위치를 표현할 때는 a부터 h로 표현한다.

입력 조건

첫째 줄에 8x8 좌표 평면상에서 현재 나이트가 위치한 곳의 좌표를 나타내는 두 문자로 구성된 문자열이 입력된다. 입력 문자는 a1처럼 열과 행으로 이뤄진다.

출력 조건

첫째 줄에 나이트가 이동할 수 있는 경우의 수를 출력한다.

# 입력 예시
a1
# 출력 예시
2

예를 들어 만약에 나이트가 a1부터 있을 때 이동할 수 있는 경우의 수는 다음 2가지이다.

오른쪽으로 두 칸 이동 후 아래로 한 칸 이동하기(c2)
아래로 두 칸 이동 후 오른쪽으로 한 칸 이동하기(b3)

a1의 위치는 좌표 평면에서 구석의 위치에 해당하며 나이트는 정원의 밖으로는 나갈 수 없기 때문이다.

만약 나이트가 c2에 위치해 있다면 나이트가 이동할 수 있는 경우의 수는 6가지이다.

<해설>

나이트가 이동할 수 있는 경로를 하나씩 확인하여 이동하면 된다는 점에서 앞서 다루웠던 '상하좌우' 문제와 유사하지만, 8x8 좌표 평면을 벗어나지 않도록 꼼꼼하게 검사하는 과정이 필요하다.

나이트의 이동 경로를 steps 변수에 넣는다면, 문제의 2가지 규칙에 따라
steps = [(-2, -2), (-1, -2), (1, -2), (2, -1), (2, 1), (1, 2), (-1, 2), (-2, 1)]

현재 위치를 기준으로 아래쪽/오른쪽은 양수, 위쪽/왼쪽은 음수의 값을 대입했다.

➡️ 이제 나이트의 현재 위치가 주어지면 현재 위치에서 이동 경로를 더한 다음, 8x8 좌표 평면에 있는지 확인하면 된다. 이는 반복문으로 처리한다.

더 까다롭게 문제를 출제한다면 입력 문자가 ㅁ1과 같은 열과 행 형태가 아닌, 1a와 같은 행과 열 형태로 들어왔을 때의 예외 처리를 요구할 수 있다.

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

# 나이트가 이동할 수 있는 8가지 방향 정의
steps = [(-2, -2), (-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)

앞서 '상하좌우' 문제에서는 dx, dy 리스트를 선언하여 이동할 방향을 기록하였고, 이번 문제에서는 steps 변수가 dx, dy 변수의 기능을 대신하여 수행했다.

📌 2가지 형태 모두 자주 사용되므로 꼭 알아두자!!

2) 게임 개발

난이도: ⭐⭐
풀이 시간: 40분
시간 제한: 1초
메모리 제한: 128MB

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

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

캐릭터의 움직임을 설정하기 위해 정해 놓은 매뉴얼은 아래와 같다.

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

위 과정을 반복적으로 수행하면서 캐릭터의 움직임에 이상이 있는지 테스트하려고 한다. 매뉴얼에 따라 캐릭터를 이동시킨 뒤에, 캐릭터가 방문한 칸의 수를 출력하는 프로그램을 만드시오.

입력 조건

첫째 줄에 맵의 세로 크기 N과 가로 크기 M을 공백으로 구분하여 입력한다. (3<=N, M<=50)
둘째 줄에 게임 캐릭터가 있는 칸의 좌표(A, B)와 바라보는 방향 d가 각각 서로 공백으로 구분하여 주어진다. 방향 d의 값으로는 다음과 같이 4가지로 존재한다.
- 0 : 북쪽
- 1 : 동쪽
- 2 : 남쪽
- 3 : 서쪽
셋째 줄부터 맵이 육지인지 바다인지에 대한 정보가 주어진다. N개의 줄에 맵의 상태가 북쪽부터 남쪽 순서대로, 각 줄의 데이터는 서쪽부터 동쪽 순서대로 주어진다. 맵의 외곽은 항상 바다로 되어 있다.
- 0 : 육지
- 1 : 바다
처음에 게임 캐릭터가 위치한 칸의 상태는 항상 육지

출력 조건

첫째 줄에 이동을 마친 후 캐릭터가 방문한 칸의 수

# 입력예시
4 4      # 4x4 맵 생성
1 1 0    # (1,1)에 북쪽(0)을 바라보고 서 있는 캐릭터
1 1 1 1  # 첫 줄은 모두 바다
1 0 0 1  # 둘째 줄은 바다/육지/육지/바다
1 1 0 1  # 셋째 줄은 바다/바다/육지/바다
1 1 1 1  # 넷째 줄은 모두 바다

# 출력예시
3

<해설>

시뮬레이션 문제 ➡ 삼성전자 공채 코딩 테스트에서 자주 출제되는 대표적인 유형

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

📌 2차원 리스트를 선언할 때는 리스트 컴프리헨션을 이용하는 것이 효율적

# 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 == 4:
    nx = x - dx[direction]
    ny = y - dy[direction]
    # 뒤로 갈 수 있다면 이동하기
    if array[nx][m-ny] == 0:
      x = nx
      y = ny
    # 뒤가 바다로 막혀있는 경우
    else:
      break
    turn_time = 0

print(count)