[알고리즘] 구현 with Python

💡 구현

구현이란 '알고리즘을 소스코드로 바꾸는 과정'이라고 할 수 있다.

알고리즘 교재에서는 대부분 구현을 별도의 유형으로 다루지 않지만, 코딩테스트에서는 구현이 중심으로 되는 문제가 자주 출제되기 때문에 다뤄보기로 한다. 보통 구현문제는 '풀이를 떠올리는 것은 쉽지만 소스코드로 옮기기 어려운 문제'를 의미한다.

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

💡 주의점

  완전 탐색처럼 많은 경우의 수를 계산할때 주의해할 점은 일반 코딩 테스트환경에서는 파이썬으로 제출한 코드가 1초에 2000만번(2*10^7)의 연산을 수행하는 것이다. 대부분의 코딩테스트에서는 시간제한이 1초임으로 이를 기억하도록 하자.

💡 구현 알고리즘의 대표적 예시

Q1. 상하좌우

  여행가 A는 N * N크기의 정사각형 공간위에 서있다. 이공간은 1*1 크기의 정사각형으로 나누어져 있다. 가장 왼쪽 위 좌표는 (1,1)이며 가장 오른쪽 아래 좌표는 (N, N)에 해당한다. 여행가 A는 상하좌우 방향으로 이동할 수 있으며 시작 좌표는 항상(1,1)이다. 우리 앞에 여행가 A가 이동할 계획이 적힌 계획서가 놓여있다.

  계획서에는 L, R, U, D 중 하나의 문자가 반복적으로 적혀있다. 각 문자의 의미는 다음과 같다.

L : 왼쪽으로 한칸 이동

R : 오른쪽으로 한칸이동

U : 위로 한칸 이동

D : 아래로 한칸 이동

  이때 여행가 A가 N*N 크기의 정사각형 공간을 벗어나는 움직임은 무시된다. 계획서가 주여졌을 때 여행가 A가 최종적으로 도착할 지점의 좌표를 출력하는 프로그램을 작성하시오.

일반적인 좌표와 다름에 주의하자

* 입력 조건

- 첫째줄에 공간의 크기를 나타내는 N이 주어진다.(1<= N <= 100)

- 둘째줄에 여행가 A가 이동할 계획서 내용이 주어진다.(1<= 이동횟수 <= 100)

* 출력 조건

- 첫째 줄에 여행가 A가 최종적으로 도착할 지점의 좌표 (X, Y)를 공백으로 구분하여 출력한다.

 

* 입력 예시

5

R R R U D D

* 출력 예시

3 4

 

[문제 아이디어]

움직임을 다음과 같이 나타낼 수 있다. 다시 말하지만 일반적인 좌표와 다름에 주의하자.(항상 헷갈림ㅜㅜ)

move_types = ['U', 'D', 'L', 'R']

dx = [-1, 1, 0, 0]

dy = [0, 0, -1, 1]

 

[코드]

n = int(input())
plans = input().split()

# 상하좌우에 따른 이동방향
move_types = ['U', 'D', 'L', 'R']
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1] 

# 시작 좌표
x, y = 1, 1

# 이동 계획에 따라 움직인다
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)

---

Q2. 시각

정수 N이 입력되면 00시 00분 00초부터 N시 59분 59초까지의 모든 시각 중에서 3이 하나라도 포함되는 모든 경우의 수를 구하는 프로그램을 작성하시오, 예를 들어 1을 입력했을 때 다음은 3이 하나라도 포함되어 있으므로 세어야하는 시각이다.

- 00시 00분 03초

반면 다음은 3이 하나도 포함되어 있지 않으므로 세면 안되는 시각이다.

- 00시 02분 25초

 

*입력조건

- 첫째줄에 정수 N이 입력된다 (0<=N<=23)

*출력 조건

- 00시 00분 00초부터 N시 59분 59초까지의 모든 시각 중에서 3이 하나라도 포함되는 모든 경우의 수를 출력한다.

 

*입력 예시

5

*출력 예시

11475

 

[문제 아이디어]

 완전탐색으로 해당 문제를 해결할 시에 24*60*60 = 8640번의 경우의 수가 있다.

 주의점에서 말해듯이 파이썬은 1초에 이천만번의 연산이 가능하다고 했으니 이정도는 완전탐색이 가능하다. 때문에 조건문을 이용해 여러 경우로 빼주는 것보다는 전부 반복문 처리하여 간결한 코드를 가져가는 것이 좋다.

 

[코드]

hour = int(input())

count = 0
for h in range(0, hour+1):
  for m in range(60):
    for s in range(60):
      # 매시각 확인
      if '3' in str(h) + str(m) +str(s):
        count += 1

print(count)

---

💡 구현 알고리즘 문제

Q1. 왕실의 나이트

왕실 정원은 체스판과 같은 8*8좌표 평면이다. 왕실 정원의 특정한 한 칸에 나이트가 서있다.  나이트는 이동할때 L자 형태로만 이동할 수 있으며 정원 밖으로는 나갈 수 없다. 나이트는 특정한 위치에서 다음과 같은 2가지 경우로 이동할 수 있다.

1) 수평으로 두칸 이동한 뒤에 수직으로 한칸 이동

2) 수직으로 두칸 이동한 뒤에 수평으로 한칸 이동

 

이처럼 8*8좌표 평면상에서 나이트 위치가 주어졌을 때 나이트가 이동할 수 있는 경우의 수를 출력하는 프로그램을 작성하시오. 이때 왕실의 정원에서 행 위치를 표현할 때는 1부터 8로 표현하며, 열 위치를 표현할 때는 a부터 h로 표현한다. 예를 들어 만약 나이트가 a1에 있을 때 이동할 수 있는 경우의 수는 c2,b3 두가지 이다. c2에 위치해 있다면 경우의 수는 6가지 이다.

 

*입력조건

- 첫째줄에 8*8 좌표평면 상에서 현재 나이트가 위치한 곳의 좌표를 나타내는 두문자로 구성된 문자열이 입력된다. 입력문자는 a1처럼 열과 행으로 이뤄진다.

*출력 조건

- 첫째 줄에 나이트가 이동할 수 있는 경우의 수를 출력하시오.

 

*입력 예시

a1

*출력 예시

2

 

[문제 아이디어]

 시뮬레이션 문제유형이다. 상하좌우와 비슷한 문제인데, 좌표설정에서 차이가 있다.

아스키 코드로 'a'는 97 이고 'z'는 122임을 알아두자.

 

[코드]

position = input()

# 이동방향 정의
move_col = [2, 2, -2, -2, 1, 1, -1, -1]
move_row = [1, -1, 1, -1, 2, -2, 2, -2]

# 이동 가능한 방향의 갯수 구하기
count = 0
for i in range(len(move_col)):
  next_col = ord(position[0]) + move_col[i]
  next_row = int(position[1]) + move_row[i]

  # 해당 방향으로 이동 가능 여부
  if ord('a')<=next_col<=ord('h') and 1<=next_row<=8:
    count += 1

print(count)

---

Q2. 문자열 재정렬

알파멧 대문자와 숫자(0~9)로만 구성된 문자열이 입력으로 주어집니다. 이때 모든 알파멧을 오름차순으로 정렬하여 이어서 출력한 뒤에 그 뒤에 모든 숫자를 더한 값을 이어서 출력합니다.

 

*입력조건

- 첫째줄에 하나의 문자열 s가 주어집니다,(1<=S의 길이<=10,000)

*출력 조건

- 첫째 줄에 문제에서 요구하는 정답을 출력합니다.

 

*입력 예시

K1KA5CB7

*출력 예시

ABCKK13

 

[문제 아이디어]

 파이썬에는 문자열 구성이 알파벳인지 확인해주는 isalpha()라는 함수를 제공한다.

참고로 isdigit()는 숫자 구성인지를 확인해주며, isalnum()은 숫자 혹은 알파벳인지를 확인해준다.

 

[코드]

string = input()

alpha = []
number = 0

for s in string:
  if s.isalpha():
    alpha.append(s)
  # 모든 숫자는 더한다
  else:
    number += int(s)

# 오름차순 정렬
alpha.sort()

print( "".join(alpha) + str(number))