'알고리즘/바킹독의 실전 알고리즘' 카테고리의 글 목록 (4 Page)

알고리즘/바킹독의 실전 알고리즘

[0x0E] 정렬 I 2022.08.02
[0x0D] 시뮬레이션 2022.08.01
[0x0C] 백트래킹 2022.07.31
[0x0B] 재귀 2022.07.30
[0x0A] DFS 2022.07.30

PREV 이전 1 2 3 4 5 6 NEXT 다음

[0x0E] 정렬 I

2022. 8. 2. 21:26

병합 정렬 (Merge Sort)

분할 정복을 이용한 정렬이다. 분할하는 과정에서 O(N), 합치는데 O(NlogN)이 소요되므로 O(NlogN)이다.

언제나 O(NlogN)이 보장된다.

숫자를 임시로 저장할 공간이 추가로 필요하기 때문에 공간복잡도는 O(N)이다.

1. 주어진 리스트를 두개로 나눈다.

2. 나눈 리스트 2개를 정렬한다.

3. 정렬된 두 리스트를 합친다.

#include <iostream>

using namespace std;

int n = 10;
int arr[1000001] = { 15, 25, 22, 357, 16, 23, -53, 12, 46, 3 };
int tmp[1000001]; // merge 함수에서 리스트 2개를 합친 결과를 임시로 저장하고 있을 변수

// mid = (st+en)/2라고 할 때 arr[st:mid], arr[mid:en]은 이미 정렬이 되어있는 상태일 때 arr[st:mid]와 arr[mid:en]을 합친다.
void merge(int st, int en) {
	int mid = (st + en) / 2;
	int lidx = st;
	int ridx = mid;

	for (int i = st; i < en; ++i)
	{
		if (ridx == en) tmp[i] = arr[lidx++];
		else if (lidx == mid) tmp[i] = arr[ridx++];
		else if (arr[lidx] <= arr[ridx]) tmp[i] = arr[lidx++]; // stable sort
		else tmp[i] = arr[ridx++];
	}
	for (int i = st; i < en; ++i)
		arr[i] = tmp[i];
}

// arr[st:en]을 정렬하고 싶다.
void merge_sort(int st, int en) {
	if (en == st + 1) return; // 길이 1인 경우
	int mid = (st + en) / 2;
	merge_sort(st, mid); // arr[st:mid]을 정렬한다.
	merge_sort(mid, en); // arr[mid:en]을 정렬한다.
	merge(st, en); // arr[st:mid]와 arr[mid:en]을 합친다.
}

int main()
{
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

	merge_sort(0, n);
	for (int i = 0; i < n; i++) cout << arr[i] << ' ';  // -53 3 12 15 16 22 23 25 46 357

	return 0;
}

하나의 배열을 두개로 쪼개서 각 배열의 크기가 1이 될때까지 재귀를 호출한다.

실제로 배열 2개를 사용하는것은 아니고 인덱스를 2개를 사용함으로써 쪼갠것과 마찬가지의 작업을 한다.

퀵 정렬 (Quick Sort)

평균적으로 O(NlogN)의 속도를 내지만 최악의 경우 O(N²)이다.

pivot을 기준으로 바로 값의 교환이 이루어지기 때문에 공간 복잡도는 O(1)이다.

평균적인 속도가 나올때는 병합 정렬보다는 빠르다. 하지만 라이브러리 사용이 불가능한 코딩 테스트를 치룰때는 언제나 최악의 상황을 상정해야 하므로 퀵 정렬보다는 병합 정렬 또는 힙 정렬을 이용해야 한다.

함수 호출시 인자에 n-1을 주는경우

#include <iostream>
#include <algorithm>

using namespace std;

int n = 10;
int arr[1000001] = {15, 25, 22, 357, 16, 23, -53, 12, 46, 3};

void quick_sort(int st, int en)
{
	if (st >= en) return;

	int pivot = st;
	int left = st + 1;
	int right = en;

	while (left <= right)
	{
		while (left <= en && arr[left] <= arr[pivot]) left++;
		while (right > st && arr[right] >= arr[pivot]) right--;

		if (left > right) swap(arr[pivot], arr[right]);
		else swap(arr[left], arr[right]);
	}
	quick_sort(st, right - 1);
	quick_sort(right + 1, en);
}

int main()
{
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

	quick_sort(0, n-1);
	for (int i = 0; i < n; i++) cout << arr[i] << ' '; // -53 3 12 15 16 22 23 25 46 357

	return 0;
}

함수 내에서 en을 1 빼는경우

#include <iostream>
#include <algorithm>

using namespace std;

int n = 10;
int arr[1000001] = {15, 25, 22, 357, 16, 23, -53, 12, 46, 3};

void quick_sort(int st, int en)
{
	if (st >= en - 1) return;

	int pivot = st;
	int left = st + 1;
	int right = en - 1;

	while (left <= right)
	{
		while (left <= en - 1 && arr[left] <= arr[pivot]) left++;
		while (right > st && arr[right] >= arr[pivot]) right--;

		if (left > right) swap(arr[pivot], arr[right]);
		else swap(arr[left], arr[right]);
	}
	quick_sort(st, right - 1);
	quick_sort(right + 1, en);
}

int main()
{
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

	quick_sort(0, n);
	for (int i = 0; i < n; i++) cout << arr[i] << ' '; // -53 3 12 15 16 22 23 25 46 357

	return 0;
}

번외 : Stable Sort

우선순위가 같은 원소들끼리는 원래의 순서를 따라가도록 하는 정렬

예를들어 38, 21, 21, 21이 있다면 수가 같을 때 리스트 앞쪽의 수를 먼저 골라서 정렬한다.

병합 정렬은 Stable Sort이고 퀵 정렬은 Unstable Sort이다.

저작자표시

'알고리즘 > 바킹독의 실전 알고리즘' 카테고리의 다른 글

[0x10] 다이나믹 프로그래밍 (0)	2022.08.03
[0x0F] 정렬 II (0)	2022.08.02
[0x0D] 시뮬레이션 (0)	2022.08.01
[0x0C] 백트래킹 (0)	2022.07.31
[0x0B] 재귀 (0)	2022.07.30

[0x0D] 시뮬레이션

2022. 8. 1. 21:32

BFS, DFS 등의 자료구조처럼 정형화 되어있지 않아서 어렵다.

연습 문제

15683: 감시

#include <iostream>
#include <vector>

using namespace std;

int n, m;
int office[10][10];
vector<pair<int, int>> cameras;
int answer = 9999;

const int dx[4] = { 1, 0, -1, 0 };
const int dy[4] = { 0, -1, 0, 1 };

void upd(int k, int dir, vector<pair<int, int>>& v)
{
	dir %= 4;
	int nx, ny;
	nx = cameras[k].first + dx[dir];
	ny = cameras[k].second + dy[dir];

	while (nx >= 0 && nx < n && ny >= 0 && ny < m)
	{
		if (office[nx][ny] == 6)
		{
			return;
		}
		if (office[nx][ny] == 0)
		{
			office[nx][ny] = -1;
			v.push_back({ nx, ny });
		}

		nx += dx[dir];
		ny += dy[dir];
	}
}

void init_table(vector<pair<int, int>>& v)
{
	while (!v.empty())
	{
		office[v.back().first][v.back().second] = 0;
		v.pop_back();
	}
}

void backtracking(int k)
{
	if (k == cameras.size())
	{
		int s = 0;
		for (int x = 0; x < n; ++x)
		{
			for (int y = 0; y < m; ++y)
			{
				if (!office[x][y])
				{
					s++;
				}
			}
		}
		answer = (answer < s) ? answer : s;
		return;
	}

	for (int i = 0; i < 4; ++i)
	{
		int cx, cy;
		cx = cameras[k].first;
		cy = cameras[k].second;

		vector<pair<int, int>> v;

		// 현재 카메라 좌표에서 카메라 타입에 따라 감시구역 설정
		if (office[cx][cy] == 1)
		{
			upd(k, i, v);
		}
		else if (office[cx][cy] == 2)
		{
			upd(k, i, v);
			upd(k, i + 2, v);
		}
		else if (office[cx][cy] == 3)
		{
			upd(k, i, v);
			upd(k, i + 1, v);
		}
		else if (office[cx][cy] == 4)
		{
			upd(k, i, v);
			upd(k, i + 1, v);
			upd(k, i + 2, v);
		}
		else if (office[cx][cy] == 5)
		{
			upd(k, i, v);
			upd(k, i + 1, v);
			upd(k, i + 2, v);
			upd(k, i + 3, v);
		}

		backtracking(k + 1);
		init_table(v);
	}
}

int main()
{
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

	// 세로크기n 가로크기m
	cin >> n >> m;

	for (int x = 0; x < n; ++x)
	{
		for (int y = 0; y < m; ++y)
		{
			cin >> office[x][y];
			if (office[x][y] >= 1 && office[x][y] <= 5)
			{
				cameras.push_back({ x, y });
			}
		}
	}

	backtracking(0);

	cout << answer;

	return 0;
}

upd 함수와 4진법의 접근이 핵심이다.

자잘한 부분들은 어느정도 떠올렸는데 udp를 어떻게 구현할지 도무지 감이 안잡혀서 결국 해답을 보고 참고해서 백트래킹으로 풀어냈다.

해답 코드는 백트래킹 대신 4ⁿ의 루프를 가지는 for문을 이용한다.

18808: 스티커 붙이기

#include <iostream>
#include <algorithm>

using namespace std;

int notebook[50][50];
int sticker[12][12];

int n, m, k;
int r, c;
int answer;

bool is_pastable(int& x, int& y)
{
	for (int i = 0; i < r; ++i)
	{
		for (int j = 0; j < c; ++j)
		{
			if (x + i >= n || y + j >= m)
			{
				return false;
			}
			if (notebook[x + i][y + j] + sticker[i][j] == 2)
			{
				return false;
			}
		}
	}
	return true;
}

void paste(int& x, int& y)
{
	for (int i = 0; i < r; ++i)
	{
		for (int j = 0; j < c; ++j)
		{
			if (sticker[i][j])
			{
				notebook[x + i][y + j] = 1;
			}
		}
	}
}

void rotate()
{
	int tmp[12][12] = {};

	for (int i = 0; i < r; ++i)
	{
		for (int j = 0; j < c; ++j)
		{
			tmp[i][j] = sticker[i][j];
		}
	}

	for (int i = 0; i < c; ++i)
	{
		for (int j = 0; j < r; ++j)
		{
			sticker[i][j] = tmp[r-j-1][i];
		}
	}
	swap(r, c);
}

void func(int& s)
{
	for (int i = 0; i < 4; ++i)
	{
		// 현재 노트에 붙일 수 있는가 판별
		for (int x = 0; x < n; ++x)
		{
			for (int y = 0; y < m; ++y)
			{
				if (is_pastable(x, y))
				{
					paste(x, y);
					answer += s;
					return;
				}
			}
		}
		rotate();
	}
}

int main()
{
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

	// n가로 m세로 스티커개수k

	cin >> n >> m >> k;

	for (int i = 0; i < k; ++i)
	{	// r행 c열

		cin >> r >> c;

		int s = 0;

		for (int x = 0; x < r; ++x)
		{
			for (int y = 0; y < c; ++y)
			{
				cin >> sticker[x][y];
				if (sticker[x][y])
				{
					s++;
				}
			}
		}
		func(s);
	}

	cout << answer;

	return 0;
}

이 문제도 사실상 해답을 보고 푼거나 마찬가지

스티커의 회전이 핵심이다.

처음에 문제 이해를 잘못해서 모든 스티커에 대한 완전 탐색을 구현하려고 해서 까마득 했음

그게 아니라 그냥 순서대로 붙이는거라서 어느정도의 풀이는 떠올림

12100: 2048 (Easy)

#include <iostream>
#include <vector>

using namespace std;

int n, answer;

int mx(vector<vector<int>>& v)
{
	int m = 0;

	for (int i = 0; i < n; ++i)
	{
		for (int j = 0; j < n; ++j)
		{
			m = (v[i][j] > m) ? v[i][j] : m;
		}
	}
	return m;
}

vector<vector<int>> push_numbers(vector<vector<int>> v, int& dir)
{

	// 우측으로
	if (dir == 0)
	{
		for (int i = 0; i < n; ++i)
		{
			int t[101] = {};
			int idx = 0;

			for (int j = n - 1 ; j >= 0; --j)
			{
				if (v[i][j] == 0)
				{
					continue;
				}
				if (t[idx] == 0)
				{
					t[idx] = v[i][j];
				}
				else if (t[idx] == v[i][j])
				{
					t[idx++] *= 2;
				}
				else
				{
					t[++idx] = v[i][j];
				}
			}
			for (int j = 0; j < n; ++j)
			{
				v[i][j] = t[n-j-1];
			}
		}
	}

	// 위로
	else if (dir == 1)
	{
		for (int i = 0; i < n; ++i)
		{
			int t[101] = {};
			int idx = 0;

			for (int j = 0; j < n; ++j)
			{
				if (v[j][i] == 0)
				{
					continue;
				}
				if (t[idx] == 0)
				{
					t[idx] = v[j][i];
				}
				else if (t[idx] == v[j][i])
				{
					t[idx++] *= 2;
				}
				else
				{
					t[++idx] = v[j][i];
				}
			}
			for (int j = 0; j < n; ++j)
			{
				v[j][i] = t[j];
			}
		}
	}

	// 좌측으로
	else if (dir == 2)
	{
		for (int i = 0; i < n; ++i)
		{
			int t[101] = {};
			int idx = 0;

			for (int j = 0; j < n; ++j)
			{
				if (v[i][j] == 0)
				{
					continue;
				}
				if (t[idx] == 0)
				{
					t[idx] = v[i][j];
				}
				else if (t[idx] == v[i][j])
				{
					t[idx++] *= 2;
				}
				else
				{
					t[++idx] = v[i][j];
				}
			}
			for (int j = 0; j < n; ++j)
			{
				v[i][j] = t[j];
			}
		}
	}

	// 아래로
	else
	{
		for (int i = 0; i < n; ++i)
		{
			int t[101] = {};
			int idx = 0;

			for (int j = n-1; j >= 0; --j)
			{
				if (v[j][i] == 0)
				{
					continue;
				}
				if (t[idx] == 0)
				{
					t[idx] = v[j][i];
				}
				else if (t[idx] == v[j][i])
				{
					t[idx++] *= 2;
				}
				else
				{
					t[++idx] = v[j][i];
				}
			}
			for (int j = 0; j < n; ++j)
			{
				v[j][i] = t[n - j - 1];
			}
		}
	}
	return v;
}

void backtracking(int k, vector<vector<int>> v)
{
	if (k == 5)
	{
		int m = mx(v);
		answer = answer > m ? answer : m;
		return;
	}

	for (int i = 0; i < 4; ++i)
	{
		backtracking(k + 1, push_numbers(v, i));
	}
}

int main()
{
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

	vector<vector<int>> v2;

	cin >> n;

	for (int i = 0; i < n; ++i)
	{
		vector<int> v1;
		for (int i = 0; i < n; ++i)
		{
			int t;
			cin >> t;
			v1.push_back(t);
		}
		v2.push_back(v1);
	}

	backtracking(0, v2);

	cout << answer;

	return 0;
}

어떻게든 2차원 벡터를 이용해서 풀어보고 싶어가지고 개고생을 했다.

핵심은 한쪽으로 숫자를 밀어넣는 부분이다. 전체적으로 보면 사실상 브루트포스이다.

구현문제들이 진짜 막막하다.

dfs, bfs, 백트래킹, 브루트포스가 섞여서 나오는데 돌아버릴것같음

저작자표시

'알고리즘 > 바킹독의 실전 알고리즘' 카테고리의 다른 글

[0x0F] 정렬 II (0)	2022.08.02
[0x0E] 정렬 I (0)	2022.08.02
[0x0C] 백트래킹 (0)	2022.07.31
[0x0B] 재귀 (0)	2022.07.30
[0x0A] DFS (0)	2022.07.30

[0x0C] 백트래킹

2022. 7. 31. 03:45

현재 상태에서 가능한 모든 후보군을 따라 들어가며 탐색하는 알고리즘

상태공간트리라는 개념을 이용한다.

재귀 호출 전후로 선택지를 true와 false로 변경해 주는걸 잊으면 안된다.

가지치기가 빈번하게 일어날수록 시간 복잡도를 계산하기 매우 어렵다.

재귀로 구현되는 경우 n값이 크지 않아야 한다.

원소가 n개인 집합에서 부분집합의 개수는 공집합을 포함하여 2ⁿ개이다.

n값이크지 않은 경우에 완전탐색, 구현할때 자주 써먹을 수 있을 것 같다.

백트래킹의 전형적인 코드

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

int n,m;
int arr[10];
bool isused[10];

void func(int k){ // 현재 k개까지 수를 택했음.
  if(k == m){ // m개를 모두 택했으면
    for(int i = 0; i < m; i++)
      cout << arr[i] << ' '; // arr에 기록해둔 수를 출력
    cout << '\n';
    return;
  }

  for(int i = 1; i <= n; i++){ // 1부터 n까지의 수에 대해
    if(!isused[i]){ // 아직 i가 사용되지 않았으면
      arr[k] = i; // k번째 수를 i로 정함
      isused[i] = 1; // i를 사용되었다고 표시
      func(k+1); // 다음 수를 정하러 한 단계 더 들어감
      isused[i] = 0; // k번째 수를 i로 정한 모든 경우에 대해 다 확인했으니 i를 이제 사용되지않았다고 명시함.
    }
  }
}

int main(void){
  ios::sync_with_stdio(0);
  cin.tie(0);
  cin >> n >> m;
  func(0);
}

출처 : 바킹독

연습 문제

15649: N과 M (1)

#include <iostream>

using namespace std;

int nums[10];
bool isUsed[10];

int n, m;

void backtracking(int k)
{
	if (k == m)
	{
		for (int i = 0; i < m; ++i)
		{
			cout << nums[i] << ' ';
		}
		cout << '\n';
		return;
	}

	for (int i = 1; i <= n; ++i)
	{
		if (!isUsed[i])
		{
			nums[k] = i;
			isUsed[i] = true;
			backtracking(k + 1);
			isUsed[i] = false;
		}
	}
}

int main()
{
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

	cin >> n >> m;

	backtracking(0);

	return 0;
}

백트래킹 입문 문제

코드를 잘 뜯어먹어보면 어느정도 이해가 간다.

9663: N-Queen

#include <iostream>

using namespace std;

int answer;
bool isExRow[16];
bool isExDiagonal1[32];
bool isExDiagonal2[32];

int n;

void backtracking(int k)
{
	if (k == n)
	{
		answer++;
		return;
	}

	for (int i = 0; i < n; ++i)
	{
		if (isExRow[i] || isExDiagonal1[i + k] || isExDiagonal2[i - k + n - 1])
		{
			continue;
		}
		isExRow[i] = true;
		isExDiagonal1[i + k] = true;
		isExDiagonal2[i - k + n - 1] = true;
		
		backtracking(k + 1);

		isExRow[i] = false;
		isExDiagonal1[i + k] = false;
		isExDiagonal2[i - k + n - 1] = false;
	}
}

int main()
{
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

	cin >> n;

	backtracking(0);

	cout << answer;

	return 0;
}

퀸의 공격 경로를 확인하는게 가장 어려운 부분. 조금 변칙적이지만 전형적인 백트래킹 문제.

행에 놓는게 기본이니 행의 검사는 안해도 됨.

좌하단에서 우상단의 경로는 x+y, 좌상단에서 우하단의 경로는 x-y(인데 index가 음수로 가지 않기위해 n-1을 더해준다)

1182: 부분수열의 합

#include <iostream>

using namespace std;

int answer = 0;
int nums[20];

int n, s;

void backtracking(int k, int tot)
{
	if (k == n)
	{
		if (tot == s) // 상태공간트리 끝에 도달
		{
			answer++;
		}
		return;
	}
	backtracking(k + 1, tot); // 합계에서 수를 선택하지 않음
	backtracking(k + 1, tot + nums[k]); // 합계에서 수를 선택해서 합산
}

int main()
{
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

	cin >> n >> s;
	for (int i = 0; i < n; ++i)
	{
		cin >> nums[i];
	}

	backtracking(0, 0);

	if (s == 0)
	{
		answer--; // s가 0일때 공집합 제거
	}

	cout << answer;

	return 0;
}

더하거나, 더하지 않거나 두개의 경우가 있다는 것을 알아야 한다.

중복이 허용되지 않는 순열

기본 문제

15650: N과 M (2)

#include <iostream>

using namespace std;

int n, m;
bool isused[20];
int nums[20];

void backtracking(int k)
{
	if (k == m)
	{
		for (int i = 0; i < k; ++i)
		{
			cout << nums[i] << ' ';
		}
		cout << '\n';
		return;
	}

	// 같은수는 고르면 안돼서 1을 더함
	int st = (k != 0) ? nums[k - 1] + 1 : 1;

	for (int i = st; i <= n; ++i)
	{
		if (!isused[i])
		{
			isused[i] = true;
			nums[k] = i;
			backtracking(k + 1);
			isused[i] = false;
		}
	}
}

int main()
{
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

	cin >> n >> m;

	backtracking(0);

	return 0;
}

st와 같은 개념을 떠올리긴 했는데 구현이 떠오르지 않아서 풀이를 봤음

중복이 허용되지 않는 순열, 비내림차순

15651: N과 M (3)

#include <iostream>

using namespace std;

int n, m;
int nums[20];

void backtracking(int k)
{
	if (k == m)
	{
		for (int i = 0; i < k; ++i)
		{
			cout << nums[i] << ' ';
		}
		cout << '\n';
		return;
	}

	for (int i = 1; i <= n; ++i)
	{
		nums[k] = i;
		backtracking(k + 1);
	}
}

int main()
{
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

	cin >> n >> m;

	backtracking(0);

	return 0;
}

중복이 허용되는 순열의 경우 isused가 필요가 없다

15652: N과 M (4)

#include <iostream>

using namespace std;

int n, m;
int nums[20];

void backtracking(int k)
{
	if (k == m)
	{
		for (int i = 0; i < k; ++i)
		{
			cout << nums[i] << ' ';
		}
		cout << '\n';
		return;
	}

	int st = (k != 0) ? nums[k - 1] : 1;

	for (int i = st; i <= n; ++i)
	{
		nums[k] = i;
		backtracking(k + 1);
	}
}

int main()
{
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

	cin >> n >> m;

	backtracking(0);

	return 0;
}

중복이 허용되는 순열, 비내림차순

15654: N과 M (5)

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int n, m;
int nums[10];
vector<int> arr;
bool isused[10001];

void backtracking(int k)
{
	if (k == m)
	{
		for (int i = 0; i < k; ++i)
		{
			cout << nums[i] << ' ';
		}
		cout << '\n';
		return;
	}

	for (int i = 0; i < n; ++i)
	{
		if (!isused[arr[i]])
		{
			nums[k] = arr[i];
			isused[arr[i]] = true;
			backtracking(k + 1);
			isused[arr[i]] = false;
		}
	}
}

int main()
{
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

	cin >> n >> m;

	for (int i = 0; i < n; ++i)
	{
		int t;
		cin >> t;
		arr.push_back(t);
	}

	sort(arr.begin(), arr.end());

	backtracking(0);

	return 0;
}

1~8이 아닌 임의의 수에 대한 순열. 기본적인 백트래킹과 똑같은 방식. vector와 정렬을 이용해 해결

** isused를 1만까지 늘릴필요 없이 인덱스를 보관하면 됨. vector도 안써도 됨

중복을 허용하지 않는 순열, 임의의 수

15655: N과 M (6)

#include <iostream>
#include <algorithm>

using namespace std;

int n, m;
int idx[10];
int nums[10];
bool isused[10];

void backtracking(int k)
{
	if (k == m)
	{
		for (int i = 0; i < k; ++i)
		{
			cout << nums[idx[i]] << ' ';
		}
		cout << '\n';
		return;
	}

	int st = (k != 0) ? idx[k - 1] + 1 : 0;

	for (int i = st; i < n; ++i)
	{
		if (!isused[i])
		{
			idx[k] = i;
			isused[i] = true;
			backtracking(k + 1);
			isused[i] = false;
		}
	}
}

int main()
{
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

	cin >> n >> m;

	for (int i = 0; i < n; ++i)
	{
		cin >> nums[i];
	}

	sort(nums, nums + n);

	backtracking(0);

	return 0;
}

임의의 수를 이용하는 경우 직접적인 수가 아닌 해당 수가 저장된 배열의 인덱스를 보관해서 해야 한다.

중복을 허용하지 않는 순열, 임의의 수, 비내림차순

15656: N과 M (7)

#include <iostream>
#include <algorithm>

using namespace std;

int n, m;
int idx[10];
int nums[10];

void backtracking(int k)
{
	if (k == m)
	{
		for (int i = 0; i < k; ++i)
		{
			cout << nums[idx[i]] << ' ';
		}
		cout << '\n';
		return;
	}

	for (int i = 0; i < n; ++i)
	{
		idx[k] = i;
		backtracking(k + 1);
	}
}

int main()
{
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

	cin >> n >> m;

	for (int i = 0; i < n; ++i)
	{
		cin >> nums[i];
	}

	sort(nums, nums + n);

	backtracking(0);

	return 0;
}

중복이 허용되는 순열, 임의의 수

15657: N과 M (8)

#include <iostream>
#include <algorithm>

using namespace std;

int n, m;
int idx[10];
int nums[10];

void backtracking(int k)
{
	if (k == m)
	{
		for (int i = 0; i < k; ++i)
		{
			cout << nums[idx[i]] << ' ';
		}
		cout << '\n';
		return;
	}

	int st = (k != 0) ? idx[k - 1] : 0;

	for (int i = st; i < n; ++i)
	{
		idx[k] = i;
		backtracking(k + 1);
	}
}

int main()
{
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

	cin >> n >> m;

	for (int i = 0; i < n; ++i)
	{
		cin >> nums[i];
	}

	sort(nums, nums + n);

	backtracking(0);

	return 0;
}

중복을 허용하는 순열, 임의의 수, 비내림차순

15663: N과 M (9)

#include <iostream>
#include <algorithm>

using namespace std;

int n, m;
int arr[10];
int nums[10];
bool isused[10];

void backtracking(int k)
{
	if (k == m)
	{
		for (int i = 0; i < k; ++i)
		{
			cout << arr[i] << ' ';
		}
		cout << '\n';
		return;
	}

	int tmp = 0;
	for (int i = 0; i < n; ++i)
	{
		if (!isused[i] && tmp != nums[i])
		{
			arr[k] = nums[i];
			tmp = arr[k];
			isused[i] = true;
			backtracking(k + 1);
			isused[i] = false;
		}
	}
}

int main()
{
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

	cin >> n >> m;

	for (int i = 0; i < n; ++i)
	{
		cin >> nums[i];
	}

	sort(nums, nums + n);

	backtracking(0);

	return 0;
}

이번에는 isused에 배열의 인덱스 사용여부를 저장하지만 arr에는 인덱스가 아닌 숫자를 직접 저장한다.

tmp에 최근 숫자를 저장함으로써 79 79와 같은 같은 수열이 두번 나오지 않게 방지함.

이 문제가 가장 이해하기 어려운거같음.

중복이 허용되지 않는 순열, 중복된 숫자가 포함된 임의의 수

15664: N과 M (10)

#include <iostream>
#include <algorithm>

using namespace std;

int n, m;
int arr[10];
int idx[10];
int nums[10];
bool isused[10];

void backtracking(int k)
{
	if (k == m)
	{
		for (int i = 0; i < k; ++i)
		{
			cout << arr[i] << ' ';
		}
		cout << '\n';
		return;
	}

	int st = (k != 0) ? idx[k-1] + 1 : 0;
	int tmp = 0;

	for (int i = st; i < n; ++i)
	{
		if (!isused[i] && tmp != nums[i])
		{
			idx[k] = i;
			arr[k] = nums[i];
			tmp = arr[k];
			isused[i] = true;
			backtracking(k + 1);
			isused[i] = false;
		}
	}
}

int main()
{
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

	cin >> n >> m;

	for (int i = 0; i < n; ++i)
	{
		cin >> nums[i];
	}

	sort(nums, nums + n);

	backtracking(0);

	return 0;
}

idx, arr, isused 모두 사용한다.

중복을 허용하지 않는 순열, 중복된 숫자가 포함된 임의의 수, 비내림차순

15665: M과 N (11)

#include <iostream>
#include <algorithm>

using namespace std;

int n, m;
int arr[10];
int idx[10];
int nums[10];

void backtracking(int k)
{
	if (k == m)
	{
		for (int i = 0; i < k; ++i)
		{
			cout << arr[i] << ' ';
		}
		cout << '\n';
		return;
	}

	int tmp = 0;

	for (int i = 0; i < n; ++i)
	{
		if (tmp != nums[i])
		{
			idx[k] = i;
			arr[k] = nums[i];
			tmp = arr[k];
			backtracking(k + 1);
		}
	}
}

int main()
{
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

	cin >> n >> m;

	for (int i = 0; i < n; ++i)
	{
		cin >> nums[i];
	}

	sort(nums, nums + n);

	backtracking(0);

	return 0;
}

중복이 허용되는 조합. isused 미사용

15666: N과 M (12)

#include <iostream>
#include <algorithm>

using namespace std;

int n, m;
int arr[10];
int idx[10];
int nums[10];

void backtracking(int k)
{
	if (k == m)
	{
		for (int i = 0; i < k; ++i)
		{
			cout << arr[i] << ' ';
		}
		cout << '\n';
		return;
	}

	int st = (k != 0) ? idx[k - 1] : 0;
	int tmp = 0;

	for (int i = st; i < n; ++i)
	{
		if (tmp != nums[i])
		{
			idx[k] = i;
			arr[k] = nums[i];
			tmp = arr[k];
			backtracking(k + 1);
		}
	}
}

int main()
{
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

	cin >> n >> m;

	for (int i = 0; i < n; ++i)
	{
		cin >> nums[i];
	}

	sort(nums, nums + n);

	backtracking(0);

	return 0;
}

N과 M 정리

- 1부터 N까지 오름차순인 경우의 백트래킹

중복이 허용되지 않는 순열 : isused와 고른 숫자를 보관할 arr 두개만 있으면 된다

중복이 허용되지 않는 순열 및 오름차순 : 앞서 저장된 숫자보다 큰곳부터 시작하는 st가 추가로 필요하다. 0인경우 1, 0이 아닌경우 바로 앞에 저장된 숫자에 +1

중복이 허용되는 순열 : isused와 st를 사용하지 않는다

중복이 허용되는 순열 및 오름차순 : isused를 사용하지 않고 st만 추가로 필요하다

- 임의의 수에 대한 경우의 백트래킹

* 입력을 다 받고 오름차순으로 정렬해야한다 *

중복이 허용되지 않는 순열 : 고른 숫자의 인덱스를 보관할 idxarr가 추가로 필요하다. isused는 사용중인 인덱스를 true/false 하도록 한다.

중복이 허용되지 않는 순열 및 오름차순 : st를 사용하며, 숫자가 아닌 인덱스로 판별한다. 0인경우 0, 0이 아닌경우 바로 앞에 저장된 인덱스에 +1

중복이 허용되는 순열 : isused와 st를 사용하지 않는다

중복이 허용되는 순열 및 오름차순 : isused를 사용하지 않고 st만 추가로 필요하다

- 중복된 숫자가 포함된 임의의 수에 대한 경우의 백트래킹

* 입력을 다 받고 오름차순으로 정렬해야한다 *

중복이 허용되지 않는 순열 : 고른 숫자를 보관할 arr가 필요하다. idx는 사용하지 않는다. 현재 선택된 값을 임시로 보관하여 비교할 tmp가 추가로 필요하다. isused 판별할 때 tmp != nums[i]도 추가로 판별해야 한다

중복이 허용되지 않는 순열 및 오름차순 : 값 저장은 여전히 하며, idx도 추가로 필요하다. idx를 토대로 st도 사용한다

중복이 허용되는 순열 : isused와 st를 사용하지 않는다

중복이 허용되는 순열 및 오름차순 : isused를 사용하지 않고 st만 추가로 필요하다

6603: 로또

// N과 M을 통해 익힌 코드로 풀이한 코드

#include <iostream>
#include <algorithm>

using namespace std;

int arr[15];
int idx[15];
int nums[15];
bool isused[15];

void backtracking(int k, int& n)
{
	if (k == 6)
	{
		for (int i = 0; i < 6; ++i)
		{
			cout << arr[i] << ' ';
		}
		cout << '\n';
		return;
	}

	int st = (k != 0) ? idx[k - 1] : 0;

	for (int i = st; i < n; ++i)
	{
		if (!isused[i])
		{
			idx[k] = i;
			arr[k] = nums[i];
			isused[i] = true;
			backtracking(k + 1, n);
			isused[i] = false;
		}
	}
}

int main()
{
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

	while (true)
	{
		int n;
		cin >> n;
		
		if (!n)
		{
			return 0;
		}

		for (int i = 0; i < n; ++i)
		{
			cin >> nums[i];
		}

		sort(nums, nums + n);

		backtracking(0, n);

		cout << '\n';
	}

	return 0;
}

// next_permutation을 이용해 풀이한 코드

#include <iostream>
#include <algorithm>

using namespace std;

int nums[15];
int arr[15];

int main()
{
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

	while (true)
	{
		int n;
		cin >> n;
		
		if (!n)
		{
			return 0;
		}

		for (int i = 0; i < n; ++i)
		{
			cin >> nums[i];
			if (i >= 6)
			{
				arr[i] = 1;
			}
		}

		sort(nums, nums + n);

		do {
			for (int i = 0; i < n; ++i)
			{
				if (!arr[i])
				{
					cout << arr[i] + nums[i] << ' ';
				}
			}
			cout << '\n';
		} while (next_permutation(arr, arr + n));

		cout << '\n';
	}

	return 0;
}

저작자표시

'알고리즘 > 바킹독의 실전 알고리즘' 카테고리의 다른 글

[0x0E] 정렬 I (0)	2022.08.02
[0x0D] 시뮬레이션 (0)	2022.08.01
[0x0B] 재귀 (0)	2022.07.30
[0x0A] DFS (0)	2022.07.30
[0x09] BFS (0)	2022.07.28

[0x0B] 재귀

2022. 7. 30. 02:21

모든 입력은 base condition으로 수렴해야 한다.

인자로 어떤 것을 받고 어디까지 계산한 후 자기 자신에게 넘겨줄지 명확하게 정해야 한다.

모든 재귀 함수는 반복문만으로 동일한 동작을 할 수 있다.

반복문으로 구현했을때에 비해 코드가 간결해지지만 메모리와 시간에서 손해를 본다.

재귀함수가 자기 자신을 부를 때 스택 영역에 계속 누적이 된다.

재귀함수를 절차적으로 계속 따라들어가며 생각하면 답이없다. 절차지향적인 사고를 탈피해야 한다.

재귀함수 예제문제들을 풀어보니 문제에 귀납적인 내용이 적혀있다. 이걸 토대로 구현하면 될 것 같다.

작거나 큰 문제를 확장시키거나 쪼개간다는 점에서 DP와 개념은 비슷한데 memoization이 사용되지 않는다는 점이 차이인 것 같다.

연습 문제

1629: 곱셈

#include <iostream>

using namespace std;
using ll = long long;

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

	ll val = powmod(a, b / 2, c);
	val = val * val % c;

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

int main()
{
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

	ll a, b, c;

	cin >> a >> b >> c;

	cout << powmod(a, b, c);
	
	return 0;
}

a^b = a^b/2 * a^b/2

(a*b)%c = (a%c)*(b%c)%c

위 두개를 알아야 한다. 그리고 b가 홀수인 경우 a를 한번 더 곱해줘야 한다는 걸 주의해야 한다.

큰 문제를 작은 문제로 쪼개서 해결한다는 점에서 뭔가 DP랑 유사한 것 같다.

11729: 하노이 탑 이동 순서

#include <iostream>

using namespace std;

void tower_of_hanoi(int n, int start, int dest)
{
	if (n == 1)
	{
		cout << start << " " << dest << '\n';
		return;
	}

	tower_of_hanoi(n - 1, start, 6 - start - dest);
	cout << start << " " << dest << '\n';
	tower_of_hanoi(n - 1, 6 - start - dest, dest);
	return;
}

int main()
{
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

	int n;

	cin >> n;

	cout << (1 << n) - 1 << '\n';
	tower_of_hanoi(n, 1, 3);
	
	return 0;
}

n이 성립되면 n-1도 성립되는것을 이해해야 한다.

n-1을 2번, n을 3번, n-1을 3번으로 옮긴다는 것을 알면 금방 풀 수 있는 문제이다.

즉, 귀납적 사고법이 반드시 필요한 문제.

1074: Z

#include <iostream>

using namespace std;

int z_search(int n, int r, int c)
{
	if (n == 0)	return 0;

	int half = 1 << (n - 1);

	if (r < half && c < half) return z_search(n - 1, r, c);
	else if (r < half && c >= half) return half * half + z_search(n - 1, r, c - half);
	else if (r >= half && c < half) return 2 * half * half + z_search(n - 1, r - half, c);
	else return 3 * half * half + z_search(n - 1, r - half, c - half);
}

int main()
{
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	// r행 c열
	int n, r, c;

	cin >> n >> r >> c;

	cout << z_search(n, r, c);
	
	return 0;
}

재귀의 n값마다 행과 열의 사분면을 파악해서 재귀 호출이 달라져야한다.

예를들어 3사분면에 있다면 1-2분면의 값을 모두 더하고 나머지값은 더 작은 사분면으로 판단시키기 위해 값을 조정하여 재귀를 호출한다.

n=1일때의 사분면 판정을 생각하면 확장이 쉽다.

기본 문제

1780: 종이의 개수

#include <iostream>

using namespace std;

int paper[2200][2200];
int cnt[3];

bool same_paper_judge(int x, int y, int n)
{
	int t = paper[x][y];

	for (int i = 0; i < n; ++i)
	{
		for (int j = 0; j < n; ++j)
		{
			if (t != paper[x + i][y + j])
			{
				return false;
			}
		}
	}

	return true;
}

void recursion(int x, int y, int n)
{
	if (same_paper_judge(x, y, n))
	{
		cnt[paper[x][y] + 1]++;
		return;
	}

	int div = n / 3;

	for (int i = 0; i < 3; ++i)
	{
		for (int j = 0; j < 3; ++j)
		{
			recursion(x + div * i, y + div * j, div);
		}
	}
}
int main()
{
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

	int n;
	
	cin >> n;

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

	recursion(0, 0, n);

	for (int i = 0; i < 3; ++i)
	{
		cout << cnt[i] << '\n';
	}
	
	return 0;
}

9개로 나누어 분할정복 하는것이 포인트

1992: 쿼드 트리

#include <iostream>
#include <string>
#include <vector>

using namespace std;

string quad[65];
vector<char> answer;

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

	return true;
}

void quad_tree(int x, int y, int n)
{
	if (same_judge(x, y, n))
	{
		answer.push_back(quad[x][y]);
		return;
	}
	int div = n / 2;

	answer.push_back('(');

	for (int i = 0; i < 2; ++i)
	{
		for (int j = 0; j < 2; ++j)
		{
			quad_tree(x + div * i, y + div * j, div);
		}
	}
	answer.push_back(')');
}
int main()
{
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

	int n;
	
	cin >> n;

	for (int i = 0; i < n; ++i)
	{
		cin >> quad[i];
	}

	quad_tree(0, 0, n);

	for (auto& a : answer)
	{
		cout << a;
	}
	
	return 0;
}

4개로 분할 정복 하면서 중간에 괄호를 끼워넣는게 포인트

2630: 색종이 만들기

#include <iostream>

using namespace std;

int paper[128][128];
int answer[2]; // 흰0 파1

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

	return true;
}

void recursion(int x, int y, int n)
{
	if (same_judge(x, y, n))
	{
		answer[paper[x][y]]++;
		return;
	}
	int div = n / 2;

	for (int i = 0; i < 2; ++i)
	{
		for (int j = 0; j < 2; ++j)
		{
			recursion(x + div * i, y + div * j, div);
		}
	}
}
int main()
{
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

	int n;
	
	cin >> n;

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

	recursion(0, 0, n);

	for (int i = 0; i < 2; ++i)
	{
		cout << answer[i] << '\n';
	}
	
	return 0;
}

저작자표시

'알고리즘 > 바킹독의 실전 알고리즘' 카테고리의 다른 글

[0x0D] 시뮬레이션 (0)	2022.08.01
[0x0C] 백트래킹 (0)	2022.07.31
[0x0A] DFS (0)	2022.07.30
[0x09] BFS (0)	2022.07.28
[0x08] 스택의 활용 (0)	2022.07.25

[0x0A] DFS

2022. 7. 30. 01:55

BFS의 큐가 스택으로 바뀌었다는 점 말고는 구현에서 차이가 없다.

다만 최단 거리를 계산할 땐 DFS를 사용할 수 없다.

그렇기에 다차원 배열에서 BFS 대신 DFS를 굳이 써야할 일은 없다.

그래프와 트리에서 사용하는 개념이다.

저작자표시

'알고리즘 > 바킹독의 실전 알고리즘' 카테고리의 다른 글

[0x0C] 백트래킹 (0)	2022.07.31
[0x0B] 재귀 (0)	2022.07.30
[0x09] BFS (0)	2022.07.28
[0x08] 스택의 활용 (0)	2022.07.25
[0x07] 덱(Deque) (0)	2022.07.25

PREV 이전 1 2 3 4 5 6 NEXT 다음

erikanes's Macchiato