- 이것이 취업을 위한 코딩테스다 with 파이썬(이코테 2021) 유튜브 영상을 보면서 공부한 자료입니다.
- https://www.youtube.com/watch?v=m-9pAwq1o3w&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC
구현(Implementation)
-
구현이란, 머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정이다.
-
흔히 알고리즘 대회에서 구현 유형의 문제란, 풀이를 떠올리는 것은 쉽지만 소스코드로 옮기기 어려운 문제를 말한다.
-
구현 유형의 예시는 다음과 같다.
- 알고리즘은 간단한데, 코드가 길어지는 문제
- 실수 연산을 다루고, 특정 소수점 자리까지 출력해야 하는 문제
- 문자열을 특정한 기준에 따라, 끊어 처리해야 하는 문제
- 적절한 라이브러리를 찾아서 사용해야 하는 문제 -
일반적으로 알고리즘 문제에서의 2차원 공간은 행렬(Matrix)의 의미로 사용된다.
- 시뮬레이션 및 완전 탐색 문제에서는, 2차원 공간에서의 방향 벡터가 자주 활용된다.
<문제 1> 상하좌우
입력 예시
5
R R R U D D
- 첫째 줄에 공간의 크기를 나타내는 N이 주어진다.
- 둘째 줄에 여행가 A가 이동할 계획서 내용이 주어진다.
출력 예시
3 4
- 첫째 줄에 여행가 A가 최종적으로 도착할 지점의 좌표 (X, Y)를 공백을 기준으로 구분하여 출력한다.
<풀이 1> 상하좌우
문제 해결 아이디어
- 요구사항대로 구현하면 되는, 구현 문제에 해당한다.
- 일련의 명령에 따라 개체를 차례대로 이동시킨다는 점에서, 시뮬레이션 유형으로 분류된다.
- 구현의 대표적인 문제 유형이, 시뮬레이션 유형이다.
n = int(input())
data = list(input().split())
move_types = ['L', 'R', 'U', 'D']
steps = [(0, -1), (0, 1), (-1, 0), (1, 0)]
x, y = 1, 1
for i in range(len(data)):
for j in range(len(move_types)):
if data[i] == move_types[j]:
nx = x + steps[j][0]
ny = y + steps[j][1]
if 1 <= nx <= n and 1 <= ny <= n:
x, y = nx, ny
print(x, y)<문제 2> 시각
입력 예시
5
- 첫째 줄에 정수 N이 입력된다.
출력 예시
11475
- 00시 00분 00초부터 N시 59분 59초까지의 모든 시각 중에서 3이, 하나라도 포함되는 모든 경우의 수를 출력한다.
<풀이 2> 시각
문제 해결 아이디어
- 이 문제는 가능한 모든 시각의 경우를 하나씩 모두 세서 풀 수 있는 있는 문제이다.
- 단순히 시각을 1씩 증가시키면서, 3이 하나라도 포함되어 있는지를 확인하면 된다.
- 이러한 유형은 완전 탐색(Brute Forcing) 문제 유형이라고 한다.
- 완전 탐색 : 가능한 경우의 수를 모두 검사해보는 탐색 방법
h = int(input())
res = 0
for i in range(0, h + 1):
for j in range(60):
for k in range(60):
if '3' in str(i) + str(j) + str(k):
res += 1
print(res)<문제 3> 왕실의 나이트
입력 조건
a1
- 첫째 줄에 8x8 좌표 평면상에서 나이트가 위치한 곳의 좌표를 나타내는 두 문자로 구성된 문자열이 입력된다.
출력 조건
2
- 이동할 수 있는 경우의 수를 출력한다.
<풀이 3> 왕실의 나이트
- 나이트의 8가지 경로를 하나씩 확인하며, 각 위치로 이동이 가능한지 확인한다.
- 리스트를 이용하여, 8가지 방향에 대한 방향 벡터를 정의한다.
now = input()
row = int(now[1])
col = int(ord(now[0])) - int(ord('a')) + 1
steps = [(-2, -1), (-2, -1), (-1, -2), (-1, 2), (1, -2), (1, 2), (2, -1), (2, 1)]
res = 0
for step in steps:
n_row = row + step[1]
n_col = row + step[0]
if 1 <= n_row <= 8 and 1 <= n_col <= 8:
res += 1
print(res)
<문제 4> 문자열 재정렬
입력 예시 1
K1KA5CB7
- 첫째 줄에 하나의 문자열 S가 주어진다.
출력 예시 1
ABCKK13
- 첫째 줄에 문제에서 요구하는 정답을 출력한다.
입력 예시 2
AJKDLSI412K4JSJ9D
출력 예시 2
ADDIJJJKKLSS20
<풀이 4> 문자열 재정렬
문제 해결 아이디어
- 문자열이 입력되었을 때 문자를 하나씩 확인한다.
- 숫자인 경우 따로 합계를 계산한다.
- 알파벳의 경우 별도의 리스트에 저장한다.
data = input()
res = []
val = 0
for d in data:
if d.isalpha():
res.append(d)
else:
val += int(d)
res.sort()
if val != 0:
res.append(str(val))
print(''.join(res))
안녕하세요.