알고리즘을 좋아하는 나

동전 문제와 비슷한 풀이다.

tetrahedron에 먼저 사면체에 필요한 폭탄들의 개수를 넣어준다.

그리고 동전 문제처럼 minimumQuantity[tetrahedron[i]] = 1을 해주고,

계산한다.

동전 문제 풀이와 약간 다른점은 동전문제는 나누고나서 뭐 쭉 했다면,

이건 시간초과가 나서  minimumQuantity[i]를 구할 때, minimumQuantity[minimumQuantity[i - tetrahedron[j]] + 1 이런식으로 구했다.

동전문제도 이렇게 변경해서 풀 수 있을거 같다.

coinList[i]에는 i를 만들기위한 최소 동전 개수가 들어간다.

Bottom-Up 방식

Greedy Algorithm은 그 상황에 따라 그 상황이 최적이라고 가정하고, 최적해를 구하는 방법이다.

결론적으로는 해답에 도달한다.

하지만 그 선택들을 수집해서 최종적인 답이 최적이라는 보장이 없다.

Greedy Algorithm은 대부분 두 가지 조건이 만족된다.

1. 탐욕스런 선택 조건(Greedy Choice Proerty): 앞의 선택이 뒤에 영향을 주지 않는다.
2. 최적 부분 구조 조건(Optimal Substructure): 문제에 대한 최적해가 부분문제에 대해서도 최적해다.

문제로 돌아오면,

 K를 만드는 최소의 Ai 개수를 구하는 것이다.

풀이 방법은

오름차순으로 정렬된 동전의 가치를 저장한다.

내림차순으로 동전과 K의 가치를 비교한다. 동전의 가치가 더 크다면 그 동전은 사용하지 않고,

다음 동전으로 넘어간다.

K 가치가 더 큰게 나오면 K -= (K / Ai) * Ai를 해준다.

몇개를 사용하는지 체크해주기 위해 result += (K / Ai)를 해준다.

언어 목록

1. JavaScript: 7
2. Python: 6
3. C++: 3
4. Rust: 2
5. Go: 1
6. Vue: 1
7. Jupyter Notebook: 1
8. Java: 1
9. Swift: 1
10. Unknow Languages: 2

Front-End쪽 프레임워크 관련 Repository들이 많이 보인다.

JS가 뜨는만큼 필요한 기능인 Type Annotation API도 보인다.

가상화폐가 요즘 핫한데, bitcoin과 관련된 Repository인 misocoin도 보인다.

Caputre한 ScreenShot을 글자로 변환해주는 CaptuocrToy도 있다.

나머지는 Machine Learning 관련이다.

Machine Learning과 Deep Learning 관련 Repository는 NVDIA, Facebook, Google, Qihoo360 의 것들이다.

JS는 꾸준히 점유율이 높고, 가상화폐가 뜨면서 관련된 Repository도 점유율이 높아졌다.

딥러닝과 머신러닝쪽은 잘 몰라서 지켜봐야겠다.

min ~ max에 i^2 의 배수가 몇개 있는지를 찾는다.

그리고 있으면 count에 더해준다.

이 경우는 n의 m승 이미 계산된거.

이 경우는 i 가 6인경우로 예를 들 수 있다.

i가 6이면 2와 3에서 증가된다.

6의 배수들을 1로 변경해주고,

이 코드에서 6의 배수들이 중복으로 계산됐던걸 빼준다.

에라토스테네스의 체를 이용해서 소수들을 구하고

시간복잡도를 줄여주기 위해

i -= 2 를 해줬다.

그리고 for loop을 2개 중첩안시킴

에라토스테네스의 체의 방법을 사용하는데, 소수를 구하는게 목적이 아니고 K 번째 지워지는 숫자를 구하는게 목적

1 1 1 1    모

1 1 1 0    도

1 1 0 0    개

1 0 0 0    걸

0 0 0 0    윷

1이 나올때마다 count에 --해줘서 character형 배열에서 뽑아 쓰는식으로 했다.

0! = 1

팩토리얼 구하는 문제.

N은 약수의 처음 주어진 숫자와 마지막 숫자를 곱해주면 나온다.

예를 들어 9가 N이면

3 이 약수로 있다.

그러면 3 * 3 = 9

20 이면

2 4 5 10

2 * 10 = 20 

20 은 2 * 2 * 5 로 소인수 분해가 된다.

2 와 10