그리디greedy , 구현

 

📍그리디 Greedy  = 욕심쟁이 알고리즘 = 탐욕법

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

 

- 기준에 따라 좋은 것을 선택하는 알고리즘 

➡️ 코테 문제에서 '가장 큰 순서대로', '가장 작은 순서대로' 와 같은 기준을 제시해줌 

 

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

2839번: 설탕 배달

 

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
	
		 int N = sc.nextInt();
				
			if (N == 4 || N == 7) {
				System.out.println(-1);
			}
			else if (N % 5 == 0) {
				System.out.println(N / 5);
			}
			else if (N % 5 == 1 || N % 5 == 3) {
				System.out.println((N / 5) + 1);
			}
			else if (N % 5 == 2 || N % 5 == 4) {
				System.out.println((N / 5) + 2);
			}
	}
}

 

 

* 최적의 해 

: 대부분의 문제는 그리디 알고리즘을 이용했을 때 '최적의 해'를 찾을 수 없을 가능성이 다분함 

- 대부분의 그리디 알고리즘 문제에서는 문제풀이를 위한 최소한의 아이디어를 떠올리고 이것이 정당한지 검토할 수 있어야 한다 

➡️ 그리디 알고리즘으로 얻은 값이 정말 최적의 선택지인지 추론해야 함 

예를 들어 거스름돈 문제에서 큰 동전을 우선하여 배분한 경우가 무조건 거스름돈이 가장 적게 나오는 경우라도 할 수 없다

 

 

 

◼️ '수열' 파악하기 

- 반복되는 수열이 나타나는 문제인지 확인하기 

 

◼️ 적절한 함수 사용하기 

- sort(), min()등 계산을 빠르게 해주는 함수 활용 

 

 

 

 

 

📍구현 implementation 

: 머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정 

- 어떤 문제를 풀든 간에 소스코드를 작성하는 과정은 필수이므로 구현 문제 유형은 모든 범위의 코딩 테스트 문제 유형을 포함하는 개념

- 사소한 입력 조건 등을 문제에서 명시해주며 문제의 길이가 꽤 긴 편 

 

 

- '이것이 코딩테스트다' 책에서는 완전탐색과 시뮬레이션 유형을 '구현'으로 묶어둠 

 

*완전 탐색

: 모든 경우의 수를 주저 없이 다 계산하는 해결 방법

 

* 시뮬레이션 

: 문제에서 제시한 알고리즘을 한 단계씩 차례대로 직접 수행 

 

◼️  방향 Direction 을 설정해서 이동하는 문제

- 일련의 명령에 따라 개체를 차례대로 이동시키는 문제 

➡️ dx, dy라는 별도의 리스트를 만들어 방향을 정하는 것이 효과적 

; 하나의 배열을 만들어서 반복문을 이용하여 모든 방향을 차례대로 확인할 수도 있음