[바킹독의 실전 알고리즘] 복습 - 0x0B

오젼·2025년 6월 28일
알고리즘
0

[바킹독의 실전 알고리즘]

목록 보기
20/23

0x0A DFS

깊이 우선 탐색.

DFS는 문제가 따로 없다.
다차원 배열 순회 문제는 DFS 보다 BFS로 풀어야 함.
나중에 그래프와 트리에선 DFS가 필요하다.

0x0B 재귀

귀납적 사고방식이 돼야 한다..
"1번 도미노가 쓰러진다', 'k번 도미노가 쓰러지면 k+1번 도미노도 쓰러진다'가 참이니까 모든 도미노가 쓰러진다"

base case가 있어야 한다. 모든 입력은 base case로 수렴해야 한다.

재귀는 모두 반복문으로 바꿀 수 있다. 재귀는 반복문에 비해 코드가 간결해질 수는 있지만 함수 호출 비용 때문에 메모리와 시간에서 손해를 본다.

재귀 함수가 자기 자신을 부를 때 스택 영역에 함수 정보가 누적된다. 지역 변수도 스택 메모리에 할당된다. 스택 메모리가 제한적일 경우 재귀를 너무 깊게 들어가거나 지역 변수로 너무 큰 크기의 배열을 잡으면 메모리 초과가 된다.

1629 | 곱셈

핵심 - 거듭제곱 & 모듈러 문제

이 문제는 단순히 A^B % C를 구하면 되는 것처럼 보이지만,
두 가지 이슈를 반드시 고려해야 한다.

  1. 오버플로우
    A^B는 너무 커져서 long long으로도 못 담는다.
    중간중간에 % C를 적용해줘야 한다. (모듈러 연산은 분배법칙이 적용된다)

  2. 시간복잡도
    A를 B번 곱하면서 계산하면 시간복잡도는 O(B)
    B는 최대 2,147,483,647 (약 2 * 10⁹)
    약 20억번 연산.
    시간제한은 0.5초. c++ 기준 일반적으로 1초에 약 1억번(10⁸) 연산.
    시간제한 0.5초면 약 5천만 번 연산 가능.

해결법 - 분할 정복

이 문제는 지수를 절반씩 줄여가며 계산하는 분할 정복 방식으로 해결할 수 있다.
즉, 빠른 거듭제곱 (Fast Exponentiation) 을 사용해야 한다.

기존 방식은?

  • 일반적으로 거듭제곱을 계산할 때는
    3^10 → 3^9 → 3^8 → ... → 3^1 처럼
    지수를 1씩 줄여가며 곱하는 방식 (O(B))

→ B가 커지면 시간초과 발생

빠른 거듭제곱 방식은?

  • 3^10 → 3^5 → 3^2 → 3^1 처럼
    지수를 반씩 줄이면서 재귀적으로 계산

  • 계산 방식은 아래와 같다:

    • 지수가 짝수라면,
      → 이전 결과를 제곱:

      ab=(ab/2)2a^b = (a^{b/2})^2

    • 지수가 홀수라면,
      → 제곱한 결과에 밑(a)을 한 번 더 곱해줌:

      ab=(ab/2)2⋅aa^b = (a^{b/2})^2 \cdot a

오버플로우는 어떻게 방지?

곱셈 연산은 모듈러 연산의 분배법칙이 성립하기 때문에,
중간중간에 mod C를 적용해도 결과는 유지된다.

즉, 계산할 때마다

(a * b) % C

를 해주면,
오버플로우를 방지하면서도 정답은 변하지 않는다.

시간복잡도는 얼마나 줄어드나?

  • 분할 정복을 쓰면 계산 횟수는 O(log B)로 줄어든다.

예를 들어:

B=2,147,483,647≈2×109B = 2,147,483,647 \approx 2 \times 10^9
log⁡2(2×109)≈31\log_2(2 \times 10^9) \approx 31

즉, 20억이라는 큰 수라도 31번만 계산하면 된다

실전 팁: log₂ 추정 쉽게 하기

자리 수로 log₂를 대충 추정할 수 있다:

  • 공식:

    log⁡2(n)≈(자리 수)×3.3\log_2(n) \approx (\text{자리 수}) \times 3.3

예시:

  • 20억 = 약 10자리 수
  • log⁡2(2×109)≈10×3.3=33\log_2(2 \times 10^9) \approx 10 \times 3.3 = 33

→ 실제 log₂ 값 31과 거의 비슷!

풀이 코드

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

ll func(ll a, ll b, ll c) {
	if (b == 1) return a % c;

	ll result = func(a, b / 2, c);
	result = (result * result) % c;

	if (b % 2 == 0) return result;
	return (a % c) * result % c;
}

int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);

	ll a, b, c;
	cin >> a >> b >> c;
	cout << func(a, b, c);
}

그냥 제곱을 한다면

ll func(ll a, ll b, ll c) {
	if (b == 1) return a;

	ll result = func(a, b / 2, c);

	if (b % 2 == 0) return result;
	return result;
}

근데 모듈러 연산을 적용하면

ll func(ll a, ll b, ll c) {
	if (b == 1) return a % c;

	ll result = func(a, b / 2, c);
	result = (result * result) % c;

	if (b % 2 == 0) return result;
	return (a % c) * result % c;
}

또는

ll func(ll a, ll b, ll c) {
	if (b == 1) return a % c;

	ll result = func(a, b / 2, c);
	result = (result * result) % c;

	if (b % 2 == 0) return result;
	return a * result % c;
}

적당히 값이 오버플로가 날 거 같은 부분에 %c로 제한 걸어주면 됨.

수학적으로는 곱셈 결과에만 % c를 적용해도 정답은 동일하지만,
중간 계산에서 값이 long long 범위를 초과할 수 있기 때문에,
보통은 곱셈하기 전에 a % c, b % c를 먼저 해주는 것이 안전하다.

그니까 (a % c) * result % c나 a * result % c나 계산 결과는 동일한데 a * result가 overflow가 발생할 것 같다면 a % c * result로 제한해주면 되는 거

이제 진짜 이해했다...

11729 | 하노이 탑 이동 순서

처음 버전

#include <bits/stdc++.h>
using namespace std;

void print_hanoi(int n, int from, int to) {
	if (n == 1) {
		cout << from << ' ' << to << '\n';
		return;
	}

	// f(n-1) + 1 + f(n-1): n-1개를 빈 곳에 옮기고 + n번째를 to에 옮기고 + n-1을 빈 곳에서 to로 옮김
	print_hanoi(n - 1, from, 6 - from - to);
	cout << from << ' ' << to << '\n';
	print_hanoi(n - 1, 6 - from - to, to);
}

int hanoi(int n) {
	if (n == 1) return 1;
	return 2 * hanoi(n - 1) + 1;
}

int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);

	int n;
	cin >> n;
	cout << hanoi(n) << '\n';
	print_hanoi(n, 1, 3);
}

이동 횟수와 이동 과정을 둘다 재귀로 문제를 풀었는데, 사실 이동 횟수는 굳이 재귀로 계산하지 않아도 된다!

개선 버전

#include <bits/stdc++.h>
using namespace std;

void print_hanoi(int n, int from, int to) {
	if (n == 1) {
		cout << from << ' ' << to << '\n';
		return;
	}

	// f(n-1) + 1 + f(n-1): n-1개를 빈 곳에 옮기고 + n번째를 to에 옮기고 + n-1을
	// 빈 곳에서 to로 옮김
	print_hanoi(n - 1, from, 6 - from - to);
	cout << from << ' ' << to << '\n';
	print_hanoi(n - 1, 6 - from - to, to);
}

int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);

	int n;
	cin >> n;
	cout << (1 << n) - 1 << '\n';
	print_hanoi(n, 1, 3);
}

하노이 탑은 등비수열!

하노이 탑 이동 횟수는 다음 점화식을 따른다:

an=2an−1+1a_n = 2a_{n-1} + 1

이 점화식은 아래와 같이 변형할 수 있다:

an+1=2(an−1+1)a_n + 1 = 2(a_{n-1} + 1)

여기서 bn=an+1b_n = a_n + 1로 두면:

bn=2bn−1b_n = 2b_{n-1}

즉, 공비가 2인 등비수열

따라서 일반항은:

bn=b1⋅2n−1=2⋅2n−1=2nb_n = b_1 \cdot 2^{n-1} = 2 \cdot 2^{n-1} = 2^n

이제 원래 수열로 다시 바꿔주면:

an=bn−1=2n−1a_n = b_n - 1 = 2^n - 1

결론

하노이 탑에서 n개의 원판을 옮기는 최소 이동 횟수는

2n−12^n - 1

그래서 이동 횟수는 재귀로 구하지 않아도 됨!
이동 과정만 재귀로 잘 구성해주면 된다.

cout << (1 << n) - 1 << '\n';

이렇게 하면 바로 2n−12^n - 1 값을 계산할 수 있음

1074 | Z

처음 버전

#include <bits/stdc++.h>
using namespace std;

int cnt, ans;
int N, r, c;

void func(int x, int y, int k) {
	if (k == 1) {
		if (x == r && y == c) ans = cnt;
		++cnt;
		return;
	}

	func(x, y, k / 2);
	func(x, y + k / 2, k / 2);
	func(x + k / 2, y, k / 2);
	func(x + k / 2, y + k / 2, k / 2);
}

int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> N >> r >> c;
	func(0, 0, 1LL << N);
	cout << ans;
}

처음엔 각 사분면을 모두 들어가서 계산을 했다. 시간초과.

최악의 경우 2^15 * 2^15 연산. 2^30
2^10(1024)이 약 10^3이니까 (2^10)^3 ≈ (10^3)^3 = 10^9. 약 10억번.

시간제한 0.5초 c++기준 1초당 약 1억번 연산. 5천만번이 최대.

그니까 시간 초과 당연.

개선 버전

#include <bits/stdc++.h>
using namespace std;

int N, r, c, ans;

void func(int x, int y, int k, int cnt) {
	if (k == 1) {
		if (x == r && y == c) ans = cnt;
		return;
	}

	k = k / 2;
	if (x + k <= r && y + k <= c) return func(x + k, y + k, k, cnt + k * k * 3);
	if (x + k <= r && y <= c) return func(x + k, y, k, cnt + k * k * 2);
	if (x <= r && y + k <= c) return func(x, y + k, k, cnt + k * k);
	return func(x, y, k, cnt);
}

int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> N >> r >> c;
	func(0, 0, 1LL << N, 0);
	cout << ans;
}

시간 복잡도 분석 및 개선 효과

개선 버전에서는 사분면 4개를 모두 재귀적으로 호출하지 않고,
(r, c)가 포함된 단 하나의 사분면만 재귀 호출한다.

이로 인해 시간 복잡도는 다음과 같이 O(N)으로 줄어든다:

k는 처음에 2^N이고, 한 번 호출할 때마다 k = k / 2로 절반씩 줄어듦.

그러니 k^(n-1)로 줄어드는 것.

따라서 전체 재귀 호출 깊이는 log₂(2^N) = N
각 호출은 상수 시간 연산만 하므로 총 연산 횟수는 O(N)

즉 최악의 경우 15번

17478 | 재귀함수가 뭔가요?

간단

1780 | 종이의 개수

#include <bits/stdc++.h>
using namespace std;

int board[2200][2200];
int cnt[3];

bool check(int x, int y, int n) {
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < n; ++j) {
			if (board[x][y] != board[x + i][y + j]) return false;
		}
	}
	cnt[board[x][y] + 1] += 1;
	return true;
}

void func(int x, int y, int n) {
	if (check(x, y, n)) return;

	n /= 3;
	for (int i = 0; i < 3; ++i) {
		for (int j = 0; j < 3; ++j) func(x + i * n, y + j * n, n);
	}
}

int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);

	int N;
	cin >> N;

	for (int i = 0; i < N; ++i) {
		for (int j = 0; j < N; ++j) cin >> board[i][j];
	}

	func(0, 0, N);
	for (int i = 0; i < 3; ++i) cout << cnt[i] << '\n';
}

int(pow(3, 7)) 해보면 2187 나옴.
배열 넉넉하게 int board[2200][2200] 정도 잡고
2200 * 2200 * 4 / pow(10, 6) 해보면
19.36. 약 19.36MB. 메모리 충분.

2630 | 색종이 만들기

위 문제와 유형 똑같. 간단.

#include <bits/stdc++.h>
using namespace std;

int board[130][130];
int cnt[2];

bool check(int x, int y, int n) {
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < n; ++j) {
			if (board[x][y] != board[x + i][y + j]) return false;
		}
	}
	return true;
}

void func(int x, int y, int n) {
	if (check(x, y, n)) {
		cnt[board[x][y]] += 1;
		return;
	}

	n /= 2;
	func(x, y, n);
	func(x, y + n, n);
	func(x + n, y, n);
	func(x + n, y + n, n);
}

int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);

	int N;
	cin >> N;

	for (int i = 0; i < N; ++i)
		for (int j = 0; j < N; ++j) cin >> board[i][j];
	func(0, 0, N);
	cout << cnt[0] << '\n' << cnt[1];
}

1992 | 쿼드트리

위 유형들이랑 똑같. 간단.

2447 | 별 찍기 - 10

간단.

공간 쓰는 버전

#include <bits/stdc++.h>
using namespace std;

char board[2200][2200];

void f(int r, int c, int n) {
	if (n == 1) {
		board[r][c] = '*';
		return;
	}
	n /= 3;
	for (int i = 0; i < 3; ++i) {
		for (int j = 0; j < 3; ++j) {
			if (i == 1 && j == 1) continue;
			f(r + n * i, c + n * j, n);
		}
	}
}

int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);

	int n;
	cin >> n;

	for (int i = 0; i < n; ++i) fill(board[i], board[i] + n, ' ');
	f(0, 0, n);
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < n; ++j) cout << board[i][j];
		cout << '\n';
	}
}

공간 안 쓰는 방법도 있음

공간 안 쓰는 버전

#include <bits/stdc++.h>
using namespace std;

void print(int r, int c, int n) {
	if ((r / n) % 3 == 1 && (c / n) % 3 == 1) {
		cout << ' ';
		return;
	}

	if (n == 1) {
		cout << '*';
		return;
	}

	print(r, c, n / 3);
}

int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);

	int n;
	cin >> n;

	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < n; ++j) {
			print(i, j, n / 3);
		}
		cout << '\n';
	}
}

좌표 하나하나마다 재귀로 해당 좌표가 공백인지 아닌지 판단하는 거임. 근데 이렇게 생각하는 것보다 첫 번째 버전이 훨씬 직관적이고 좋은 듯..

그래도 아이디어 이해해놓으면 좋을 것 같아서 끝까지 이해해봤다.

블록의 크기를 점점 줄여가면서(n / 3),
그때의 블록 크기 기준으로
내 좌표 (r, c)가 가운데 블록에 해당하는지를
if ((r / n) % 3 == 1 && (c / n) % 3 == 1) 으로 판단한다.

블록 단위로 생각하기

  • r / size : 현재 size 크기의 블록 기준으로 세로 몇 번째 블록인지
  • c / size : 현재 size 크기의 블록 기준으로 가로 몇 번째 블록인지
  • 3×3 블록 중 가운데인지 확인
    (r / size) % 3 == 1 && (c / size) % 3 == 1
    → 현재 좌표가 3×3 블록 중 가운데 칸에 위치함

2448 | 별 찍기 - 11

아... 머리 아파....
못 풀었다

#include <bits/stdc++.h>
using namespace std;

char board[4000][8000];

void f(int r, int c, int n) {
	if (n == 3) {
		board[r][c] = '*';
		board[r + 1][c - 1] = board[r + 1][c + 1] = '*';
		for (int i = -2; i <= 2; ++i) board[r + 2][c + i] = '*';
		return;
	}
	n /= 2;
	f(r, c, n);
	f(r + n, c - n, n);
	f(r + n, c + n, n);
}

int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);

	int N;
	cin >> N;

	for (int i = 0; i < N; ++i) fill(board[i], board[i] + N * 2 - 1, ' ');
	f(0, N - 1, N);

	for (int i = 0; i < N; ++i) {
		for (int j = 0; j < N * 2 - 1; ++j) cout << board[i][j];
		cout << '\n';
	}
}

챗지피티한테 아이디어 얻어서 다시 풀었다...
풀고 나니까 쉽네

  * 
 * *
*****

이 모양이 기본이다!

그니까 n==3이 베이스 컨디션임.

그 전에는 가운데 삼각형 꼭짓점을 기준으로
(r, c), (r + n/2, c - n/2), (r + n/2, c + n/2) 로 타고타고 들어가면 됨!

profile
오젼
이전 포스트

[바킹독의 실전 알고리즘] 복습 - 0x09 (2)

다음 포스트

[바킹독의 실전 알고리즘] 복습 - 0x0C

0개의 댓글