코딩테스트, 기초, 백트래킹 backtracking 소개
Вставка
- Опубліковано 21 січ 2021
- 유료강의: / @user-pw9fm4gc7e
챕터리스트: • 코딩테스트 BackTracking
code: colab.research.google.com/git...
C++ : github.com/NoCodeProgram/Codi...
버튼마다 알파벳이 할당이 되어있다.
1[],2[abc],3[def]
4[ghi],5[jkl],6[mno]
7[pqrs],8[tuv],9[wxyz]
Input이 25인경우, 모든 문자조합을 return하여라.
답 : [aj,ak,al,bj,bk,bl,cj,ck,cl]
좋은 강의 감사합니다 👍
캬...드디어 백트레킹만 하면 코테 영상들 완강이네욧 ㅎㅎ
와,,, 진짜 좋은 강의 감사합니다
좋은 강의 감사합니다
이렇게 저같은 후배들을위해서 지식공유해주셔서 정말 감사합니다 꾸벅x10000000
명강의네요
이해가 쏙 됐어요. 좋은 강의 감사합니다
하나 궁금한게 있습니다. 백트래킹이라 하지만, 결국 모든 가능한방법을 찾는것이고 이를 재귀함수로 처리한다고 이해가 되는데요(재귀함수로 처리하면서 가능한 모든것을 찾은 후 없으면 다시 돌아가니 백트래킹). 모든 방법을 찾는것이면, 그냥 반복문으로 처리하는것과 어떤차이인지 궁금합니다.
Pruning이라는 가지치기를 통해서 끝까지 가지 않고, 조건에 맞지 않으면 포기하고 처음으로 백 하니 시간복잡도 차이를 갖는걸까요?
worst case로 넘어간다면 모든 경우의 수를 체크하게 됩니다. 하지만 더이상 가능성이 없는 decision tree의 내부까지는 search를 할 필요가 없기 때문에 optimization이 가능해집니다. 챕터 문제를 몇개정도 더 풀어보면 반복문과의 차이가 어떤것인지 감을 잡으실 수 있을겁니다.
이건 잘 이해가안되네요. 나중에 다시 와서 해야겠네요. 저장!
좋은 풀이법 공유해주셔서 감사합니다. 얼마전 가입했었다가 자금난 때문에 잠시 가입을 취소했습니다.. 좋은 풀이법 무료 공개해주시는데 죄송하네요.. 조만간 꼭 다시 가입할게요!
구독만으로도 감사합니다. 코딩테스트 영상들은 추후에 일부영상 유료화 전환예정입니다. 그 전에 많이 배워가시기 바랍니다.
space complexity는 문제에서 모든 경우의 수를 다 저장하라고 했으니 letter는 O(N)이지만 output때문에 O(4^N)아닌가요?
네 맞습니다. 문제를 푸는 과정은 O(n) 이고, output저장까지 포함하면 말씀하신데로 O(4^n)이 될 것입니다.
선생님! 질문이 있습니다.
7:29 부분에서 back tracking이 끝난 후 추가된 c를 지워줘야 한다고 말씀해주신 부분입니다.
BT 함수 종료조건에 따르면 문자열의 길이가 digits의 길이와 동일해지는 순간 retrun하게 되어있습니다.
즉, digits보다 길이가 긴 문자열은 아예 생성이 되지 않을 것 같은데 실제로는 문자열이 계속 길어지더라구요... 이유가 뭘까요?
제가 생각하는 operation flow는...
for loop에서 BT가 재귀 호출 될 때,
인덱스 증가, 문자열 1개 추가 -> 문자열의 길이가 종료조건에 도달했는지 판정 -> 도달했으면 return(종료) 입니다
생각을 조금 더 해보고 다시 질문드립니다! (너무 얕게 생각했어요!)
우선 위 첫 질문에 대해 제가 제대로 교정했는지에 대한 확인을 받고싶습니다.
(Correction)
1-1. recursive function은 일반적인 함수와 다르게 return했다고 완전히 종료되는것이 아니라 '함수 call stack'가장 위에 쌓인 결과를 pop하고 이전 상태에 놓인다
1-2. 1-1의 결과로 함수 call stack은 pop이 되었지만, 문자열 조합 crntStr은 여전히 남아 있다
(결론) 따라서 recursive function이 종료조건을 만나 return 되면
-> 1. index 가 1 줄어든다 (call stack, top 빠져 나갔으므로 바로 그 아래 index값으로 줄어듬)
-> 2. 줄어든 index에 대응하는 함수 call stack에 맞춰서 해당 레벨에 맞게 문자열 길이를 맞춰준다.
(제 생각)만약 index가 1 증가 할 때 문자열이 3개가 붙는 문제였다면 문자열 갯수를 3개 줄여줘야한다 (crntStr.pop() 세번)
이게 맞을까요!?
@@deadliest9779 1-1. recursive function은 일반적인 함수와 다르게 return했다고 완전히 종료되는것이 아니라 '함수 call stack'가장 위에 쌓인 결과를 pop하고 이전 상태에 놓인다 -> 맞습니다.
1-2. 1-1의 결과로 함수 call stack은 pop이 되었지만, 문자열 조합 crntStr은 여전히 남아 있다 ->맞습니다
결론) 따라서 recursive function이 종료조건을 만나 return 되면
-> 1. index 가 1 줄어든다 (call stack, top 빠져 나갔으므로 바로 그 아래 index값으로 줄어듬) - 맞습니다만, 원리가 다릅니다. C++기준 index는 copy가 되었기때문에 줄어드는것이 아니라 기존의 1이 작은 index값을 읽는것 뿐입니다.
-> 2. 줄어든 index에 대응하는 함수 call stack에 맞춰서 해당 레벨에 맞게 문자열 길이를 맞춰준다. -> 역시나 줄어든것이 아니라 원래 1이 적은 index를 가지고 문자열 길이를 맞춥니다.
(제 생각)만약 index가 1 증가 할 때 문자열이 3개가 붙는 문제였다면 문자열 갯수를 3개 줄여줘야한다 (crntStr.pop() 세번), 네 맞습니다.
@@user-pw9fm4gc7e 이해가 무척 어려웠는데 조금씩 나아가고 있습니다
자꾸 보다보니 머릿속에 구조가 잡히는데 옳은 개념인지 다시 질문남깁니다.
1. (Vertical stack) Recursive call이 발생 할 때마다 수직 방향으로 call stack이 쌓인다
2. (Horizontal Decision space) 해당 call stack때 마다 새로운 Decision Space가 수평방향으로 펼쳐진다. Decision space를 올바르게 업데이트 하기 위해 'Process'가 필요 할 수 있다
3. (Exit Condition) Recursive call때 마다 내부적으로 Decision Space를 활용해 만든 자료가 Exit Condition에 도달한다
4 . (After Exit) recursive call 결과가 exit(=return)되면 call stack이 하나 줄어듦에 따라 여기에 맞춰서 이전 상태의 'Process'를 진행해준다
ps) iterative가 아닌 recursive 방법이 정말 우아하고 멋지다고 생각해서 열심히 공부하고 있습니다. 좋은 강의 정말 감사합니다
@@deadliest9779
1. (Vertical stack) Recursive call이 발생 할 때마다 수직 방향으로 call stack이 쌓인다 - 맞습니다.
2. (Horizontal Decision space) 해당 call stack때 마다 새로운 Decision Space가 수평방향으로 펼쳐진다. Decision space를 올바르게 업데이트 하기 위해 'Process'가 필요 할 수 있다 - 맞습니다.
3. (Exit Condition) Recursive call때 마다 내부적으로 Decision Space를 활용해 만든 자료가 Exit Condition에 도달한다 - 맞습니다.
4 . (After Exit) recursive call 결과가 exit(=return)되면 call stack이 하나 줄어듦에 따라 여기에 맞춰서 이전 상태의 'Process'를 진행해준다 - 맞습니다.
ps, recursion은 stack overflow 가 날 수 있기때문에, 인터뷰에서나 실전에서는 iterative way가 더 선호됩니다.
@@deadliest9779 제가 인터뷰어로 문제를 출제하는경우 인터뷰이가 recursion을 사용한다면 recursion방법의 단점과 iterative한 방법을 사용해보라고 요구합니다.
안녕하세요. C++ 메모리 최적화 아래처럼 하면 되나요? 지적사항이 있다면 고쳐보겠습니다
class Solution {
public:
map m;
void setup() {
m.emplace('2', std::vector{'a', 'b', 'c'});
m.emplace('3', std::vector{'d', 'e', 'f'});
m.emplace('4', std::vector{'g', 'h', 'i'});
m.emplace('5', std::vector{'j', 'k', 'l'});
m.emplace('6', std::vector{'m', 'n', 'o'});
m.emplace('7', std::vector{'p', 'q', 'r', 's'});
m.emplace('8', std::vector{'t', 'u', 'v'});
m.emplace('9', std::vector{'w', 'x', 'y', 'z'});
}
void backtracking(vector &answer, const string &digits, string &substring, int n) {
if (digits.length() == substring.length() && substring.length() > 0) {
answer.emplace_back(substring);
return;
}
for (char &x : m[digits[n]]) {
substring.push_back(x);
backtracking(answer, digits, substring, n + 1);
substring.pop_back();
}
}
vector letterCombinations(string digits) {
setup();
vector answer;
string substring = "";
backtracking(answer, digits, substring, 0);
return answer;
}
};
setup 부분의 std::vec을 std::array로 하시는게 조금 더 좋긴하지만, 맞는것 같습니다. 정확한 코드리뷰는 물리적인 시간이 필요한 관계로 제가 여유가 있을때 확인 가능합니다. 알고리즘의 동작 체크는 leetcode 17번에서 확인하실수 있습니다.
@@user-pw9fm4gc7e 감사합니다. 풀었는데 맞긴 했는데, 선생님이 지적해주신 메모리 부분이 맞는지 궁금했습니다. 감사합니다
알듯말듯 지워준다는 말을 이해가 안되네요.... js로 푸는데 다른 강의에서도 pop()을 하고 방문했던걸 다시 false로 바꿔주는데 여기서 뭔가 힌트를 얻고 갑니다.
const input = require("fs").readFileSync("example.txt").toString().trim();
const n = Number(input);
let arr = [];
for (let i = 1; i {
if (depth == n) {
let result = [];
for (let i of selected) {
result.push(arr[i]);
}
for (let x of result) answer += x + " ";
answer += "
";
return;
}
for (let i = 0; i < arr.length; i++) {
if (visited[i]) continue;
selected.push(i);
visited[i] = true;
dfs(arr, depth + 1);
selected.pop();
visited[i] = false;
}
};
dfs(arr, 0);
console.log(answer);
이코드에서
dfs(arr, depth + 1);
selected.pop();
visited[i] = false;
마지막 이 부분에서 dfs(arr,depth+1) 이 함수는 처음 돌때 select[0], visited = [true, false, false]를 가져가는 건가요? 어차피 selected.pop()를 못만나니까?