알고리즘 분류별 공부

알고리즘 - Greedy

탐욕 알고리즘은 경우를 선택할 때 그 순간의 최선의 경우를 선택해가는 알고리즘이다.

언제 사용하는가?

그때 그때 선택을 하기 때문에 성능이 빨라야 하는 경우에 사용한다.

이전의 선택이 이후에 영향을 주지 않는 경우, 부분의 최선이 합쳐져 전체의 최선이 되는 경우에 사용한다.

in java

List<Integer> list = new ArrayList<>();
list.add(1);
list.add(2);
list.add(3);
Collections.sort(list);


list.get(list.size()-1);

위와 같이 정렬을 해서 그때 그때 최소/최대값을 찾거나 문제에 따라 알맞는 최선의 값을 구한다.

알고리즘 - DP

분할정복법으로 하나의 큰 문제를 여러 개의 작은 문제로 나누어서 해결해가는 것이다.

일반적인 재귀와 유사하며 일반적으로 문제의 점화식을 도출해내면 해결할 수 있다.

언제 사용하는가?

동일한 문제가 반복해서 나타나는 경우

부분 문제의 최적 결과 값을 사용해 전체 문제의 최적 결과를 낼 수 있는 경우

최대/최소를 계산하거나 특정 조건 내 카운트, 확률 등의 경우가 있다.

풀이 방법

1. 문제의 변수 파악

   보통 정답으로 구해야하는 것을 변수로 둔다.

2. 점화식 도출

   피보나치에서 d(p) = d(p-1) + d(p-2)

3. 결과값 저장

   결과값을 dp에 저장해간다.

4. 점화식을 따르지 않는 가장 작은 상태 기록

   최종 결과 중에 원하는 값을 가져간다.

5. 구현

   • Top-down: 재귀 사용

     위에서부터 내려오면서 이전의 상태 사용해가며 문제 해결

   • Bottom-up: 반복문 사용

     아래부터 계산을 수행하고 누적해 전체의 큰 문제 해결

in java

참고