그리디(greedy)

👉 그리디 알고리즘(탐욕법)은 현재 상황에서 지금 당장 좋은 것만 고르는 방법을 의미한다.

• 문제를 풀기 위한 최소한의 아이디어를 떠올릴 수 있는 능력을 요구
• 그리디 해법은 정당성 분석이 중요! ⇒ 단순히 가장 좋아 보이는 것을 반복적으로 선택해도 최적의 해를 구할 수 있는지 검토 ⇒ 대부분 그리디 알고리즘 문제에서는 문제풀이를 위한 최소한의 아이디어를 떠올리고 이것이 정당한지 검토할 수 있어야 답을 도출할 수 있다!
  

# 예제 1. 거스름 돈 
# n = int(input())
# count = 0 

# coin_types = [500, 100, 50, 10]

# for coin in coin_types: 
#   count += n // coin 
#   n %= coin 

# print(count)

#예제 2. 1로 만들기 
# n, k = map(int, input().split())
# result = 0

# while True: 
#   target = (n  // k) * k 
#   result += (n - target)
#   n = target 
#   if n < k : 
#       break 
#   result += 1 
#   n //= k 

# result +=(n-1)
# print(result)

# 예제 3. 곱하기 혹은 더하기 
# data = input()

# result = int(data[0])

# for i in range(1, len(data)) : 
#   num = int(data[i])
#   if num <= 1 or result <=1 : 
#     result += num 
#   else : 
#     result *= num 

# print(result)

# 예제 4. 모험가 길드 
# n = int(input())
# data = list(map(int, input().split()))
# data.sort()

# result = 0 # 총 그룹의 수 
# count = 0  # 현재 그룹에 포함된 모험가의 수 

# for i in data : 
#   count += 1
#   if count >= i : 
#     result += 1 
#     count = 0 

# print(result)

구현(implementation)

👉 구현이란 머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정이다

단 알고리즘 대회에서 구현 유형의 문제란 풀이를 떠올리는 것은 쉽지만 소스코드로 옯기기 어려운 문제를 지칭한다.

• 완전 탐색 : 모든 경우의 수를 주저 없이 다 계산하는 해결 방법
• 시뮬레이션: 문제에서 제시한 알고리즘을 한 단계씩 차례대로 직접 수행해야 하는 문제 유형

#  # 1. 상하좌우 

# #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. 시각 (완전탐색)
# 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)

# # 3. 왕실의 나이트 
# input_data = input()
# row = int(input_data[1])
# col = 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_col = col + step[1]
#   if 1 <= next_row <= 8 and 1 <= next_col <= 8 : 
#     result += 1 
# print(result)

# 4. 문자열 재정렬 
# 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(result)
# print(''.join(result))