[1] 그리디 & 구현

[1] 그리디 알고리즘(탐욕법)

• 현재상황에서 지금 당장 좋은 것만 고르는 방법
• 문제를 풀기위한 최소한의 아이디어를 떠올릴 수 있는 능력
• 반복적으로 선택해도 최적의 해인지 → 정당성이 중요
• 탐욕법으로 얻은 해가 최적의 해가 되는 상황에서 이를 추론할 수 있어야 풀리도록 출제됨

거스름돈 문제

n=1260
count=0

array=[500,100,50,10]

for coin in arry:
	count += n//coin
	n %=coin

print(count)

public class Main{
	public static void main(String[] args){
		int n=1260;
		int cnt=0;
		int[] coinTypes={500,100,50,10};

		for(int i=0;i<4;i++){
			cnt += n/coinTypes[i];
			n %= coinTypes[i];
		}
		System.out.println(cnt);
	}
}

• 시간 복잡도 : O(K) ; K는 화페의 종류

---

[2] 구현

• 머릿속에 있는 알고리즘으 소스코드로 바꾸는 과정
• 풀이를 떠올리는 것은 쉽지만 소스코드로 옮기기 어려운 문제
  • 알고리즘 간단 but 코드가 지나칠 만큼 길어짐
  • 실수연산, 특정 소수점자리까지 출력
  • 문자열을 특정 기준에 따라 끊어 처리
  • 적절한 라이브러리를 찾아 사용해야하는 문제

2차원 공간 → 행렬(matrix) ; 표로 나타냄

시뮬레이션 및 완전탐색 문제 : 2차원 공간에서의 방향 벡터

• x: 행 / y:열
• 상하좌우 모두 출력

 

---

출처 : https://www.youtube.com/watch?v=2zjoKjt97vQ&list=RDCMUChflhu32f5EUHlY7_SetNWw&start_radio=1&rv=2zjoKjt97vQ&t=2226