※ (링크) 바킹독 유튜브 영상을 통해
학습한 내용을 정리한 것입니다.
본인은 JAVA를 활용해 학습하였습니다
비상업적 목적이며, 개인 복습을 위해 업로드한 글임을 다시 한 번 더 이야기드립니다.
본문의 모든 내용의 출처는 아래 명시된 링크와 같습니다.
[목차] 알고리즘 설명, 연습 문제 1 - 거듭제곱, 연습 문제 2 - 하노이 탑, 연습 문제 3 - Z
[실전 알고리즘] 0x0B강 - 재귀
안녕하세요, 재귀 파트를 시작하겠습니다. 지금 자신있게 말할 수 있는게 있는데 이 파트가 정말 어려울 것입니다. 물론 이전의 내용들 중에서도 군데군데 어려운게 있었겠지만 이번 단원에서
blog.encrypted.gg
출처: blog.encrypted.gg/943?category=773649
알고리즘 설명
재귀: 하나의 함수에서 자기 자신을 다시 호출해 작업을 수행하는 알고리즘
이 코드는 어떻게 수행할 수 있는 걸까요? 재귀로 푼다는 것은 귀납적으로 푼다는 것입니다. 지금까지 작성한 코드는 일반적으로 순차적으로 진행되는 코드였습니다. 이러한 방식과 귀납적인 방식의 차이가 무엇인지 먼저 알아보겠습니다.
도미노로 예를 들자면, 제일 앞 도미노를 쓰러트리면 모든 도미노가 쓰러집니다. 그렇다면 왜 모든 도미노가 쓰러질까요? 두 가지 방법으로 설명할 수 있습니다.
- 첫 번째, 1번 도미노가 쓰러지면 다음 도미노가 쓰러지고, 그 다음 도미노가 쓰러지면 마지막 도미노가 쓰러질때까지 반복됩니다.
- 두 번째, 1번 도미노가 쓰러집니다. 즉, k번 도미노가 쓰러지면 k + 1번 도미노도 쓰러진다는 것이 참이기에 모든 도미노가 쓰러집니다.
두 번째 이유로 모두 쓰러지는 것이 한 번에 인식되어야만 합니다. 즉, 당연하게 생각하던 절차 지향적 사고를 벗어나야 재귀를 명확히 이해할 수 있습니다.
절차지향적 사고
n부터 1까지 출력하는 문제로 절차지향적 사고와 귀납적 사고의 차이를 보겠습니다.
먼저 절차지향적 사고로 example01(3)의 출력 결과가 왜 [ 3 2 1 ]인지를 생각한다면, 코드의 동작 흐름을 그대로 따라가면 됩니다. 메서드가 호출되면 3를 출력한 후 example01(2)를 호출하며, 2를 출력한 뒤 example01(1)을 호출해 1를 출력한 후 example01(0)을 호출합니다.
이번에는 귀납적 사고로 이해해보도록 하겠습니다.
귀납적 사고
" example01(1)이 1을 출력한다. " 이는 명확합니다. example01(k)가 example01(k-1), example01(k-2), ... 1 을 출력하면, example01(k+1)은 k + 1, k , k - 1, ... 1을 출력합니다. 즉, k+1 부터 1까지 출력합니다.
이는 example01(k + 1)이 호출될 때, 어떤 상황이 생기는가를 보면 되는데,
k + 1이 출력된 이후 example01(k)가 호출되고 1까지 차례로 출력과 호출을 반복합니다. example01(k + 1)은 k + 1부터 1까지 차례로 출력함을 알 수 있습니다. "
위 문장이 참이므로 귀납적으로 example01 함수가 n부터 1까지 차례로 출력하는 함수임을 알 수 있게 됩니다.
재귀함수 조건
- Base Condition
- 특정 입력에 대해 자기 자신을 호출하지 않고 종료하는 것
- 모든 입력은 Base Condition으로 수렴해야 함 - 위 조건 중 하나라도 지켜지지 않는다면, 무한 반복 후 Runtime Error 발생
재귀에 대한 정보 1
- [ 함수를 명확하게 정의하기 ] 함수 인자로 어떤 것을 받고 어디까지 계산한 뒤, 자기 자신에게 넘길 것인지 명확하게 해야 함
- 모든 재귀 함수는 반복문만으로 동일 동작을 하는 함수를 만들 수 있음
- 재귀는 적재적소에 사용하면 굉장히 간결하고 효율적이지만, 메모리/시간 축면에서는 손해를 봄
굳이 재귀를 쓰지 않아도 구현에 어려움이 없으면 반복문을 사용하는 것이 좋지만, 재귀 없이 구현을 하면 코드가 너무 복잡한 일부 문제는 재귀로 구현하는 것이 좋습니다. 이는 경험을 통해 노하우를 얻는 것이 좋습니다.
재귀에 대한 정보 2
- 한 개의 재귀함수가 자기 자신을 여러 번 호출하면 비효율적일 수 있음
이미 계산한 값을 다시 계산하는 일이 빈번하게 발생해, 시간복잡도가 굉장히 커지는 일이 발생합니다. 이러한 사례처럼 한 함수가 자기자신을 여러 번 호출할 경우 시간복잡도가 과도하게 커질 수 있기에 유의해야 합니다.
위 문제는 다이나믹 프로그래밍을 이용해 O(N)에 해결할 수 있습니다.
재귀에 대한 정보 3
- 재귀함수가 자기 자신을 부를 때 Stack 영역에 계속 누적 됨
메모리 구조 중 Stack에 정보가 누적됩니다. 메모리는 누적될 수 있는 크기가 제한되어 있습니다. 만약 이러한 메모리 크기를 넘어간다면 StackOverFlow가 발생합니다.
연습 문제 1 - 거듭제곱
ab mod m
이 문제는 a의 b제곱을 m으로 나눈 나머지를 구하는 코드를 작성해보겠습니다. 바로 떠오르는 방법은 a를 b번 곱하는 방법입니다.
하지만 말도 안되게 제곱 횟수가 많은 경우 자료형의 범위를 벗어나 Overflow가 발생할 수도 있습니다.
이를 방지하기 위해 곱하는 중간 중간 계속 m으로 나누어 나머지 값만 챙겨가면 됩니다.
1의 자리를 구할 때, 각 수의 1의 자리를 곱한 뒤 10의 나머지를 결과 값으로 가지는 것처럼 이 문제 또한 그렇게 접근하면 됩니다. 곱한 값을 m으로 나눈 나머지를 넘겨주는 것이죠.
재귀문제는 전반적으로 문제를 접근하고 풀이를 생각하는 것이 어려웠음..
이해할 때까지 다시 풀기
BOJ 1629번: 곱셈
힌트
- 1번 도미노가 쓰러진다.
k번 도미노가 쓰러지면 k+1번 도미노도 쓰러진다. - 1승을 계산할 수 있다.
k승을 계산했으면 2k승과 2k + 1승도 O(1)에 계산할 수 있다.
두 번 봐도 b/2로 넘겨주는 이유가 이해가 안 간다..ㅠㅠㅠ
onsil-thegreenhouse.github.io/programming/problem/2018/03/29/problem_math_power/
[Problem] 어떤 수의 n제곱 구하기(백준 1629번) - Onsil's blog
초짜 개발자 온실의
스터디 블로그
onsil-thegreenhouse.github.io
- b 값이 절반으로 줄어들며 계산하므로 시간 복잡도는 O(log b)
BOJ 11729번: 하노이 탑
11729번: 하노이 탑 이동 순서
세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로
www.acmicpc.net
하노이 탑이 기억 안 날 경우 아래 페이지에서 게임 한 번 해보기!
www.mathsisfun.com/games/towerofhanoi.html
Play Tower of Hanoi
Tower of Hanoi Object of the game is to move all the disks over to Tower 3 (with your mouse). But you cannot place a larger disk onto a smaller disk.
www.mathsisfun.com
BOJ 1074번: Z
1074번: Z
한수는 크기가 2N × 2N인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다. 만약, N > 1이 라서
www.acmicpc.net
문제집
www.acmicpc.net/workbook/view/7314
문제집: 0x0B강 - 재귀 (BaaaaaaaaaaarkingDog)
www.acmicpc.net
'Programming > Algorithm' 카테고리의 다른 글
| [바킹독: 알고리즘] 깊이 우선 탐색(DFS) (0) | 2021.04.23 |
|---|---|
| [바킹독: 알고리즘] BFS 알고리즘 (너비 우선 탐색) (0) | 2021.04.20 |
| [바킹독: 알고리즘] 스택의 활용(수식의 괄호 쌍) (0) | 2021.04.15 |
| [바킹독: 알고리즘] 덱(Deque) (0) | 2021.04.12 |
| [바킹독: 알고리즘] 큐(Queue) (0) | 2021.04.11 |
