My Tech Blog (탐욕법)

그리디 알고리즘(Greedy Algorithm)개요greedy형용사 - 1. 탐욕스러운 2.욕심 많은  그리디 알고리즘(Greedy Algorithm)은 매 순간 가장 최적이라고 판단되는 선택을 반복하여 최종 해답을 구하는 알고리즘이다. 즉, 현재 단계에서의 최선의 선택이 최종적으로도 최적해(Optimal Solution)가 된다고 가정하고 문제를 해결한다. 코딩테스트에서 만날 경우 사전에 외우고 있지 않아도 풀 수 있는 가능성이 높은 문제 유형지역 최적해(Local Optimum) → 전역 최적해(Global Optimum) 보장 가능해야 함탐욕적 선택(Greedy Choice)과 최적 부분 구조(Optimal Substructure) 만족✅ 동적 프로그래밍(Dynamic Programming)과 차이..

📑 1. 문제설명💡 2. 접근방식 조이스틱을 양 옆으로 이동하는 좌우 이동 횟수(move) 조이스틱 좌우로 이동하면서 알파벳 변경를 위해 상하 이동 하는 횟수(answer) 두 개를 answer에 누적하면서 더해줘야 한다. 여기서 문제되는 것은 단방향이 아니아 양쪽(좌,우)로 조이스틱이 움직일 수 있기 때문에 가장 빠른 경로를 찾아야 한다는 것이다. 이 때 연속된 AAA의 개수를 계산 해 주어야 한다.  ✅ 알파벳 변경 현재 인덱스에서 A를 빼준 값  vs Z부터 시작해서 현재 인덱스를 빼준 값 + 1두 개를 비교해서 더 작은 값을 선택해 준다.전자는 스틱을 정방향▼ A부터 순차적으로 Z로 내려가면서 바꾸는 거고후자는 스틱을 먼저 역방향▲으로 1칸 돌려서 Z를 만든 다음에 반대로 해당 알파벳을 찾아가..