네, 맞습니다. Backtracking 알고리즘은 일종의 DFS 방법입니다. DFS는 그래프나 트리의 모든 노드를 방문하는 탐색 알고리즘이며, Backtracking은 DFS의 변형된 형태로, 해결해야 하는 문제가 조건을 만족하는 모든 경우의 수를 찾는 것을 목표로 합니다.
설명을 정말 잘하시네요! 구독했습니다. 질문 하나만 해도 될까요? 미국에서 취업준비중인데 코테를 좀 빠르게 준비하고 싶은데 어느부분을 집중적으로 효율적이게 하는 방법이 있을까요? 이력서 내고 분명 테크니컬로 코테를 볼텐데 알고리즘 자료구조 공부해도 다음날 까먹고... 릿코드에서 풀려고해도 적용할 엄두도 안나고 패닉이네요.. 그냥 열심히 외우고 풀고 하는 방법뿐일까요
혹시 한국에서 대학수학능력 시험을 보셨는지 모르겠지만, 수능 수학문제와 아주 비슷합니다. 기본적인 알고리즘과 기초문제들은 암기수준으로 숙달을 하고, 그 이후에 약간 응용된 문제들을 풀면서 각 챕터들이 어떻게 응용될 수 있는지 보고, 최종적으로 지원하고자 하는 회사의 최신기출들을 보면 됩니다. 아예 아무것도 모르겠고 패닉수준이라면 6개월 정도 빡쎄게 봐야합니다.
절대 부족합니다. 일단은 영상을 통해서 감을 잡고 어떠한 풀이법을 적용할수있다 라는것을 체득해야합니다. 그 이후 회사별 최신 기출을 직접 풀어보는것이 좋습니다. 그리고 온사이트에서는 문제접근방법, 질문의방법, 커뮤니케이션능력,설명방법등을 전부 평가대상입니다. 결론은 '이 사람과 같이 프로젝트,일을 할 수 있는가' 를 보는것이기 때문입니다. 준비가 부족하면 노력으로 극복하면 되는것이고, 한 회사의 합격률을 0.3이라고 보면 20곳에 면접을 봐서 전부 떨어질 확률은 0.0008 밖에 안됩니다. 그러니까 한군데를 꼭 붙는다라는 생각보다는 나의 평균합격률을 0.1에서 0.5로 올리겠다 라는 마인드로 준비하는것이 최선입니다.
DFS 순서가 틀린 것 같습니다.. 설명하신 것과 같이 사전순으로 빠른 노드부터 탐색한다라고 치면 ABECDFG순서가 맞는 듯합니다. 기본적으로는 DFS, BFS 모두 중복해서 보지 않기 위한 seen set이 아닌, 중복해서 방문하지 않기 위해 visit set을 사용하는 것으로 알고있습니다. 다만 그렇게 구현하게 되면 각각 스택과 큐에 중복된 원소가 들어가 비효율적인 연산이 늘게 됩니다. 이를 해결하기 위해 BFS에서는 seen set을 사용하고, DFS에서는 재귀로 구현하는 것으로 알고있습니다. A-B-E를 방문한 상태에서는 C를 방문하지 않았기 때문에 C를 방문하는 것이 맞는데, A와 인접하기 때문에 C를 방문하지 않는 부분에서 오류가 있는 것 같습니다. 마지막 Keys and Rooms 문제에서는 방문순서가 아닌 방문 여부만 따지면 되기 때문에 문제가 되지 않는 것으로 보입니다. 제가 잘못 알고있는 부분 있으면 피드백 부탁드립니다 감사합니다.
안녕하세요. DFS, BFS 에서 seen set을 사용하던, visited set을 사용하던 상관없습니다. 또한 재귀를 사용하던 stack, queue를 사용하던 아무 상관이 없습니다. 오직 Depth를 먼저가냐, breadth가 먼저냐의 차이만 있습니다. 영상에서는 node 선택시 alphabet순서를 따질 필요가 없었기때문에 seen set을 사용해도 됩니다. 말씀하신대로 node 선택시 마다 순서가 중요하다면 seen set은 사용할 수 없습니다. 또한 여기서 순서가 중요하다면 seen상태에서 매번 sorting을 해줘야하기때문에 구현은 더 어려워집니다. graph관련영상은 ua-cam.com/play/PLDV-cCQnUlIZH0wklfVG1IN9ks4g92oN7.html 서 더 찾아볼수 있습니다. 감사합니다.
@@user-pw9fm4gc7e ua-cam.com/video/pcKY4hjDrxk/v-deo.html 우선 DFS를 스택을 사용해 구현할 때, 위의 링크와 같이 사용하여야 올바른 순서로 방문할 수 있는 것 같습니다. 위에 언급한대로 코드없는 프로그래밍님의 영상에 나와있는 방식으로 사용하게 되면 A-B-E 다음 C를 방문해야 하는데 (또는 A-B-E-G 다음), A와 인접하기 때문에 방문하지 않는 부분에서 오류가 있는 것 같습니다. DFS에서는 발견과 동시에 (방문하지 않았다면) 방문하기 때문에 seen set을 사용하든 visited set을 사용하든 상관이 없는 건 맞는 것 같네요..! 다만 seen set에 원소를 추가하는 시점이 A를 방문한 시점에서 B, C, D를 바로 추가하는 것이 아니라, B를 방문하고 B 방향으로의 DFS를 마친 이후에 (정확하게는, 전체 node set을 V라고 할 때 V\{A}로부터 induced되는 subgraph에서, B와 연결된 node를 모두 방문한 이후에) C, D를 추가하는 것이 맞습니다. BFS에서는 노드를 발견과 동시에 방문하지 않기 때문에, visited set을 사용하게 되면 큐에 중복된 원소가 들어가기 때문에 시간복잡도가 O(|V|+|E|)보다 커지게 됩니다. |V|=4이고, simple cycle인 경우(영상에서의 A, B, C, E로 induced되는 subgraph를 생각하겠습니다.)를 생각해보면, A를 방문할 때 B와 C를 enqueue하게 되고, B와 C를 방문할 때 모두 E를 enqueue하게 되는 예시가 있습니다. 이러한 경우를 피하기 위해 seen set을 사용합니다. 인접한 노드 중 사전순으로 빠른 노드부터 탐색하는 걸 언급한 이유는 A와 인접한 노드를 B-C-D순으로 , E와 인접한 노드를 B-C-G 순으로 언급하는 부분을 보고 의도한 부분인 줄 알았어요...! node 선택시마다 순서가 중요할 때 seen set을 사용할 수 없는 부분은 추가로 설명 부탁드릴게요... 기본적으로는 DFS, BFS 모두 순서가 중요하지 않지만 순서가 있다고 해서 seen set의 사용 방법이 달라지진 않는 것 같아서요... 순서가 중요한 경우, 구현단계에서 인접 리스트를 사용한다면 방문할 순서로 리스트를 만들어주면 되고, 인접행렬을 사용한다면, (node마다 방문 순서가 동일할 경우) 방문할 순서로 인덱스를 부여하면 되지 않나 싶습니다.. 그러면 representation 단계에서만 정렬해주면 되는 것 같은데 이 부분은 저랑 다른 이야기를 하는 것 같기도 하고,, 영상에서 다루는 부분은 아닌 것 같아서 넘어가셔도 될 듯합니다...! 감사합니다.
정말 쉽게 설명해주시네요. ㅎㅎ 감사합니다.
항상 잘 보고있습니다 ㅎㅎ
이해가 잘되었습니다! 감사합니다 ㅎㅎ
당신은 천재입니까,,?
고맙읍니다,,
좋은 영상 감사합니다!
감사합니다💕
정말 설명 해 주시는 거 볼 때마다 감탄합니다. 정말 감사합니다.
오랜만에 와서 다시 공부하고있습니다...
궁금증이 남겨 질문드립니다
Backtraking 챕터에서
while (call stack):
을 통해 함수 콜 스택을 쌓고 뽑는 과정을 반복하는데
이게 정확히 dfs 랑 같은 방식이라고 봐도 될까요?
네, 맞습니다. Backtracking 알고리즘은 일종의 DFS 방법입니다. DFS는 그래프나 트리의 모든 노드를 방문하는 탐색 알고리즘이며, Backtracking은 DFS의 변형된 형태로, 해결해야 하는 문제가 조건을 만족하는 모든 경우의 수를 찾는 것을 목표로 합니다.
@@user-pw9fm4gc7e 여기서 공부할 때 마다 팔 다리가 하나씩 더 생기고 더 유능해지는 느낌입니다
답변 달아주셔서 감사합니다!
설명을 정말 잘하시네요! 구독했습니다.
질문 하나만 해도 될까요?
미국에서 취업준비중인데 코테를 좀 빠르게 준비하고 싶은데 어느부분을 집중적으로 효율적이게 하는 방법이 있을까요?
이력서 내고 분명 테크니컬로 코테를 볼텐데 알고리즘 자료구조 공부해도 다음날 까먹고... 릿코드에서 풀려고해도 적용할 엄두도 안나고 패닉이네요..
그냥 열심히 외우고 풀고 하는 방법뿐일까요
혹시 한국에서 대학수학능력 시험을 보셨는지 모르겠지만, 수능 수학문제와 아주 비슷합니다. 기본적인 알고리즘과 기초문제들은 암기수준으로 숙달을 하고, 그 이후에 약간 응용된 문제들을 풀면서 각 챕터들이 어떻게 응용될 수 있는지 보고, 최종적으로 지원하고자 하는 회사의 최신기출들을 보면 됩니다. 아예 아무것도 모르겠고 패닉수준이라면 6개월 정도 빡쎄게 봐야합니다.
@@user-pw9fm4gc7e 암기랑 반복이 답이군요.
감사합니다. 선생님
코드없는프로그래밍 코딩테스트 영상들은 빠르고 쉽게 챕터별 기초문제와 기본응용문제를 학습할수있습니다.
@@user-pw9fm4gc7e 선생님 지금 유튜브 채널에 영상만 올리신게 전부신거죠?
미국 코테 기준으로 저거만 봐도 충분할지 모르겠네요
절대 부족합니다. 일단은 영상을 통해서 감을 잡고 어떠한 풀이법을 적용할수있다 라는것을 체득해야합니다. 그 이후 회사별 최신 기출을 직접 풀어보는것이 좋습니다. 그리고 온사이트에서는 문제접근방법, 질문의방법, 커뮤니케이션능력,설명방법등을 전부 평가대상입니다. 결론은 '이 사람과 같이 프로젝트,일을 할 수 있는가' 를 보는것이기 때문입니다. 준비가 부족하면 노력으로 극복하면 되는것이고, 한 회사의 합격률을 0.3이라고 보면 20곳에 면접을 봐서 전부 떨어질 확률은 0.0008 밖에 안됩니다. 그러니까 한군데를 꼭 붙는다라는 생각보다는 나의 평균합격률을 0.1에서 0.5로 올리겠다 라는 마인드로 준비하는것이 최선입니다.
감사합니다 와. DFS 이제 이해했습니다. 이걸 왜 구현못하고 헤맸을까요...
혹시 사용하시는 그림 툴이 어떤건가요??
DFS 순서가 틀린 것 같습니다.. 설명하신 것과 같이 사전순으로 빠른 노드부터 탐색한다라고 치면 ABECDFG순서가 맞는 듯합니다.
기본적으로는 DFS, BFS 모두 중복해서 보지 않기 위한 seen set이 아닌, 중복해서 방문하지 않기 위해 visit set을 사용하는 것으로 알고있습니다.
다만 그렇게 구현하게 되면 각각 스택과 큐에 중복된 원소가 들어가 비효율적인 연산이 늘게 됩니다. 이를 해결하기 위해 BFS에서는 seen set을 사용하고, DFS에서는 재귀로 구현하는 것으로 알고있습니다.
A-B-E를 방문한 상태에서는 C를 방문하지 않았기 때문에 C를 방문하는 것이 맞는데, A와 인접하기 때문에 C를 방문하지 않는 부분에서 오류가 있는 것 같습니다. 마지막 Keys and Rooms 문제에서는 방문순서가 아닌 방문 여부만 따지면 되기 때문에 문제가 되지 않는 것으로 보입니다.
제가 잘못 알고있는 부분 있으면 피드백 부탁드립니다 감사합니다.
안녕하세요. DFS, BFS 에서 seen set을 사용하던, visited set을 사용하던 상관없습니다. 또한 재귀를 사용하던 stack, queue를 사용하던 아무 상관이 없습니다. 오직 Depth를 먼저가냐, breadth가 먼저냐의 차이만 있습니다.
영상에서는 node 선택시 alphabet순서를 따질 필요가 없었기때문에 seen set을 사용해도 됩니다. 말씀하신대로 node 선택시 마다 순서가 중요하다면 seen set은 사용할 수 없습니다. 또한 여기서 순서가 중요하다면 seen상태에서 매번 sorting을 해줘야하기때문에 구현은 더 어려워집니다.
graph관련영상은 ua-cam.com/play/PLDV-cCQnUlIZH0wklfVG1IN9ks4g92oN7.html 서 더 찾아볼수 있습니다. 감사합니다.
@@user-pw9fm4gc7e
ua-cam.com/video/pcKY4hjDrxk/v-deo.html
우선 DFS를 스택을 사용해 구현할 때, 위의 링크와 같이 사용하여야 올바른 순서로 방문할 수 있는 것 같습니다. 위에 언급한대로 코드없는 프로그래밍님의 영상에 나와있는 방식으로 사용하게 되면 A-B-E 다음 C를 방문해야 하는데 (또는 A-B-E-G 다음), A와 인접하기 때문에 방문하지 않는 부분에서 오류가 있는 것 같습니다.
DFS에서는 발견과 동시에 (방문하지 않았다면) 방문하기 때문에 seen set을 사용하든 visited set을 사용하든 상관이 없는 건 맞는 것 같네요..! 다만 seen set에 원소를 추가하는 시점이 A를 방문한 시점에서 B, C, D를 바로 추가하는 것이 아니라, B를 방문하고 B 방향으로의 DFS를 마친 이후에 (정확하게는, 전체 node set을 V라고 할 때 V\{A}로부터 induced되는 subgraph에서, B와 연결된 node를 모두 방문한 이후에) C, D를 추가하는 것이 맞습니다.
BFS에서는 노드를 발견과 동시에 방문하지 않기 때문에, visited set을 사용하게 되면 큐에 중복된 원소가 들어가기 때문에 시간복잡도가 O(|V|+|E|)보다 커지게 됩니다. |V|=4이고, simple cycle인 경우(영상에서의 A, B, C, E로 induced되는 subgraph를 생각하겠습니다.)를 생각해보면, A를 방문할 때 B와 C를 enqueue하게 되고, B와 C를 방문할 때 모두 E를 enqueue하게 되는 예시가 있습니다. 이러한 경우를 피하기 위해 seen set을 사용합니다.
인접한 노드 중 사전순으로 빠른 노드부터 탐색하는 걸 언급한 이유는 A와 인접한 노드를 B-C-D순으로 , E와 인접한 노드를 B-C-G 순으로 언급하는 부분을 보고 의도한 부분인 줄 알았어요...! node 선택시마다 순서가 중요할 때 seen set을 사용할 수 없는 부분은 추가로 설명 부탁드릴게요... 기본적으로는 DFS, BFS 모두 순서가 중요하지 않지만 순서가 있다고 해서 seen set의 사용 방법이 달라지진 않는 것 같아서요... 순서가 중요한 경우, 구현단계에서 인접 리스트를 사용한다면 방문할 순서로 리스트를 만들어주면 되고, 인접행렬을 사용한다면, (node마다 방문 순서가 동일할 경우) 방문할 순서로 인덱스를 부여하면 되지 않나 싶습니다.. 그러면 representation 단계에서만 정렬해주면 되는 것 같은데 이 부분은 저랑 다른 이야기를 하는 것 같기도 하고,, 영상에서 다루는 부분은 아닌 것 같아서 넘어가셔도 될 듯합니다...!
감사합니다.