🔎 구현

코딩 테스트에서 구현이란 '머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정'
프로그래밍 언어의 문법을 정확히 알고 있어야 하며 문제의 요구사항에 어긋나지 않는 답안 코드를 실수 없이 작성해야 함

구현 유형의 문제 = '풀이를 떠올리는 것은 쉽지만 소스코드로 옮기기 어려운 문제'를 의미

보통 구현 유형의 문제는 사소한 입력 조건 등을 문제에서 명시해주며 문제의 길이가 꽤 긴 편임

해당 책에서는 완전 탐색, 시뮬레이션 유형을 모두 '구현' 유형으로 묶어서 다룸

• 완전탐색은 모든 경우의 수를 주저 없이 다 계산하는 해결 방법을 의미
• 시뮬레이션은 문제에서 제시한 알고리즘을 한 단계씩 차례대로 직접 수행해야 하는 문제 유형을 의미

---

⚠ 고려해야 할 메모리 제약 사항과 채점 환경

변수의 표현 범위

파이썬에서는 프로그래머가 직접 자료형을 지정할 필요가 없으며 매우 큰 수의 연산 또한 기본으로 지원함

파이썬에서 리스트 크기

파이썬에서 여러 개의 변수를 사용할 때는 리스트를 이용함
리스트를 이용할 때에 고려해야 할 사항 => 코딩 테스트의 메모리 제한 (대체로 128 ~ 512MB)
알고리즘 문제 중 때로는 수백만 개 이상의 데이터를 처리해야 하는 문제가 출제되곤 함 => 메모리 제한을 염두에 두고 코딩해야 함

int 자료형 데이터의 개수에 따른 메모리 사용량

데이터의 개수(리스트의 길이)	메모리 사용량
1,000	약 4KB
1,000,000	약 4MB
10,000,000	약 40MB

일반적인 코딩 테스트 수준에서는 메모리 사용량 제한보다 더 적은 크기의 메모리를 사용해야 한다는 점 정도만 기억하자

채점 환경

보통 접하는 코딩 테스트 환경은 아래와 같음

• 시간 제한: 1초
• 메모리 제한: 128MB

파이썬은 C/C++에 비해 동작 속도 느림
1초에 2,000만 번의 연산을 수행한다고 가정하면 크게 무리가 없다는 점만 기억하자
(Pypy3는 대략 1초에 2,000만 번에서 1억 번 정도의 연산을 처리할 수 있음)

알고리즘 문제를 풀 때는 시간 제한과 데이터의 개수를 먼저 확인한 뒤에 이 문제를 어느 정도의 시간 복잡도의 알고리즘으로 작성해야 풀 수 있을 것인지 예측할 수 있어야 함

---

✏️ 예제

📝 상하좌우

여행가 A는 N x N 크기의 정사각형 공간 위에 서 있음 (공간은 1 x 1 크기의 정사각형)
가장 왼쪽 위 좌표는 (1, 1), 가장 오른쪽 아래 좌표는 (N, N)에 해당함
여행가 A는 상(U), 하(D), 좌(L), 우(R) 방향으로 이동할 수 있으며, 시작 좌표는 (1, 1)
계획서에는 하나의 줄에 띄어쓰기를 기준으로 하여 L, R, U, D 중 하나의 문자가 반복적으로 적혀 있음
여행가 A가 N x N 크기의 정사각형 공간을 벗어나는 움직임은 무시됨

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

• 입력 조건
  - 첫째 줄에 공간의 크기를 나타내는 N이 주어짐 (1 ≤ N ≤ 100)
  - 둘째 줄에 여행가 A가 이동할 계획서 내용이 주어짐 (1 ≤ 이동 횟수 ≤ 100)
• 출력 조건
  - 첫째 줄에 여행가 A가 최종적으로 도착할 지점의 좌표 (X, Y)를 공백으로 구분하여 출력함

문제 해설

연산 횟수는 이동 횟수에 비례하게 됨, 이동 횟수가 N번인 경우 시간 복잡도는 O(N)
일련의 명령에 따라 개체를 차례대로 이동시킨다는 점에서 시뮬레이션 유형으로 분류됨
코딩 테스트에서의 시뮬레이션 유형, 구현 유형, 완전 탐색 유형은 서로 유사한 점이 많음
가장 난이도가 낮은 1 ~ 2번 문제 => 대부분 그리디 알고리즘이나 구현 문제

---

📝 시각

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

• 입력 조건
  - 첫째 줄에 정수 N이 입력됨 (0 ≤ N ≤ 23)
• 출력 조건
  - 00시 00분 00초부터 N시 59분 59초까지의 모든 시각 중에서 3이 하나라도 포함되는 모든 경우의 수를 출력함

문제 해설

모든 시각의 경우를 하나씩 세서 쉽게 풀 수 있는 문제 (하루는 86,400초이기에 모든 경우는 86,400가지밖에 존재하지 않기 때문)
  => 경우의 수가 100,000개도 되지 않으므로 파이썬에서 문자열 연산을 이용해 3이 시각에 포함되어 있는지 확인해도 시간 제한 2초 안에 문제 해결 가능
단순히 시각을 1씩 증가시키며 3이 하나라도 포함되어 있는지 확인하면 됨
시, 분, 초에 대한 경우의 수 => 24 x 60 x 60 => 3중 반복문

이러한 유형은 완전 탐색 유형으로 분류되기도 함
일반적으로 완전 탐색 알고리즘은 비효율적인 시간 복잡도를 가지고 있기에 데이터 개수가 큰 경우 정상적으로 동작하지 않을 수 있음
따라서, 확인(탐색)해야 할 전체 데이터 개수가 100만 개 이하일 때 완전 탐색을 사용하면 적절함

---

✏️ 실전 문제

📝 왕실의 나이트

왕실 정원은 8 x 8 좌표 평면, 행 위치를 표현할 때는 1 ~ 8, 열 위치를 표현할 때는 a ~ h로 표현
특정한 한 칸에 나이트가 서 있음, L자 형태로만 이동할 수 있으며 정원 밖으로는 나갈 수 없음
다음과 같은 2가지 경우로 이동할 수 있음
  1. 수평으로 두 칸 이동한 뒤에 수직으로 한 칸 이동하기
  2. 수직으로 두 칸 이동한 뒤에 수평으로 한 칸 이동하기

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

• 입력 조건
  - 첫째 줄에 8 x 8 좌표 평면상에서 현재 나이트가 위치한 곳의 좌표를 나타내는 두 문자로 구성된 문자열이 입력됨, 입력 문자는 a1처럼 열과 행으로 이뤄짐
• 출력 조건
  - 첫째 줄에 나이트가 이동할 수 있는 경우의 수를 출력하시오
  

문제 해설

예제 '상하좌우' 문제와 유사
나이트가 이동할 수 있는 경로를 하나씩 확인하여 이동하면 됨 (단, 8 x 8 좌표 평면을 벗어나지 않도록 확인)
나이트의 이동 경로를 steps 변수에 넣는다면, steps = [(-2, -1), (-1, -2), (1, -2), (2, -1), (2, 1), (1, 2), (-1, 2), (-2, 1)]

소스코드

---

📝 게임 개발

캐릭터가 있는 장소는 1 x 1크기의 정사각형으로 이뤄진 N x M 크기의 정사각형
각각의 칸은 육지 또는 바다, 캐릭터는 동서남북 중 한 곳을 바라봄
맵의 각 칸은 (A, B)로 나타낼 수 있고, A는 북쪽으로부터 떨어진 칸의 개수, B는 서쪽으로부터 떨어진 칸의 개수임
캐릭터는 상하좌우로 움직일 수 있고, 바다로 되어 있는 공간에는 갈 수 없음

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

매뉴얼에 따라 캐릭터를 이동시킨 뒤, 캐릭터가 방문한 칸의 수를 출력하는 프로그램을 만드시오

• 입력 조건
  - 첫째 줄에 맵의 세로 크기 N과 가로 크기 M을 공백으로 구분하여 입력함(3 ≤ N, M ≤ 50)
  - 둘째 줄에 게임 캐릭터가 있는 칸의 좌표 (A, B)와 바라보는 방향 d가 각각 서로 공백으로 구분하여 주어짐
    방향 d의 값: 0 북쪽, 1 동쪽, 2 남쪽, 3 서쪽
  - 셋째 줄부터 맵이 육지인지 바다인지에 대한 정보가 주어짐
    N개의 줄에 맵의 상태가 북쪽부터 남쪽 순서대로, 각 줄의 데이터는 서쪽부터 동쪽 순서대로 주어짐, 맵의 외각은 항상 바다
    0 육지, 1 바다
  - 처음 게임 캐릭터가 위치한 칸의 상태는 항상 육지
• 출력 조건
  - 첫째 줄에 이동을 마친 후 캐릭터가 방문한 칸의 수를 출력
  

문제 해설

전형적인 시뮬레이션 문제, 요구하는 내용을 오류 없이 성실히 구현만 하면 풀 수 있음
단, 문제를 바르게 이해하여 소스코드로 옮기는 과정이 간단하지 않음 => 반복적인 숙달 필요

방향을 설정해서 이동하는 문제 유형에서는 dx, dy라는 별도의 리스트를 만들어 방향 정하는 것이 효과적
2차원 리스트를 선언할 때는 컴프리헨션을 이용하는 것이 효율적

소스코드

---

📒 이것이 코딩 테스트다 교재를 통해 학습한 내용을 정리하였습니다.