Ch4 Implementation 4-1

📚 구현 (Implementation) 알고리즘

‘머릿속에 있는 알고리즘을 소스 코드로 바꾸는 과정’

문제 해결 분야에서 구현 유형의 문제는

• 풀이를 떠올리는 것은 쉽지만 소스 코드로 옮기기 어려운 문제
• 피지컬(언어 문법에 능숙, 빠른 타자)을 요구하는 문제

소스 코드로 옮기기 어려운 문제란?

• 알고리즘은 간단한데 코드가 지나칠 만큼 길어지는 문제
• 특정 소수점 자리까지 출력해야 하는 문제
• 문자열이 입력으로 주어졌을 때 한 문자 단위로 끊어서 리스트에 넣어야 하는(파싱을 해야 하는) 문제

⏩ 대체로 사소한 조건 설정이 많은 문제일수록 까다로움

문법을 정확히 숙지하고, 라이브러리를 사용할 수 있어야 한다.

• Ex) N개의 원소가 들어 있는 리스트에서 R개의 원소를 뽑아 한 줄로 세우는 모든 경우(순열)를 구해야 하는 문제 itertools와 같은 표준 라이브러리 사용하면 쉽게 코드를 짤 수 있다. 이는 곧 언어의 문법의 이해와 경험이 있어야 떠올릴 수 있는 해결방법이다.

이 책의 ‘구현’ 유형은 완전 탐색, 시뮬레이션을 모두 묶어 다룬다.

• 완전 탐색 (Brute Forcing) : 모든 경우의 수를 주저 없이 다 계산하는 해결 방법

• 시뮬레이션 (Simulation) : 문제에서 제시한 알고리즘을 한 단계씩 차례대로 직접 수행

---

📃 [예제 1] 상하좌우

• 난이도: ⭐
• 풀이 시간: 15분
• 시간 제한: 1초
• 메모리 제한: 128MB

[문제]

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

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

이때 여행가 A가 N x N 크기의 정사각형 공간을 벗어나는 움직임은 무시한다.

계획서가 주어졌을 때 여행가 A가 최종적으로 도착할 지점의 좌표를 출력하는 프로그램을 작성하시오.

[입력조건]

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

[출력 조건]

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

# 입력 예시
5
R R R U D D

# 출력 예시
3 4

# 1. 나의 풀이

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

for i in plans:  # 입력 좌표 하나씩 확인하여 이동
	if i == 'L' and y < 1:
		y -= 1
	elif i == 'R' and y < n+1:
		y += 1
	elif i == 'U' and x > 1:
		x -= 1
	elif i == 'D' and x < n+1:
		x += 1

print(x, y)



# 2. 교재 답안

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)

• 시뮬레이션 유형 : 일련의 명령에 따라서 개체를 차례대로 이동시키기 때문에

• 연산 횟수는 이동 횟수에 비례

  이동 횟수가 N번인 경우 시간 복잡도는 O(N) 이다.

문제를 풀이한 과정을 보면 좌, 우, 위, 아래 4가지 이동방향을 List로 만들어서 사용하고 있다.

그리디 유형의 거스름돈 문제에서도 500원, 100원, 50원, 10원의 화폐단위를 List로 만들어서 사용했었는데, 반복적으로 사용하는 값들에 대해서는 리스트에 담아두고 접근하는 방식으로 알고리즘을 작성하는 것이 좀 더 효율적으로 풀 수 있는 것 같다.

‘나의 풀이’ 처럼 if문으로 접근한다면 이동방향이 사방팔방으로 늘어나는 경우에는 코드가 길어지게 되기 때문에 가독성 측면에서도 좋지 않아 보인다.

---

📃 [예제 2] 시각

• 난이도: ⭐
• 풀이 시간: 15분
• 시간 제한: 2초
• 메모리 제한: 128MB

[문제]

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

[입력 조건]

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

[출력 조건]

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

# 입력 예시
5

# 출력 예시
11475

# 1. 나의 풀이

h = int(input())
cnt = 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):  # if item in list: list 안에 특정 값 확인 방법
				cnt += 1
print(cnt)


# 2. 교재 풀이

h = int(input())
count = 0

for i in range(h+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)

• 완전탐색(Brute Forcing) 유형 : 가능한 경우의 수를 모두 검사

• 모든 시각의 경우를 하나씩 모두 세서 푸는 문제 전체 시, 분, 초에 대한 경우의 수 : 24 × 60 × 60

일반적으로 완전 탐색 알고리즘은 비효율적인 시간 복잡도를 가지고 있으므로 전체 데이터의 수가 100만 개 이하일 때 완전 탐색을 사용하면 적절하다.

---