나는 근본없이 ps 문제를 풀어봐서 그런지, 백트래킹은 하나도 안 풀고 dp만 접해봤었음.
근데 백트래킹이 dp의 하위 버젼이라는 느낌이 들다가 이런 글을 보게 됐음.
결국 백트래킹이라는 게 이전 상태로 돌아갈 필요가 있을 때, 돌아가면서 계속해서 완전탐색을 하는 방법이라고 생각이 들었음.
그래서 dfs를 써서 그 위의 부모 노드(?)로 돌아가는 방법이 꽤나 유리하겟구나 싶었음. 실제로 구현은 재귀함수로 구현하는 경우도 많이 봣는데,
재귀도 결국엔 콜 스택을 쌓아놓고 return 하면서 그 콜이 불려진 콜로 다시 돌아가는 형태니까 재귀라는 것도 그냥 call stack에서 하나씩 꺼내는 형태의 dfs구나 하는 생각이 들었음.
혹시 틀렷거나 피드백 줄 거 있으면 댓글좀
내가 백트래킹 처음 배울 때도 얘만큼 이해했다면 얼마나 좋았을까...
나도 뭐 여기서 검색해서 주워온 거라
개고수 캬
call stack이면 파이썬인가요? 잘은 모르겠지만 파이썬은 재귀함수 tail recursion 최적화가 없어서 깊이가 깊어지면 시간복잡도가 엄청 크게 증가하는 문제가 있어 재귀함수를 보통 안씁니다 일단 제가 이해하기에는 dp와 백트래킹은 아얘 다른 방향의 개념인데, 우선 백트래킹에 대해 쉽게 설명하면 'N과 M'이라는 문제가 가장 비유가 적절한데, N개중 M개로 만들 수 있는 순서쌍 다 출력하세요. 하면 풀 수 있는 방법이 두가지가 있어요 하나가, if(m == 1) 1중포문 if(m == 2) 2중포문 .... if(m == 100) 100중포문 이렇게 해서 m마다 포문을 돌리는 방법이 있고 두번째 방법이 backtracking입니다. m개를 선택한다, 처럼 가변적인 개수를 선택해야 할 때
for문으로 코드를 못짜기 때문에.. 짤수는 있는데 위에처럼 if(m==100)까지 몇백줄짜리 코드를 짜야할수 있어요 그래서 이럴때 완전탐색을 진행하기 위해 백트래킹이라는 방식을 이용해서 나온게 백트래킹이고 dp는 애초에 개념자체가 시간을 빠르게 하기 위해서, 이전 문제의 답을 바로 끌여다 쓴다는 시간 최적화 테크닉에 가깝다고 생각해요
백트래킹은 가변적인 개수를 세기 위해 사용하는 게 아닌걸요
그러게요 다를때에도 쓰기는하는데 어찌됐든 백트래킹은 구현테크닉에 가깝다고 생각해요 DP는 시간복잡도를 줄이는 내용이라면
그렇군요 초보자의 시선으로 봤을 때 재귀를 하면 함수를 스택에 차곡차곡 쌓은 다음 하나씩 pop하고 다음 함수를 불러온다고 생각했습니다. 아직 백트래킹 문제도 많이 못 풀어봐서ㅎㅎㅎㅎ 갤 눈팅 좀 해보니 n과 m 추천이 많던데 얼른 봐야겠네요
Neetcode라는 유튜버 설명을 보다보면 backtracking으로 푸는 문제들 대부분 초기 접근을 state space tree를 그리면서 설명하는데 이 때 tree 아래로 dfs로 순회할 때 반복되는 연산이 나오면 caching을 한다는 식으로 이야기를 진행하다가 dp로 푸는 설명등을 본 듯 해서 저렇게 얘기한 것 같습니다ㅅ