[그리디 알고리즘]

contents	dated
그리디 알고리즘 소개 (바크킹) backjoon  1931, 2217, 1026	2024.07.18

 

 

Greedy =  지금 가장 최적인 답을 근시안 적으로 택하는 알고리즘 

             = 관찰을 통해서  탐색 범위를 줄이는 알고리즘 

 

 

이상적인 알고리즘 풀이

          1. 관찰을 통해 탐색 범위를 줄이는 방법을 고안한다. 

          2. 탐색 범위를 줄여도 올바른 결과를 낸다는 사실을 수학적으로 증명한다. 

          3. 구현해서 문제를 통과한다. 

 

현실적인 알고리즘 풀이 

          1. 관찰을 통해 탐색 범위를 줄이는 방법을 고안한다. 

          2. 탐색 범위를 줄여도 올바른 결과를 낸다는 강한 믿음을 가진다. 

          3. 믿음을 가지고 구현해서 문제를 통과한다. 

 

코딩 테스트에서 추천 전력 

 

        1. 거의 똑같은 문제를 풀어봤거나 간단한 문제여서 나의 그리디 풀이를 100% 확신한다. 

             --> 짜서 제출해보고 틀리면 빠르게 손절 

 

        2. 100% 확신은 없지만 맞는 것 같은 그리디 풀이를 찾았다. 

             --> 일단은 넘어가고 다른 문제를 풀게 없거나 종료가 20~40분 남은 시점에 코딩 시작 

 

 

BOJ1931

import sys 

N = int(sys.stdin.readline())
timeline= []
for i in range(N):
    start, end = map(int, sys.stdin.readline().split())
    timeline.append((start,end))

timeline.sort(key=lambda x : (x[1], x[0]))
count = 1 
end = timeline[0][1]
for i in range(1,N):
    if timeline[i][0]>=end:
        end = timeline[i][1]
        count += 1

print(count)

#lambda의 개념 
#그리디 알고리즘 
#key의 개념

 

 

BOJ 2217

import sys

N = int(input())
list =[]
for i in range(N):
    list.append(int(input()))

list.sort(reverse=True)
result = []

for j in range(N):
    result.append(list[j]*(j+1))

print(max(result))

 

BOJ 1026

import sys  


N= int(input())
first= list(map(int, sys.stdin.readline().split()))
second= list(map(int, sys.stdin.readline().split()))

first.sort()
second.sort(reverse=True)

answer=0
for i in range(N):
    answer+= int(first[i])*int(second[i])

print(answer)