2. 그리디 알고리즘 & 구현

💡 동빈나 님의 이코테 2021 강의 몰아보기 를 보면서 공부한 내용을 정리하고 있습니다. 더 자세한 내용은 이것이 취업을 위한 코딩 테스트다 with 파이썬 을 참고해주세요 😊 학습 도구로는 리플렛 을 사용하고 있고 원본 소스코드는 동빈님의 Github 에서 확인할 수 있고 스스로 공부한 소스코드는 Github 에서 확인할 수 있습니다.

그리디 알고리즘

• 현재 상황에서 지금 당장 좋은 것만 고르는 방법

• 일반적으로는 문제를 받자마자 풀기 위한 최소한의 아이디어를 떠올릴 수 있는 능력을 요구

• 그리디 해법은 그 정당성 분석이 매우 중요함

  • 단순히 가장 좋아보이는 것을 반복적으로 선택해도 최적의 해를 구할 수 있는지 검토

• 일반적으로는 최적의 해를 보장할 수 없을 때가 많다.

• 하지만 코테에서는 탐욕법으로 얻은 해가 최적의 해가 되는 상황에서, 이를 논할 수 있어야 풀리도록 문제가 풀제된다.

  • 탐욕법이 최적의 해가 되는 상황에서 문제가 출제된다.

거스름돈 문제

문제

• 편의점 알바가 500, 100, 50, 10 원짜리 동전을 무한정 가지고 있다.

• 손님에게 거스름돈을 최소한의 동전개수로 거슬러주기 위해서는 어떻게 해야할까

해결

• 풀이

  • 돈의 단위가 큰 동전부터 우선적으로 거술러주면 된다.

  • 예를 들어 거스름돈이 1,250 원일 경우, 총 5개의 동전으로 거술러 주는 것이 동전 수를 최소화 하는 방법이다.

    • 500 * 2

    • 100 * 2

    • 50 * 1

• 정당성 분석

  • 왜 큰 화폐단위부터 거슬러주는게 최적의 해를 보장하는 것일까?

  • 가지고 있는 동전 중에서 가장 큰 단위가 항상 작은 단위의 배수가 되므로 작은 단위의 동전을 종합해서 다른 해가 나올 수 없기 때문이다.

  • 예를 들면 800원이 거스름 돈이라고 할 때, 500원, 400원, 100원이 있다면,

    • 그리디로 풀게되면 5001 + 1003 = 총 4개의 동전이 답이 된다.

    • 하지만 정답은 400*2 = 2개이다.

    • 이 경우, 500원이 400원의 배수가 아니기 때문에 400원을 조합해서 다른 해가 나올 수 있게 되는 것!

• 그리디 알고리즘 정리

  1. 문제 풀이를 위해서 최소한의 아이디어 떠올리기

  2. 그 해답이 정당한지 분석하기

#### 최소동전개수 거스름돈
array = [500, 100, 50, 10]
coin_num = 0
change = 1260

for coin in array:
  coin_num += change // coin
  change %= coin
print("거스름돈 동전의 개수는 ", coin_num, " 개 입니다.")

1이 될 때까지

문제

• 두 개의 숫자 N, K가 주어진다.

• 어떠한 수 N이 1이 될 때까지 두 과정 중 하나를 반복적으로 선택하여 수행한다.

  • N에서 1을 뺀다.

  • N에서 K를 나눈다.

• 예를들면 N=17, K=4 이면,

  • 1번 수행 후, N=16

  • 2번 수행 후, N=4

  • 3번 수행 후, N=1

• 전체적으로 실행한 횟수는 3이 된다.

• 이처럼 어떤 조건과 수행해야할 일이 주어지고 그 수행의 최소 횟수를 구하는 프로그램을 작성해야하는 것

해결

• 주어진 N에 대하여 최대한 많이 나누는 것이 이득이다.

• 목표는 N의 값을 줄여서 1까지 만드는 것

• N의 값을 작게 만드는데 가장 좋은 방법은 1을 빼는 것보다는 K로 나누는 것이다.

• 정당성 분석

  • N이 아무리 큰 수여도 K로 계속 나눈다면 기하 급수적으로 빠르게 줄일 수 있다.

  • K가 2이상이기만 하면 K로 나누는 것이 1을 빼는 것보다 항상 빠르게 N을 줄일 수 있음

# 1이 될 때까지
n = 25
k = 5
cnt = 0

while True:
  if n % k == 0:
    n = n // k
  else:
    n -= 1

  cnt += 1

  if n == 1:
    break

print(cnt)


# 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)

곱하기 혹은 더하기 문제

문제

• 각 자리가 숫자(0-9)로만 이루어진 문자열 S 가 주어졌을 때,

• 왼쪽부터 오른쪽으로 하나씩 모든 숫자를 확인하며 숫자 사이에 * 혹은 + 연산자를 넣어서

• 결과적으로 만들어질 수 있는 가장 큰 수를 구하는 프로그램

• 단, + 보다 * 를 먼저 게산하는 일반적인 방식과 다르게, 모든 연산은 왼쪽에서부터 차례대로 이루어진다고 가정한다.

• 예를 들어 "02984" 라는 문자열로 만들 수 있는 가장 큰 수는 (0+2) * 9 * 8 * 4 = 576 이다.

• 만들어질 수 있는 가장 큰 수는 항상 20억 이하의 정수이다.

  • 정수의 최대 범위가 21억이기 때문!

  • 파이썬에서는 정수 범위가 정해져있지 않기 때문에 큰 문제가 되지 않음

해결

• 조건에 맞으면 더하기, 조건 안맞으면 곱하기 -> 전형적인 그리디 알고리즘

• 두 수 중 하나라도 0 또는 1인 경우 더하기가 유리하다.

• 나머지 경우에는 모두 곱셈이 유리함!

• java 의 경우 : 문자열의 특정 포인트 접근을 위하여 charAt(n) method 사용

### 곱하기 혹은 더하기 문제
# 0일 경우 무조건 더하기
# 0이 아니면 무조건 곱하기가 유리

numbers = list(map(int, input()))
sum = 0

for num in numbers:
  if sum == 0 or num == 0:
    sum += num
  else:
    sum *= num

print(sum)


## 풀이
# 두 수 중 하나라도 0 또는 1인 경우 더하기가 유리하다. 
# 나머지 경우에는 모두 곱셈이 유리함! 
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)

모험가 길드 문제

문제

• 한 마을에 모험가가 n 명 존재

• 이들을 대상으로 공포도를 측정함

• 공포도가 높은 모험가는 쉽게 공포를 느껴 위험 상황에서 제대로 대처할 능력이 떨어진다.

• 모험가 그룹 길드장은 모험가 그룹을 안전하게 구성하고자 공포도가 X인 모험가는 반드시 X 명 이상으로 구성한 모험가 그룹에 참여해야 여행을 떠날 수 있도록 규정함

• 동빈이는 최대 몇 개의 모험가 그룹을 만들 수 있을까?

• N명의 모험가에 대한 정보가 주어졌을 때, 여행을 떠날 수 잇는 그룹 수의 최댓값을 구하는 프로그램을 작성해야함!

해결

• 입력값을 오름차순으로 정렬 후

• 현재 그룹에 포함된 모험가의 수 >= 현재 확인하고 있는 공포도 -> 바로 그룹결성가능!

# 모험가 길드 문제

x = int(input())
scare_points = list(map(int, input().split()))
scare_points.sort()

result = 0
count = 0

for point in range(len(scare_points)):
  count += 1

  if count >= point:
    result += 1
    count = 0

print(result)

---

구현 : 시뮬레이션과 완전 탐색

• 기본적으로 머리속에 있는 알고리즘을 소스코드로 옮기는 작업!

• 보통 알고리즘 대회에서 구현 유형의 문제

  • 풀이를 떠올리는 건 쉬운데 소스코드로 옮기기 어려운 문제

• 대표적인 유형은 다음과 같음

  • 알고리즘은 간단하지만 코드가 지나칠만큼 길어지는 문제

  • 실수 연산을 다루고 특정 소수점 자리까지 출력해야하는 문제

  • 문자열 특정한 기준에 따라서 끊어 처리해야하는 문제

  • 적절한 라이브러리를 찾아서 사용해야하는 문제

• 2차원 공간 -> 행렬의 의미로 사용

• 2차원 공간에서의 방향 벡터가 많이 사용됨

상하좌우 문제

문제

• N 이 100이하로 주어짐

• N * N 정사각형 공간 위에 서있음

• 가장 왼쪽 위 좌표는 (1, 1), 가장 오른쪽 아래 좌표는 (N, N) 이다.

• 여행가 A는 상, 하, 좌, 우로 이동 가능하며 시작 좌표는 항상 (1, 1)

• 여행할 계획표가 주어진다. 계획표에는 L, R, U, D 가 적혀있고 각각 왼쪽, 오른쪽, 위, 아래로 1칸씩 이동하는 것을 의미함

해결

• 요구사항대로 충실히 구현하면 됨

# 상하좌우 문제
# 상하좌우 이동시 변경될 좌표값 -> 미리 배열로 정의

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

dx = [0, 0, 1, -1]
dy = [-1, 1, 0, 0]
move_types = ['L', 'R', 'U', 'D']

x, y = 1, 1

for plan in plans:
  for i in range(len(move_types)):
    if plan == move_types[i]:
      tx = x + dx[i]
      ty = y + dy[i]
  
  if tx < 1 or tx > size or ty < 1 or ty > size:
    continue
  
  x, y = tx, ty

print(x, y)

시각 문제

문제

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

• 1을 입력했다면,

  • 00시 00분 03초

  • 00시 13분 30초

• 다음은 세면 안되는 시각

  • 00시 02분 55초

  • 01시 27분 45초 등

풀이

• 가능한 모든 시각의 경우의 수를 모두 세서 풀 수 있는 문제 = 완전 탐색 문제!

• 하루는 24 * 60 * 60 = 86,400 초 -> 하루에 가능한 경우의 수는 86,400가지

  • python 기준 1초에 2000 만번 연산을 처리한다고 가정하면 모든 경우의 수를 돌아도 전혀 무리되지 않음

• 시각을 단순히 0부터 1씩 증가시키면서 3이 하나라도 포함되어있는지를 검사한다.

# 시각
# 3이 하나라도 포함되는 시각의 모든 경우의 수
# 00:00:00 ~ N:59:59

hour = int(input())
count = 0

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

# 5
# 11475

왕실의 나이트 문제

문제

• 행복왕국의 왕실 정원은 체스판과 같은 8 * 8 좌표 평면 -> 2차원!

• 특정 칸에 나이트가 서있다.

• 말을 타고 있어서 이동할 때에는 L자 형태로만 이동할 수 있고

  • 수평으로 2칸 + 수직으로 1칸

  • 수직으로 2칸 + 수평으로 1칸

• 정원 밖으로는 이동할 수 없다.

• 나이트가 이동할 수 있는 경우의 수를 출력하는 프로그램

• 행 위치는 1 - 8

• 열 위치는 a - h 로 표현한다.

해결

• 역시 구현문제의 일종이다. 요구사항대로 충실하게 구현만 하면 됨

• 리스트를 활용하여 8가지 방향에 대한 방향 벡터를 정의한다.

# 왕실의 나이트 문제
# 역시 구현문제 -> 요구사항대로 충실히 구현만 하면 됨

# 풀이
pin = input() 

# a - h 의 문자값을 숫자로 바꾸는 작업 필요
tx = ord(pin[0])

x = tx - ord('a') + 1
y = int(pin[1])

result = 0

# 총 경우의 수는 8가지 일듯
moves = [(+2, -1), (+2, +1), (-2, -1), (-2, +1), (-1, +2), (-1, -2), (+1, -2), (+1, +2)]

for move in moves:
  nx = x + move[0]
  ny = y + move[1]

  if nx < 1 or nx > 8 or ny < 1 or ny > 8:
    continue
  
  result += 1

print(result)

문자의 재정렬 문제

문제

• 알파벳 대문자와 숫자 (0-9)로만 구성된 문자열이 입력으로 주어짐

• 모든 알파벳을 오름차순으로 정렬하여 이어서 출력한 뒤에, 그 뒤에 모든 숫자를 더한 값을 이어서 출력한다.

• 예를 들어, K1KA5CB7 이라는 값이 들어오면 ABCKK13 으로 출력한다.

• 참고

  • 코딩에서 숫자와 수

    • 숫자 : 0 - 9

    • 수 : 100, 1230 와 같은 정수

해결

• 주어진 요구를 충실하게 수행하면 될듯.

• 주어진 요구

  • 알파벳 먼저 앞으로 정렬

  • 숫자를 알파벳 정렬 이후에 정렬

• 해결 아이디어

  1. 입력값받고

  2. 반복 -> 문자는 문자배열에, 숫자는 숫자배열에 넣기

  3. 문자배열 정렬, 출력

  4. 숫자배열 정렬, 출력

• 풀이

# 문자의 재정렬
# 문자정렬+숫자정렬문제일때 
# ord('0') : 48
# ord('9') : 57
# ord('A') : 65
# ord('Z') : 90

chars = list(input())

alpabets = []
nums = []

for char in chars:
  if ord(char) <= ord('9'):
    nums.append(int(char))
  else:
    alpabets.append(char)

alpabets.sort()
nums.sort()

print(''.join(str(w) for w in (alpabets+nums)))

# K1KA5CB7
# ABCKK157

# AJKDLSI412K4JSJ9D
# ADDIJJJKKLSS12449


# 문자의 재정렬 : 문자 정렬 + 숫자 합계
# 풀이
# 문자의 재정렬 풀이
# 문자정렬 + 숫자의 합

chars = input()
result = []
sum = 0

for char in chars:
  if char.isalpha():
    result.append(char)
  else:
    sum += int(char)
  
result.sort()

if sum != 0:
  result.append(str(sum))

print(''.join(result))

# K1KA5CB7
# ABCKK13

# AJKDLSI412K4JSJ9D
# ADDIJJJKKLSS20