'알고리즘' 카테고리의 글 목록 (4 Page)

알고리즘

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

[0x10] 다이나믹 프로그래밍

2022. 8. 3. 23:41

DP를 푸는 과정

1. 테이블 정의하기

2. 점화식 찾기

3. 초기값 정하기

코딩테스트에 나올 수준의 DP는 일단 점화식만 찾고나면 그 뒤는 초기값을 채워넣은 후에 반복문을 돌면서 배열을 채워넣으면 끝이다.

하지만 그 점화식을 찾는게 가장 어렵다.

주어진 문제가 DP로 풀 수 있는 문제라는 것 자체를 눈치채지 못할 수도 있다.

이 부분은 그저 많이 풀면서 테이블을 잡고 식을 세우는 과정을 반복학습 하는 수 밖에 없다.

연습 문제

1463: 1로 만들기

BFS로 구현할수도 있다. 하지만 DP를 이용하면 더 짧막하게 구현할 수 있다.

1. 테이블 정의하기

D[i] = i를 1로 만들기 위해 필요한 연산 사용 횟수의 최소값

2. 점화식 찾기

예를들어 D[12] 를 찾는다고 하면 총 3가지의 행동을 할 수 있다.

3으로 나누거나 (D[12] = D[4] + 1)
2로 나누거나 (D[12] = D[6] + 1)
1을 빼거나 (D[12] = D[11] + 1)

최소값을 찾는것이기 때문에 D[12] = min(D[4]+1, D[6]+1, D[11]+1)이 성립하게 된다.

즉, D[K] = min(D[K/3]+1, D[K/2]+1, D[K-1]+1) 이다.

3. 초기값 정의하기

D[1] = 0

#include <iostream>
#include <algorithm>

using namespace std;

int arr[1000001];

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

	int n;
	cin >> n;

	for (int i = 2; i <= n; ++i)
	{
		arr[i] = arr[i - 1] + 1;
		if (i % 2 == 0) arr[i] = min(arr[i], arr[i / 2] + 1);
		if (i % 3 == 0) arr[i] = min(arr[i], arr[i / 3] + 1);
	}

	cout << arr[n];

	return 0;
}

9095: 1, 2, 3 더하기

1. 테이블 정의하기

D[i] = i를 1, 2, 3의 합으로 나타내는 방법의 수

2. 점화식 찾기

D[4]인 경우,

1+1+1+1, 3+1, 2+1+1, 1+2+1 / (3을 1, 2, 3의 합으로 나타내는 방법) + 1, D[3]

1+1+2, 2+2 / (2를 1, 2, 3의 합으로 나타내는 방법) + 2, D[2]

1+3 / (1을 1, 2, 3의 합으로 나타내는 방법) + 3, D[1]

D[4] = D[1] + D[2] + D[3]

D[i] = D[i-1] + D[i-2] + D[i-3]

3. 초기값 정의하기

D[1] = 1, D[2] = 2, D[3] = 4

초기값이 3개는 주어져야 한다.

#include <iostream>

using namespace std;

int arr[12];

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

	int tc, n;
	cin >> tc;

	// 미리 테이블을 구해두고 바로 출력해준다
	arr[1] = 1;
	arr[2] = 2;
	arr[3] = 4;

	for (int i = 4; i <= 11; ++i)
		arr[i] = arr[i - 3] + arr[i - 2] + arr[i - 1];

	while (tc--)
	{
		cin >> n;
		cout << arr[n] << '\n';
	}

	return 0;
}

2579: 계단 오르기

1. 테이블 정의하기

(X) D[i] = i번째 계단까지 올라섰을 때 점수 합의 최대값 (연속해서 3개의 계단을 밟을수 없다는 조건때문에 사용할 수 없음)

(O) D[i][j] = 현재까지 j개의 계단을 연속해서 밟고 i번째 계단까지 올라섰을 때 점수 합의 최대값. i번째 계단은 반드시 밟아야 함

2. 점화식 찾기

D[k][1] = max(D[k-2][1], D[k-2][2]) + S[k]
D[k[2] = D[k-1][1] + S[k]

3. 초기값 정의하기

D[1][1] = S[1], D[1][2] = 0

D[2][1] = S[2], D[2][2] = S[1] + S[2]

#include <iostream>

using namespace std;

int arr[301];
int psum[301][3];

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

	int n;
	cin >> n;

	for (int i = 1; i <= n; ++i)
		cin >> arr[i];

	psum[1][1] = arr[1];
	psum[1][2] = 0; // 현재 계단은 한개밖에 없다
	psum[2][1] = arr[2]; // 2층까지 한개를 연속해서 밟았다면 k-1개는 건너뛰었다는 뜻
	psum[2][2] = arr[1] + arr[2]; // 2층까지 두개를 연속해서 밟았다면 k-1, k 둘 다 밟았다는 뜻

	for (int i = 3; i <= n; ++i)
	{
		// i번째 계단이 연속해서 한개째 밟고 있다면 i-1번째 계단은 건너뛰고 i-2번째 계단을 밟았다는 뜻
		psum[i][1] = max(psum[i - 2][1], psum[i - 2][2]) + arr[i];
		// i번째 계단이 연속해서 두개째 밟고있는 계단이라면 i-1번째 계단을 밟았다는 뜻. 연속으로 3개는 밟지 못하므로 i-2 또는 i-1의 연속2개는 안된다
		psum[i][2] = psum[i - 1][1] + arr[i];
	}

	cout << max(psum[n][1], psum[n][2]);

	return 0;
}

1149: RGB거리

1. 테이블 정의하기

D[i][0] = i번째 집까지 칠할 때 비용의 최소값, i번째 집은 빨강

D[i][1] = i번째 집까지 칠할 때 비용의 최소값, i번째 집은 초록

D[i][2] = i번째 집까지 칠할 때 비용의 최소값, i번째 집은 파랑

2. 점화식 찾기

D[i][0] = min(D[i-1][1], D[i-1][2]) + R[i]
D[i][1] = min(D[i-1][0], D[i-1][2]) + G[i]
D[i][2] = min(D[i-1][0], D[i-1][1]) + B[i]

3. 초기값 정의하기

D[1][0] = R[1]

D[1][1] = G[1]

D[1][2] = B[1]

최종적으로 D[N]중 가장 작은값을 출력하면 된다.

#include <iostream>
#include <algorithm>

using namespace std;

int arr[1001][3];
int r[1001], g[1001], b[1001];

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

	int n, answer = 0;
	cin >> n;

	for (int i = 1; i <= n; ++i)
	{
		cin >> r[i] >> g[i] >> b[i];
	}

	arr[1][0] = r[1];
	arr[1][1] = g[1];
	arr[1][2] = b[1];

	for (int i = 2; i <= n; ++i)
	{
		arr[i][0] = min(arr[i-1][1], arr[i-1][2]) + r[i];
		arr[i][1] = min(arr[i-1][0], arr[i-1][2]) + g[i];
		arr[i][2] = min(arr[i-1][0], arr[i-1][1]) + b[i];
	}

	cout << *min_element(arr[n], arr[n]+3);

	return 0;
}

11726: 2×n 타일링

1. 테이블 정의하기

D[i] = 2×i 크기의 직사각형을 채우는 방법의 수

2. 점화식 찾기

2×1 크기의 타일을 하나 놓았을 때 나머지 타일을 채우는 방법의 수는 D[i-1]
1×2 크기의 타일을 하나 놓았을 때, 아래쪽 공간에는 똑같은 1×2 타일만 들어갈 수 있다. 이 때, 나머지 타일을 채우는 방법의 수는 D[i-2]

D[i] = D[i-1] + D[i-2]

3. 초기값 정의하기

D[1] = 1, D[2] = 2

#include <iostream>

using namespace std;

int arr[1001];
int mod = 10007;

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

	int n;
	cin >> n;

	arr[1] = 1;
	arr[2] = 2;

	for (int i = 3; i <= n; ++i)
		arr[i] = (arr[i - 1] + arr[i - 2]) % mod; // 매번 mod의 나머지값만 가져가면 된다

	cout << arr[n];

	return 0;
}

11659: 구간 합 구하기 4

1. 테이블 정의하기

D[i] = A[1] + A[2] + ... + A[i] = D[i-1] + A[i]

2. 점화식 찾기

D[j] - D[i-1] = (A[1] + A[2] + .. A[j]) - (A[1] + A[2] + .. + A[i-1)

3. 초기값 정의하기

D[0] = 0

#include <iostream>

using namespace std;

int arr[100001];
int prefixSum[100001];

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

	int n, m;
	cin >> n >> m;

	for (int i = 1; i <= n; ++i)
	{
		cin >> arr[i];
		prefixSum[i] = prefixSum[i - 1] + arr[i];
	}

	while (m--)
	{
		int i, j;
		cin >> i >> j;
		cout << prefixSum[j] - prefixSum[i - 1] << '\n';
	}

	return 0;
}

기본 문제

1003: 피보나치 함수

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

vector<pair<int, int>>v(41);

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

	int tc;
	cin >> tc;
	v[0] = { 1, 0 };
	v[1] = { 0, 1 };
	for (int i = 2; i <= 40; ++i)
		v[i] = { v[i - 1].first + v[i - 2].first, v[i - 1].second + v[i - 2].second };
	while (tc--)
	{
		int n;
		cin >> n;
		cout << v[n].first << ' ' << v[n].second << '\n';
	}

	return 0;
}

1932: 정수 삼각형

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

int t[501][501];
int n;

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

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

	for (int i = n-1; i > 0; --i)
	{
		for (int j = 1; j <= i; ++j)
			t[i][j] = max(t[i + 1][j], t[i + 1][j + 1]) + t[i][j];
	}
	cout << t[1][1];
	
	return 0;
}

비재귀 top-down으로 깔끔하게 구현이 됨

처음에는 bottom-down으로 하려다가 도무지 답이 안나와서 구글링의 도움을 받았다

11727: 2×n 타일링 2

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

int n, mod = 10007;
int t[1001];

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

	cin >> n;
	
	t[1] = 1;
	t[2] = 3;
	for (int i = 3; i <= n; ++i)
		t[i] = (t[i - 1] + t[i - 2] * 2) % mod;
	cout << t[n];

	return 0;
}

2193: 이친수

using namespace std;
using ll = long long;
int n;
ll t[91];

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

	cin >> n;
	t[0] = 1; t[1] = 1; t[2] = 1;
	for (int i = 3; i <= n; ++i)
	{
		for (int j = 0; j <= i - 2; ++j) t[i] += t[j];
	}
	cout << t[n];

	return 0;
}

나름 자력으로 풀었음

1912: 연속합

#include <bits/stdc++.h>
using namespace std;
int n, mx, ans;
int t[100001];

int main(void)
{
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cin >> n;
	for (int i = 0; i < n; ++i) cin >> t[i];

	mx = ans = t[0];
	for (int i = 1; i < n; ++i)
	{
		mx = max(t[i], t[i] + mx);
		ans = max(ans, mx);
	}
	cout << ans;
	return 0;
}

절반정도는 접근했다가 생각의 늪에 빠져서 못풀고 구글링했음

최대값들 중의 최대값을 선별해야됨

저작자표시

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

[0x12] 수학 (0)	2022.08.05
[0x11] 그리디 (0)	2022.08.04
[0x0F] 정렬 II (0)	2022.08.02
[0x0E] 정렬 I (0)	2022.08.02
[0x0D] 시뮬레이션 (0)	2022.08.01

[0x0F] 정렬 II

2022. 8. 2. 23:27

카운팅 정렬 (Counting Sort)

수의 범위가 어느정도 한정적일 때에만 사용할 수 있다.

대략적으로 수의 범위가 천만 이하일때 사용한다고 보면 된다.

15688: 수 정렬하기 5

#include <iostream>

using namespace std;

int csarr[2000001];
int n;

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

	cin >> n;

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

	for (int i = 0; i < 2000001; ++i)
	{
		while (csarr[i]--)
		{
			cout << i - 1000000 << '\n';
		}
	}

	return 0;
}

기수 정렬 (Radix Sort)

자릿수를 이용해서 정렬을 수행하는 알고리즘.

각 자리수에 대해 카운팅 정렬을 수행하는 알고리즘이라고 볼 수도 있다.

자릿수가 D일때 시간복잡도는 O(DK)이다.

기수 정렬의 최대 단점은 N의 크기에 따라 공간 복잡도가 비례해서 증가한다는 점이다.

이 문제를 어느정도 해결하려면 각 리스트를 vector 또는 연결 리스트로 사용해야 하는데 vector나 연결 리스트나 둘다 STL이 없으면 구현이 많이 까다롭고, STL을 쓸수 있으면 STL sort 함수를 쓰는게 모든면에서 낫다.

한마디로 구현을 해야 할 상황이 아예 존재하지 않는다. 개념만 이해하고 STL을 쓸 수 없는 상황에서는 병합 정렬이나 힙 정렬을 이용하면 된다.

STL sort

퀵 정렬을 기반으로 하지만 리스트가 불균등하게 쪼개지는 상황이 반복되어 재귀의 깊이가 너무 깊어지면 O(NlogN)이 보장되는 알고리즘으로 나머지를 처리한다. 그렇기 때문에 최악의 경우에도 O(NlogN)이 보장된다.

퀵 정렬을 기반으로 한 만큼 Unstable Sort이다.

꼭 Stable Sort가 필요하다면 stable_sort 를 사용하면 된다.

pair, tuple을 정렬하는 경우 앞의 원소의 대소를 비교하고 값이 같으면 그 뒤의 원소의 대소를 비교하는 방식으로 처리한다.

비교 함수를 내가 정해서 넘겨줄 수도 있다.

비교 함수는 두 값이 같을 때(또는 우선순위가 같을 때) 반드시 false를 반환해주어야 한다.

인자로 STL 또는 객체 전달시 reference를 사용해야 한다. 그래야 불필요한 공간을 사용하지 않기 때문이다.

custom compare 함수를 직접 만들 때, 2개의 인자를 받을 수 있다.

순서대로 n+1, n이며 return이 true인 경우만 값의 교환이 일어난다.

번외 : Comparison Sort, Non-comparison Sort

버블, 병합, 퀵 정렬은 Comparison Sort

카운팅, 기수 정렬은 Non-comparison Sort

코딩 테스트에서 STL 사용을 의도적으로 막지 않은 이상, 정렬을 구현하고 앉아있으면 호구다.

연습 문제

1431: 시리얼 번호

#include <iostream>
#include <algorithm>
#include <string>

using namespace std;

string s[50];

// a는 n+1, b는 n이 들어감
// true인 경우만 교환이 이뤄진다
bool comp(const string& a, const string& b)
{
	if (a.length() != b.length())
	{
		return a.length() < b.length();
	}
	else if (a.length() == b.length())
	{
		int asum = 0;
		int bsum = 0;

		for (auto i = 0; i < a.length(); ++i)
		{
			if (isdigit(a[i])) asum += a[i] - '0';
			if (isdigit(b[i])) bsum += b[i] - '0';
		}
		if (asum != bsum)
			return asum < bsum;
	}
	return a < b;
}

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 >> s[i];
	}

	sort(s, s + n, comp);

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

	return 0;
}

custom compare 함수의 인자를 뭘로 받았는지, true/false시 어떻게 돌아가는지 몰라서 조금 찾아보고 금방 이해함

11652: 카드

#include <iostream>
#include <algorithm>

using namespace std;

using ll = long long;
ll arr[100001];

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

	int n;
	int cnt = 1, mxcnt = 1;
	ll mxval;

	cin >> n;

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

	sort(arr, arr + n);

	arr[n] = (1 << 62) + 1;

	mxval = arr[0];

	for (int i = 0; i < n; ++i)
	{
		if (arr[i] == arr[i + 1])
		{
			cnt++;
		}
		else
		{
			if (mxcnt < cnt)
			{
				mxcnt = cnt;
				mxval = arr[i];
			}
			cnt = 1;
		}
	}

	cout << mxval;

	return 0;
}

기본 문제

5648: 역원소 정렬

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

using namespace std;
using ll = long long;

vector<ll> arr;

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)
	{
		string t;
		cin >> t;
		reverse(t.begin(), t.end());
		arr.push_back(stoll(t));
	}

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

	for (auto& item : arr)
	{
		cout << item << '\n';
	}

	return 0;
}

1181: 단어 정렬

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

using namespace std;

vector<string> arr;

bool comp(const string& a, const string& b)
{
	if (a.length() != b.length())
	{
		return a.length() < b.length();
	}

	return a < b;
}

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)
	{
		string t;
		cin >> t;
		arr.push_back(t);
	}

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

	for (int i = 0; i < n - 1; ++i)
	{
		if (arr[i] == arr[i + 1]) continue;
		cout << arr[i] << '\n';
	}
	cout << arr.back();

	return 0;
}

2910: 빈도 정렬

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

using namespace std;

vector<pair<int, int>> v;

bool comp(const pair<int, int>& a, const pair<int, int>& b)
{
	return a.second > b.second;
}

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

	int n, c;

	cin >> n >> c;

	for (int i = 0; i < n; ++i)
	{
		int t;
		cin >> t;

		// find를 사용시 pair 구조체의 멤버함수에 operator== 가 정의되어 있지 않아서 문제가 생긴다.
		// 이런경우 find_if로 조건을 직접 만든 메소드를 인자로 넘겨줘야 한다
		// sort의 custom compare와 같은 개념이다
		auto iter = find_if(v.begin(), v.end(), [&t](const pair<int, int>& elem) { return elem.first == t; });

		if (iter != v.end())
		{
			(*iter).second += 1;
		}
		else
		{
			v.push_back({ t, 1 });
		}
	}

	stable_sort(v.begin(), v.end(), comp);

	for (auto& elem : v)
	{
		for (int i = 0; i < elem.second; ++i)
		{
			cout << elem.first << ' ';
		}
	}

	return 0;
}

람다식과 stable_sort를 같이 사용함

10814: 나이순 정렬

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

using namespace std;

vector<pair<int, string>> arr;

bool comp(const pair<int, string>& a, const pair<int, string>& b)
{
	return a.first < b.first;
}

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)
	{
		int t;
		string ts;
		cin >> t >> ts;
		arr.push_back({ t, ts });
	}

	stable_sort(arr.begin(), arr.end(), comp);

	for (auto& data : arr)
	{
		cout << data.first << ' ' << data.second << '\n';
	}

	return 0;
}

stable_sort만 주의하면 큰 문제 없다.

11656: 접미사 배열

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

using namespace std;

vector<string> v;

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

	string s;

	cin >> s;

	for (auto i = 0; i < s.length(); ++i)
		v.push_back(s.substr(i, s.length()-i));

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

	for (auto& elem : v)
		cout << elem << '\n';

	return 0;
}

string의 substr 사용. 해당 문자열의 1번째 인자 시작 위치부터 2번째 인자의 갯수만큼 반환한다.

10825: 국영수

#include <iostream>
#include <string>
#include <vector>
#include <tuple>
#include <algorithm>

using namespace std;
using Elements = pair<string, tuple<int, int, int>>;

vector<Elements> v;

bool comp(const Elements& a, const Elements& b)
{
	if (get<0>(a.second) != get<0>(b.second))
		return get<0>(a.second) > get<0>(b.second);
	else if (get<1>(a.second) != get<1>(b.second))
		return get<1>(a.second) < get<1>(b.second);
	else if (get<2>(a.second) != get<2>(b.second))
		return get<2>(a.second) > get<2>(b.second);
	return a.first < b.first;
}

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

	int n;
	cin >> n;

	while (n--)
	{
		string name;
		int lan, eng, mat;

		cin >> name >> lan >> eng >> mat;

		v.push_back({ name, {lan, eng, mat} });
	}

	sort(v.begin(), v.end(), comp);

	for (auto& elem : v)
		cout << elem.first << '\n';

	return 0;
}

comp함수의 조건을 잘 조절하는게 포인트

응용 문제

7795: 먹을 것인가 먹힐 것인가

#include <iostream>
#include <algorithm>

using namespace std;

int arrA[20001];
int arrB[20001];

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

	int tc;
	cin >> tc;

	while (tc--)
	{
		int n, m;
		size_t answer = 0;

		cin >> n >> m;

		for (int i = 0; i < n; ++i)
			cin >> arrA[i];
		for (int i = 0; i < m; ++i)
			cin >> arrB[i];

		sort(arrB, arrB + m);

		for (int i = 0; i < n; ++i)
			answer += lower_bound(arrB, arrB + m, arrA[i]) - arrB;
		cout << answer << '\n';
	}

	return 0;
}

바킹독님 얘기로는 이분 탐색을 쓰지 않고 정렬만으로도 풀수 있다고 했다.

나중에 고민해보기로.

저작자표시

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

[0x11] 그리디 (0)	2022.08.04
[0x10] 다이나믹 프로그래밍 (0)	2022.08.03
[0x0E] 정렬 I (0)	2022.08.02
[0x0D] 시뮬레이션 (0)	2022.08.01
[0x0C] 백트래킹 (0)	2022.07.31

[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

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

erikanes's Macchiato

알고리즘

[0x10] 다이나믹 프로그래밍

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

[0x0F] 정렬 II

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

[0x0E] 정렬 I

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

[0x0D] 시뮬레이션

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

[0x0C] 백트래킹

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

+ Recent posts

티스토리툴바