코딩테스트 알고리즘 - 2. DFS
Вставка
- Опубліковано 22 сер 2021
- 비전공자 출신으로서 대기업 준비 과정을 공유합니다.
기본문제 : www.acmicpc.net/problem/2667
코드 : github.com/ChangguHan/codingt...
00:15 개념
03:15 재귀함수
05:33 문제풀이 아이디어
06:40 시간복잡도
07:45 자료구조
08:15 기본문제
#DFS #코딩테스트 #알고리즘 #비전공자 #개발자
와 문제까지 같이 설명들으니깐 진짜 이해가 잘 됐습니다. 감사합니다!
설명을 너무 잘해주십니다. 막혀있던 부분이 뻥 뚫리는 부분이고 덕분에 골드 그래프 문제까진 숭숭 풉니다 감사합니다
Backtracking 에 유용하다
이 한 문장이
단순 개념설명 및 문제풀이를 넘어선 설명이 되었네요 :)
코테 스터디 세 번 정도밖에 안해서 어려움 느끼고 있는데
쉽게설명해주셔서 감사드려용
알고리즘 강의는 장고님이 최고십니다
좋은 영상 감사합니다 ❤
감사합니다!!
장고님 덕에 아무것도 안보이던 코딩테스트 준비에 조금이라도 윤곽이 잡힌 느낌이 듭니다!!
완강 하겠습니다!!!!!
선생님덕에 눈떴습니다.. 이젠 그래프가 제일재밌어여
잘봤습니다
3:13
장고님. 자식 노드가 우선인 경우에는
1->2->3->4->6에서 다시 1로 돌아와서 5가 아니라
2로 돌아와서 5번으로 가는거 아닌가요...? 초보라자 헷갈리네요ㅠㅠ
함수 실행이 대부분 메모리에 스택 영역에서 이루어진다는 점에서 재귀 자체가 스택 방식으로 동작한다고 이해했는데 맞나요?
안녕하세요 장고님 dfs(y,x)로 하셨는데 왜 dfs(x,y)로 안하신건지 궁금합니다. 딱히 xy순서는 상관없는건가요?
+) gpt에게 물어보니
dfs 함수에서 (y, x)로 받아주는 이유는 보통 행(row)을 먼저 처리하고 열(column)을 나중에 처리하는 방식을 따르기 때문입니다. 이 방식은 대부분의 프로그래밍 언어에서 행 우선 순회(row-major order)를 따르는 관행입니다.
행(row)은 보통 수직 방향으로 이동하고, 열(column)은 수평 방향으로 이동하기 때문에 좌표를 (y, x)로 받아들이는 것이 직관적입니다. 이렇게 하면 코드가 좀 더 이해하기 쉬워집니다.
또한, 다른 프로그래머와 협업할 때 행과 열을 헷갈리지 않도록 하기 위해 일반적으로 이러한 관행을 따릅니다. 따라서 (y, x) 순서로 좌표를 받아들이는 것이 좋은 습관입니다.
라는 답변을 받았습니다! 혹시나 저와같이 궁금해하는분이 계실까 덧글남깁니다. 만약 이러한 이유가 아니라면 의견주세요 :3
윗분이 말씀하신 것 처럼 컴퓨터에서는 2차원 배열을 처리할때 가로로 진행하는 것이 효율적이기 때문에 map[y][x] 이런식으로 순서가 되는데 함수 정의할때 인자값의 순서는 상관이 없어서 일반적으로 배열하는 순서인 x, y로 작성하신 것 같네요.
안녕하세요 장고님 영상 잘보고 있습니다.
혹시 2667번 문제도 BFS로 풀어도 될 것 같아서 질문드립니다.
시간복잡도 측면에서 DFS나 BFS나 비슷한거 같은데
문제를 보았을때 아이디어를 DFS 또는 BFS를 사용해서 풀어야겠다 하는 기준이 있을까요?
진희님 안녕하세요 ^^
2667문제 BFS로 푸셔도 돼요!
제 개인적인 생각으로는 그래프 탐색은 BFS로 푸는게 쉬운것 같아요.
DFS는 재귀를 사용하기 때문에 좀 난이도가 있잖아요?
그래서 꼭 필요한 경우(백트래킹)에만 사용하는게 좋을것 같습니다.
답변이 되셨으면 좋겠네요!!
꾸준히 홧팅입니다
@@developer_jango 감사합니다 ㅎㅎ
사실 저도 한씨입니다 하핫.
한씨 홧팅!
장고님 bfs 시간복잡도는 상수포함을 했는데 dfs 시간복잡도는 왜 상수가 포함 안될까여?
키드밀리 폼 미쳣다