그리디 알고리즘(Greedy)과 구현(Implementation) (2)

구현(Implementation)

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

- 풀이는 쉽지만 소스코드로 옮기기 어려운 문제를 의미

구현하기 어려운 문제

1 ) 알고리즘은 간단한데 코드가 지나칠 만큼 길어지는 문제

2 ) 특정 소수점 자리까지 출력해야 하는 문제

3 ) 문자열이 입력으로 주어졌을 때 한 문자 단위로 끊어서 리스트에 넣어야 하는(파싱해야 하는) 문제

완전탐색과 시뮬레이션

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

- 시뮬레이션 : 문제에서 제시한 알고리즘을 한 단계씩 차례대로 수행

 

문제 1 ) 상하좌우

n = int(input())

directions = list(input().split())
direction = ['R', 'L', 'U', 'D']
dx = [0, 0, -1, 1]
dy = [1, -1, 0, 0]
x, y = 1, 1

for i in directions:
  for j in range(4):
    if direction[j] == i:
      nx = x + dx[j]
      ny = y + dy[j]
      if nx <= 0 or ny <= 0 or nx > n or ny > n:
        break
      x, y = nx, ny

print(x, y)

 

- 연산 횟수는 이동 횟수에 비례 -> 이동 횟수 N번인 경우, 시간 복잡도는 O(N) - 시뮬레이션 유형

 

문제 2 ) 시각

n = int(input())
count = 0

for hour in range(n+1):
  for minute in range(60):
    for second in range(60):
      if '3' in str(hour) + str(minute) + str(second):
        count += 1

print(count)

 

- 전체 시, 분, 초에 대한 경우의 수 24 X 60 X 60 총 3중 반복문을 사용 - 완전 탐색 유형 (가능한 경우의 수 모두 검사)

 

문제 3 ) 왕실의 나이트

# 내 풀이
directions = [(2,-1),(2, 1),(-2, 1),(-2,-1),(1, 2),(-1, 2), (1, -2), (-1, -2)]

x, y = input()
x = ord(x) - 96
y = int(y)
count = 0

for i in range(8):
  nx = x + directions[i][0]
  ny = y + directions[i][1]
  if nx <= 0 or ny <= 0 or nx >= 9 or ny >= 9:
    continue
  count += 1

print(count)

# 이코테 풀이
# 현재 나이트의 위치 입력받기
input_data = input()
row = int(input_data[1])
column = int(ord(input_data[0]) - int(ord('a')) + 1

# 나이트가 이동할 수 있는 8가지 방향 정의
steps =  [(2,-1),(2, 1),(-2, 1),(-2,-1),(1, 2),(-1, 2), (1, -2), (-1, -2)]

# 8가지 방향에 대하여 각 위치로 이동이 가능한지 확인
result = 0
for step in steps:
	next_row = row + step[0]
    next_colum = column + step[1]
    # 해당 위치로 이동이 가능하다면 카운트 증가
    if next_row >= 1 and next_row <= 8 and next_column >= 1 and next_column <= 8:
    	result += 1
        
 print(result)

문제 4 ) 문자열 재정렬

# 내 풀이

s = list(input())
num = 0
result = []
s.sort()

for i in s:
  if ord(i) >= 65:
    result.append(i)
    continue
  else:
    i = int(i)
    num += i
    
result.append(num)

for i in result:
  print(i, end='')

# 이코테 풀이
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))
 
 print(''.join(result))