[알고리즘] 구현(Implementation)

이것이 취업을 위한 코딩 테스트다. with 파이썬 책을 참고하여 정리한 내용입니다.

구현 (Implementation)

• 머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정
• 피지컬 문제. 즉, 생각한 것을 소스코드로 구현할 수 있는가.
• 언어에 익숙한 사람이 유리. 라이브러리를 잘 사용하는 등.
• 완전 탐색, 시뮬레이션 등
• 완전 탐색 : 모든 경우의 수를 주저 없이 다 계산하는 방법
• 시뮬레이션 : 문제에서 제시한 알고리즘을 한 단계씩 차례대로 직접 수행

코딩 테스트 채점 시스템의 제약

파이썬에서 리스트 크기

데이터의 개수(리스트의 길이)	메모리 사용량
1,000	약 4KB
1,000,000	약 4MB
10,000,000	약 40MB

채점 환경

• 1초에 2,000만 번의 연산을 수행한다고 가정하면 크게 무리가 없다.
• 시간 제한이 1초이고, 데이터 개수가 100만 개인 문제가 있다면, 시간 복잡도 $O(NlogN)$ 이내의 알고리즘을 이용하여 문제를 풀어야 함
  • N = 1,000,000 일 때 NlogN은 약 20,000,000 이기 때문에

구현 문제에 접근하는 방법

• 보통 구현 문제는 사소한 입력 조건 등을 문제에서 명시해주며 문제의 길이가 꽤 긴 편임.
• 고차원적인 사고력을 요구하는 문제는 나오지 않는 편이라 문법에 익숙하다면 오히려 쉽게 풀 수 있다.
• Pypy3는 파이썬3의 문법을 그대로 지원, 실행 속도는 더 빠름
• 특히, 반복문이 많을수록 Pypy3와 파이썬3의 속도가 차이 나는데, Pypy3의 실행속도는 떄론 C/C++와 견줄 만큼 빠름
• 대략 1초에 2,000만 번에서 1억 번 정도의 연산을 처리할 수 있다고 기억
• Pypy3도 지원한다면 이를 이용하도록

예제 1) 상하좌우

여행가 A는 N x N 크기의 정사각형 공간 위에 서 있다. 이 공간은 1 x 1 크기의 정사각형으로 나누어져 있다. 가장 왼쪽 위 좌표는 (1, 1)이며, 가장 오른쪽 아래 좌표는 (N, N)에 해당한다. 여행가 A는 상, 하, 좌, 우 방향으로 이동할 수 있으며, 시작 좌표는 항상 (1, 1)이다. 이동 계획서에는 하나의 줄에 띄어쓰기를 기준으로 하여 L, R, U, D 중 하나의 문자가 반복적으로 적혀있다. 각 문자의 의미는 다음과 같다.

• L : 왼쪽으로 한 칸 이동
• R : 오른쪽으로 한 칸 이동
• U : 위로 한 칸 이동
• D : 아래로 한 칸 이동

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

입력 조건

• 첫째 줄에 공간의 크기를 나타내는 N이 주어진다. $(1 \leq N \leq 100)$
• 둘째 줄에 여행가 A가 이동할 계획서 내용이 주어진다. $(1 \leq \text{이동 횟수} \leq 100)$

출력 조건

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

입력 예시

5
R R R U D D

출력 예시

3 4

문제 해설

• 문제를 요구사항 대로 구현하면 연산 횟수는 이동 횟수에 비례 $\rightarrow$ 시간 복잡도 : $O(N)$
• 따라서 시간 복잡도는 매우 넉넉한 편
• 시뮬레이션 유형으로 분류되는 문제

답안 예시

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

# L, R, U, D에 따른 이동 방향
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)

예제 2) 시각

정수 N이 입력되면 00시 00분 00초부터 N시 59분 59초까지의 모든 시각 중에서 3이 하나라도 포함되는 모든 경우의 수를 구하는 프로그램을 작성하시오.

입력 조건

• 첫째 줄에 정수 N이 입력된다. $0 \leq N \leq 23$

출력 조건

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

문제 해설

• 모든 경우를 세서 풀 수 있는 문제이다. 완전 탐색 유형으로 분류된다.
• 00시 00분 00초 부터 23시 59분 59초까지의 모든 경우의 수는 86,400가지 밖에 없기 때문에(24 * 60 * 60).
• 경우의 수가 100,000개도 되지 않으므로 시간제한 2초 안에 문제를 해결할 수 있다.
• 매 시각을 문자열로 변경한 후 ‘3’이 포함되어 있는지 검사한다.

답안 예시

n = int(input())

count = 0
for i in range(n + 1):
  for j in range(60):
    for k in range(60):
      # 매 시각 안에 '3'이 포함되어 있다면 카운트 증가
      if '3' in str(i) + str(j) + str(k):
        count += 1

print(count)