[Day 41] 2022-0819 : 재귀함수

🐈오늘 공부한 것

✔️섹션 3 시작 ! 

섹션 3 대단원의 막이 올랐다(박수~~👏👏) 프로젝트를 제외하고 섹션은 4까지 있는데, 벌써 절반을 넘었다고 생각하니 기분이 묘했다. 이번 섹션의 목표는 "사용자 친화적이고 안전한 웹앱 만들기" 이다. 사용자 친화적인 UX/UI 를 구성하고, 리액트 심화와 리덕스, 웹 표준과 마지막 인증, 보안까지 많은 내용을 짧은 시간안에 배워야 한다. 지난 세션에서는 리액트 얼레벌레... 서버 얼레벌레... 이런 느낌이었는데 이번 섹션에서는 보충 내용을 많이 공부해서 두 배로 배워가고싶다...!

✔️재귀 함수 

재귀 함수란 자기 자신을 계속해서 호출하는 함수를 의미한다. 계속해서 호출할 때 종료조건이 없다면 스택 오버플로우가 발생할 수 있으니 반드시 종료 조건이 필요하고 또 반대로 재귀를 지속하는 재귀 조건도 필요하다. 재귀 함수에서는 큰 문제를 작은 문제로 쪼개어 그 작은 문제를 식으로 만들어서 푼다. 이렇게 작게 쪼개어 재귀를 반복하여 문제를 해결하는 부분을 점화식으로 생각하면 된다. 수학 공부를 열심히 안해서 점화식에 대해 이번에 처음으로 공부하게 되었는데, 예전에 다이나믹 프로그래밍 기법에서 많이 등장했던게 기억난다. 모든 재귀 함수는 반복문으로 표현할 수 있는데 (계속 반복해서 호출하니깐) 반복문이 성능은 좋아도 명령형 방식이라 실질적인 가독성은 떨어질 수 있다. 재귀 함수는 간결하게 표현될 수 있기 때문에 효율이 그리 좋지는 않아도 코드의 유지보수성을 높일 수 있다는 장점이 있다. 알고리즘 문제에서는 하나의 식으로 해결될 수 있을 때 사용하면 효율적이다. 

✔️피보나치 수열

피보나치 수열은 0번째와 1번째를 제외한 각 항이 그 항의 -1 번째 항과 -2 번째 항으로 이루어진 수열이다. 피보나치 수열의 특정 항을 구하는 문제는 재귀 함수를 사용할 수 있는 대표적인 문제 중 하나이다. 

피보나치 수열에서도 종료 조건과 재귀 조건을 표현할 수 있는데, 먼저 종료 조건은 매개변수로 넘어온 항이 0이거나 1일 때 그에 맞는 값을 리턴해줌으로써 종료할 수 있다. 재귀 조건에서는 피보나치 수열 점화식을 이용할 수 있는데...

F(n) = F(n-1) + F(n-2)

 위와 같이 표현할 수 있다. 이를 자바스크립트 코드로 표현하면...

function fibonacci(num) {
  if (num === 0) return 0;
  if (num === 1) return 1;

  return fibonacci(num - 1) + fibonacci(num - 2);
}

위와 같이 표현할 수 있다. 그동안 절차 지향적인 프로그래밍에 익숙해져 있다가 for문을 사용하는 명령형 방식에 익숙해져 있다가 뭔가 함수 호출 스택의 동작까지 생각하면서 코드를 짜려니 머리가 아파져서 그림으로 다시 정리해봤다. 

코플릿에서도 재귀 문제를 많이 풀었는데 중요한 것은 어느 시점에서 함수가 종료되고 어떤 값을 리턴하느냐인 것 같다. 처음 문제를 정의할 때 어떤 값을 입력받고 어떻게 출력해야하는지, 그리고 문제를 어떻게 '쪼갤 수' 있는지에 집중하면서 식을 만들었는데 도움이 많이 되었다! 

✔️DFS 

내일 알고리즘 스터디 발표를 위해서 어떤 내용을 준비할까 하다가... 그동안 공부했던 내용과 약간 다른 방향이긴 하지만 DFS 를 하기로 결정했다. 예전에 DFS - 순열과 조합에 대해서 잠시 공부해본 적이 있는데, 그 때 기억으로 재귀 함수를 사용해서 많이 풀었던 것 같아서 겸사겸사 준비했다. 오늘 공부하면서 새롭게 알게된 내용은, 놀랍게도 DFS 가 그래프의 탐색을 위한 알고리즘 이라는 것이다... (그것도 몰랐음...바보다;;) 배열, 리스트같은 선형 자료구조에서는 순차적으로 연결(?) 되어 있기 때문에 탐색은 쉽지만 각 요소간의 비선형적 연결을 표현할 수는 없는데, 그래프를 가지고 각 객체간의 연결 관계를 표현할 수 있다고 한다.

 

DFS를 공부하다보니 그럼 그래프는 도대체 언제 쓰이는건지 궁금증이 생겨서 간단하게 서치해봤는데, 실생활에서는 웹페이지의 연결 링크를 예시로 들 수 있고, 소셜미디어의 친구 연결 관계 등의 예시를 찾을 수 있었다. 예전 TIL 스터디 발표모임에서 그래프 자료구조에 대해서 인공지능 신경망까지 연결지어서 설명을 들었던 것 같은데 아무튼 그런 각 객체간의 연결구조를 표현할 수 있는 자료구조라고 한다. 

 

뭔가 많이 공부하진 않아서 크게 쓸 내용이 없긴 한데 그래도 복기를 위해서 몇 자 적어보자면. DFS는 깊이 우선 탐색으로 특정 노드에서 출발해(일반적인 코테 문제에서는 조건이 주어진다고 함) 각 노드에 연결된 노드들을 작은 것부터 큰 순서대로 가장 깊은 노드까지 방문하여 모든 노드의 탐색을 마칠 수 있는 알고리즘이다. 하나의 끝 지점에 해당하는 노드에 도달한 뒤에는 다시 상위 노드로 돌아가는데 이 때 노드 방문 여부를 체크하여 방문하지 않은 노드만 탐색할 수 있다. 이 방식은 스택 자료구조를 통해 구현할 수 있는데, 재귀 함수를 사용해 간결하게 구현할 수 있어서 그 쪽을 많이 쓰는 것 같다.

🐈더 공부할 것

1. express 라우팅 공부해서 정리하기 

2. DFS 개념정리 마무리하고 문제풀기

3. 섹션 2 전체 복습하기

4. 알고리즘 문제 복기하기 + 블로그에 기록 남기기

🐈오늘의 느낀 점

1.섹션 회고에서도 낮 시간을 더 압축적으로 써야지...! 라고 다짐했는데, 오늘은 음.. 65% 정도 지킨 것 같다. 정규시간에 에너지를 확 쓰면 그 뒤에 체력이 안되어서 쉽게 지치는게 문제인 것 같다. 오늘도 달리기하러 나가려고 했는데 비가 온다.... 날씨가..날씨가 안따라주는거임..!!!! 아무튼 그런거임

 

2. 오늘 오랜만에 코플릿 페어를 했는데, 데일리 코딩도 그렇고 전보다 문제 난이도가 확 어려워졌다. 시간 내에 못 풀 정도는 아니었지만... 만약 페어님이 없이 혼자 했다면 분명 끈기있게 보지 못하고 몇 문제 못풀었을 것 같다. 페어프로그래밍 최고! 내 코드도 설명할 수 있고 페어님의 코드도 볼 수 있고 모르는 부분은 같이 머리 맞대면서 고민할 수 있어서 매우 좋다...!