---

📌 공부할 때 참고한 영상은 나동빈님의 이코테 2021 강의 입니다.

---

1. 구현: 시뮬레이션과 완전 탐색

$Implementation, 구현$

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

• 아무리 알고리즘을 잘 세워도 실제로 코드로 작성해서 프로그램으로 만들지 않으면 그 알고리즘이 동작하지 않을 수 있다.

• 사실 당연한 소리로 모든 문제가 다 구현 유형의 문제라고 할 수 있겠지만 일반적으로 특정 문제를 구현 유형의 문제라고 부를 때는 문제에서 요구하는 내용이 구현에 초점이 맞추어져 있거나, 구현이 어려운 문제를 말한다.
  즉 구현 유형의 문제란 풀이를 떠올리는 것은 쉽지만 소스코드로 옮기기 어려운 문제를 지칭하곤 한다.

• 예시로는 다음과 같은 문제들을 말한다.

  • 알고리즘은 간단하지만 코드가 길어지는 문제
  • 실수 연산 및 특정 소수점 자리가지 출력하는 문제
  • 문자열을 특정한 기준에 따라 끊어서 처리하는 문제
    특히 문자열 처리에 있어 파이썬은 다른 언어들보다 사용하기 편리하기 때문에 낮은 난이도의 문제들이 1, 2번 문제에서 출제되곤 한다.
  • 적절한 라이브러리를 찾아 사용해야 하는 문제
    예를들어 itertools 라이브러리를 통해 순열 혹은 조합을 찾을 때 간결하게 코드로 표현할 수 있다.

• 이런 구현의 문제들은 많은 코드들 작성과 다양한 라이브러리들이 존재한다는 것을 공부함과 같이 미리 연습을 해놓아야 다양한 구현 문제들을 잘 대응할 수 있다.
  이 강의에서는 시뮬레이션과 완전 탐색을 중점하로 해서 구현 유형 파트를 다룬다.

1.1. 행렬

많은 코딩테스트 문제에서는 2차원 공간에서의 처리를 요구한다. 그렇기 때문에 행렬에 대한 이해는 필수적이다.
많은 언어들에서 2차원 배열이라고 부르는 것과 동일하고, 파이썬에서는 2차원 리스트라고 할 수 있겠다.

많은 완전탐색 혹은 시뮬레이션 문제를 접할 때 문제에서 가장 왼쪽 위 첫번째 원소의 위치를 $(0, 0)$과 같이 정의하는 경우가 많다.
그리고 여기에 맞춰 시뮬레이션 문제에서는 어떤 게임의 캐릭터가 특정 위치(그림에서의 $(2, 2)$)에 존재했다가 이동한다는 상황이 주어진다. 그런 상황에서 2차원 공간에서의 방향 벡터가 자주 사용된다.
동서남북의 방향으로 한칸 씩 이동해보면 다음과 같다.

1.2. 상하좌우 문제 예시

❓ 상하좌우 문제 상황

1. 여행가 A는 NxN 크기의 정사각형 공간 위에 있음 (각 공간은 1x1 크기의 정사각형으로 나누어져 있음)
2. 가장 왼쪽 위 좌표는 $(1, 1)$, 가장 오른쪽 아래 좌표는 $(N, N)$
3. 상하좌우 방향으로 한 칸씩 이동 가능하며 시작 좌표는 항상 $(1, 1)$
4. 이동 계획서에는
   한 줄에 띄어쓰기를 기준으로 한 칸씩 이동하라는 L(왼쪽), R(오른쪽), U(위쪽), D(아래쪽) 중 하나의 문자가 반복적으로 적혀 있음
5. 이 때 정사각형 공간을 벗어나는 움직임은 무시됨

예시의 그림을 보면 다음과 같다.

이 상황에서 공간 밖으로 이탈하게 만드는 U는 무시되기에 이는 N=5인 계획서와 지도가 된다.

이제 문제를 보면 다음과 같다.

1. 입력 조건

• 첫째 줄에 공간의 크기 N이 주어진다. (1<=N<=100)
• 둘째 줄에 A가 이동할 계획서가 주어진다. (1<=이동 횟수<=100)

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

5
R R R R L U U D D D D U

4. 출력

4 4

그림으로 보면 다음과 같다. 각 움직임은 1부터 카운트했다.

2. 문제

몇가지 문제를 더 풀어보자.

2.1. 문제 1

• 정수 N이 입력되면 00시 00분 00초부터 N시 59분 59초까지의 모든 시각 중, 3이 하나라도 포함되는 모든 경우의 수를 구하는 프로그램을 작성하라.
• 1시(N=1) 를 입력한다면 다음과 같다.

00시 00분 03초
00시 00분 13초
...
00시 33분 40초
...
01시 59분 53초

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

3

• 출력

8325

2.1.1. 해결 아이디어

• 모든 경우를 다 세야하는 완전 탐색 문제인 구현 문제다.
• 하루는 86,400(=24*60*60)초
• 단순히 1초씩 증가시키며 가능한 모든 경우의 수가 3이 하나라도 포함되는지 완전 탐색 하는 방법을 사용하면 된다.

2.1.2. ⭐ 코드로 확인

2.2. 문제 2

• 왕실 정원은 8x8 좌표 평면과 같다.
• 특정한 한 칸의 병사는 말을 타고 있어 L자 형태로만 이동가능 하며 정원 밖으로 나갈 수 없다.
• L자 형태는 다음과 같은 2가지 경우로 이동할 수 있다.
  • 수평으로 두 칸 이동한 뒤에 수직으로 한 칸 이동
  • 수직으로 두 칸 이동한 뒤에 수평으로 한 칸 이동
• 병사가 이동할 수 있는 경우의 수를 출력하는 프로그램을 작성하라.
• 그림으로 보면 다음과 같다.
  
• c2에 있을 때 이동할 수 있는 경우의 수는 6가지다.
• 입력 조건
  8x8 좌표 평면상 현재 병사가 위치한 곳의 좌표를 나타내는 두 문자로 구성된 문자열이 입력된다.
• 출력 조건
  나이트가 이동할 수 있는 경우의 수를 출력하라.
• 입력

d7

• 출력

6

2.2.1. 해결 아이디어

• 병사의 8가지 경로를 하나씩 확인하며 각 위치로 이동이 가능한지 확인한다.
• 앞서 배운 것과 같이 리스트를 이용하여 8가지 방향에 대한 방향 벡터를 정의하여 사용한다.

2.2.2. ⭐ 코드로 확인

2.3. 문제 3

• 알파벳 대문자와 숫자(0~9)로만 구성된 문자열이 입력으로 주어진다.
• 모든 알파벳을 오름차순으로 정렬하여 이어서 출력한 뒤, 그 뒤에 모든 숫자를 더한 값을 이어서 출력한다.
• K1KA5CB7 -> ABCKK13
• 입력 조건
  하나의 문자열 S가 주어진다. (1<=S의 길이<=10,000)
• 출력 조건
  문제에서 요구하는 정답을 출력한다.
• 입력

BDA555SFEUSQSQ12

• 출력

ABDEFQQSSSU18

2.3.1. 해결 아이디어

• 입력된 문자열의 문자를 하나씩 확인한다.
• 숫자인 경우 따로 변수를 이용해 합계를 계산한다.
• 알파벳이라면 별도의 리스트에 하나씩 저장한다.
• 이후 리스트에 저장된 알파벳을 정렬한 후 출력하고, 숫자 합게를 뒤에 붙여 출력한다.

2.3.2. ⭐ 코드로 확인