재귀2 [알고리즘] 재귀와 깊이 우선 탐색(DFS) 알고리즘 문제를 풀다가 재귀를 사용하는 방법이 흥미로워 정리해 놓으려 합니다. 이전 글에서 짧고 부족한 재귀를 이해하는 설명을 했습니다. 이번에는 여러 선택지가 있는 재귀에서 후퇴하는 방법입니다. 앞선 글에서 피보나치 수열을 예시로 설명을 했습니다. 그리고 이 수열의 표현식을 '점화식'이라고 하죠. N번째 항의 값은 그 이전 항(들)의 어떠한 로직으로 표현됩니다. 그런데 알고리즘에서는 이러한 일종의 점화식도 있습니다. N번째 항의 값은 N-1번째에 어떤 로직을 수행해서 이뤄지는데, 어떤 로직의 경우의 수가 2개 이상입니다. 예를 들어보겠습니다. 좋은 바코드 문제입니다. 1, 2, 3으로만 이루어진 수열 바코드를 만들어야 합니다. 이 바코드를 만드는 데에 조건이 걸려 있습니다. 바코드에서 인접한 두 부분 .. 2022. 7. 28. [알고리즘] 재귀란, 느낌으로 이해하기 알고리즘 문제를 풀다가 재귀를 활용하는 방법이 어렵고 흥미로워서, 저처럼 재귀를 처음 접하며 혼란스러운 사람들에게 조금이나마 도움이 되고자합니다. 우선 제가 어렴풋이 느꼈던 재귀란 대충 이러합니다. 재귀는 같은 로직으로 조금씩 나누어 해결하는 것. 그리고, 나는 '초기값'과 '조금씩' 집중하고 나머지는 믿고 맡기는 것. 예를 들어 설명해보겠습니다. 아주 간단한 예시로는 피보나치 수열이 있습니다. 피보나치 수열은 이렇게 표현하죠. Fn = F(n-1) + F(n-2) ( F1 , F2 = 1) N번째 항은 이전 두 항을 더한 값이다. n-1, n-2번째 항을 구하기 위해서는 또 그들의 이전 값들을 더하고 또 더하는 것을 반복해야합니다. 즉, 같은 로직이 반복되고 있습니다. 그리고 중요하것은 이것입니다. '.. 2022. 7. 27. 이전 1 다음
