[알고리즘] 4. 그리디 && 구현

Index

1. 그리디

2. 구현

3. 추천 문제

4. 참고자료

---

1.  그리디

Greedy Algorithm

- 현재 상황에서 지금 당장 좋은 것만 고르는 방법

- 정당성 분석, 반복적 선택시 최적의해 보존되는지 검토

 

(Exam)

- 거스름 돈: 가장 큰 동전의 단위가 항상 작은 단위의 배수이므로 작은 단위의 동전들을 종합해 다른 해가 나올 수 없음

 

2.  구현

Implementation

- 머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정(problem->thinking->solution)

- 2차원 공간을 다룰 경우 Matirx(행렬)을 사용

- 시뮬레이션 및 완전 탐색의 경우 2차원 공간에서의 방향 벡터가 활용

dx = [0, -1, 0, 1]
dy = [1, 0, -1, 0]


for i in range(4):
  nx = x + dx[i]
  ny = y + dy[i]

- 완전 탐색(Brute Forcing): 가능한 경우의 수를 모두 검사해보는 탐색 방법

 

 

(유형)

- 알고리즘은 간단한데 코드가 지나칠 만큼 길어지는 문제

- 실수 연산을 다루고, 특정 소수점 자리까지 출력해야 하는 문제

- 문자열을 특정한 기준에 따라 끊어서 처리하는 문제

- 적절한 라이브 사용하는 문제

 

3.   추천 문제

그리디

- 체육복(https://school.programmers.co.kr/learn/courses/30/lessons/42862)

- 조이스틱(https://school.programmers.co.kr/learn/courses/30/lessons/42860)

- 큰 수 만들기(https://school.programmers.co.kr/learn/courses/30/lessons/42883)

- 구명보트(https://school.programmers.co.kr/learn/courses/30/lessons/42885)

- 섬 연결하기(https://school.programmers.co.kr/learn/courses/30/lessons/42861)

- 단속카메라(https://school.programmers.co.kr/learn/courses/30/lessons/42884)

 

---

참고 자료

[Video: 동빈나의 이코테 2021 (그리디/구현)] https://www.youtube.com/watch?v=2zjoKjt97vQ&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC&index=3