bright

acmicpc.net/problem/2217

# 2217

n = int(input()) # 로프의 수 
data = []

for i in range(n):
  data.append(int(input()))

data.sort(reverse=True)

max_w = []

for i in range(n):
  max_w.append( data[i]*(i+1))

print(max(max_w))

너무 어렵게 생각하지 않는 것이 중요하다.

기본적으로 입력받은 중량 값을 역으로 정렬하여 사용한다. 

우선, 가장 기본적으로 들 수 있는 중량은 제일 큰 로프의 중량 값이다.

2가지의 로프를 사용한다면, 

가장 큰 로프는 그다음으로 큰 로프보다 항상 크므로 

두 번째 로프의 2배만큼의 중량을 들 수 있을 것이다. 

3가지의 로프를 사용하고.. 그 이상의 로프를 사용한다고 해도 마찬가지이다. 

이렇게 새로운 배열을 만들고 나서 가장 큰 값을 고르면 된다. 

www.acmicpc.net/problem/13305

# 13305 

n = int(input()) # 도시의 수 
dist = list(map(int, input().split() ))
cost = list(map(int, input().split() ))

# 처음 출발할 때, 무조건 기름 필요 
total = cost[0]*dist[0]
m = cost[0]

# 나보다 작은 값이 나오면 그 이후로 그 값으로 계산 
# 마지막 나라의 가격은 사실상 사용되지 않으므로 무시 가능 
for i in range(1,n-1):
  if cost[i] < m : 
    total += dist[i] * cost[i]
    m = cost[i]
  else : 
    total += dist[i]*m

print(total)

+) 주의사항 

만약에 계속 min 함수를 이용해서 최솟값을 찾고자 하면 시간 초과 오류가 날 수 있음. 

처음에 아래와 같이 코드를 작성했더니 시간 초과 오류가 남. 

# 13305 

n = int(input()) # 도시의 수 
dist = list(map(int, input().split() ))
cost = list(map(int, input().split() ))

# 처음 출발할 때, 무조건 기름 필요 
total = cost[0]*dist[0]

# 가장 작은 값 이후로는 다 작은 값으로 계산 
e = len(cost)
while e > 1 : 
  cost = cost[:e] 

  small = min(cost)
  s_i = cost.index(small)

  # print("최소값은", small, "index : ", s_i)

  for i in dist[s_i:e] :
    total += small* i
    #print('total: ', total)
    #print(dist[s_i:e])

  e = s_i

if e == 0 : 
  total -= cost[0]*dist[0]

print(total)

www.acmicpc.net/problem/4796

# 4796

data = [] 
while True : 
  L, p, v = map(int, input().split() ) 
  if L + p + v == 0 : 
    break 
  else : 
    data.append([L,p,v])

for i in data : 
  L, p, v = i[0], i[1], i[2]

  cnt = ( v//p )*L
  re = v - p*(v//p)

  if re <= L :
    cnt += re
  else : 
    cnt += L
  
  print("Case",str(data.index(i)+1)+":",cnt)

# 효율성 만족 x  정확성은 만족 

def solution(people, limit):
    answer = 0

    people.sort()
    
    while people:
        total = people.pop(0) 
        answer += 1 
        
        if len(people) >= 1 : 
            for i in range(len(people)-1, -1, -1 ):
                if total+ people[i] <= limit : 
                    people.pop(i)
                    break     
    return answer

# 효율성, 정확성 둘 다 만족

def solution(people, limit) :
    answer = 0
    people.sort()

    start = 0
    end = len(people) - 1
    while start < end :
        if people[end] + people[start] <= limit :
            start += 1
            answer += 1
        end -= 1
    return len(people) - answer

정렬한 다음, 작은 것과 큰 것을 묶어 태우기 위해서 투포인터를 사용한다. 

answer 에 묶어 보낼 수 있는 경우를 세서 저장한다. 

만약 가장 작은 값이랑 가장 큰 값을 더해서 limit 보다 크다면, 가장 큰 값을 하나 감소한다. 

list 의 remove, del 등의 연산은 index를 하나씩 수정해야 하므로 최대 O(n) 의 시간이 필요하다. 

효율성을 위해서 지우지 않고, 위와 같은 방식으로 index를 조정하여 사용하는 방법을 생각할 필요가 있다. 

import copy

def solution(n, lost, reserve):
    
    lost.sort()
    reserve.sort()
    
    tmp_lost = copy.deepcopy(lost)
    tmp_reserve = copy.deepcopy(reserve)
    
    for i in lost:
        for j in reserve:
            if i == j : 
                tmp_lost.remove(i)
                tmp_reserve.remove(j)
                
    lost = tmp_lost
    reserve = tmp_reserve 
    
    answer = n - len(lost) 
    
    for i in lost: 
        if i-1 in reserve :
            answer += 1 
            reserve.remove(i-1)
        elif i+1 in reserve:
            answer += 1 
            reserve.remove(i+1)
    
    return answer

쉬워보이는데 오류가 생각보다 많이 난다. 

내가 수정한 내용은 아래와 같다. 

1. lost 정렬하기 ( greedy 니까 작은 수 부터 정렬해서 앞 사람한테 먼저 빌리고 없으면 다음사람에게 빌린다 ) 

2. 잃어버렸는데 여벌이 있는 학생 처리하기 

   - 얘네는 잃어버렸지만, 여분이 있으므로 수업에 참여할 수 있다. 

   - 하지만 빌려줄 수는 없음. 

   => lost 랑 reserve 에 모두 들어가 있는데 실제로 처리는 안되므로 빼주어야 한다. 

   - 이 때, if 문 안에서 바로 lost 랑 reserve를 remove 로 처리하면 누락 될 수 있으므로, 깊은 copy를 통해 따로 바꿀

     리스트를 마련한 다음에 나중에 대입해준다. 

3. 처음에 잃어버리지 않은 학생 수를 세는 것은 ( n - len(lost) ) 2 단계 이후에 적용한다. 

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        result = 0 
        
        for i in range(len(prices)-1):
            if prices[i] < prices[i+1]:
                result += prices[i+1] - prices[i]
                
        return result 

쌀 때 사서 비쌀 때 팔아 가장 높은 수익을 얻는 문제.

그리디 알고리즘을 사용하여 풀면 간단하다. 

만약, 현재보다 다음 값이 오른다면 사고 판다. 

leetcode.com/problems/best-time-to-buy-and-sell-stock-ii/

n = int(input()) # 회의의 수 

data=[]
for i in range(n):
  data.append(list(map(int,input().split())))   # [ 시작시간, 끝나는 시간 ]

data=sorted(data, key = lambda x: (x[1],x[0]) )

cnt= 0
m = 0

for meet in data:
  if meet[0] >= m : 
    cnt += 1 
    m = meet[1]

print(cnt)

step1) 가장 빨리 끝나는 순서로 정렬한 수, 시작 시간 별로 정렬한다. 

step2) 제일 처음으로 , 가장 빨리 끝나는 강의가 포함된다. 

step3) 그 이후로는, 앞의 강의가 끝나는 시간에 가장 가깝게 시작되는 강의를 배치하고 그 강의 끝에 다시 가장 가까운 강의를 배치한다. 

https://www.acmicpc.net/problem/1931

1. 정의 

매 순간 최적이라고 생각되는 것을 선택하여 최적 해에 도달하는 기법. 

2. 속성 

- greedy choice propoerty   :  앞의 선택이 이후에 영향을 주지 않음 .

- optimal substructure         :  문제 전체에 대한 최적 해가 부분 문제에서도 최적 해를 만족해야 함. 

3. 대표 예제 

1)  분할 가능한 배낭 문제 ( Fractional knapsack problem ) 

     풀이 방법 :  단위 무게당 값어치가 가장 큰 것 부터 가방에 넣는다. 

                        <--> Dynamic Programming의 '0-1 Knapsack Problem)이랑 차이! 

2)  교실 할당 문제 ( Activity-Selection Problem )  : 한정된 교실 내에 최대 수업을 배정하자. 

     풀이 방법 : 종료 시간이 가장 빠른 수업을 배치하고 이와 겹치지 않는 나머지 수업을 배치함. (  O(n)  ) 

3)  Huffman Coding :  그리디 알고리즘을 사용해서 데이터를 압축하는 기법. 

     풀이 방법 : 문자가 나오는 빈도에 따라 암호화 비트 수를 달리한다. 높은 빈도의 문자열은 짦게, 낮은 빈도의 문자열은 길게. 

                      문자열이 길 수록 더욱 압축률이 좋다. ( O(nlogn)  ) 

n = int(input()) # 1<=n<=1000
data= list(map(int,input().split()))

k = 0 
cnt = 0 

for i in data:
  if i == k : 
    cnt += 1 
    k = ( i + 1 ) %3 

print(cnt)

# 볼링공 고르기 

n, m = map(int,input().split())
data = list(map(int, input().split()))
# n은 공의 수, m 은 최대 무게 
# 서로 다른 무게를 골라야함.. 

cnt = 0 
next = 0 

for index in range(n):
  next = index +1 
  while next < n : 
    if data[index] != data[next]:
      cnt += 1
    next += 1
    
print (cnt)

# 볼링공의 최대 무게를 활용해 보자 

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

array = [ 0 ] * 11 

for x in data:
  array[x] += 1 

cnt = 0 
for i in range(1, m+1 ):
  n -= array[i]
  cnt += array[i] * n 
    
print (cnt)