[데브코스] TIL - 7일차

오늘 공부한 내용 💻

• 자료구조 & 알고리즘 - 백 트래킹
• [실습] N-Queen
• 자료구조 & 알고리즘 - 동적 계획법
• [실습] 단어 퍼즐

어려웠던 내용 🤢

백 트래킹(Back Tracking)

• 백 트래킹이란?
  모든 경우의 수를 탐색하는 알고리즘이다.

• 백 트래킹의 특징

  • DFS나 BFS를 사용할 수 있다.
  • 효율을 위해서 탐색하지 않아도 되는 곳을 미리 막는것을 가지치기(Pruning)이라고 한다.
  • 자바스크립트는 재귀 효율이 나쁘기 때문에 DFS로 구현할 경우 스택을 이용하는 것이 좋다.
  • 탐색에 순환이 발생할 수 있다면 BFS를 이용하는 것이 좋다.

• 백 트래킹의 핵심은 가지치기(Pruning) 이다!

• 백 트래킹 작성 방법

  • 우선 모든 경우의 수를 찾을 수 있도록 코드를 짠다.
  • 이후 문제에서 특정한 조건을 만족하는 것만 탐색하고 나머지는 탐색하지 않도록 조건문을 작성한다.
  • 절대로 답이 될 수 없는 것에 대해서는 탐색을 종료한다.
    
    

동적 계획법(Dynamic Programming)

• 동적 계획법이란?
  해결한 작은 문제로 큰 문제를 해결하는 문제 풀이 방식이다.

• 동적 계획법은 특정 알고리즘이 아닌 문제 해결 방식임.

• 메모리를 많이 사용하지만 성능이 빠르다 !

• 두 가지 방법론이 존재한다.

  • 메모이제이션(Memoization)
    하향식 접근법
    DP에서 작은 문제들의 결과는 항상 같다.
    
    
  • 타뷸레이션(Tabulation)
    상향식 접근법
    필요한 방법을 미리 계산해두고 사용한다.

• 알겠는데, 언제 써야하는데 ????!!!!??

  가장 작은 문제를 정의할 수 있는가?
  작은 문제로 큰 문제를 해결할 수 있는가?

  위의 두 가지 조건을 만족하면 동적 계획법 문제라는 걸 알 수 있다 ~

더 공부할 내용 📃

• [실습] 단어 퍼즐 너무 어려운거 아니냐고!

• 동적 계획법 문제 찾아서 더 풀어보기
  
  

느낀점 👀

> '휴식이 ,,, 필요해 ,,,'

알바 다녀와서 할 일이 산더미인데 ! 피곤을 못이기고 잠이 들어서 !
본인에게 굉장히 실망한 하루 !
오늘 강의 양이 많지 않았어서 꾸역꾸역 해낼수 있었다 ...
함수형 프로그래밍 강의도 들어야 하는데 ,,, 후 ಠ﹏ಠ

N-Queen문제는 학교 다닐때 과제로 풀었던 문제라서 익숙했다 !
그렇다고 풀 수 있었다는 말은 아닙니다ㅋ
그때는 이차원 배열로 구현을 했던 것 같은데 이렇게 일차원 배열로 구현을 할 생각을 하다니 세상 사람들 나 빼고 다 너무 똑똑하고 ... 예 ...그렇슴다 ...

참고 사이트 🙄

• https://programmers.co.kr/