알고리즘 분류/재귀
-
이번 포스트에서는 재귀의 동작 과정에서 발생할 수 있는 엄청난 중복 호출과 이를 극복하기 위한 메모이제이션에 대해서 살펴보자. 피보나치! 피보나치 수열 구하기 피보나치 수 - 위키백과, 우리 모두의 백과사전 위키백과, 우리 모두의 백과사전. 피보나치 수를 이용한 사각형 채우기 수학에서 피보나치 수(영어: Fibonacci numbers)는 첫째 및 둘째 항이 1이며 그 뒤의 모든 항은 바로 앞 두 항의 합인 수열이다. ko.wikipedia.org 피보나치 수는 첫째항과 둘째 항이 1이고 그 뒤의 항은 바로 앞 두 항의 합인 수열이다. 1, 1, 2, 3, 5, 8, ... 이렇게 전개된다. 알고리즘 계에서는 달나라 토끼에서부터 건물 페인트 칠하기, 계단 오르기 등 정말 다양한 가면을 쓰면서 등장하는 녀..
[재귀]05. 메모이제이션(memoization)이번 포스트에서는 재귀의 동작 과정에서 발생할 수 있는 엄청난 중복 호출과 이를 극복하기 위한 메모이제이션에 대해서 살펴보자. 피보나치! 피보나치 수열 구하기 피보나치 수 - 위키백과, 우리 모두의 백과사전 위키백과, 우리 모두의 백과사전. 피보나치 수를 이용한 사각형 채우기 수학에서 피보나치 수(영어: Fibonacci numbers)는 첫째 및 둘째 항이 1이며 그 뒤의 모든 항은 바로 앞 두 항의 합인 수열이다. ko.wikipedia.org 피보나치 수는 첫째항과 둘째 항이 1이고 그 뒤의 항은 바로 앞 두 항의 합인 수열이다. 1, 1, 2, 3, 5, 8, ... 이렇게 전개된다. 알고리즘 계에서는 달나라 토끼에서부터 건물 페인트 칠하기, 계단 오르기 등 정말 다양한 가면을 쓰면서 등장하는 녀..
2022.08.01 -
앞선 포스트에서 기본적인 재귀의 특성과 재귀가 반드시 정복해야할 산임을 배웠다. 하지만 재귀 함수의 동작을 이해하더라도 재귀 함수를 작성하기가 쉽지는 않다. 이번 포스트에서는 어떻게 재귀 함수를 디자인 해야할지 살펴보고 연습해보자. 재귀 함수 디자인 재귀 함수 디자인 절차 재귀함수는 수학적 귀납법을 이용한 점화식을 찾아서 문제를 해결한다. 수학적 귀납법은 크게 다음의 두 가지 사실을 증명하는 것이다. n=1일 때, 명제 p(n)이 성립한다. n=k일 때, 명제 p(n)이 성립한다고 가정하면 n=k+1일 때도 명제 p(n)이 성립한다. 재귀함수를 작성할 때도 수학적 귀납법에 의거해서 작성해주는데 먼저 구하려는 내용을 수학적 귀납법으로 풀고 점화식을 찾아야 한다.풀이 결과 1번 항목이 base part가 되..
[재귀]04. 재귀함수 디자인 절차앞선 포스트에서 기본적인 재귀의 특성과 재귀가 반드시 정복해야할 산임을 배웠다. 하지만 재귀 함수의 동작을 이해하더라도 재귀 함수를 작성하기가 쉽지는 않다. 이번 포스트에서는 어떻게 재귀 함수를 디자인 해야할지 살펴보고 연습해보자. 재귀 함수 디자인 재귀 함수 디자인 절차 재귀함수는 수학적 귀납법을 이용한 점화식을 찾아서 문제를 해결한다. 수학적 귀납법은 크게 다음의 두 가지 사실을 증명하는 것이다. n=1일 때, 명제 p(n)이 성립한다. n=k일 때, 명제 p(n)이 성립한다고 가정하면 n=k+1일 때도 명제 p(n)이 성립한다. 재귀함수를 작성할 때도 수학적 귀납법에 의거해서 작성해주는데 먼저 구하려는 내용을 수학적 귀납법으로 풀고 점화식을 찾아야 한다.풀이 결과 1번 항목이 base part가 되..
2022.08.01 -
동일한 로직을 여러 번 적용하기 위해서는 반복문을 적용할 수 있는데 이 반복문은 재귀의 형태로 변경이 가능하다. 그런데 일반적으로 사람들은 반복문에 상대적으로 익숙하기 때문에 굳이 당장 손이 가지않는 재귀를 사용하려 하지 않는다. 하지만 알고리즘에서 재귀는 선택이 아닌 필수이다.! 이번 포스트에서는 반복문과 재귀를 비교해보고 최종적으로 왜 재귀를 써야하는지 살펴보자. 반복문 vs 재귀 반복문과 재귀 함수의 비교 일반적으로 반복문과 재귀 함수는 다음과 같이 비교할 수 있다. 재귀 함수 반복문 종료 조건 기본 파트에서 return 반복문 종료 조건 수행 시간 메서드 호출 비용으로 상대적으로 느림 상대적으로 빠름 메모리 stack 메모리 점유로 상대적으로 많이 사용 상대적으로 적게 사용 작성 난이도 이해하면..
[재귀]03. 반복문 vs 재귀동일한 로직을 여러 번 적용하기 위해서는 반복문을 적용할 수 있는데 이 반복문은 재귀의 형태로 변경이 가능하다. 그런데 일반적으로 사람들은 반복문에 상대적으로 익숙하기 때문에 굳이 당장 손이 가지않는 재귀를 사용하려 하지 않는다. 하지만 알고리즘에서 재귀는 선택이 아닌 필수이다.! 이번 포스트에서는 반복문과 재귀를 비교해보고 최종적으로 왜 재귀를 써야하는지 살펴보자. 반복문 vs 재귀 반복문과 재귀 함수의 비교 일반적으로 반복문과 재귀 함수는 다음과 같이 비교할 수 있다. 재귀 함수 반복문 종료 조건 기본 파트에서 return 반복문 종료 조건 수행 시간 메서드 호출 비용으로 상대적으로 느림 상대적으로 빠름 메모리 stack 메모리 점유로 상대적으로 많이 사용 상대적으로 적게 사용 작성 난이도 이해하면..
2022.07.31 -
이번 포스트에서는 재귀 함수가 어떻게 호출되면서 동작하는지 살펴보자. 재귀함수 동작이 처음에 와닿지 않는 경우가 많은데 재귀를 이해하기 위해서는 메모리에서 함수들이 어떻게 동작하는지 손으로 스택을 직접 그려가면서 공부하는 방법이 제일 좋다. 함수의 호출과 메모리 함수들을 호출되면서 stack 영역에 해당 함수만을 위한 메모리 공간을 확보하고 함수의 동작을 처리한다. 함수에서 또 다른 함수를 호출하는 경우 기존 함수의 메모리 공간 위에 새로운 함수를 위한 메모리 공간을 쌓게(stack)된다. 이때 기존의 메모리는 동작을 일시 정지하는 pending 상태가 되고 맨 위의 메모리 공간만 활성화 상태가 된다. 그리고 메서드가 return 되면 점유하고 있던 메모리 공간을 반환하고 기존에 pending 되어있던 ..
[재귀]02. 재귀 함수와 호출 트리이번 포스트에서는 재귀 함수가 어떻게 호출되면서 동작하는지 살펴보자. 재귀함수 동작이 처음에 와닿지 않는 경우가 많은데 재귀를 이해하기 위해서는 메모리에서 함수들이 어떻게 동작하는지 손으로 스택을 직접 그려가면서 공부하는 방법이 제일 좋다. 함수의 호출과 메모리 함수들을 호출되면서 stack 영역에 해당 함수만을 위한 메모리 공간을 확보하고 함수의 동작을 처리한다. 함수에서 또 다른 함수를 호출하는 경우 기존 함수의 메모리 공간 위에 새로운 함수를 위한 메모리 공간을 쌓게(stack)된다. 이때 기존의 메모리는 동작을 일시 정지하는 pending 상태가 되고 맨 위의 메모리 공간만 활성화 상태가 된다. 그리고 메서드가 return 되면 점유하고 있던 메모리 공간을 반환하고 기존에 pending 되어있던 ..
2022.07.30 -
이번 포스트에서는 재귀가 왜 필요한지와 기본적인 재귀의 흐름에 대해서 살펴보자. 재귀함수 재귀란? 재귀(再歸, recursion )란 러시아의 전통인형 마요르카 처럼 내 안에 또 다른 나 즉 모양이나 동작은 동일하지만 크기만 작은 나를 찾아가는 과정이다. 우리는 수학 시간에도 재귀의 성격을 잘 배운적이 있다. 1부터 n까지의 곱을 구하는 펙토리얼 연산이 그 예이다. n! = 1 * 2 * 3 * ... * (n-2) * (n-1) * n 여기서 맨 마지막의 *n을 제외하면 나머지는 (n-1)! 이 된다. 즉 크기만 1작아진 펙토리얼이다. 이렇게 하나의 문제 내에 크기는 다르지만 동일한 성격의 다른 문제를 하나 이상 포함하고 있는 것을 재귀적 구조라고 한다. 이런 재귀를 프로그래밍 함수에 적용한 것을 재귀..
[재귀]01. 재귀 함수이번 포스트에서는 재귀가 왜 필요한지와 기본적인 재귀의 흐름에 대해서 살펴보자. 재귀함수 재귀란? 재귀(再歸, recursion )란 러시아의 전통인형 마요르카 처럼 내 안에 또 다른 나 즉 모양이나 동작은 동일하지만 크기만 작은 나를 찾아가는 과정이다. 우리는 수학 시간에도 재귀의 성격을 잘 배운적이 있다. 1부터 n까지의 곱을 구하는 펙토리얼 연산이 그 예이다. n! = 1 * 2 * 3 * ... * (n-2) * (n-1) * n 여기서 맨 마지막의 *n을 제외하면 나머지는 (n-1)! 이 된다. 즉 크기만 1작아진 펙토리얼이다. 이렇게 하나의 문제 내에 크기는 다르지만 동일한 성격의 다른 문제를 하나 이상 포함하고 있는 것을 재귀적 구조라고 한다. 이런 재귀를 프로그래밍 함수에 적용한 것을 재귀..
2022.07.30