오늘의 공부

2742번: 기찍 N (acmicpc.net)

..이 문제를 잊지 않기 위해서 포스팅하기로 했다.

#include <iostream>
using namespace std;
int N;
int main()
{
	cin >> N;
	for (int i = 0; i < N; ++i)
	{
		//cout << N - i << '\n';
		printf("%d\n", N - i);
	}
}

슥 채우고 넘어가려고 했는데 실패가 떠서 요근래 가장 당황스러웠다. 

100,000를 출력할 때 확실히 시간이 오래걸리긴 했다.

왜 자꾸 시간초과가 날까 검색해보다가 

cout, cin, endl가 printf나 '\n'보다 연산이 오래걸려서 그렇다고 했다.

그래서 그 출력 한줄 바꿔줬더니 4초만에 완료됐다.

나는 습관적으로 cin, cout을 사용하니까 다음에 시간초과 나거나 할 때 출력부분을 의심해 볼 만도 한 것 같다.

그리고 뭔가 입력과 출력에 대한 부분을 다시 깊게 찾아보는 것도 좋은 방법인 것 같다. 

11047번: 동전 0 (acmicpc.net)

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

int N, K;
vector<int> value;
int func()
{
	int answer = 0;
	int i = N-1;
	do {
		answer += (K / value[i]);
		K %= value[i];
		--i;
	} while (i >= 0);

	return answer;
}

int main()
{
	cin >> N >> K;
	int temp = 0;
	for (int i = 0; i < N; ++i)
	{
		cin >> temp;
		value.push_back(temp);
	}
	cout << func();
}

Greedy 알고리즘 문제로 간단하게 풀 수 있는 문제이다.

완전탐색을 진행하더라도 N번. 즉 10번만 돌면 되기 때문에 시간복잡도가 O(N)이다.

1302번: 베스트셀러 (acmicpc.net)

map을 이용해서 입력받은 책의 이름들을 key값으로 넣어주었다. 

이렇게 하면 문제는 출력할 때 동일 우선순위(=value가 같을 때)에서 알파벳 순서대로 출력할 때 발생하게 된다.

그래서 map의 value값과 key값을 따로 정렬해주었다.

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

int N;
map<string, int> m;

bool cmp(const pair<string, int> &a, const pair<string, int> &b)
{
	if (a.second == b.second)
	{
		return a.first < b.first;
	} 
	return a.second > b.second;
}


int main()
{
	cin >> N;

	string temp;
	for (int i = 0; i < N; ++i)
	{
		cin >> temp;
		m[temp] += 1;
	}

	vector<pair<string, int>> vec(m.begin(), m.end());
	sort(vec.begin(), vec.end(), cmp);

	cout << vec[0].first;
}

programmers.co.kr/learn/courses/30/lessons/43105

앞서 풀었던 문제 중 땅따먹기와 개념이 비슷한 문제이다. 

int Find_max(int n1, int n2)
{
	return n1 > n2 ? n1 : n2;
}

int solution(vector<vector<int>> triangle) {
	int answer = 0;

	int triangle_size = triangle.size();

	for (int i = 0; i < triangle_size-1; ++i)
	{
		for (int j = 0; j < triangle[i+1].size(); ++j)
		{
			if (j < 1 || (j == triangle[i + 1].size() - 1))
			{
				// 왼쪽 끝// 오른쪽 끝 
				if (j < 1)
				{
					triangle[i + 1][j] += triangle[i][0];
				}
				else
				{
					triangle[i + 1][j] += triangle[i][j-1];
				}
				
			}
			else
			{
				triangle[i + 1][j] += Find_max(triangle[i][j - 1], triangle[i][j]);
			}
		}
	}
	
	answer = triangle[triangle_size - 1][0];
	for (int i = 1; i < triangle[triangle_size - 1].size(); ++i)
	{
		if (answer < triangle[triangle_size - 1][i])
		{
			answer = triangle[triangle_size - 1][i];
		}
	}

	return answer;
}

programmers.co.kr/learn/courses/30/lessons/12973

효율성 테스트까지 통과하기 위해서는 Stack을 이용해서 풀어야 한다.

괄호 { } 맞추기 문제, 그리고 카카오 테스트 중에 크레인 인형 뽑기와 비슷했던 문제였다.

stack의 top과 s의 idx값을 비교했을 때 같으면 stack의 top을 pop하고 같지 않다면 s의 idx값을 현재 stack에 넣어준다. 

#include <iostream>
#include<string>
#include <stack>
using namespace std;
int solution(string s)
{
	int answer = 0;
	stack<char> Stack;

	int idx = 0;

	Stack.push(s[idx++]);

	while (idx < s.size())
	{
		if (Stack.empty())
		{
			Stack.push(s[idx++]);
		}
		char s_top = Stack.top();

		if (!Stack.empty() && s_top == s[idx])
		{
			Stack.pop();
		}
		else
		{
			Stack.push(s[idx]);
		}
		idx += 1;

	}

	if (Stack.empty())
		answer = 1;
	else
		answer = 0;

	return answer;
}

www.acmicpc.net/problem/13904

우선 입력받은 데이터를 점수를 기반으로 정렬했다. 

vector의 second에 점수가 first에 과제 제출 기한이 담겨있다. 

탐욕법을 이용해서 푸는 문제로 점수를 기준으로 가장 큰 수부터 마감일에 가깝게 넣는다. 

오름차순으로 정렬된 벡터의 값에서 0번은 (한 번 돌릴 때마다 erase를 해주므로) 제일 점수가 큰 값이다.

따라서 0번을 뽑아서 해당 마감일에 이미 다른 점수가 있으면 전 날, 전전날을 계속 찾아본다.

비어있는 날이 있다면 해당 날짜에 넣고 없다면 버린다. 

왜 계속 틀렸을까 고민했던 문제이다. 그래서 이것저것 잘못 생각한 게 있었나 고민해봤지만 답이 나오지 않았다. 

그럴 수 밖에.. 틀린 이유는 따로 있었다.

밑에 answer에 더해주는 for문에서 n의 범위값을 틀려서 계속 채점 오류가 발생했다.

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
bool cmp(const pair<int, int> &a, const pair<int, int> &b) 
{
	if (a.second == b.second)
	{
		return a.first < b.first;
	}
	return a.second > b.second;
}

int max_score(vector<pair<int, int>>& v, int &n)
{
	vector<int> tempv;
	tempv.resize(1001);
	int idx = 0;
	int answer = 0;
	while (idx < n) {

		for (int i = v[0].first; i > 0; --i)
		{
			if (tempv[i] != 0)
			{
				continue;
			}
			else
			{
				tempv[i] = v[0].second;
				break;
			}
		}

		idx += 1;
		v.erase(v.begin());
	}

	for (int i = 0; i <=1000; ++i)
	{
		answer += tempv[i];
	}
	return answer;
}


int main()
{
	vector<pair<int, int>>  v;
	int n;
	cin >> n;

	for (int i = 0; i < n; i++)
	{
		int n1, n2;
		cin >> n1 >> n2;
		v.push_back(make_pair(n1, n2));
	}
	sort(v.begin(), v.end(), cmp);
	int answer = max_score(v, n);
	cout << answer;
    
    return 0;
}

기수 정렬과 계수 정렬

최악의 경우에도 비교 정렬들보다 빠른 정렬 알고리즘

최악의 경우 정렬 시간이 O(nlogn)보다 빠를 수는 없을까? 원소 두 개를 비교함에 의해 정렬하는 비교정렬은 최악의경우 수행 시간이 O(nlogn)보다 빨라질 수는 없다.

그런데 입력 원소들이 특수한 성질을 만족하는 경우 O(nlogn)의 한계를 극복할 수 있는 정렬 알고리즘들이 존재한다.

기수 정렬과 계수 정렬이다.

◎ 기수 정렬

기수 정렬은 문자열의 정렬에도 사용되는 방법이다.

입력이 모두 k 이하의 자리수를 가진 자연수인 특수한 경우에(자연수가 아닌 제한된 종류를 가진 알파벳 등도 해당 된다) 사용할 수 있는 방법으로 O(n) 시간이 소요되는 정렬 알고리즘이다.

작동의 순서는 다음과 같다.

1. 우선 가장 낮은 자리수만 가지고 모든 수를 재배열(정렬)한다.

2. 그런 다음 가장 낮은 자리수는 잊어버린다. 

3. 그 다음은 앞과 같은 방법으로 더이상 자리수가 안 남을 때까지 반복한다.

구현 방법은 우선 0부터 9까지의 버킷을 만든다.

그 후에 1의 자리를 비교한다. 0123같은 경우에는 3번 버킷에, 2154는 4번 버킷에 들어간다.

이 때 버킷의 각 번호는 FIFO의 구조를 가진 queue이다. 

그 후 0번 버킷부터 9번버킷까지 각 버킷에 저장된 숫자들을 뺀다.

다음으로는 10의 자리를 비교해서 위와 같은 과정을 거친다.

이 과정을 거치게 되면 마지막에는 정렬된 배열을 갖게 된다.

만약 첫 문자에서 정렬을 시작하게 된다면 MSD 기수 정렬, 마지막 문자에서부터 정렬을 시작하게 되면 LSD 기수 정렬이라고 한다. 

이 알고리즘은 "안정성을 유지하면서 정렬된다" 

이 말은 같은 값을 가진 아이템들은 정렬 후에도 원래의 순서가 유지되는 성질을 가진 정렬을 일컫는 말이다.

즉, 값이 같은 원소끼리는 정렬 후에 원래의 순서가 바뀌지 않는 성질을 말한다. 

◎ 계수 정렬

계수 정렬은 정렬하고자 하는 원소들의 값이 O(n)을 넘지 않는 경우에 사용할 수 있다. 

기본적인 특성은 버켓 정렬과 유사하지만 중복되는 키 값의 누적된 횟수를 구해서 그것을 인덱스로 삼는다.

작동의 순서는 다음과 같다.

ex) 0,3,2,1,0,0,2,3,1,1,1 을 정렬한다고 할 때 

1. 우선 각 배열의 원소를 훑어보고 각 키의 값이 몇 번씩 있는지 빈도수를 구한다.

2. 각 키의 등장 횟수를 누적 합으로 바꿔준다.

3. 위의 누적합은 새로 할당할 공간의 최댓값이 된다. 

즉 숫자 0의 인덱스는 1과 3의 사이이다. 

0이 3번 반복뒤니까 0을 3번째 인덱스에 넣은 후에 0의 누적 합을 2로 줄인다. 그 후 3의 누적 합은 11이므로 3을 11번 인덱스에 집어 넣고 3의 누적 합을 10으로 줄여준다. 

4. 2의 경우에도 마찬가지로 빈도 수는 2, 누적합은 9이므로 9에 넣고 누적합을 8로 줄여준다. 

이런 식으로 반복하며 정렬해야 하는 모든 값의 인덱스를 정해줄 수 있다.

계수정렬도 마찬가지로 안정 정렬이며 다른 정렬들 보다 시간 복잡도에서 좋은 효율을 보이는 이유는 키 값의 비교를 하지 않고 (비교정렬) 바로 자기 자리를 찾기 때문이다. 

참고 자료;

쉽게 배우는 알고리즘 - 관계 중심의 사고법 (출판사; 한빛 아카데미 / 저; 문병로) 

programmers.co.kr/learn/courses/30/lessons/12951

처음에는 그냥 공백 구분해서 제일 앞글자만 대문자로 바꿔주면 되는 줄 알았더니 다른 조건들이 있었다.

1. 문자열 중간에 있는 대문자를 소문자로 바꾸기

2. 공백이 길게 있는 경우 그 공백도 answer에 그대로 추가해야 함

그러니까 hello    woRld 같은 경우에 Hello WoRld로 출력하면 안되고 Hello    World로 출력해야 한다.

ssstream으로 풀고 테스트 실행했는데 눈이 침침했는지 분명 똑같은 결과인데 뭐가 다르다는 거야; 하면서 한참 고민했다.

웃기네 

string solution(string s) {
	string answer = "";

	int index = 0;
	bool prev_blank = true;
	while (index < s.size())
	{
		if (prev_blank && s[index] != ' ')
		{
			s[index] = toupper(s[index]);
			prev_blank = false; 
		}
		else if (s[index] == ' ')
		{
			prev_blank = true;
		}
		else if(isupper(s[index]))
		{
			s[index] = tolower(s[index]);
		}

		answer += s[index];
		index += 1;
	}

	return answer;
}