[이론]파이썬 알고리즘 - 구현(Implementation)

1. 구현 유형의 문제란

• 알고리즘은 간단하지만 코드가 길어지는 문제
• 실수 연산을 다루고 특정 소수점 자리까지 출력해야 하는 문제
• 문자열을 특정한 기준에 따라서 처리해야 하는 문제
• 특정한 라이브러리를 찾아서 사용해야 하는 문제

2. 행렬

• 프로그래밍에서의 좌표계는 일반적인 수학에서의 좌표계와는 다른 의미
• 알고리즘 문제에서의 2차원 공간은 행렬의 의미로 사용됨
• 완전탐색 문제에서는 2차원 공간에서의 방향벡터가 자주 활용됨
  ※ 방향벡터: dx=[-1,0,1,0], dy=[0,1,0,-1] (위, 오, 아래, 왼)

for i in range(4):
    #다음위치
    nx=x+dx[i]
    ny=y+dy[i]

예 1) 시각 문제
정수 N이 입력면 00시 00분 00초부터 N시 59분 59초까지의 모든 시각 중에서 3이 하나라도 포함되는 모든 경우의 수를 구하는 프로그램. 00시 00분 00초부터 23시 59분 59초까지의 모든 경우의 수는 86400가지밖에 되지 않는다.(24x60x60) 따라서 모든 경우의 수를 다 따져도 성능에 문제가 없는데 이러한 유형을 완전탐색(Brute Forcing) 유형이라고 한다.
답안:

h=int(input())
count=0

for i in range(h+1):
  for j in range(60):
    for k in range(60):
      if '3' in str(i)+str(j)+str(k):
        count+=1
print(count)

예 2) 상하좌우 문제
N x N크기의 정사각형 공간 위에 서 있는 사람이 (1,1)에서 출발하여 상,하,좌,우 방향으로 이동할 수 있다. 계획서에는 L,R,U,D가 써 있으며 이는 각각 좌,우,상,하를 뜻한다.
답안:

n=int(input())
x,y=1,1
plans=input()

# 문제에서 주어진 방향에 따른 이동 방향 dx, dy
dx=[0,0,-1,1]
dy=[-1,1,0,0]
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)

예 3) 문자열 재정렬
알파벳 대문자와 숫자(0~9)로만 구성된 문자열이 주어졌을 때 모든 알파벳을 오름차순으로 정렬하여 이어서 출력하고 그 뒤에 모든 숫자들의 합을 이어서 출력. 문제에서 주어진 대로 구현하면 해결 가능하다.
답안:

data=input()
result=[]
value=0

# 문자를 하나씩 확인
for x in data:
  # 알파벳이면 결과 리스트에 삽입
  if x.isalpha():
    result.append(x)
  # 숫자는 따로 더해줌
  else:
    value+=int(x)
result.sort()
# 숫자가 하나라도 존재하면 결과 리스트 뒤에 삽입
if value!=0:
  result.append(str(value))
# 리스트를 join을 사용하여 한번에 출력
print(''.join(result))