[이코테]그리디 & 구현

Coding Test 2

이코테 2

1. 그리디

• 그리디 알고리즘(탐욕법)은 현재 상황에서 지금 당장 좋은 것만 고르는 방법을 의미한다.
• 일반적인 그리디 알고리즘은 문제를 풀기 위한 최소한의 아이디어를 떠올릴 수 있는 능력을 요구한다.
• 그리디 해법은 그 정당성 분석이 중요하다.
• 단순히 가장 좋아 보이는 것을 반복적으로 선택해도 최적의 해를 구할 수 있는지 검토한다.

---

문제1-거스름돈

해당 화폐로 거슬러 줄 수 있는 동전의 개수 세기

n = 1260
count = 0

array = [500, 100, 50, 10]

for coin in array :
    count += n//coin
    n %= coin

print(count)

시간 복잡도는 O(n)
금액과 무관, 동전의 총 종류에만 영향 받음

---

문제2-1이 될 때까지

어떠한 수 N이 1이 될 때까지 다음의 두 과정 중 하나를 반복적으로 선택하여 수행하려고 합니다. 단, 두 번째 연산은 N이 K로 나누어 떨어질 때만 선택할 수 있습니다.

1. N에서 1을 뺍니다.
2. N을 K로 나눕니다. N이 1이 될 때까지 1번 혹은 2번의 과정을 수행해야 하는 최소 횟수를 구하는 프로그램을 작성하세요.

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)

N에 대하여 최대한 많이 나누기를 수행하면 된다.

---

문제3-곱하기 혹은 더하기

각 자리 숫자(0부터 9)로만 이루어진 문자열 S가 주어졌을 때, 왼쪽으로 하나씩 모든 숫자를 확인하며 숫자 사이에 ‘x’ 혹은 ‘+’ 연산자를 넣어 결과적으로 만들어질 수 있는 가장 큰 수를 구하는 프로그램을 작성하세요. 단 모든 연산은 왼쪽에서부터 순서대로 이루어지다고 가정

data = input

result = int(data[0])

for i in range(1, len(ata)) :
    num = int(data[i])
    if num <= 1 or result <= 1: #num은 현재수, result는 직전수
        result += num
    else :
        result *= num

print(result)

두 수 중에서 하나라도 1 이하인 경우에는 더하며, 두 수가 모두 2 이상인 경우에는 곱하면 된다.

---

문제4-모험가 길드

모험가 길드장이 모험가 그룹을 안전하게 구성하고자 공포도가 X인 모험가는 반드시 X명 이상으로 구성한 모험가 그룹에 참여해야 여행을 떠날 수 있도록 규정했습니다. 길드장은 최대 몇 개의 모험가 그룹을 만들 수 있는지 궁급합니다. N명의 모험가에 대한 정보가 주어졌을 때, 여행을 떠날 수 있는 그룹 수의 최댓값을 구하는 프로그램을 작성하세요.

n = int(input())
data = list(map(int, input().split()))
data.sort()

result = 0
count = 0

for i in data :
    count += 1
    if count >= i: #count는 모험가 수, i는 공포도
        result += 1
        count = 0

print(result)

오름차순 정렬 후, 앞에서부터 공포도를 하나씩 확인하며 ‘현재 그룹에 포함된 모험가의 수’가 ‘현재 확인하고 있는 공포도’보다 크거나 같다면 이를 그룹으로 설정하면 된다.

---

2. 구현

풀이를 떠올리는 것은 쉽지만 소스코드로 옮기기 어려운 문제

• 알고리즘은 간단한데 코드가 지나칠 만큼 길어지는 문제
• 실수 연산을 다루고, 특정 소수점 자리까지 출력해야 하는 문제
• 문자열을 특정한 기준에 따라서 끊어 처리해야 하는 문제
• 적절한 라이브러리를 찾아서 사용해야 하는 문제

---

문제1-시각

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

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이 들어있는지 확인

---

문제2-왕실의 나이트

8x8 좌표 평면상에서 나이트의 위치가 주어졌을 때 나이트가 이동할 수 있는 경우의 수를 출력하는 프로그램을 작성하세요.

1. 수평으로 두 칸 이동한 뒤에 수직으로 한 칸 이동하기
2. 수직으로 두 칸 이동한 뒤에 수평으로 한 칸 이동하기

input_data = input()
row = int(input_data[1])
column = int(ord(input_data[0])) - int(ord('a')) + 1

steps = [(-2, -1), (-1, -2), (1, -2), (2, -1), (2, 1), (1, 2), (-1, 2), (-2, 1)]

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)

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

---

문제3-문자열 재정렬

알파벳 대문자와 숫자(0~9)로만 구성된 문자열이 입력으로 주어진다. 이때 모든 알파벳을 오름차순으로 정렬하여 이어서 출력한 뒤에, 그 뒤에 모든 숫자를 더한 값을 이어서 출력한다.

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

숫자는 따로 합계 계산
알파벳은 별도의 리스트에 저장