[COS Pro] 1급 5차 C++ (n진법,재귀)

63분 한문제 못풀었따~

 

---

못 푼 문제 : 문제7) 재귀..

그래프의 노드 수와 노드 연결 순서가 주어질 때, 몇 번째 연결에 사이클이 생기는지 알고 싶습니다. 예를 들어, 노드가 3개이고 노드를 [[1, 2], [1, 3], [2, 3]] 순으로 연결한다면 아래 그림과 같습니다.

따라서 3번째 연결에서 사이클이 생깁니다.

그래프의 노드 수 n, 노드 연결 순서 connections가 매개변수로 주어질 때, 몇 번째 연결에 사이클이 생기는지 return 하도록 solution 함수를 작성하려 합니다. 빈칸을 채워 전체 코드를 완성해주세요.

 

매개변수 설명
그래프의 노드 수 n, 노드 연결 순서 connections가 solution 함수의 매개변수로 주어집니다.
* 그래프의 노드 수 n은 3 이상 10 이하입니다.
* connections은 길이가 3 이상 50 이하인 배열입니다.
* connections 배열의 각 행은 [a, b]는 a번 노드와 b번 노드를 연결한다는 의미입니다.
* 항상 사이클이 생기는 경우만 주어집니다.

return 값 설명
몇 번째 연결에서 사이클이 생기는지 return 합니다.

예시 : 3, [[1, 2], [1, 3], [2, 3]]  답 3

 

---

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

int find(vector<int> &parent, int u) {
	if(u == parent[u])
		return u;

	parent[u] = find(parent, parent[u]);
	return parent[u];
}

bool merge(vector<int> &parent, int u, int v) {
	u = find(parent, u);
	v = find(parent, v);

	if(u == v)
		return true;

	parent[u] = v;
	return false;
}

int solution(int vertex, vector<vector<int>> connections) {
	int answer = 0;

	vector<int> parent(vertex+1);
	for(int i = 1; i <= vertex; i++)
		parent[i] = i;

	for(int i = 0; i < connections.size(); i++)
		if(merge(parent, connections[i][0], connections[i][1])) {
			answer = i + 1;
			break;
		}

	return answer;
}

 

---

 

문제 6)

p 진법으로 표현한 수란, 각 자리를 0부터 p-1의 숫자로만 나타낸 수를 의미합니다. p 진법으로 표현한 자연수 두개를 더한 결과를 q 진법으로 표현하려 합니다.

예를 들어, 3진법 수 112001과 12010을 더한 결과를 8진법으로 나타내면 1005입니다.

solution 함수의 매개변수로 p 진법 자연수를 담은 문자열 s1, s2와 두 수를 나타내는 진법의 기수 p, 두 수의 덧셈 결과를 표현할 진법의 기수 q가 매개변수로 주어집니다. p진법으로 표현된 두 수를 더한 결과를 q 진법으로 나타낸 값을 return 하도록 solution 함수를 완성해주세요.

 

매개변수 설명

p 진법으로 자연수를 담은 문자열 s1, s2와 두 수를 표현한 진법의 기수 p, 두 수의 덧셈 결과를 표현할 진법의 기수 q가 solution 함수의 매개변수로 주어집니다.
* p와 q는 2 이상 10 이하인 자연수입니다.
* s1과 s2의 길이는 1 이상 9 이하입니다.
* s1과 s2의 원소는 '0', '1', '2', …, ‘p-1’로만 구성됩니다.
* s1이나 s2가 ‘0’인 경우는 주어지지 않습니다.

 

return 값 설명

두 수를 더한 결과를 q 진법으로 나타낸 값을 문자열로 return 하도록 solution 함수를 완성해주세요.

 

---

// 다음과 같이 include를 사용할 수 있습니다.
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int pow(int x, int y) {
	int ret = 1 ;
	for(int i=0; i<y; i++) {
		ret *= x;
	}
	return ret;
}

int to10(string num, int n) {
	int ret = 0;
	for(int i=0; i<num.size(); i++){
		ret += (num[num.size()-1-i] - '0') * pow(n,i); 	
	}
	return ret;
}


string ton(int num, int n) {
	string ret = "";
	vector<int> v;
	
	while(num >= n) {
		v.push_back(num%n);
		num = num / n;
	} v.push_back(num);
	reverse(v.begin(),v.end());
	
	for(int i : v) ret.push_back(i+'0');
	return ret;
}

string solution(string s1, string s2, int p, int q) {
    
    string answer = ton(to10(s1,p)+to10(s2,p),q);
    return answer;
}

---

정답 -> 재귀로 n진법 만들기

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

using namespace std;

int numbers_int[] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
string numbers_char = "0123456789";

const int char_to_int(char ch) {
    for (int i = 0; i < 10; i++)
        if (ch == numbers_char[i])
            return numbers_int[i];
}

const char int_to_char(int val) {
    for (int i = 0; i < 10; i++)
        if (val == numbers_int[i])
            return numbers_char[i];
}

string convert_scale(int num, int q) {
    if (num == 0) return "";
    return convert_scale(num / q, q) + int_to_char(num % q);
}

int parse_decimal(string s, int p) {
    int num = 0;
    for (int i = s.size() - 1, mul = 1; i >= 0; i--, mul *= p)
        num += char_to_int(s[i]) * mul;
    return num;
}

string solution(string s1, string s2, int p, int q) {
    int num1 = parse_decimal(s1, p);
    int num2 = parse_decimal(s2, p);
    string answer = convert_scale(num1 + num2, q);
    return answer;
}

---

문제9)

못하는 재귀로 겨우겨우 했더니 queue를 이용한 간단한 방법이 있었다... ㄹㅇ감탄

 

정수 number와 target이 주어졌을 때, 다음 세 연산을 이용해 number를 target으로 만들려 합니다.

연산 1. 1을 더합니다.
연산 2. 1을 뺍니다.
연산 3. 2를 곱합니다.

정수 number와 target이 매개변수로 주어질 때, number로 target으로 만들려면 연산을 최소 몇 번 해야 하는지 return 하도록 solution 함수를 작성해 주세요.

 매개변수 설명

두 정수 number와 target이 solution 함수의 매개변수로 주어집니다.
* number와 target은 0 이상 10,000 이하입니다.

return 값 설명

number를 target으로 만들려면 연산을 최소 몇 번 해야 하는지 return 합니다.

---

// 다음과 같이 include를 사용할 수 있습니다.
#include <iostream>
#include <vector>
#include <string>

using namespace std;
int ret = 10000;
int oper(int current, int target, int cnt) {
	
	if(current == target) {
		ret = min(ret, cnt);
		return 0;
	}
	if(ret >= cnt)oper(current + 1, target, cnt+1);
	if(ret >= cnt)oper(current - 1, target, cnt+1);
	if(ret >= cnt)oper(current * 2, target, cnt+1);
	
	return 0;
}

int solution(int number, int target) {
	ret = 10000;
	oper(number,target,0);
	int answer = ret;
	return answer;
}

---

정답 

---

#include <vector>
#include <queue>

using namespace std;

int solution(int number, int target) {
	int answer = 0;

	vector<int> visited(10001, 0);
	queue<int> q;
	q.push(number);
	visited[number] = 1;

	while(!q.empty()) {
		int x = q.front();
		q.pop();

		if(x == target)
			break;

		if(x+1 <= 10000 && visited[x+1] == 0) {
			visited[x+1] = visited[x]+1;
			q.push(x+1);
		}
		if(x-1 >= 0 && visited[x-1] == 0) {
			visited[x-1] = visited[x]+1;
			q.push(x-1);
		}
		if(2*x <= 10000 && visited[2*x] == 0) {
			visited[2*x] = visited[x]+1;
			q.push(2*x);
		}
	}

	answer = visited[target]-1;
	return answer;
}