관심이 가는 개발 보물창고

https://www.acmicpc.net/problem/2559

많은 깨달음을 주는 문제였다.

수열이 주어졌을 때, K(연속되는 수)의 합 중 가장 큰 값을 리턴해달라는 문제다.

N(수열의 개수) : 1 ~ 10만

K는 1과 N 사이의 정수이므로 최대는 10만 정도

단순하게 생각하면 10^10만이라 시간 안에 문제를 해결할 수 없다.

어떤 연속된 수의 합을 빠르게 구할 수 있는 방법은 누적합(prefix sum)을 이용하는 것이다.

누적합은 0 ~ k 구간의 합을 미리 차곡차곡 더해서 저장해 둔다.

문제의 예시를 보면

10 5

3 -2 -4 -9 0 3 7 13 8 -3

5개의 연속된 수열의 최댓값은 31이다.

각각의 누적합을 구해보면

1까지의 누적합은 0 + 3

2까지의 누적합은 0 + 3 - 2

3까지의 누적합은 0 + 3 -2 - 4

가만히 보면 3까지의 누적합은 2까지의 누적합 + 입력된 숫자다.

입력을 받을 때 누적합의 배열도 같이 채워나가면 된다.

-9 0 3 7 13의 구간 합을 알고 싶다면?

[13까지의 누적합] - [-4까지의 누적합]이다.

[13까지의 누적합] = 3 -2 -4 -9 0 3 7 13

[-4까지의 누적합] = 3 -2 -4

[구하려고 하는 것] = -9 0 3 7 13

누적합을 미리 정해놓고 가져다 쓰는 건 랜덤 접근이므로 O(1)

K는 최대 10만

10만 x O(1) => 시간 안에 해결이 가능하다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int n, k, num, sum, ans = -10000004;
int arr[100005];
int main()
{
    cin >> n >> k;
    for (int i = 1; i <= n; i++)
    {
        cin >> num;
        arr[i] = arr[i - 1] + num;
    }
    
    for (int i = k; i <= n; i++)
    {
        ans = max(ans, arr[i] - arr[i - k]);
    }
    
    cout << ans << '\n';
    return 0;
}

https://www.acmicpc.net/problem/1620

지문이 엄청 길지만, 핵심은 마지막에 있다.

포켓몬 이름을 대면 그에 대응되는 숫자를

숫자를 대면 그에 대응되는 이름을 리턴해주면 된다.

그런데 경우의 수가 생각보다 크다.

포켓몬 개수는 1 ~ 10만

내가 맞춰야 하는 개수(쿼리의 수)도 1 ~ 10만

문자열을 숫자로 바꾸는 것

숫자를 문자열로 바꾸는 것

그런데 생각해 보면 둘 다 문자열로 저장해도 상관없다.

그래서 저장할 때에는 둘 다 문자열로 저장한다.

쿼리의 수가 최대 10만이니, 어떤 포켓몬 이름이나 숫자를 물어보더라도 빠르게 찾아서 리턴해줘야 하므로

unordered_map(정렬되지 않은 맵 = 해시맵)을 사용해서 find를 O(1)에 찾을 수 있도록 한다.

그런데, ios_base::sync_with_stdio(false)를 통해서 scanf, cin의 동기화를 꺼줘야 아슬아슬하게 시간 초과를 면할 수 있다.

#include <iostream>
#include <unordered_map>
#include <string>
using namespace std;

int n, m;
string s;
unordered_map<string, string> mp;
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
    {
        cin >> s;
        mp[s] = to_string(i);
        mp[to_string(i)] = s;
    }
    
    for (int i = 1; i <= m; i++)
    {
        cin >> s;
        cout << mp[s] << '\n';
    }
    return 0;
}

https://www.acmicpc.net/problem/9375

간단하면서도, 생각보다 어려웠던 문제.

같은 종류의 옷은 한 번만 사용할 수 있다.

여기서는 종류가 중요하지, 그 옷의 이름은 중요하지 않다.

# 모자가 1개라면?

(모자 착용), (모자 미착용) = 2가지

신해빈은 무조건 하나의 옷은 착용해야 하므로 마지막 미착용의 경우의 수는 빼야 한다.

2 - 1 = 1가지.

# 모자가 2개라면? 

같은 종류의 옷은 못 입는다고 하였으니,

(모자 A) (모자 B) (모자 미착용) = 3가지

신해빈은 무조건 하나의 옷은 착용해야 하므로 마지막 미착용의 경우의 수는 빼야 한다.

3 - 1 = 2가지.

# 모자가 2개이고, 렌즈가 1개라면?.

(모자A, 렌즈 미착용)

(모자 B, 렌즈 미착용)

(모자 미착용, 렌즈 착용)

(모자 A, 렌즈 착용)

(모자 B, 렌즈 착용)

(모자 미착용, 렌즈 미착용)

신해빈은 무조건 하나의 옷은 챙겨야 하기 때문에 아예 입지 않는 경우를 1개 빼야 한다.

6 - 1 = 5가지

#include <iostream>
#include <map>
#include <vector>
using namespace std;

int t, n, ans = 1;
string s1, s2;
map<string, int> mp;
int main()
{
    cin >> t;
    while (t--)
    {
        cin >> n;
        mp.clear();
        for (int i = 0; i < n; i++)
        {
            cin >> s1 >> s2;
            mp[s2]++;
        }
        
        ans = 1;
        for (auto item : mp)
        {
            ans *= (item.second + 1);
        }
        
        cout << ans - 1 << '\n';
    }
    return 0;
}

https://www.acmicpc.net/problem/9996

접미사(prefix), 접두사(suffix) 개념과 약간의 string 테크닉이 필요한 문제.

접미사 + * + 접두사

* 에는 어떠한 문자열이나 공백이 올 수 있다고 한다.

여러 개의 테스트 케이스 문자열이 들어온다고 했을 때,

접미사와 접두사가 같은 문자열이라면 중간의 문자열들은 * 로 대체가 되면서

맞으면 DA, 틀리면 NE를 출력하면 된다.

다만 주의할 점이, 접두사와 접미사가 같은 문자열인 경우에는 그 크기도 같이 생각해줘야 한다.

aba * aba 라면

들어온 문자열이 aba 일 경우에는 DA 를 뱉게 되는데,

문제에서는 임의의 문자열로 변환해 파일 이름을 같게 만들 수 있어야 한다는 조건이 있으므로

적어도 접두사 + 접미사의 크기가 들어온 문자열의 크기보다는 작아야 한다는 것을 알 수 있다.

#include <iostream>
#include <string>
using namespace std;

int N;
string pattern, str, pre, suf;
int main()
{
	cin >> N >> pattern;

	int pos = pattern.find('*');
	pre = pattern.substr(0, pos);
	suf = pattern.substr(pos + 1);
	for (int i = 0; i < N; i++)
	{
		cin >> str;

		if (pre.size() + suf.size() > str.size())
		{
			cout << "NE\n";
		}
		else
		{
			if (pre == str.substr(0, pre.size()) && 
				suf == str.substr(str.size() - suf.size()))
			{
				cout << "DA\n";
			}
			else
			{
				cout << "NE\n";
			}
		}
	}
	return 0;
}

https://www.acmicpc.net/problem/11655

ROT 13의 규칙은 소문자든 대문자든 알파벳이 오른쪽으로 13칸 이동한 알파벳을 출력하면 된다.

13칸을 이동할 때, a ~ z를 넘어가는 범위가 존재한다면, 다시 a부터 시작할 수 있도록 약간의 모듈러 연산을 추가해서 다른 문자의 아스키코드로 넘어가지 않도록 이를 방지한다.

#include <iostream>
#include <string>
#include <cstring>
using namespace std;

string str;
int pos;
int main()
{
	getline(cin, str);

	for (int i = 0; i < str.size(); i++)
	{
		if (isalpha(str[i]))
		{
			if (isupper(str[i]))
			{
				pos = ((str[i] - 'A') + 13) % 26;
				str[i] = pos + 'A';
			}
				
			else
			{
				pos = ((str[i] - 'a') + 13) % 26;
				str[i] = pos + 'a';
			}
		}
	}

	cout << str << '\n';
	return 0;
}

조합은 순서를 고려하지 않습니다.

순서는 고려하지 않고 다양하게 몇 개를 뽑을 지에 집중합니다.

조합을 구현하는 테크닉은 3가지가 있습니다.

중첩 반복문

n명 중 r개를 선택하는 방법일 때, r의 수가 3개 이하라면 반복문으로 빠르고 쉽게 구현할 수 있습니다.

for (int i = 0; i < n; i++) {
	for (int j = i + 1; j < n; j++) {
    		for (int k = j + 1; k < n; k++) {
            	}
    	}
}

next_permutation 을 이용하자.

순열의 특징을 가져와 1은 애들이 선택됐다고 보면 되고, 0은 선택받지 못한 애들이 됩니다.

즉 5C2 라면 chk 배열을 {0, 0, 0, 1, 1}이라고 두고, 1일 때에만 출력하면 됩니다.

int main()
{
	vector<int> input = { 3,5,1,7,9 };
	vector<int> chk = { 0,0,0,1,1 };
	do
	{
		for (int i = 0; i < chk.size(); i++)
		{
			if (chk[i] == 1)
			{
				cout << input[i] << ' ';
			}
		}
		cout << '\n';
	} while (next_permutation(chk.begin(), chk.end()));
}

7 9
1 9
1 7
5 9
5 7
5 1
3 9
3 7
3 1
3 5

재귀 구현

조합이라는 것도 즉, 그 현재 순간에 내가 하나를 선택하는 방법입니다.

따라서 그 순간 마다 하나를 pick 하는 과정이 동일하기 때문에 재귀 방법으로 구현할 수 있습니다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

// 5C2 구하기 (조합)
int n = 5, k = 2;
vector<int> v = { 3,5,1,7,9 };

void combi(int start, vector<int>& picked)
{
	if (picked.size() == k)
	{
		for (int it : picked) cout << it << ' ';
		cout << '\n';
		return;
	}

	for (int i = start + 1; i < n; i++)
	{
		picked.push_back(v[i]);
		combi(i, picked);
		picked.pop_back();
	}
}

int main()
{
	vector<int> picked;
	combi(-1, picked);
}

재귀 방법이 처음에는 이상한 구조라고 생각되지만, 쉽게 현재 구간에서 나는 어떤 선택을 할 것인지를 결정해 주면 됩니다.

동시에 기저사례(종료조건)은 nCr 일 때 이미 r개를 뽑았다면 그때를 출력하고 빠져나가면 됩니다.

자연수 N과 K가 주어졌을 때, 이항 계수 nCk 를 구하는 문제입니다.

해당 숫자를 10,007로 나누는 의미는 대부분 큰 숫자인 경우에 해당 숫자로 나누는 테크닉이 필요합니다.

이항 계수는 중요한 성질을 가지고 있습니다.

n과 k가 같을 때 혹은 k가 0일 때는 1입니다. 이를 통해 base condition 을 만족할 수 있고,

파스칼 법칙에 의하면 nCr = n-1Cr-1 + n-1Cr 을 만족하게 됩니다.

이러한 법칙을 하나씩 하다 보면 반복되는 구간이 생기게 됩니다. 반복되는 것을 계속해서 계산하는 것은 낭비입니다. 따라서 한 번 구한 답을 캐시에 저장하면, 이후에 꺼내다 쓰면 됩니다. 이것을 메모리제이션이라고 합니다.

위에서 base condition도 만족하지 않고, 메모도 하지 않았다면 적어도 한 번은 계산해야 되기 때문에

dp[n][k] = func(n - 1, k - 1) + func(n - 1, k) 를 통해 구하고 리턴합니다. 다만 주의할 점은 계산할 때마다 10,007 로 나누어 줘야 합니다.

따라서 dp[n][k] = (func(n - 1, k - 1) % 10,007 + func(n - 1, k) % 10,007) % 10,007

이렇게 푸는 방식을 dp(다이내믹 프로그래밍) 중에서도 Top-down 방식입니다.

#include <iostream>
using namespace std;

typedef long long ll;
int n, k;
ll dp[1001][1001];

const int MOD = 10007;

ll combination(int n, int k)
{
	if (dp[n][k] != 0) return dp[n][k];
	if (n == k || k == 0) return 1;

	dp[n][k] = (combination(n - 1, k - 1) % MOD + combination(n - 1, k) % MOD) % MOD;

	return dp[n][k];
}

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

	cin >> n >> k;
	cout << combination(n, k) << endl;
	return 0;
}

오랜만에 파라메트릭 서치 문제를 풀었습니다.

파라메트릭 서치 문제는 최적화 문제를 결정 문제로 바꾸어 푸는 문제입니다.

주어진 문제는 여러 개의 랜선의 길이가 주어졌을 때, 각 랜선들을 mid로 자르면 나눠지는 랜선의 개수가 N개 이상을 만들면 되는데, 이때 mid의 길이를 가능한 최대로 뽑고 싶다는 것이 이 문제의 핵심입니다.

예시에서는 200m로 잘랐을 때 11개를 만들 수 있으며 나올 수 있는 최대 길이라고 합니다.

어떻게 11개가 나왔을까요.

802 / 200 = 4

743 / 200 = 3

457 / 200 = 2

539 / 200 = 2

4 + 3 + 2 + 2 = 11개가 됩니다.

정리하면 어떻게 자르든 11개 이상만 나오면 조건을 만족하며, 그때 자른 길이 중 최대를 저장하면 됩니다.

만약에 조건 11개를 만족하더라도 200보다 작을 수 있는 경우의 수가 존재할 수 있습니다.

무슨 말이냐면, 

802 / 199 = 4

743 / 199 = 3

457 / 199 = 2

539 / 199 = 2

4 + 3 + 2 + 2 = 11개

어떤가요. 주어진 조건을 만족하면서도 자른 길이가 199m입니다.

정답이 한 가지가 아니라 여러 가지라는 뜻이죠.

즉 우리는 조건을 만족하더라도 더 최대로 자를 수 있는 경우가 있으면 그것이 정답이라는 뜻입니다.

조건을 만족한다! 더 길게 잘라볼까?????

조건을 만족하지 못한다! 좀만 적게 잘라보자...

약간 실생활을 생각해보면 됩니다.

이정도 자르면 4개는 나오겠지??

싹둑, 어라? 3개네 좀 더 짧게 잘라야겠다!

이런 경험이 있을 것입니다.

이렇게 조건을 만족하더라도 더 가보자!!처럼 이러한 방식을 파라메트릭 서치라고 합니다!

자르는 방법은 다음과 같습니다.

len의 길이로 자른다고 가정했을 때 나오는 개수를 우리는 아래와 같이 작성할 수 있습니다.

bool calc(int len)
{
    int cnt = 0;
    for(int i = 0; i < K; i++)
    {
        cnt += v[i] / len;
    }
    
    return cnt >= N;
}

랜선의 길이가 2^31 - 1보다 작거나 같은 자연수이기 때문에 이 말은 곧 0부터 int의 최댓값까지 나올 수 있다는 말이므로.

우리가 자르고자 하는 길이의 탐색 구간은 0 ~ INT_MAX까지! 

자연수라고 했으니까 0이 아니고 1로 해도 됩니다.

그런데 여러 문제를 풀어보니까 0이 실수도 안 하고 그렇습니다.

기존의 이진 탐색처럼 반복문을 구성하고 해당 mid(자를 길이)를 선택했다면 그걸로 잘라보고,

조건을 만족한다면 더 나아가 보고 (여기서 나아간다는 뜻은 길이를 더 길게 잘라보겠다는 뜻)

조건을 만족하지 못한다면 더 짧게 잘라보고

하면서 길이를 갱신해나가면 됩니다.

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <climits>
using namespace std;

int K, N;
vector<int> v;

bool calc(int len)
{
    int cnt = 0;
    for(int i = 0; i < K; i++)
    {
        cnt += v[i] / len;
    }
    
    return cnt >= N;
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
    cin >> K >> N;
    v.resize(K);
    for(int i = 0; i < K; i++) cin >> v[i];
    long long left = 0;
    long long right = INT_MAX;
    long long ans = 0;
    while(left <= right)
    {
        long long mid = (left + right) / 2;
        
        if(calc(mid))
        {
            ans = max(ans, mid);
            left = mid + 1;
        }
        else
            right = mid - 1;
    }
    
    cout << ans << endl;
    return 0;
}

객체지향 프로그래밍을 해봤다면 지문 이해가 쉬웠을 것 같습니다.

어떤 자연수 M의 분해합이 N인 경우, M을 N의 생성자라고 합니다.

간단히 말하자면 M으로 인해 N이 생겨났으니, 주체인 M이 N의 생성자라고 생각하면 됩니다.

그랬을 때 문제에서 N이 입력으로 주어지면 우리는 M을 구해야 합니다.

그중에서도 가장 작은 M을 구하려면 M을 1부터 검사하면서 N을 만들 수 있는 생성자를 찾아가면 됩니다.

언제까지 찾으면 될까요?

확실한 건 M은 N보다 클 수 없습니다. 생성자니까요.

따라서 N보다 작을 때까지만 루프를 돌면 됩니다.

calc함수는 어떤 자연수의 각 숫자의 합을 리턴하는 함수입니다.

문자열로 쪼개서 계산해도 되지만, 이러한 방식이 오히려 더 편할 수 있습니다.

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;

int calc(int n)
{
    int sum = 0;
    while(n)
    {
        sum += n % 10;
        n /= 10;
    }
    return sum;
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
    int n;
    cin >> n;
    
    int cur = 1;
    bool found = false;
    while(cur < n)
    {
        int num = cur + calc(cur);
        if(num == n)
        {
            cout << cur << endl;
            found = true;
            break;
        }
        cur++;
    }
    
    if(found == false)
        cout << "0\n";
    return 0;
}

[문제풀이]

오랜만에 트리 문제를 풀어봤는데,,, 너무 쩔쩔매던 문제였습니다... (개념은 알고 있는데 구현을 못하니..)

주말에 다시 풀어봐야겠습니다.

여튼 문제에서는 트리를 구성하고 전위 순회, 중위 순회, 후위 순회를 그대로 출력하면 됩니다.

전위 순회는 parent, leftChild, rightChild

중위 순회는 leftChild, parent, rightChild

후위 순회는 leftChild, rightChild, parent

Tree의 구성은 node 들도 구성되어 있습니다.

node의 구성은 데이터를 저장할 char와 자식 노드를 가리킬 2개의 포인터를 구성하면 됩니다.

struct Node
{
	char data;
	Node* leftChild;
	Node* rightChild;
};

순회는 위에서부터 아래로 쭉 보기 때문에 반복되는 구문이 필요합니다.

이때 반복은 재귀 형식으로 구현하면 됩니다.

전위 순회

void preorder(Node* root)
{
	if (root)
	{
		cout << root->data;
		preorder(root->leftChild);
		preorder(root->rightChild);
	}
}

루트에서 출발해서 자신의 데이터를 출력하고 왼쪽, 오른쪽으로 줄기를 타고 내려갑니다.

만약에 루트가 nullptr이면 종료합니다.

중위 순회

void inorder(Node* root)
{
	if (root)
	{
		inorder(root->leftChild);
		cout << root->data;
		inorder(root->rightChild);
	}
}

후위 순회

void postorder(Node* root)
{
	if (root)
	{
		postorder(root->leftChild);
		postorder(root->rightChild);
		cout << root->data;
	}
}

입력을 받아서 노드를 구성할 때는 parent, left, right 순으로 데이터가 들어오며 parent는 root를 의미하면서 동시에 데이터이므로 데이터를 저장하고, 이어서 left와 right를 저장합니다.

주의할 점은 '.' 입력이면 자식이 없다는 뜻이므로 무시합니다. '.' 이외의 값이 들어오면 각각 자식 노드를 가리키게 설정해주면 됩니다.

출력은 'A' 노드가 항상 루트노드 이므로 root는 'A' 노드를 가리킬 수 있게 합니다.

그런 다음 위에서 구현한 전위, 중위, 후위 순회를 각각 호출하면 됩니다.

#include <iostream>
#include <vector>
using namespace std;

// 자료구조 Tree 구현

struct Node
{
	char data;
	Node* leftChild;
	Node* rightChild;
};

void preorder(Node* root)
{
	if (root)
	{
		cout << root->data;
		preorder(root->leftChild);
		preorder(root->rightChild);
	}
}

void inorder(Node* root)
{
	if (root)
	{
		inorder(root->leftChild);
		cout << root->data;
		inorder(root->rightChild);
	}
}

void postorder(Node* root)
{
	if (root)
	{
		postorder(root->leftChild);
		postorder(root->rightChild);
		cout << root->data;
	}
}

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

	int n;
	cin >> n;
	vector<Node*> nodes(26);

	for (int i = 0; i < 26; i++)
	{
		nodes[i] = new Node();
	}
	
	for (int i = 0; i < n; i++)
	{
		char parent, left, right;
		cin >> parent >> left >> right;

		nodes[parent - 'A']->data = parent;

		if (left != '.')
		{
			nodes[parent - 'A']->leftChild = nodes[left - 'A'];
		}

		if (right != '.')
		{
			nodes[parent - 'A']->rightChild = nodes[right - 'A'];
		}
	}

	Node* root = nodes[0];
	preorder(root); cout << endl;
	inorder(root); cout << endl;
	postorder(root); cout << endl;

	return 0;
}