그리디(greedy) 컨닝페이퍼

greedy라 아주 맘에 드는 이름이다.-> 내 식성과 비슷한거같다 후후후

 

근데 뭔가 이름이 거창하지만 진짜 별거 없는거같다

그리고 이따구로 푸는게 맞나싶다 그냥 기도 메타랑 다를께 뭔데

 

그냥 단계단계별로 최고 좋은 조건 고르고 최적해와 맞기를 기도하는거다

그래서 최적해가 아닐수있고 정확히 말하자면 최적해임을 검증하는 과정이 필요하다.

 

그래서 근사값을 뽑아낼수있는 하나의 전략이라고 보면된다. 근데 우리는 풀기만 하면 장땡이니까 좀 애매하면 써봐서 풀리면 좋은거지뭐

 

그리디 알고리즘의 특징은 

극단적인걸 좋아하는데 -> 무조건 큰경우부터 , 무조건 작은 경우부터, 무조건 긴 경우 부터, 무조건 짧은 경우부터 이런식으로 문제를 접근할때 극단적인 시각으로 접근하면된다 .

그래서 정렬과 함께 사용하는 경우가 많다. -> 조건에 따라 정렬해놓고 하나하나씩 풀어나가 보는것이다 그렇다면 파이썬에서 정렬은 어떻게하는지보자

 

 

정렬

일단 정렬의 기본적인것

 

1. 리스트.sort() 를 하면 리스트 자체가 바뀜

만약 새로운 리스트를 뽑고싶다면 sorted()함수를 사용하자

 

2. 오름차순 내림차순

reverse = Ture,False이걸로 구분하면됨 True일때 작은것부터 정렬

 

3.key에 신기한거 넣어도 숫자 혹은 문자열 이런 기존에 구분할 수 있는 것이라면 알잘딱 하게 구분해줌 

리스트.sort(key=len) 이런것도됨 알잘딱하게 알아들음

 

정렬하는 예시 

sorted (리스트 , key = 조건 )
예시 :

data = [(10,10),(15,12),(20,10),(25,8),(30,5)] 

data_lsit = sorted(data , key = lamda x:x[1]/ x[0], reverse = True)

이런식으로 람다로 처리가능 값들간의 계산 이런것도 가능

students = [
        ('홍길동', 3.9, 2016303),
        ('김철수', 3.0, 2016302),
        ('최자영', 4.3, 2016301),
]
sorted(students, key=lambda student: student[2])
[('최자영', 4.3, 2016301), ('김철수', 3.0, 2016302), ('홍길동', 3.9, 2016303)]

뭐 이런식으로 특정값을 키로 던져줄수도 있음

 

문제풀다 나온 꿀팁

정렬부터해 제발!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! 

정렬안할꺼면 풀지마

그리고 정렬하고 문제풀때 뭔가 어떤 조건들중 최소값 이런식으로 여러가지 방향성이있으니까 머리를 열고 생각해야한다

ex) 캔디캔디 같은 문제

캔디캔디 말나온김에 돌아버린 노래한번 듣고가자

https://www.youtube.com/watch?v=UoK8DaJRDaM&list=RDEMG_uKXfzSX1fRct2gG5sqhA&index=2 

진짜 캔디캔디 왜 못풀었을까 아아아악

 

 

정렬할떄 기준이 하나가 아닐수있음 

ex)1931번 회의시간

meetingList.sort(key= lambda x : (x[1], x[0]))

이렇게 ()와 ,로 묶어서 줄경우 첫번쨰 기준이 같을경우 두번쨰 기준으로 정렬됨 이런거 필요한경우 있으니 꼭기억하자