탐욕..알고리즘

그냥 큰거부터 해결해 그게 최선일 확률이 커 편할수있어

거스름돈을 최소한의 동전으로 내어줘야하는데

손님이 4260원일 줬다고치자

나에겐 500원짜리 100원짜리 50원짜리 10원짜리 원짜리가 있어

그럼 500원짜리로 먼저 8개채우고 100원짜리 2개와 50원1개 10원1개로

내어주면 최소한의 효율적인 동전갯수겟지 ? 100원짜리로 40개할필요는 없으니까.. 그런식으로 알고리즘을 짜는게 탐욕이다..

구현

데이터를 정렬할 수 있는가?
데어터를 효율적으로 탐색할수 있는가?
데이터를 조합할 수 있는가?

그냥 내가 생각한 문제 해결 과정을 컴퓨터적 사고로 구현하는것..

크게 2가지

완전탐색과 시뮬레이션

완전탐색

모든 문제는 완전탐색으로 풀수있어. 정확하고 빠를 수록 구현이 좋다고 할수있지
완전탐색은 모든경우의 수를 전부확인하여 문제를 푸는방식이고

시물레이션은 문제에서 요구하는 복잡한 구현 요구사항을 하나도 빠트리지 않고 코드로 써서 시뮬레이션하는것과 같은 느낌이다

완전탐색은 정말 무작정 답이 무조건 있다는 방법으로 푸는것
1부터 100까지 요소가 배열에 있을때 처음부터 끝까지 전부 탐색해서 무언가의 요소를 찾는것

위에쓴 예시로 무언가의 요소를 찾으라고 했을때 O(N) 보다 낮아야한다고 한다면
효율적으로 동작할수없을수있다 이진탐색으로 찾는게 효율적일수있지 그래서 모든방법을 생각해보고 효율적으로 동작하는 알고리즘이 전부탐색하는 방법밖에 없다면

완전탐색을 쓰는거..

시뮬레이션

시뮬레이션은 모든 과정과 조건이 제시되어, 그 과정을 거친결과가 무엇인지 확인하는것, 문제에서 설명해 준 로직 그대로 코드 작성하면 문제해결을 떠올리는것 자체는 쉬울수있는데 자세하게 코드로 적는게 까다로울수있다.

무언가 알고리즘 문제가 주어졌을때 이것을 하나도 트릴지않고 전부 조건에 적어야 정답을 받을수있는경우? 하나라도 놓친다면 통과할수 없게되는거..

다이나믹 프로그래밍

이것은 한번 계산한것은 다시 계산하지 않게 하는방법

피보나치할때 메모이제이션 재귀적으로 많은수는 컨트롤하기 힘들때 계산한 것을
저장해놓고 꺼내쓸수있다면 시간복잡도가 줄어들것

양갈래로 뻗어나가는 피보나치 재귀 트리를 보며 이것 계산한것을 저장하면

o(n제곱) 이 o(n)으로 줄어들어 한쪽트리만으로만으로도 계산할수있게되어 훨씬 바른 결과를 받을수있고 많은수도 컨트롤이 가능한것