이분 탐색에 대해 공부하고 문제를 풀다 보니
그리디 알고리즘과 투 포인터 알고리즘이라는 걸 알게 되었다

뭔지 궁금하니 가볍게만 알아보자

탐욕의 항아리

투 포인터

링크에다가 정리해서 적어놓았고
간단하게 이것들에 대한 생각을 적겠다

그리디 알고리즘

뜻

그리디… (욕심이라는 뜻)

닉값 하려는 듯이 욕심쟁이다

마시멜로 실험 아는가?

이놈은 고민 1초도 안하고 집어먹을 놈이다

매 순간순간 당장 이득인 것만 고르는 형태로
전부 탐색 후 최적을 찾는 방식이 아닌
탐색 할 때마다 지금 최적인 것만 마구잡이로 고르는 방식이다

왜 이런식으로 일처리를 하는가?

단순하다
그게 제일 빠르니까

단점으로는
최적을 보상하지 못한다는 거지만
어지간해선 최적에 비슷한 답을 들고온다

외판원 문제 같은 특수한 상황을 제외하고
얼마나 최적인지 보다 속도가 중요하다면
채용할 가치가 있는 알고리즘이다

예시

대표적 예시인 거스름 돈 문제다 ```py 입력: N (거슬러 줄 금액) 동전종류 = [500, 100, 50, 10] 카운트 = 0

for coin in 동전종류: 카운트 += N // coin N = N % coin

출력: 카운트

# 투 포인터 알고리즘

이분 탐색 보다 알게 된걸로
<br><br>
점 두개의 위치를 기록해<br>
처리하는 알고리즘이다<br><br>
특정 값을 찾는 거라면 몰라도<br>
두 값의 특정 조건을 찾는 경우는<br>
투 포인터가 더 빠르고 간단하다
<br><br>
간단히 말해서<br><br>
“모든 쌍/구간”이 필요하면 → 투 포인터

“특정 값/경계”가 필요하면 → 이분 탐색
<br>
<br>
라고 보면 된다

## 예시

1. 배열의 가장 왼쪽을 가리키는 포인터를 ‘left’로, 가장 오른쪽을 가리키는 포인터를 ‘right’로 설정한다.

2. left가 right보다 왼쪽에 있는 동안 반복한다:
   • 두 포인터가 가리키는 값을 더해서 ‘현재 합’을 구한다.
   • 만약 ‘현재 합’이 목표값과 같으면,
     • 쌍을 찾은 것이므로 쌍을 출력(또는 저장)한다.
     • 두 포인터 모두 한 칸씩 안쪽으로 이동한다.
   • 만약 ‘현재 합’이 목표값보다 작으면,
     • left 포인터를 한 칸 오른쪽으로 이동한다.
   • 만약 ‘현재 합’이 목표값보다 크면,
     • right 포인터를 한 칸 왼쪽으로 이동한다.
3. 포인터가 서로 만나거나 교차하면 반복을 종료한다. ```