[개념정리] DFS+BFS (혹시,,, 문제풀이 전에 이코테 책을 보시나요!?) #25
deslog
started this conversation in
Show and tell
Replies: 1 comment
-
|
블로그에서부터 시작해서 이번 DFS+BFS 정리하신 글까지 모두 정독했습니다😀 생각을 정리해서 글로 작성하는 것 많이 배워갑니다! |
Beta Was this translation helpful? Give feedback.
0 replies
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Uh oh!
There was an error while loading. Please reload this page.
-
⚫️ 재귀함수
DFS와 BFS를 이해하기 위해서 재귀를 필수적으로 이해해야한다. 나는 아직 재귀함수를 어떻게 돌려서 결과값을 찾으면 되겟다! 싶은 감이 아직 없다….. 어떻게 다들 이걸 그렇게 빨리빨리 머리회전을 하시는것인지..
▪️ 대표 알고리즘 구현해보기
라이브 코딩에서 ‘팩토리얼’ 혹은 ‘피보나치 수열’ 알아요? 그거 구현한번만 해볼래요? 이런식으로 진행되는 경우도 있다. (주변에서 그랬었음!) 그래서 대표적으로 어떻게 구현할 것인지 알아두는 것도 중요할 것 같다.
🔖 팩토리얼 함수 구현하기
재귀로 구현하기
재귀 아이디어는 아래 그림과 같다. 작은 문제들을 먼저 해결해주면서 차례대로 올라오면 된다.
🔖 피보나치 수열 구현하기
수열 1, 1, 2, 3, 5,,, 를 구현했고 num에 알고싶은 위치 index를 넣으면 그 수를 알려준다
▪️ 재귀와 반복문의 시간복잡도 (팩토리얼 함수 기준으로 설명)
재귀로 구현이 된다는 의미는, 어쨌든 반복문으로도 구현이 가능하다는 소리다. 즉, 두개의 시간복잡도는 같다. 팩토리얼 함수를 기준으로 시간복잡도를 따져보면, 재귀함수도 결국 n-1번의 팩토리얼 함수를 불러내고, n-1번의 연산을 수행한다. 즉, O(n-1)이라는 소린데, 빅오표기법에서는 상수값을 날리므로
O(n)이다.▪️ 재귀와 반복문의 공간복잡도 (팩토리얼 함수 기준으로 설명)
for문을 사용했을 경우, for문 내부에서의
i라는 변수와result라는 변수 , 총 두 개가 생성된다. 그러므로O(1)의 공간복잡도를 가진다.재귀를 사용했을 경우에는, 함수가 불려질때마다 stack에 함수가 쌓이게된다. 만약 num이 10으로 입력됐다면, 총 10번의 factorial 함수가 스택에 쌓이게 되고, 10개의 num 변수가 메모리에 올라가게 된다. 입력하는 n에 따라 n-1개의 변수가 메모리에 올라가므로,
O(n)의 공간복잡도를 갖는다.정리하자면 공간복잡도는 비교적 시간복잡도보다는 중요하지 않지만, 굳이 따져보며자면 메모리 적인 측면에서 재귀는 그닥 효율적이라고 볼 순 없을 것 같다. 재귀는,, 보다 함수를 편하게 표기하고 조금더 효율적인 명시를 위해서 자주 사용된다고 하니,,, 마음껏 재귀를 남발할 순 없겠다.
하지만 이런 재귀의 공간복잡도 문제를 해결할 수 있는 ‘꼬리재귀함수’라는 것도 존재한다고 하니, 꼭 알아보자!
⚫️ DFS
깊이 우선 탐색, 그래프의 깊은 부분을 우선적으로 탐색하는 알고리즘
스택자료구조를 이용한다.DFS의 동작과정
예제코드
▪️ DFS를 주로 사용하는 경우
⚫️ BFS
너비우선탐색, 가까운 노드부터 탐색하는 알고리즘이다.
큐자료구조를 이용한다.BFS의 동작과정
예제코드
O(N)이고, 인덱스로 접근하는 것은O(1)이다.▪️ BFS를 주로 사용하는 경우
⚫️ 이코테 예제
1️⃣ 음료수 얼려먹기 (p.149)
💬 나의 풀이
✅ 정답코드
아니 여기서
dfs를 호출하면, 반환되는 값이 unused인데 어떻게 처리하지? 고민했다. ㅋㅋㅋㅋ 사실 근데, 얼음이 얼마나 크게!! 몇칸을 차지해서 생성되었는지는 중요하지 않다. 그냥 인접된 얼음틀들을 전부 방문처리해주면 되는것! 그래서dfs를 호출해서 방문처리만 해주고, dfs를 통해 반환되는 return 값은 무시해도 좋다.어차피
if iceFrame[x][y] == 0을 통해서 이미 얼음틀은 생겼기 때문에, 몇칸이 되는지는 중요하지 않음!2️⃣ 미로탈출 (p. 152)
💬 나의 풀이
✅ 정답코드
각 miro의 값을 +1씩해주면서 miro 값 자체를 변경해주는 과정을 기억하자. 이런 유형 좀 많은듯? 단지 번호 매기기 등등…
Beta Was this translation helpful? Give feedback.
All reactions