백트래킹
- 모든 경우의 수를 탐색하는 알고리즘이다.
- DFS or BFS를 사용 가능하다.
(효율을 위해 탐색하지 않아도 되는 곳을 미리 막는 것이 중요한데, 이를 가지치기 라고 한다.) - JS는 효율성때문에 스택을 활용하는게 좋을 것 같다!
- 탐색 중 순환이 나타나면 BFS를 사용하자.
DP
가장 작은 문제를 정의할 수 있다면 사용하자.
- 작은 문제를 통해 큰 문제를 해결하는 방식
- 특정 알고리즘이 아니고, 문제 해결 방식을 의미한다.
- 메모리를 많이 사용 but 빠른 성능
DP의 두가지 방법론이 있는데, 그 중 코딩테스트에 많이 사용되는 메모이제이션에 대하여 아라보자.
- 메모이제이션
- 하향식 접근법
- DP에서 작은 문제들의 결과는 항상 같다.
따라서, 이 결과들을 메모리에 저장하여 필요할 때 꺼내쓰는 것이 메모이제이션이다.
후기
오늘은 코테 문제 2개 푸는게 전부지만, 아직 많이 부족해서인지 두 문제 모두 어떻게 풀지.. 손도 못 댔다..
꾸준히 코테 연습하다보면 괜찮아지겠지..?
