[알고리즘] Greedy (python)

그리디 알고리즘
글로벌 최적을 찾기 위해 로컬 최적의 선택을 하는 휴리스틱 문제해결 알고리즘

잘 작동하기 위해 2가지 조건이 있다

• 탐욕선택 속성
  앞의 선택이 이후 선택에 영향을 주지 않는다
• 최적 부분 구조
  첫줄에 적은것과 비슷한 의미. 로컬 최적이 글로벌 최적이 되는 경우이다.

휴리스틱

교수님이 휴리스틱에 대해 1시간 넘게 열정적으로 설명해 주셨던 기억이 난다.. 설명하며 되게 행복해 보이셨다

합리적이고 체계적인 판단이 어려울 때, 필요 없을 때 빠르게 사용할 수 있는 간편추론의 방법

알고리즘에서는 최적해가 될 가능성이 없는 답들을 탐색하지 않고 답의 후보개수를 줄이는 방법이라고 한다..

• 가지치기 기법 (pruning)
• 담금질 기법 (simulated annealing)
• 유전 알고리즘 (genetic algorithm)
  대표적으로 이 3가지이고, 솔직히 수업을 들을때는 왜 중요한지도 모르겠고 잘 이해도 안되었는데 요즘 인공지능이 많이 중요해지면서 이러한 기법이 더 중요해지고 있다는 것을 느꼈다.
  특히 stable diffusion모델 checkpoint를 이것 저것 둘러보다 보면 pruned model이 많이 보인다..
  이 부분은 따로 다뤄봐야겠다.

백준 2138 전구와 스위치

import sys
input = sys.stdin.readline

n = int(input())
status = list(map(int, input().rstrip()))
target = list(map(int, input().rstrip()))

def change(stat, target):
    cop = stat[:]
    ans = 0
    for i in range(1, n):
        if cop[i-1] == target[i-1]:
            continue
        ans += 1
        for j in range(i-1, i+2):
            if j<n:
                cop[j] = 1 - cop[j]
    if cop == target:
        return ans 
    else:
        return float('inf')

cand = change(status, target)
status[0] = 1-status[0]
status[1] = 1-status[1]
cand = min(cand, change(status, target)+1)

print(-1) if cand==float('inf') else print(cand)