알고리즘 - 스택 Ⅱ
백트래킹 복습
진행하던 경로가 non-promising 하면 더이상 진행하지 않고 이전 단계로 돌아가서 다른 해결책을 찾는 알고리즘
*기본 형식
def backtrack(이번 선택):
if 종료조건:
return
for 아래 선택 in 이번 선택의 아래 선택들:
if 유망여부판단(아래 선택):
backtrack(아래선택)
선택 해제
# 재귀함수의 형태백트래킹의 대표적인 문제 N-Queen
풀어보기
깊이 우선 탐색 (DFS - Depth First Search)
Search는 그래프를 탐색하는 알고리즘.
네트워크 분석 생각하면 됨.
깊이 우선 탐색 DFS vs. 너비 우선 탐색 BFS (Breadth First Search)
- 깊이 우선 탐색의 경우 한 경로를 끝까지 가본 다음 다른 경로로
- 너비 우선 탐색의 경우 각 단계를 살펴보면서
DFS == 재귀를 이용한 완전 탐색
참고) 햄버거 다이어트 문제
다이나믹 프로그래밍 (DP)
중복 연산에 대해 한 번 연산해 둔 것을 기억해 두었다가 사용하는 것.
메모이제이션 Memoization - Top Down 방식: 필요한 경우에만 계산해서 메모
타뷸레이션 Tabulation - Bottom Up 방식: 필요하지 않아도 일단 계산해서 메모
DP 문제에서는 대부분 Bottom Up, Tabulation 방식으로 풀면 된다.
큰 문제가 작은 문제로 쪼개질 때, 작은 문제에 중복되는 연산이 많을 때 사용.
피보나치 함수를 생각하면 쉽다.
Today I Thought
오늘은 중간에 병원을 다녀와야 해서 수업을 실시간으로 듣지 못하는 바람에 조금 더 시간이 부족했다. 지난주와 비슷하게 원리는 대강 알겠는데, 코드로 구현하라면 못할듯. 계속 풀지 못하는 문제들이 쌓여가서 스스로 문제를 풀어보는 것도 중요하지만 튜터님이 풀어주신 방법을 차근차근 이해해 보는 것도 중요한 것 같다.
발전 중...