[이것이 코딩테스트다] 2. 그리디 & 구현

해당 강의를 참고하여 공부를 진행했습니다.

https://www.youtube.com/watch?v=m-9pAwq1o3w&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC

---

그리디

[문제] 거스름돈

당신은 음식점의 계산을 도와주는 점원입니다. 카운터에는 거스름돈으로 사용할 500원, 100원, 50원, 10원짜리 동전이 무한히 존재한다고 가정합니다. 손님에게 거슬러 주어야 할 돈이 N원일 때 거슬러 주어야 할 동전의 최소 개수를 구하세요. 단, 거슬러 줘야 할 돈 N은 항상 10의 배수입니다.

 

<나의 풀이>

money = int(input())

N = [500, 100, 50, 10]
count = []

for i in N:
    count.append(money // i)
    money %= i

print(sum(count))

 

<영상풀이>

money = int(input())

N = [500, 100, 50, 10]
count = 0

for i in N:
    count += money // i
    money %= i

print(count)

 

[문제] 1이 될 때까지

• 어떠한 수 N이 1이 될 때까지 다음의 두 과정 중 하나를 반복적으로 선택하여 수행하려고 합니다. 단, 두
  번째 연산은 N이 K로 나누어 떨어질 때만 선택할 수 있습니다.
  1. N에서 1을 뺍니다.
  2. N을 K로 나눕니다.
• 예를 들어 N이 17, K가 4라고 가정합시다. 이때 1번의 과정을 한 번 수행하면 N은 16이 됩니다. 이후에
  2번의 과정을 두 번 수행하면 N은 1이 됩니다. 결과적으로 이 경우 전체 과정을 실행한 횟수는 3이 됩니
  다. 이는 N을 1로 만드는 최소 횟수입니다.
• N과 K가 주어질 때 N이 1이 될 때까지 1번 혹은 2번의 과정을 수행해야 하는 최소 횟수를 구하는 프로그
  램을 작성하세요.

<나의 풀이>

N, K = map(int, input().split()) # 25 5

count = 0

while(N > 1):
    if N % K == 0:
        N /= K
    else:
        N -= 1
    count += 1
print(count) # 2

이렇게 해도 되지만, N일 때마다 매번 나누고, 빼야하므로 시간 복잡도가 커지는 것이 사실이다.

 

<영상풀이>

N, K = map(int, input().split()) # 25 3

result = 0

while True:
    # N이 K로 나누어 떨어지는 수가 될 때까지 빼기
    target = (N // K) * K # 1) 25 // 3 = 8, 8 * 3 = 24 2) 24 // 8 = 3,  3 * 3 = 9
    result += (N - target) # 25 - 24 = 1 2) 24 - 9 = 15
    N = target

    # N이 K보다 작을 때(더 이상 나눌 수 없을 때) 반복문 탈출
    if N < K:
        break

    # K로 나누기
    result += 1
    N //= K

result += (N - 1)
print(result)

이런 경우, N - 2라고 하여 확실히 시간 복잡도를 줄이는 코드이다.

 

[문제] 곱하기 혹은 더하기

• 각 자리가 숫자(0부터 9)로만 이루어진 문자열 S가 주어졌을 때, 왼쪽부터 오른쪽으로 하나씩 모든 숫자
  를 확인하며 숫자 사이에 '×' 혹은 '+' 연산자를 넣어 결과적으로 만들어질 수 있는 가장 큰 수를 구하는
  프로그램을 작성하세요. 단, +보다 ×를 먼저 계산하는 일반적인 방식과는 달리, 모든 연산은 왼쪽에서부
  터 순서대로 이루어진다고 가정합니다.
• 예를 들어 02984라는 문자열로 만들 수 있는 가장 큰 수는 ((((0 + 2) × 9) × 8) × 4) = 576입니다. 또
  한 만들어질 수 있는 가장 큰 수는 항상 20억 이하의 정수가 되도록 입력이 주어집니다.

N = input() # 문자열

result = int(N[0])

for i in range(1, len(N)):
    num = int(data[i])
    # 드 스 증에서 하나라도 '0' 혹은 '1'인 경우, 곱하기보다는 더하기 수행
    if num <= 1 or result <= 1:
        result += num
    else:
        result *= num

print(result)

 

[문제] 모험가 길드

• 한 마을에 모험가가 N명 있습니다. 모험가 길드에서는 N명의 모험가를 대상으로 '공포도'를 측정했는데,
  '공포도'가 높은 모험가는 쉽게 공포를 느껴 위험 상황에서 제대로 대처할 능력이 떨어집니다.
• 모험가 길드장인 동빈이는 모험가 그룹을 안전하게 구성하고자 공포도가 X인 모험가는 반드시 X명 이상
  으로 구성한 모험가 그룹에 참여해야 여행을 떠날 수 있도록 규정했습니다.
• 동빈이는 최대 몇 개의 모험가 그룹을 만들 수 있는지 궁금합니다. N명의 모험가에 대한 정보가 주어졌을
  때, 여행을 떠날 수 있는 그룹 수의 최댓값을 구하는 프로그램을 작성하세요.

N = int(input())
A = list(map(int, input().split()))

A.sort()
print(A)

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

for i in A: # 공포도를 낮은 것부터 하나씩 확인하여
    count += i # 현재 그룹에 해당 모험가를 포함시키기
    # 공포도가 X인 모험가는 반드시 X명 이상으로 구성한 모험가 그룹에 참여해야함
    if count >= i:
        result += 1 # 총 그훕이 수 증가시키기
        count = 0 # 현재 그룹에 포함된 모험가의 수 초기화

print(result)

구현

행렬

 

for i in range(5):
    for j in range(5):
        print(i, j, end = '  ')
    print()

 

 

방향 벡터

# 동, 북, 서, 남
dx = [0, -1, 0, 1] # 영, 마, 영, 일
dy = [1, 0, -1, 0] # 일, 영, 마, 영

x, y = 2, 2

for i in range(4):
    nx = x + dx[i]
    ny = y + dy[i]
    print(nx, ny)

 

상하좌우

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

# 동 북 서 남
# 오 위 왼
dx = [0, -1, 0, 1]
dy = [1, 0, -1, 0]
move_types = ['R', 'U', 'L', '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이 입력되면 00시 00분 00초부터 N시 59분 59초까지의 모든 시각 중에서 3이 하나라도 포함되는 모든 경우의 수를 구하는 프로그램을 작성하세요. 예를 들어 1을 입력했을 때 다음은 3이 하나라도 포함되어 있으므로 세어야 하는 시각입니다.
  • 00시 00분 03초
  • 00시 13분 30초

N = int(input()) # 0 <= N <= 23
count = 0

for i in range(N+1):
    for j in range(60):
        for k in range(60):
            if '3' in str(i) + str(j) + str(k):
                count += 1

print(count)

 사실 이 문제에서 좀 내가 독립적으로 보려고 했다... 만약 입력이 5이라면, 시 부분은 00~05까지 가능하다니까 6가지, 그리고 분 부분은 0~59 가능한데 거기에 3이 있는 경우 16가지 , 초도 마찬가지 고로 6* 16 * 16 이런식으로 생각했었는데, 

 

• 시간에서 "3"이 포함되는 경우: 03:00:00 ~ 03:59:59 (1시간)
• 분에서 "3"이 포함되는 경우: 00:03:00 ~ 00:03:59, 00:13:00 ~ 00:13:59, ... , 00:53:00 ~ 00:53:59 (매 시간마다 6분)
• 초에서 "3"이 포함되는 경우: 00:00:03, 00:00:13, ... , 00:00:53 (매 분마다 6초)

이런 부분도 있다는 것을 생각하지 못했다. 그러므로 3중 for문을 사용하여 결론을 도출하면 된다고 생각이 들었다.

 

왕실의 나이트 

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

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

# 8가지 방향에 대하여 각 위치로 이동이 가능한지 확인
result = 0

for step in steps:
    # 이동하고자 하는 위치 확인
    next_row = row + step[0]
    next_column = column + step[1]
    # 해당 위치로 이동이 가능하다면 카운트 증가
    if next_row >= 1 and next_row <= 8 and next_column >= 1 and next_column <= 8:
        result += 1

print(result)

 

문자열 재정렬

N = input()
result = []
value = 0

for i in N:
    if i.isalpha():
        result.append(i)
    else:
        value += int(i)

result.sort()

# 숫자 하나라도 존재하는 경우 가장 뒤에 삽입
if value != 0:
    result.append(str(value))

print(''.join(result))