알고리즘 10주차

09. 억지 기법과 탐욕적 전략

 

09-1 문제 해결 과정

문제의 이해 - 설계 방향 결정 - 알고리즘 설계 - 정확성 검증 - 알고리즘 분석 - 알고리즘 구현

 

*설계 방향 결정

- 순서적 알고리즘 / 병렬적 알고리즘

- 최적해 / 근사해

 

*알고리즘 설계 기법

- 억지 기법: 문제의 정의를 직접 사용. 원하는 답을 구할 때까지 모든 경우 테스트.

- 탐욕적 기법: 단순하고 직관적인 방법. 어떤 결정을 해야할 때마다 그 순간에 최적인 것을 선택.

- 분할 정복: 큰 문제를 해결 가능한 작은 문제들로 반복적으로 분할하여 해결.

- 동적 계획법: 분할 정복과 유사. 작은 문제를 해결한 결과를 저장하여 큰 문제를 해결할 때 사용.

- 공간으로 시간 벌기: 추가 공간을 사용하여 처리시간을 단축

- 백트래킹과 분기한정

 

 

09-2 억지 기법

 

예시) 순차 탐색, 선택 정렬, 문자열 매칭 문제

 

억지 기법이란? brute-force

- 문제 해결을 위해 가능한 모든 경우의 수를 하나하나 전부 시험해본다.

- 논리적 최적화를 하기 전에 문제를 처음부터 끝까지 단순한 반복과 탐색으로 푼다.

 

 

09-3 탐욕적 기법

 

탐욕적 기법이란? greedy

- 문제를 해결할 때 각 단계에서 최적이라고 생각되는 선택을 반복적으로 한다. 선택은 갱신할 수 있다.

- 전체 최적의 해를 보장하지 않지만, 특정 조건을 만족할 때 최적의 해를 구할 수 있다.

 

---

 

2798번 블랙잭 

N장의 카드 중에서 3장의 카드를 고른다.

플레이어가 고른 카드의 합을 M과 최대한 가깝게 만들어야 한다.

N장의 카드가 주어졌을 때, M을 넘지 않으면서 M에 최대한 가까운 카드 3장 합을 구해 출력하시오.

2402-ECC-AlgorithmStudy/백준/Bronze/2798. 블랙잭 at main · daj33/2402-ECC-AlgorithmStudy

 

1436번 영화감독 숌

종말의 수: 666이 적어도 3개 이상 연속으로 들어가는 수.

666 - 1666 - 2666 ...

N번째 영화의 제목은 세상의 종말 N으로 짓는다.

숌이 만든 N번째 영화의 제목에 들어간 수를 출력하는 프로그램을 작성하시오.

2402-ECC-AlgorithmStudy/백준/Silver/1436. 영화감독 숌 at main · daj33/2402-ECC-AlgorithmStudy

 

14469번 소가 길을 건너간 이유 3

N마리의 소가 있다.

소가 도착한 시간, 검문받는데 걸리는 시간은 소마다 다를 수 있다. 두 소가 동시에 검문을 받을 수 없다.

모든 소가 농장에 입장하려면 걸리는 시간. 

2402-ECC-AlgorithmStudy/백준/Silver/14469. 소가 길을 건너간 이유 3/소가 길을 건너간 이유 3

 

2847번 게임을 만든 동준이

핵심 전략: 레벨을 내림차순으로 정렬하여, 해당 레벨을 처리하는 순간마다 다른 레벨의 점수를 조정하여 조건을 만족하도록 한다.

(예시를 문제를 손으로 풀어보며, 해결방식을 직접 고민해보는 과정이 필요하다)

2402-ECC-AlgorithmStudy/백준/Silver/2847. 게임을 만든 동준이 at main · daj33/2402-ECC-AlgorithmStudy

 

*레벨을 오름차 순으로 정렬했을 경우, 위 전략을 실행할 수 없다 

n = int(input())
scores = []
count = 0
for i in range(n):
  s = int(input())
  scores.append(s)
  for j in range(len(scores)-1):
    while(scores[j] >= scores[j+1]):
      scores[j]-=1
      count += 1
print(count)

 

반례: [5, 3. 7. 4]의 경우, 위의 알고리즘으로 해결할 수 없다

5

5, 3 → 2, 3 

2, 3, 7 

2, 3, 7, 4 → 2, 3, 3, 4

최종 결과 2, 3, 3, 4로 문제의 조건을 충족하지 못한다.

 

즉, 다음 값(j+1)을 이미 고정된 값으로 가정하여, 수정하지 않고 있다. 그러나 j+2에 의해 j+1의 값이 바뀔 수 있어, 조건을 만족하지 못하는 경우가 생긴다. 내림차 순으로 뒤에서부터 탐색하면 고정된 값을 순차적으로 생성하로 문제를 해결할 수 있다.

 

4

4, 7 → 4, 3 (4는 그 다음 수들에 의해 변경되지 않는다)

4, 3, 3  → 4, 3, 2 (3은 그 다음 수들에 의해 변경되지 않는다)

4, 3, 2, 5→ 4, 3, 2, 1