구현이란?
풀이는 쉬운데 소스코드로 쓰기는 어려운 문제이다.
구현 예시)
- 간단한 알고리즘, 그렇지 않은 코드
- 실수연산, 특정 소수점 자리까지 출력
- 문자열을 특정한 기준에 따라 끊어 처리
- 적절한 라이브러리 찾아서 사용하기
2차원 공간
구현 알고리즘 문제에서 2차원 공간은 행렬의 의미로 사용된다.
시뮬레이션 및 완전 탐색 문제에서는 2차원 공간에서의 방향 벡터가 자주 활용된다.
방향벡터 => dx = [0, -1, 0, 1] 나 steps =[(-1, -2), (1, 2)]뭐 이런거
상하좌우
• 여행가 A는 N × N 크기의 정사각형 공간 위에 서 있습니다. 이 공간은 1 × 1 크기의 정사각형으로 나누어져 있습니다. 가장 왼쪽 위 좌표는 (1, 1)이며, 가장 오른쪽 아래 좌표는 (N, N)에 해당합니다. 여행가 A는 상, 하, 좌, 우 방향으로 이동할 수 있으며, 시작 좌표는 항상 (1, 1)입니다. 우리 앞에는 여행가 A가 이동할 계획이 적힌 계획서가 놓여 있습니다.
• 계획서에는 하나의 줄에 띄어쓰기를 기준으로 하여 L, R, U, D 중 하나의 문자가 반복적으로 적혀 있습니다. 각 문자의 의미는 다음과 같습니다.
- L: 왼쪽으로 한 칸 이동
R: 오른쪽으로 한 칸 이동
U: 위로 한 칸 이동
D: 아래로 한 칸 이동
• 이때 여행가 A가 N × N 크기의 정사각형 공간을 벗어나는 움직임은 무시됩니다.
입출력
<입력>
5
R R R U D D
<출력>
=> 3 4
해설
요구사항대로 구현하면 됨.
명령에 따라 개체를 이동시킨다는 점에서 시뮬레이션 유형이라고도 불린다. 그런데 용어는 거기서 거기다.
L, R, U, D에 따른 이동 방향 벡터를 만든다
이동 방향 벡터에 걸맞는 이동 방향 리스트를 만든다.
dy = [-1, 1, 0, 0]
dx = [0, 0, -1, 1]
move_types = ['L', 'R', 'U', 'D'] #이동 방향그다음 입력받은 이동 계획에 따라서 현재 좌표에 이동 방향 벡터를 입힌다.
그러고 나서 NxN을 벗어난 것에 대한 예외처리를 한다.
문제 없으면 이동을 수행한다.
코드
N = int(input()) # N 입력
plans = input().split() #이동 계획
x, y =1,1 #! 좌표
# ! L, R, U, D에 따른 이동방향
dy = [-1, 1, 0, 0]
dx = [0, 0, -1, 1]
move_types = ['L', 'R', 'U', 'D'] #이동 방향
for plan in plans:
for i in range(len(move_types)): #이동 계획이 LRUD중 무엇인지 찾기
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)
내가 한 생각
처음 내 생각은 좌표 밖을 빠져나갈 때의 예외처리가 중요한데, 각 L R U D 이동 시마다 조건을 두는 것이다.
예를 들어 내가 완쪽 끝에 있을 땐 L을 무시하는 것이다.
if 현재좌표 == (1, N) : continue
...
이렇게 일일이 모든 경우에 대해 코드를 작성하면 가독성이 떨어진다.
이동 방향 벡터를 설정해서 문제를 풀자.
시각
입출력
<입력>
5
<출력>
11475
해설
모든 시각의 경우 다 세기
=>완전 탐색(Brute Forcing)
코드
H = int(input()) #시간 입력
count = 0 #경우의 수
for h in range(H+1) : # 시간
for m in range(60): # 분
for s in range(60): # 초
# 00 00 00
if '3' in str(H)+str(m)+str(s):
count+=1
print(count)내가 한 생각
3이 들어가는 초와 분, 시각을 따져 열심히 생각해 보았으나
그런거 없고 브루트 포스로 푸는 것이다.
왕실의 나이트
입출력
<입력>
a1
<출력>
2
해설
요구사항대로 충실히 구현
현재 좌표에서의 8가지 경로를 모두 계산에 범위를 벗어나지 않은 경우에 경우의 수 +1
=> 스텝 좌표를 모두 리스트에 넣은 뒤 지금 좌표에 스텝의 좌표를 하나하나 계산하면 다음 좌표가 된다. 다음 좌표가 유효한지 검사 후 유효하면 결과 +1
코드
coor = input()
# "ord('a') == 97"
x, y = ord(coor[0])-96, int(coor[1]) #x좌표 영어를 아스키로 변환하여 a~h를 1~8로 만들기
steps = [(-2, -1), (-1, -2), (1, -2), (2, -1), (2, 1), (1, 2), (-2, 1)]
result =0
for step in steps :
nx = x+step[0]
ny = y+step[1]
if nx >=1 and ny>=1 and nx<=8 and ny<=8:
result +=1
print(result)내가 한 생각
경우의 수는 최대 8개니까 그러면 result를 8로 두자
그리고 위와 같은 경우를 만족하려면 현재 좌표엣 x좌표나 y좌표 밖으로 2만큼의 공간이 필요하다!
그럼 x<=2 이거나 x>=7 이고 y<=2이거나 y>=7이면 result-=2 하면 되겠네!
근데 이런 생각 필요 없고 착실히 브루트포스로 풀면 된다.
문자열 재정렬
입출력
<입력>
K1KA5CB7
<출력>
ABCKK13
해설
이 문제 또한 요구사항대로 충실히 구현하면 된다.
1. 알파벳인 경우 리스트에 저장
2. 숫자인 경우 따로 더하기
3. 리스트 정렬 후 숫자 붙여 출력
코드(내꺼)
instr = input()
count =0 #숫자 더하는 곳
result =[] #최종 문자열 리스트
for letter in instr:
try: #글자를 숫자로 만들어서 1 더하기
count+=int(letter)
except: #글자가 숫자 아니면 걍 결과물에 더하기
result.append(letter)
#알파벳 정렬
result.sort()
if count!=0: #숫자 있으면 리스트에 삽입
result.append(count)
print(*result, sep="") #공백없이출력교재에서는 try except 대신 isalpha로 처리한다.
내가 한 생각
교재랑 똑같이 함
구현 쉽지 않다.
그러나 배운 점=>요구사항을 보고 너무 복잡하게 규칙을 막 찾아내서 해결하려하기 보다는 요구사항대로 충실히 구현하면 될 것 같다.
