Day 7 - 2022/10/25
💡 새롭게 알게된 점
자료구조와 알고리즘
백트래킹
백트래킹이란 모든 경우의 수를 탐색하되, 효율을 위해 가지치기 방법을 이용해 탐색하지 않아도 되는 부분을 미리 막는 알고리즘이다. 주로 DFS, BFS에 사용된다.
이 가지치기를 얼마나 잘하느냐가 효율성을 결정한다.
자바스크립트는 재귀 효율이 나쁘기 때문에 백트래킹을 DFS로 구현할 경우 스택을 이용하는 것이 좋다.
탐색에서 순환이 발생할 수 있다면 BFS를 이용하는 것이 좋다.
그럼 백트래킹 로직을 어떻게 작성할까?
우선 모든 경우의 수를 찾을 수 있도록 구현
이후 문제에서의 특정한 조건을 만족하는 경우만 탐색하고 나머지는 제외
동적 계획법
동적 계획법이란 문제를 작은 단위의 문제로 나눠 해결한 작은 문제로 큰 문제를 해결하는 문제 풀이 방식이다.
Dynammic Programming(DP)이라고도 불리는 동적 계획법은 메모리를 많이 사용하지만 성능이 매우 빠르다.
메모이제이션
메모이제이션은 하향식 접근법으로, 동적 계획법에서 작은 문제들의 결과는 항상 같기 때문에 이 결과들을 메모리에 저장해 필요할 때 꺼내쓰는 방법이다. (Lazy evaluation)
즉, 이미 해결한 문제는 기록해두는 방법
타뷸레이션
타뷸레이션은 상향식 접근법으로, 필요한 값들을 미리 계산해두는 방법이다. (Eager evaluation)
메모이제이션 vs 타뷸레이션
메모이제이션은 하향식(top-down)으로 가장 큰 문제를 방문 후 작은 문제를 호출하여 답을 찾는 방식이고, 타뷸레이션은 상향식(bottom-up)으로 가장 작은 문제들 부터 답을 구해가며 전체 문제의 답을 찾는 방식이다.
그럼 어떤 상황에 메모이제이션, 타뷸레이션을 써야 할까?
흔히 top-down은 재귀 호출을 통해, bottom-up은 반복문을 통해 구현한다.
top-down 방식은 점화식을 이해하기 쉽다는 장점이 있고, bottom-up 방식은 함수를 재귀 호출 하지 않아 메모리 사용량과 시간을 줄일 수 있다는 장점이 있다.
따라서 효율성을 따진다면 타뷸레이션을, 아니라면 구현하기 편한 메모이제이션을 활용하자!
그렇다면 동적 계획법 문제에 어떻게 접근해야 할까?
문제 유형을 알 수 없다면 먼저
가장 작은 문제를 정의할 수 있는지
작은 문제를 통해 큰 문제를 해결할 수 있는 규칙이 있는지
를 확인하여 두 가지 모두 가능하다면 동적 계획법으로 해결할 수 있는 문제이다.
간혹 메모리를 너무 사용하여 통과하지 못하는 경우도 있는데, 이 경우 백트래킹을 사용하면 된다.
❗️ 느낀점
어제 DFS와 BFS에 대해 공부할 때 백트래킹에 대해 간단하게 찾아봤는데 오늘 강의로 자세하게 알 수 있었다.
아직 코딩 테스트 문제를 풀 때 어떤 방식으로 해결해야 하는지 정확하게 모르기 때문에 좀 더 연습이 필요하다 생각된다.
오늘도 고생했다👊