알고리즘 6일차

백트래킹

== 탐색 알고리즘 + 조건(유망)

솔직히 재귀에다가 조건문 박으면 백트래킹이라고 생각함.

 

백트래킹 알고리즘

# 대략 이런 모습

def backtrack(이번선택):
  if 종료조건:
	  # add, print 등등
	  return
	  
  for 아래선택 in 이번선택의 아래선택들:
	  if 유망여부판단(아래선택):
	    backtrack(아래선택)
	    선택해제 # 다시 선택을 해제하는 것이 필요할 수 있음

<도전해봐야할 문제>
nQueen(https://www.acmicpc.net/problem/9663)

유먕 여부를 판단하는 함수를 만들어보자

가로축: 여왕과 같은 가로축에 여왕을 둘 수 없음
세로축: 세로축에 하나의 여왕만 존재할 수 있다.


2차원으로 진행하면 시간초과(그래도 만들어볼것)
아래처럼 정리하면 1차원으로 가능.
queens=[None, 1 , None, None]

 

시도는 해보았지만 대각선에서의 어떻게 진행해야할지 몰랐엇고 구현자체가 너무 어렵다.
강의를 들었어도 시도를 해보았지만 가로,세로,왼쪽대각선,오른쪽대각선의 규칙은 설명대로 알았지만 구현이 너무 어렵다...

깊이우선탐색 (DFS)

DFS - 탐색 알고리즘(전부 찾음)

: 저돌적인 녀석 일단 끝까지 간 다음 딴 생각
스택을 이용함

ex) 드라마 하나씩 몰아보기 == 깊이 우선 탐색 (Depth-First-Search, DFS)

BFS - 탐색 알고리즘(전부 찾음)

:차근차근 각 단계씩 살펴봄
Queue를 이용해서 탐색.

ex) 여러 드라마 하나씩 보기 == 너비 우선 탐색 (Breadth-First-Search, BFS)

탐색 알고리즘

그래프(Graph)라는 것을 탐색

그래프 : 노드, 하나의 점(Node)과 각 노드를 연결하는 간선(Edge)으로 구성된 자료구조

트리랑 비슷하게 생겼는데 트리가 그래프 안에서 하나의 형태임

 

DP: 다이나믹 프로그래밍

현실을 표현하기 위해 (자료구조) + 현실의 문제를 풀기위해 (알고리즘)

메모이제이션

계산한 결과를 적어두고 동일한 연산을 할 때 참고함.
TOPDOWN방식으로 DP문제에 적용

 

타뷸레이션

지금 당장 필요하지 않아도 일단 계산해서 메모하는 것.

DP문제의 핵심
"어떻게 이전의 사용된 값을 재활용하지?"

 

 

<알아봐야할 내용>

의사결정 공간 트리
상태 공간 트리