Algorithm/기타 알고리즘 (2) 썸네일형 리스트형 탐욕 알고리즘 (Greedy Algorithm) 그리디(탐욕) 알고리즘 : 그리디 알고리즘은 동적 프로그래밍(Dynamic Programming) 사용 시 지나치게 많은 일을 한다는 것에서 착안하여 고안된 알고리즘이다. 여러 경우 중 하나를 결정해야할 때마다 각 단계에서 가장 최선의 선택을 하는 기법으로 이 선택이 전체적으로도 최선이기를 바란다고 볼 수 있다. ! 항상 최적의 답을 구해주지는 않음 ! -> 그리디 알고리즘은 주로 정렬 알고리즘과 짝을 이뤄 출제되는데 "가장 큰 or 작은 순서대로"라는 기준을 제시해줌. * 최단 경로를 빠르게 찾아야 하는 문제 = 플로이드 워셜 or 다익스트라 알고리즘 대표적인 그리디 문제 : 거스름돈 문제 -> 500원, 100원, 50원, 10원짜리 동전이 무한히 존재한다. 이 때, 손님에게 거슬러 줘야 할 돈이 N.. 투포인터(Two Pointer) 알고리즘 투포인터(Two Pointer)알고리즘 : 리스트에 순차적으로 접근해야 할 때 두 개의 점의 위치를 기록하면서 처리하는 것을 의미하는 알고리즘 특징 1) 각 원소마다 모든 값을 순회해야할 때 사용 특징 2) 연속하다는 특성을 이용해서 철 특징 3) 두 개의 포인터(커서)가 움직이면서 계산 특징 4) 처음부터 생각하기 어려움 -> 쉬운 방법부터 생각하기 투포인터 알고리즘의 과정 1. 시작점(start)과 끝점(end)이 첫 번재 원소의 인덱스(0)를 가리키도록 한다. 2. 현재 부분 합이 M과 같다면 카운트한다. 3. 현재 부분 합이 M보다 작다면 end를 1 증가시킨다. 4. 현재 부분 합이 M보다 크거나 같다면 start를 1 증가시킨다. 5. 모든 경우를 확인할 때까지 2번부터 4번까지의 과정을 반복.. 이전 1 다음
