- 지역 변수도 스택 메모리에 들어간다.
- 재귀가 너무 깊거나 지역 변수로 [2000][2000]과 같은 큰 배열 잡으면 메모리 초과가 날 수 있다.
- int 400만개 = 16 MB
** 함수의 정의, base condition, 재귀식을 잘 생각해서 풀어보자 **
# 문제 풀이
[BOJ] 1629_곱셈 with cpp
시간복잡도 : b가 계속 절반씩 깎이기 때문에 O(logb) #include using namespace std; using LL = long long; LL Power(LL a, LL b, LL c) { if (b == 1) // base condition { return a % c; } LL result = Power(..
hqvfx.tistory.com
[BOJ] 11729 하노이 탑 이동 순서 with cpp
원판 n개를 a에서 b로 이동하는 함수를 만든다 void func(int a, int b, int n) base condition은 n이 1일 때 a에서 b로 옮기는 것이다 if (n == 1) { cout << a << ' ' << b << '\n'; return; } 나머지 재귀식은..
hqvfx.tistory.com
[BOJ] 1074_Z with cpp
N(1<= N <= 15)이 주어졌을 때, 2^n * 2^n 배열에서 (r, c)를 방문하는 순서를 출력하는 프로그램을 작성해야 한다 규칙을 보면 배열을 4등분 하여 순서대로 진행하는 것을 알 수 있다 base conditino은 n이 0
hqvfx.tistory.com
[BOJ] 17478_재귀함수가 뭔가요? with cpp
# 생각 N에 따라 출력되는 문자의 횟수를 세어보면 된다 첫 째줄인 <어느 한 컴퓨터공학과 학생이 유명한 교수님을 찾아가 물었다.>는 단독으로 존재하기 때문에 재귀함수에 포함을 시키지 않거
hqvfx.tistory.com
[BOJ] 2630_색종이 만들기 with cpp
# 생각 전체를 탐색하면서 다 같은 색으로 이루어져있는지를 파악해야 한다 전체를 탐색했을 때 다 같은색으로 이루어져있지 않아 판단이 불가하다면 4개의 사각형으로 나누어 판단해준다 # 전
hqvfx.tistory.com
[BOJ] 1780_종이의 개수 with cpp
# 생각 같은 숫자로만 채워져 있는지 확인한다 같은 숫자로만 이루어지지 않았을 때 3x3 크기로 나누어 확인한다 입력값이 -1, 0, 1로 이루어져있기 때문에 ans배열에 +1을 해준다 # 전체 코드 #include
hqvfx.tistory.com
[BOJ] 1992_쿼드트리 with cpp
# 생각 범위 안의 원소가 모두 똑같은지 탐색한다 일치하면 출력하고 탈출하는 base condition, 일치하지 않으면 4등분 하는 재귀식을 작성한다 # 전체 코드 #include using namespace std; // 제한 : 2초, 128MB..
hqvfx.tistory.com
[BOJ] 2447_별 찍기 - 10 with cpp
# 생각 // PrintStar2 패턴은 가운데에 공백이 있고, 가운데를 제외한 전체는 별이기 때문에 base condition은 별을 넣어준다 N이 3보다 클 경우, 공백으로 채워진 가운데(N/3) * (N/3)의 정사각형을 크기 N/3
hqvfx.tistory.com
[BOJ] 2448_별 찍기 - 11 with cpp
# 생각 삼각형 모양이기 때문에 배열 크기에 주의한다 패턴을 보면 작은 삼각형이 여러개를 이루는 프랙탈 구조를 가지고 있다 가장 작은 삼각형인 n = 3 일 때 차례로 저장해주고 종료해주면 된
hqvfx.tistory.com
[BOJ] 14956_Philosopher's walk with cpp
# 생각 문제에 나오는 모양은 Hilbert Curve 모양으로 쿼드트리와 같은 분할정복 재귀문제와 동일한 방법으로 풀 수 있다 base condition은 가장 작은 사각형의 길이가 2^1이기 때문에 side가 2일때 4가지
hqvfx.tistory.com
# 출처
'Algorithm > 정리' 카테고리의 다른 글
| 0x0E,0F - 정렬 (0) | 2022.02.28 |
|---|---|
| 0x02 - 기초 코드 작성 요령2 (0) | 2022.02.15 |
| cpp (0) | 2022.02.10 |
| 0x0C - Backtracking (0) | 2022.01.31 |
| 0x01 - 기초 코드 작성 요령1 (0) | 2022.01.25 |