백트래킹 질문있습니다.
안녕하세요. 강사님.
수강생 조돌이입니다. :)
강사님께서는 백트래킹 정의를 "완전탐색(Brute Force)과 가지치기(Pruning)를 결합한 방식으로, 모든 가능한 해를 찾는 과정에서 불필요한 탐색을 줄여준다." 라고 정의하시는데요.
원상복구 방식은 백트래킹 방식과 연관되지 않나요?
예전에 백트래킹에 대해서 공부한 기억이 있는데, 강사님께서 말씀하시는 원상복구를 백트래킹이라고 이해하고 있었습니다.
제가 잘못 이해하고 있는건지 알고 싶습니다.. _ _)
항상 좋은 강의 감사드립니다!
답변 1
1
안녕하세요 ㅎㅎ
예전에 백트래킹에 대해서 공부한 기억이 있는데, 강사님께서 말씀하시는 원상복구를 백트래킹이라고 이해하고 있었습니다.
-> 사실 이게 정의가 2가지로 쓰이고 있습니다.
수강생님이 말씀하신 원상복구를 백트래킹이라고 하는 것도 있고 가지치기를 포함한게 백트래킹이라고 한 것도 있습니다.
이 부분은 영어 -> 한국말로 바꾸는 부분에서 나타난 차이라고 보시면 됩니다.
백트래킹을 영어로 설명하는 강의를 보면
recursive backtraking, recursive backtracking with optimization
이렇게 두가지로 나눠지는데요.
전자의 경우 우리나라 워딩으로 완전탐색이라는 말로 쓰이고 있기 때문에 그걸 구분하기 위해서 저는 백트래킹 = 가지치기 + 완탐으로 구분지어서 설명드리고 있습니다.
좀 더 정확히는 recursive backtracking with optimization은 DP로 최적화, 가지치기로 최적화, 비트마스킹으로 최적화 이렇게 세분화해서 설명을 하는 영어 강의가 있는데 이를 한국말로 구분지어서 설명하기 위해 DP로 최적 -> DP재귀적 탐색, 비트마스킹 -> 비트마스킹 + DP로 설명을 드리고 있습니다.
또 질문 있으시면 언제든지 질문 부탁드립니다.
좋은 수강평과 별점 5점은 제게 큰 힘이 됩니다. :)
감사합니다.
강사 큰돌 올림.
채점서버 연결 관련 질문입니다
0
8
0
삼성 s직군
0
7
0
삼성 코테 없어짐
0
49
1
코딩살구클럽 가입부탁드립니다
0
33
2
코딩살구클럽 가입 요청 확인부탁드립니다
0
32
2
5-S 테스트 케이스 질문
0
37
2
코살 문제풀이 환경
0
49
2
2 - T 오큰수 문제가 있는 것 같습니다.
0
43
1
추천 추가문제들
0
44
2
프로그래머스 코테 환경 관련해서 질문드립니다.
0
49
2
해당 문제에 대한 채점이 코딩살구클럽에서 올바르게 처리되지 않습니다.
0
44
2
균형 이진 트리 설명 시 높이 숫자
0
33
2
4-H 질문드립니다.
0
37
2
1-K 질문드립니다.
0
43
2
대기업 인적성 시험 질문
0
43
2
4-C 질문드립니다
0
43
2
[수학숙제 / BOJ 2870] 채점 서버 오작동
0
40
1
코테 준비 질문
0
53
1
살구클럽가입 요청드려요
0
41
2
1-I 문제 질문
0
46
2
코딩살구클럽 가입
0
59
2
AI 코딩 도구 사용 시 학습 방법 조언
0
56
2
코딩살구클럽 오류
0
65
2
코살클 [3-F 괄호 추가하기] 프라이빗 9번 제보
0
51
1