[アルゴリズム]階調アルゴリズム

注:これは就職のためのコードテストです。

Gredyアルゴリズムとは?

定義:現在の状況では、良い方法を選択します.
機能:
1.暗記しなくても解けるタイプ.
2.いろいろなタイプに触れて、問題を解くことで訓練します.
3.アイデアを求める質問

グリディアルゴリズムの合理性

問題の解法を見つけるときは,その正しさを検討すべきである.
★難易度は主観的難易度です.

実戦問題1-大数法則(中)

重複数列を理解する.

n, m, k = map(int, input().split())
data = list(map(int, input().split()))
data1 = sorted(data, reverse = True)
count = int(m/(k+1)) * k  # 배열 내 큰 수가 등장한 횟수
count += m % (k+1)        # 배열을 제외한 큰 수가 등장한 횟수
print(count)
result = 0
result += count * data1[0]
print(result)
result += (m-count) * data1[1]
print(result)

実戦問題2-カードゲーム(下)

行ごとに最小の数値を検索し、最大の数値

を検索します.

n , m = map(int, input().split())
result = 0
for _ in range(n):
  data = list(map(int, input().split()))
  data.sort()
  min_value = data[0]
  if result < min_value:
    result = min_value  
print(result)  

実戦問題3-1(中)まで

先減後除.固定観念を打ち破る問題.

n, k = map(int, input().split())
result = 0
while True:
    target = (n//k) * k   # n이 k로 나누어 떨어지지 않는다면 N에서 1 빼기
    result += (n-target)  # 1을 총 몇 번 뺐는 지 
    n = target
    if n < k:
        break
    result += 1
    n //= k               # 한 번에 나누기
result += (n-1)
print(result)

寄付問題1-冒険者公会(中ハ)

私の解答:昇順で並べ替えて、それから最大から最小までの順序で計算します

n = int(input())
data = list(map(int, input().split()))
result=0
max_data = max(data)
data.sort()
a = max_data 
for i in range(1,n):
    if a-data[n-i] <=0:     # 큰 수에서 정렬된 작은 수를 차례대로 뺌
        result+=1
        a=n                 # N으로 초기화 (N은 그룹 수의 최댓값으로 그룹이 한 개 이상 생성될 경우 N보다 큰 값을 가질 수 없음)
    else:
        if a == n:          # N 초기화 시 a값 초기화
            a=data[n-i]
        else:
            a-=data[n-i]
print(result)

教材プール:昇順でソートした後、現在のグループに含まれる数が現在表示されている数以上である場合、グループを設定します.(廃棄問題の残り2つ)

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)           # 총 그룹의 수 출력

結論:昇順までは同じアルゴリズムですが、それ以降は逆です。

出題2-乗算または加算(下)

私の解答:多くの場合、0を乗じて値を初期化します.

s = input()
a = list(s)
result = 0
for i in a:
    i = int(i)
    if (i == 0) or (result == 0) or (result*i>200000000):
        result += i
    else:
        result = result*i
print(result)

教材の意味:1加算時の値がより大きい.ex) 3*1 = 3//3+1 = 4

data = input()

# 첫 번째 문자를 숫자로 변경하여 대입
result = int(data[0])

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

結論:1を加算に含めるとは思わなかった。

質問の発行3-文字列の反転(中)

data = input()
count0 = 0  # 전부 0으로 바꾸는 경우
count1 = 0  # 전부 1로 바꾸는 경우

# 첫 번째 원소에 대해서 처리
if data[0] == '1':
    count0 += 1
else:
    count1 += 1

# 두 번째 원소부터 모든 원소를 확인하며
for i in range(len(data)-1):
    if data[i] != data[i+1]:
        # 다음 수에서 1로 바뀌는 경우
        if data[i+1] == '1':
            count0 += 1
        # 다음 수에서 0으로 바뀌는 경우
        else:
            count1 += 1

print(min(count0, count1))

結論:数字を逆さまにする必要はなく、数えればいい。

質問の発行4-作成できない金額(中)

-私の答え:昇順に並べて、Nより小さいコインを1つ追加して、もう1つ追加します.コインのすべての値がN以上の場合は、1を呼び出します.

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

if n <= data[0]:        # N보다 동전 값이 모두 다 큰 경우
    print(n)            # N 호출

else:
    for i in data:
        if i < n:       # N보다 동전 값이 작은 경우
            result+=i   # 모두 다 더함
        else:
            break

    print(result+1)     # 1을 더한 이유:result를 호출한 경우, 가질 수 있는 최솟값이기 때문

教材注記:1からtarget-1までのすべての金額

を作成できるとします.

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

target = 1
for x in data:
    # 만들 수 없는 금액을 찾았을 때 반복 종료
    if target < x:
        break
    target += x

# 만들 수 없는 금액 출력
print(target)

結論:似ているが違う答え...?具体的に比較する必要がある。

出題5-ボウリング選択(下)

私の解答:昇順でデータを並べ替えて比較します.半分のデータのみをナビゲートして重複を回避

import math
n, m = map(int, input().split())
data = list(map(int, input().split()))

data.sort()
result = 0

for i in range(math.ceil(n/2)):         # 절반만 탐색
    for j in range(i+1, n):             # 다음 데이터부터 차례대로 비교
        if data[i] != data[j]:          # 다르다면
            result+=1                   # 1 증가
        else:
            pass

print(result)

教材説明:重量は1~10に限る.したがって、リスト変数を宣言してから、逐次選択できます.

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

# 1부터 10까지의 무게를 담을 수 있는 리스트
array = [0] * 11

for x in data:
    # 각 무게에 해당하는 볼링공의 개수 카운트
    array[x] += 1

result = 0
# 1부터 m까지의 각 무게에 대하여 처리
for i in range(1, m+1):
    n -= array[i]           # 무게가 i인 볼링공의 개수(A가 선택할 수 있는 개수) 제외
    result += array[i]*n    # B가 선택하는 경우의 수와 곱

print(result)

結論:mathライブラリが使用できない場合、私の答えは使用できません。

出題6-無知な食いしん坊生放送(中上)

-教材解答:時間のかかる食べ物を確認する欲張りな方法+優先順位Q

import heapq

def solution(food_times, k):
     # 전체 음식을 먹는 시간보다 k가 크거나 같다면 -1
    if sum(food_times) <= k:
        return -1

    # 시간이 작은 음식부터 빼야 하므로 우선순위 큐를 이용
    q = []
    for i in range(len(food_times)):
        # (음식 시간, 음식 번호) 형태로 우선순위 큐에 삽입
        heapq.heappush(q, (food_times[i], i + 1))

    sum_value = 0   # 먹기 위해 사용한 시간
    previous = 0    # 직전에 다 먹은 음식 시간

    length = len(food_times)    # 남은 음식의 개수

    # sum_value + (현재 음식시간 - 이전 음식 시간) * 현재 음식 개수와 k 비교
    while sum_value + ((q[0][0] - previous) * length) <= k:
        now = heapq.heappop(q)[0]
        sum_value += (now - previous) * length
        length -= 1             # 다 먹은 음식 제외
        previous = now          # 이전 음식 시간 재 설정

    # 남은 음식 중에서 몇 번째 음식인지 확인하여 출력
    result = sorted(q, key = lambda x: x[1])    #음식의 번호 기준으로 정렬
    return result[(k-sum_value) % length][1]


solution([3,1,2], 5)