📌 문제 유형: DPhttps://www.acmicpc.net/problem/1463   📌 풀이 문제를 읽으면서 딱 눈에 들어오는 것은, 시간 제한이 0.15초 밖에 안된다는 점이다. 그리고 N이 1~10^6이라면, 완전탐색으로는 시간 초과가 날 것이라는 걸 느끼게 된다.  이 상태에서 문제를 좀 더 살펴보자.  3으로 나누어 떨어질 때, 2로 나누어 떨어질 때, 둘 다 아닐때 이렇게 3가지 경우에 대해 연산을 제한해 두고 있다. 이 3개의 연산을 적절히 사용해 연산 횟수를 MIN로 만드려고 한다. 드는 생각들! 1. 3의 배수일 때 (2의 배수는 아님)2. 2의 배수일 때 (3의 배수는 아님) 3. 둘 다 아닐 때 - 1을 뺀다. 4. 6의 배수일 때 ==> 이 경우가 추가되어 고려될 수 있다. ..

📌 문제유형: DP https://www.acmicpc.net/problem/1003   📌 풀이  이 문제에서 포인트는 !!! 시간 제한이 0.25초 밖에 안된다는 점이다. 따라서 재귀함수로 작성하게 되면, 1시간초과에 걸리게 된다.  그 해결 방법은 동적 계획법(DP)에 있다.  즉, 메모제이션을 활용해야 한다. 메모제이션이란 앞서 계산했던 값을 저장해두어, 추후 다시 필요하게 될 때 다시 계산하는 것이 아니라 이미 계산된 값을 불러오는 것이다.  위의 문제는, n에 대한 피보나치 수열이 계산될 때 0과 1이 몇 번씩 필요로 되는가에 있다.  DP를 풀 때 1. 하나의 예제를 가지고 직접 손으로 적어보면서 실마리를 찾는다. 2. 규칙성을 찾아본다. 3. 이를 점화식으로 세워본다. (앞에서 #를 선..

※ 구글링하면서 재구성한 내용입니다. 세상 모든 개발자 블로그 만만세※ 계속 공부하면서 내용 채울 것임. 📌 탐욕법 (Greedy Algorithm)⭐ 푸는 방법 1. 일단 완전 탐색을 고민해본다. 제한시간/메모리 초과되는지 확인한다. 2. 문제에서 규칙성을 찾으면 풀 수 있는 편이다. 3. 아이디어를 떠올리고, 반레가 있는지 따져보면 된다.  ‘각 단계에서 최적이라고 생각되는 것을 선택’ 해 나가는 방식으로 진행하여 최종적인 해답에 도달하는 알고리즘💡 각각 상황에서 '최적'이라고 생각하는 방법을 선택한다.(상황에서 가장 높은 수를 선택합니다.) 그리디 알고리즘을 적용하기 위해서는 아래 2가지 속성을 만족해야 한다고 한다.  탐욕 선택 속성(Greedy Choice Property) 이란?각 단계에서..