개발자가 되기 위한 첫 걸음

문제

방향그래프가 주어지면 주어진 시작점에서 다른 모든 정점으로의 최단 경로를 구하는 프로그램을 작성하시오. 단, 모든 간선의 가중치는 10 이하의 자연수이다.

입력

첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1≤V≤20,000, 1≤E≤300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1≤K≤V)가 주어진다. 셋째 줄부터 E개의 줄에 걸쳐 각 간선을 나타내는 세 개의 정수 (u, v, w)가 순서대로 주어진다. 이는 u에서 v로 가는 가중치 w인 간선이 존재한다는 뜻이다. u와 v는 서로 다르며 w는 10 이하의 자연수이다. 서로 다른 두 정점 사이에 여러 개의 간선이 존재할 수도 있음에 유의한다.

출력

첫째 줄부터 V개의 줄에 걸쳐, i번째 줄에 i번 정점으로의 최단 경로의 경로값을 출력한다. 시작점 자신은 0으로 출력하고, 경로가 존재하지 않는 경우에는 INF를 출력하면 된다.

여러 가지 시도를 해서 성공. 정렬하는 데서 이것저것 해 보다가 priority_queue를 발견하는데 시간이 좀 걸렸고,

자료형을 결정하는데 있어, pair를 쓸지, map을 쓸지, vector를 쓸지 결정하는 데도 시간이 걸렸다.

기본적인 예제이긴 하지만 연습으로 나쁘지 않았던 듯.

기본적인 다익스트라(Dijkstra) 알고리즘으로 해결.

추가로, 처음엔 막연히 adjacency matrix로 구현하려 했으나 공간이 너무 많이 필요하여 adjacency list로 변경.

#include<iostream>
#include<queue>
#include<map>

const int LENGTH_MAX = 200010;

using namespace std;

int main(){

////////////////// inputs, Initialize ///////////////
	int v, e, start, from, to, length;
	
	cin >> v >> e;
	cin >> start;
	
	priority_queue<pair<int, int>,vector<pair<int,int>>,greater<pair<int,int>>> q;		// save distance(result) in order of <distance, vertex>
	int dist[v];
	map<int, int> edge[v]; 					// adjacency list
	bool done[v];
	
	for(int i = 0; i < v; i++){
		dist[i] = LENGTH_MAX;
		done[i] = false;
	}

	dist[start-1] = 0;
	q.push(make_pair(0,start-1));
	
	for(int i = 0; i < e; i++){
		cin >> from >> to >> length;
		if( edge[from-1][to-1] == 0 || length < edge[from-1][to-1] ) edge[from-1][to-1] = length;
	}
	
/////////////////////// body part /////////////////////////	
	
	while(!q.empty()){
		int cur_vert = q.top().second;
		int cur_dist = q.top().first;
		q.pop();
		if(done[cur_vert]) continue;
		done[cur_vert] = true;
		for(pair<const int, int> temp : edge[cur_vert]){ // temp.first : vertex index , temp.second : edge length
			if( temp.second + cur_dist < dist[temp.first] ){
				dist[temp.first] = temp.second + cur_dist;
				q.push(make_pair(dist[temp.first], temp.first));
			}
		}
	}	
	
///////////////////// print results ///////////////////////
	for(int i = 0; i < v; i++){
		if(dist[i] == LENGTH_MAX){
			cout << "INF";
		} else {
			cout << dist[i];
		}
		cout << '\n';
	}
	
	return 0;
}

문제

규현이는 멍청하다. 왜냐하면, 1~10까지 수 밖에 모르기 때문이다. 어느날 규현이 옆을 지나가던 태석이가 규현이를 보고 이렇게 외쳤다. "빵빵!!" 규현이는 "아하!" 하면서 세상에는 빵이란 수도 있구나 했다. 그날 이후로 규현이는 매일 친구들을 볼 때면 "빵빵!!" 거리면서 인사를 했다. 규현이의 친구 중에는 태방이가 있다. 자꾸 규현이가 "빵빵!!" 거릴때 마다 자신을 놀리는 것 처럼 생각했던 태방이는 규현이에게 그건 "빵이 아니고 영이야" 라고 가르쳐 줬다.

이제 규현이는 0~10까지 수를 알고 있다. 어느날 자신이 알고 있는 숫자를 까먹지 않으려고 종이에 1~10까지 수를 썻다. (0은 잠시 까먹었다) 규현이의 친구 석원이는 밀덕이다. 계급을 엄청나게 좋아해서, 규현이가 써 놓은 숫자에 이등병 마크인 -를 모두 그렸다. 석원이는 규현이에게 이렇게 말했다. "너, 우리 위대하신 미하엘 칼라시니코프께서 뭐라고 했는지 알아? 단순함과 신뢰성, 그리고 저렴한 가격이 최고야!"

규현이는 그 말을 듣고서 아하 세상에는 음수도 있구나 했다.

이제 규현이가 아는 수는 -10부터 10까지 20개가 되었다. 아차, 0을 빼먹었구나, 21개가 되었다.

근처 사파리에 놀러간 규현이는 사파리 가이드 승환이와 함께 관광을 시작했다. "저기, 사자 1마리가 보이죠? 그 옆이 그 사자 부인이에요. 그러니깐, 1 더하기 1은 2죠" 규현이는 덧셈을 익혔다. "저 사자는 아까 그 사자의 자식 2마리 입니다. 그럼 총 사자는 몇 마리이지요?" 이제 규현이는 1+1을 제외한 다른 덧셈도 할 수 있다. 만세!

인도네시아에 놀러간 규현이는 자바 섬에 방문했다. 자바 섬에는 자바 커피를 재배하는 홍태석 농부가 있었다. 홍태석은 "ㅋㅋㅋ 님 음수와 양수와 0의 차이도 모름?" 하면서 음수와 양수와 0을 설명해주었다.

지금까지 배운 것을 종합해서, 한국으로 돌아오는 비행기에서 규현이는 종이에 수를 N개 썼다. (규현이가 아는 가장 큰 수는 10이기 때문에, 수를 10개까지만 쓸 수 있다.)  그 다음에, 가능한 모든 N*(N+1)/2개의 구간의 합을 구했다. 이 것을 해인이는 행렬로 표현했다.

규현이가 쓴 수를 A라고 하면, A[i]는 규현이가 i번째 쓴 수이다. 그리고, S[i][j]는 A[i]부터 A[j]까지 합이 0보다 크면 +, 0이면 0, 0보다 작으면 -이다. 여기서 i는 항상 j보다 작거나 같다. 이렇게 배열을 채우면 배열에는 총 N*(N+1)/2개의 문자가 있다. (+, -, 0 중 하나) 이 S 배열이 주어졌을 때, 규현이가 쓴 N개의 수 A를 구해서 출력하면 된다. 규현이는 -10부터 10까지의 정수밖에 모르기 때문에, A도 -10부터 10까지의 정수로만 이루어져 있어야 한다.

입력

첫째 줄에 수열의 크기 N이 주어진다. N은 10보다 작거나 같은 자연수이다. 둘째 줄에는 N(N+1)/2 길이의 문자열이 주어진다. 처음 N개의 문자는 부호 배열의 첫 번째 줄에 해당하고, 다음 N-1개의 문자는 두 번째 줄에 해당한다. 마찬가지로 마지막 문자는 N번째 줄에 해당하는 문자다.

출력

첫째 줄에 수열의 원소 N개를 빈 칸을 사이에 두고 출력한다. 답이 여러 가지 일 경우에는 아무거나 출력하면 된다.

양수면, 1을 더하는 방향으로 travel하고, 음수면 -1을 더하는 방향으로 travel하기 위해 sign[i][j]를 0, +1, -1로 저장하여 활용.

조건을 확인할 때도, 1~10 또는 -1~-10을 모두 확인하면 다음 단계로 넘어가야 하는데, 한 번에 확인하기 위해 양수는 그냥, 음수는 -1을 곱해서 10과 비교.

process함수의 if(idx == n)를 만들어내는 데 만 하루가 더 걸린 듯.

idx가 n-1일 때 까지 모든 경우를 travel했으면 // 또는 true가 뜨면 끝나는 식으로 짜다 보니 조건을 다 다르게 줘야 해서

코드가 너무 지저분해졌었다. 단순히 길이의 문제가 아니라, 동일한 코드를 계속 반복해서 입력해야 한다는 문제가.

그 부분을 따로 함수로 짜서 넣으려고 하니, 함수를 정의해서 값들을 주고받는 것과 같은 코드를 반복하는 것의 비용을 비교하기가 쉽지 않아서

어떻게 짜도 만족스럽지 못한 코드가 되어서 답을 맞추고도 고민.

수정하고 나니 간단해져서 다행.

#include<iostream>
#include<string>

using namespace std;

int n; // n will be the length of input;
int sign[10][10]; // + : 1, 0 :0, - : -1;
int result[10]; // number array;

bool check(int idx){
	if (idx == 0) return true;
	int i = idx;
	int sum = result[idx];
	while(i != 0){
		i--;
		sum += result[i];
		if(sign[i][idx] * sum <= 0 && sign[i][idx] != sum) {
			return false;
		}
	}
	return true;
}
		
bool process(int idx){
	if( idx == n ) return true; 
	if( result[idx] == 0){
		if(check(idx)) return process(idx+1);
		else return false;
	} else {
		for(result[idx] = sign[idx][idx]; result[idx] * sign[idx][idx] <= 10; result[idx] += sign[idx][idx]){
			if(check(idx) && process(idx+1)){
				return true;
			}
		}
	}
	return false;
}

int main(){
	
	cin >> n;
	int index = 0;
	string temp;
	cin >> temp;
	for(int i = 0; i < n; i++){
		for(int j = i; j < n; j++){
			if(temp[index] == '+') sign[i][j] = 1;
			else if(temp[index] == '-') sign[i][j] = -1;
			else sign[i][j] = 0;
			if(i == j){
				result[i] = sign[i][j];
			}
			index++;
		}
	}

	process(0);
	
	for(int i = 0; i < n; i ++){
		cout << result[i] << " ";
	}
	
	return 0;
}

문제

두 종류의 부등호 기호 ‘<’와 ‘>’가 k개 나열된 순서열  A가 있다. 우리는 이 부등호 기호 앞뒤에 서로 다른 한 자릿수 숫자를 넣어서 모든 부등호 관계를 만족시키려고 한다. 예를 들어, 제시된 부등호 순서열 A가 다음과 같다고 하자. 

A :  < < < > < < > < >

부등호 기호 앞뒤에 넣을 수 있는 숫자는 0부터 9까지의 정수이며 선택된 숫자는 모두 달라야 한다. 아래는 부등호 순서열 A를 만족시키는 한 예이다. 

3 < 4 < 5 < 6 > 1 < 2 < 8 > 7 < 9 > 0

이 상황에서 부등호 기호를 제거한 뒤, 숫자를 모두 붙이면 하나의 수를 만들 수 있는데 이 수를 주어진 부등호 관계를 만족시키는 정수라고 한다. 그런데 주어진 부등호 관계를 만족하는 정수는 하나 이상 존재한다. 예를 들어 3456128790 뿐만 아니라 5689023174도 아래와 같이 부등호 관계 A를 만족시킨다. 

5 < 6 < 8 < 9 > 0 < 2 < 3 > 1 < 7 > 4

여러분은 제시된 k개의 부등호 순서를 만족하는 (k+1)자리의 정수 중에서 최댓값과 최솟값을 찾아야 한다. 앞서 설명한 대로 각 부등호의 앞뒤에 들어가는 숫자는 { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }중에서 선택해야 하며 선택된 숫자는 모두 달라야 한다. 

입력

첫 줄에 부등호 문자의 개수를 나타내는 정수 k가 주어진다. 그 다음 줄에는 k개의 부등호 기호가 하나의 공백을 두고 한 줄에 모두 제시된다. k의 범위는 2 ≤ k ≤ 9 이다. 

출력

여러분은 제시된 부등호 관계를 만족하는 k+1 자리의 최대, 최소 정수를 첫째 줄과 둘째 줄에 각각 출력해야 한다. 단 아래 예(1)과 같이 첫 자리가 0인 경우도 정수에 포함되어야 한다. 모든 입력에 답은 항상 존재하며 출력 정수는 하나의 문자열이 되도록 해야 한다. 

codeplus에서는 back_tracking으로 해결하는 문제로 소개되었지만, BF로도 해결할 수 있을 것 같아서 해 보니 가능.

check를 최대 2*10!번 해야 할 것 같지만, 제일 큰 수부터 내려오면서, 또는 제일 작은 수부터 키우면서 확인하면 되므로 절반 정도의 portion에 해당하는 경우만 확인하면 된다. 10!은 360만 정도여서 작은 연산 횟수는 아니지만 1차적으로는 성공. 

permutation알고리즘이 제공되어 더 편한 듯.

아래는 코드.

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

using namespace std;

vector<char> sign;

bool check(vector<int> num){
	bool result = true;
	for(int i = 0; i < sign.size(); i++){
		if(sign[i] == '<'){
			result = result && (num[i] < num[i+1]);
		}
		else{
			result = result && (num[i] > num[i+1]);
		}
	}	
	return result;
}

int main(){
	
	int n;
	cin >> n;
	
	vector<int> vec;
	char temp;
	
	for(int i = 0; i < n; i++){
		vec.push_back(9-i);
		cin >> temp;
		sign.push_back(temp); 
	}
	vec.push_back(9-n);
	
	while(!check(vec)){
		prev_permutation(vec.begin(), vec.end());
	}
	
	for(int i = 0; i <= n; i++){
		cout << vec[i];
	}
	cout << '\n';
	
	vec.clear();
	
	for(int i = 0; i <= n; i++){
		vec.push_back(i);
	}
	
	while(!check(vec)){
		next_permutation(vec.begin(), vec.end());
	}
	
	for(int i = 0; i <= n; i++){
		cout << vec[i];
	}
	return 0;
}