[Python | week1-2] Greedy 알고리즘 | 이것이 코딩테스트다

week1-2

 

 

[오늘의 학습]

1. Greedy 알고리즘 개념

2. '체육복' 문제 풀이

3. 그리디 알고리즘 추천 학습

---

 

1. Greedy Algorithm 개념

 이름과 같이 탐욕스러운 방법으로 문제를 해결하는 방법입니다.

눈앞에 놓인 선택지 중 항상 더 좋은 것을 선택해 나갑니다

 

- 알고리즘 중 기본에 해당합니다. (하지만 쉽다는 것을 아님)

- 현재의 최적 값이 최종 최적 값에 영향을 주지 않을 때 사용할 수 있습니다.

- 한 번 한 선택을 취소할 수 없습니다.

- 도출 된 값이 해당 문제의 최적값인지는 알 방법이 없습니다. ( 그래서 NP-Hard에서 자주 사용 됨)

 

 

2. 문제 풀이

아쉽게도 공개된 문제가 아니므로 어떤 문제 인지 유추할 수 없도록 작성하는 것이 원칙이라 문제 설명은 없습니다.

 

풀이1

def solution(n, lost, reserve):
    u = [1]*(n+2) #구현을 편하게 하기 위해 0, n+1번호 공간 추가 부여
    
    # 잃어버린 학생의 번호에 -1
    for i in lost:
    	u[i] -= 1
    # 여벌로 가진 학생의 번호에 +1   
    for i in reserve:
    	u[i] += 1
        
    for i in range(1, n+1): #1번부터 n번까지
    	if u[i] == 2 and u[i-1] == 0: #i번이 2개 가지고 있는데 아래번호 학생은 없을 때
        	u[i-1: i+1] = [1, 1]
        elif u[i] == 2 and u[i+1] == 0: #i번이 2개 가지고 있는데 윗번호 학생은 없을 때
        	u[i: i+2] = [1, 1]
            
    return n - u.count(0)

풀이2

def solution(n, lost, reserve):
    s = set(lost) & set(reserve) #lost와 reserve의 교집합
    l = set(lost) - s
    r = set(reserve) - s
    
    for r in reserve:
    	if r-1 in l:
        	l.remove(r-1)
        elif r+1 in l:
        	l.remove(r+1)
            
    return n - len(l)

 

 

 

3. 그리디 알고리즘 추천 학습

알고리즘 정리로 유명한 Ries 마법의 슈퍼마리오 블로그입니다

마지막에 추천 백준 문제 풀어보는 것으로 그리디를 정복해봅시다!

 

https://m.blog.naver.com/PostView.naver?blogId=kks227&logNo=220775134486&referrerCode=0&searchKeyword=%EA%B7%B8%EB%A6%AC%EB%94%94 

탐욕적 기법(Greedy Algorithm) (수정: 2019-11-23)

 

블로그에 이어서 서적 추천입니다!

<이것이 코딩테스트다>라는 책인데요, 첫 알고리즘으로 그리디를 학습하니 처음 코딩을 준비하시는 분들에게 추천!

여러 서적 판매 사이트에서 판매 하므로 아래 링크는 참고만 해주세요!

 

http://www.yes24.com/Product/Goods/91433923

이것이 취업을 위한 코딩 테스트다 with 파이썬 - YES24