이것 저것 &

문제링크: https://www.acmicpc.net/problem/1939

접근방식

1. 모든 경우를 판단해주어야 하는 것을 인지

2. 근데 n이 10000으로 크기 때문에 일반적인 bfs, dfs가 불가능함을 인지

3. 그러면 방문했던 값을 저장하는 dp(메모이제이션) 방식이 가능한가 확인

4. 10,000*10,000 = 100,000,000 X 4Byte = 대략 400Mb... 즉, dp방식도 불가능

5. 이분탐색을 통해서 방문하는 범위를 줄여볼까? 생각하게 됨

문제풀이 

1. 결과값은 다리의 비용중에 하나이다.2. 최소 비용(0), 최대비용(다리 비용중 최대값)을 low, high값으로 지정하고 mid값일때, 이동가능한지 확인3. 간단한 bfs를 통해서 이동이 가능한지 확인 4. 이동이 불가하면 high값을 낮춰주고, 이동이 가능하면 low값을 올려주며 진행

이분탐색 + bfs로 해결하는 문제입니다. 아래는 정답코드입니다.

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

int n, m;
int a, b, c;
vector <pair<int, int>> vec[10001];
bool visited[10001];
int s, e;
int bfs(int cost) {
	queue <int> que;
	que.push(s);
	visited[s] = 1;

	while (!que.empty()) {

		int cur = que.front();
		que.pop();
		if (cur == e)
			return true;
		for (int i = 0; i < vec[cur].size(); i++) {
			int ncur = vec[cur][i].first;
			int ncos = vec[cur][i].second;

			if (!visited[ncur] && ncos >= cost) {
				visited[ncur] = 1;
				que.push(ncur);

			}

		}



	}

	return false;

}

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

	cin >> n >> m;
	int from, to, cost;
	int maxcost = 0;
	for (int i = 0; i < m; i++) {
		cin >> from >> to >> cost;
		vec[from].push_back(make_pair(to, cost));
		vec[to].push_back(make_pair(from, cost));
		if (cost > maxcost)
			maxcost = cost;
	}
	
	cin >> s >> e;
	
	int low = 0, high = maxcost;
	while (low <= high) {
		
		memset(visited, 0, sizeof(visited));
		int mid = (low + high)/2;

		if (bfs(mid)) {
			low = mid  + 1;
		}
		else {
			high = mid  - 1;
		}
		
	}
	cout << high << endl;

	return 0;
}

문제링크: https://www.acmicpc.net/problem/1504

다익스트라 문제입니다.

차이점은 v1과 v2를 들렸다가 n으로 도달해야한다는 점입니다.

그렇다면, 경우는 2가지 입니다.

1->v1->v2->n

1->v2->v1->n

각각의 경우에 맞춰서 다익스트라 함수를 사용해주면 됩니다.

주의할 점은 v1,v2,n 모두 도달이 가능해야 한다는 점입니다. 

아래는 정답 코드입니다.

#include <iostream>
#include <queue>
#include <vector>
#include <cstring>
using namespace std;
#define INF 2000000000

int n, e, v1, v2;
vector <pair<int, int>> vec[801];
int dist[801];

int dijkstra(int sn, int en) {
	priority_queue <pair<int, int>> pq;
	pq.push(make_pair(0, sn));

	while (!pq.empty()) {
		int cost = -1 * pq.top().first;
		int node = pq.top().second;
		pq.pop();

		for (int i = 0; i < vec[node].size(); i++) {
			int current_val = dist[node] + vec[node][i].second;
			int before_val = dist[vec[node][i].first];

			if (current_val < before_val) {
				dist[vec[node][i].first] = current_val;
				pq.push(make_pair(current_val*-1, vec[node][i].first));
			}

		}
	}

	return dist[en];

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

	cin >> n >> e;
	for (int i = 1; i <= e; i++) {
		int from, to, cost;
		cin >> from >> to >> cost;
		vec[from].push_back(make_pair(to, cost));
		vec[to].push_back(make_pair(from, cost));
	}
	cin >> v1 >> v2;

	for (int i = 1; i <= n; i++)
		dist[i] = INF; 
	dist[1] = 0;
	dijkstra(1, n);

	if (dist[v1] == INF || dist[v2] == INF || dist[n] == INF) {
		cout << -1 << endl;
		return 0;
	}


	long long result1 = 0;
	for (int i = 1; i <= n; i++)
		dist[i] = INF;
	dist[1] = 0;
	result1 += dijkstra(1,v1);
	for (int i = 1; i <= n; i++)
		dist[i] = INF;
	dist[v1] = 0;
	result1 += dijkstra(v1, v2);
	for (int i = 1; i <= n; i++)
		dist[i] = INF;
	dist[v2] = 0;
	result1 += dijkstra(v2, n);

	long long result2 = 0;
	for (int i = 1; i <= n; i++)
		dist[i] = INF;
	dist[1] = 0;
	result2 += dijkstra(1, v2);
	for (int i = 1; i <= n; i++)
		dist[i] = INF;
	dist[v2] = 0;
	result2 += dijkstra(v2, v1);
	for (int i = 1; i <= n; i++)
		dist[i] = INF;
	dist[v1] = 0;
	result2 += dijkstra(v1, n);


	cout << min(result1, result2) << endl;
	return 0;
}

문제링크: https://www.acmicpc.net/problem/1068

리프노드의 갯수를 구하는 문제입니다.

dfs 탐색을 통해서 제거된 노드의 자식노드들도 함께 제거를 하면 진행해주었습니다.

만약, 자식 노드를 가지고 있지 않다면 leaf 노드로 간주했습니다.

이때, 주의할 점은 제거된 노드의 부모노드가 leaf 노드가 될 수 있다는 점입니다.

아래는 정답 코드입니다.

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

vector <int> vec[50];
int n = 0, root;

void dfs(int n) {

	if (vec[n].size() == 0) {
		vec[n].push_back(-2);
		return;
	}
	for (int i = 0; i < vec[n].size(); i++) {
		dfs(vec[n][i]);
	}

}

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

	cin >> n;
	for (int i = 0; i < n; i++) {
		int temp;
		cin >> temp;
		if (temp == -1) 
			root = i;
		else
			vec[temp].push_back(i);
	}
	int m;
	cin >> m;

	dfs(m);
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < vec[i].size(); j++) {
			if (vec[i][j] == m)
				vec[i].erase(vec[i].begin() + j);
		}
	}
	int result = 0;
	for (int i = 0; i < n; i++)
		if (vec[i].size() == 0)
			result++;
	cout << result << endl;

	return 0;
}

문제링크: https://www.acmicpc.net/problem/15681

서브트리들의 정점 갯수를 구하는 문제

부모 노드의 경우 탐색을 해주면 안되는데,

이러한 문제를 메모이제이션을 통해서 문제를 해결할 수 있습니다.

아래는 정답 코드입니다.

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

vector <int> vec[100001];
int n, r, q;
int dp[100001];

int dfs(int n) {
	if (dp[n] != -1)
		return dp[n];
	
	int& ret = dp[n];	
	ret = 1;
	for (int i = 0; i < vec[n].size(); i++) {
		int next = vec[n][i];
		if (dp[next]!= -1)
			continue;
		ret += dfs(next);
	}
	
	return ret;
}

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

	cin >> n >> r >> q;
	for (int i = 0; i < n - 1; i++) {
		int a, b;
		cin >> a >> b;
		vec[a].push_back(b);
		vec[b].push_back(a);
	}
	for (int i = 1; i <= n; i++)
		dp[i] = -1;
	dp[r] = dfs(r);
	for (int i = 0; i < q; i++) {
		int c;
		cin >> c;
		cout << dp[c] << "\n";
	}


	return 0;
}

문제링크: www.acmicpc.net/problem/17822

개인적으로 많이 예외를 못찾아서 고민한 문제....

이런 문제일수록 구현을 간단하게 설계해야 한다.

구현해야할 것은 크게 

• 0. 입력
• 1. 원판 돌리기
• 2. 인접한 수 탐색
• 2-1. 인접한 수 지우기
• 2-2.  평균값에서 감산, 가감하기
• 3. 결과 도출

깨알팁 tip)

1. 원판 돌리기 같은경우에 시계 반대 방향은 m - k 번 시계방향으로 돌리는 것과 같다.

2. 인접한 수를 탐색하는 bfs 구현시 배열을 통해서 구현 범위를 줄일 수 있다.

아래는 정답 코드입니다.

#include <iostream>
#include <cstring>
#include <queue>
#include <cmath>
using namespace std;

int n, m, t;
int arr[51][51] = { 0, };
int result = 0;
int temp[51] = { 0, };
int visited[51][51];

int y_ar[4] = { 1,-1,0,0 };
int x_ar[4] = { 0,0,1,-1 };

//2. search
bool bfs(int y, int x) {

	memset(visited, 0, sizeof(visited));

	queue <pair<int, int>> que;
	que.push(make_pair(y, x));
	visited[y][x] = 1;

	while (!que.empty()) {
		int cy = que.front().first;
		int cx = que.front().second;
		que.pop();

		for (int i = 0; i < 4; i++) {
			int ny = cy + y_ar[i];
			int nx = cx + x_ar[i];

			if (ny < 0 || ny == n) continue;

			if (nx == m) nx = 0;
			else if (nx == -1) nx = m - 1;

			if (visited[ny][nx] == 0 && arr[ny][nx] == arr[cy][cx]) {
				que.push(make_pair(ny, nx));
				visited[ny][nx] = visited[cy][cx] + 1;
			}

		}
	}

	//erase
	bool jud = false;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
			if (visited[i][j] > 1)
				jud = true;
	if (jud == true) {
		for (int i = 0; i < n; i++)
			for (int j = 0; j < m; j++)
				if (visited[i][j] != 0)
					arr[i][j] = 0;
	}
	return jud;
}

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

	//0. init
	cin >> n >> m >> t;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
			cin >> arr[i][j];

	while (t--) {
		int x, d, k;
		cin >> x >> d >> k;
		if (d == 1)
			k = m - k;
		//1. 회전
		for (int i = x - 1; i < n; i += x) {
			
			for (int l = 0; l < k; l++) {
				for (int j = 0; j < m; j++)
					temp[j] = arr[i][j];

				for (int j = 1; j < m; j++)
					arr[i][j] = temp[j - 1];
				arr[i][0] = temp[m - 1];
			}
		}



		
		bool jud = false;
		for (int i = 0; i < n; i++)
			for (int j = 0; j < m; j++) {
				if (visited[i][j] == 0 && arr[i][j] != 0) {
					
					bool temp = bfs(i, j);
					if (temp == true)
						jud = true;
				}
			}

		//평균값 구해서 +1, -1  해주기
		if (jud == false) { 
			double sum = 0;
			double cnt = 0;
			for (int i = 0; i < n; i++)
				for (int j = 0; j < m; j++)
					if (arr[i][j] != 0 ) {
						sum += arr[i][j];
						cnt += 1;
					}
			if (cnt > 0) {
				sum = sum / cnt;
				for (int i = 0; i < n; i++)
					for (int j = 0; j < m; j++)
						if (arr[i][j] != 0) {
							if (sum > arr[i][j])
								arr[i][j] ++;
							else if (sum < arr[i][j])
								arr[i][j] --;
						}
			}
		}


	}


	//result
	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
			result += arr[i][j];
	cout << result << endl;

	
}

문제풀이: www.acmicpc.net/problem/19238

구현 순서는 

• 0. 입력값 받기
• 1. bfs로 이동거리 재기
• 2. 가장 가까운 사람에게 이동
• 3. 목적지까지 거리 도출
• 4. 목적지로 이동

주의할 점은

• 1. 이동과 동시에 도착할때, 즉 택시위치와 사람위치가 같은 경우에는 거리가 0이다.
• 2. 벽으로 막혀있어 택시가 목적지나 사람에게 도달하지 못해도 결과값은 -1이다.
• 3. 목적지에 도착하면서 연료가 바닥나는 것은 괜찮다.

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

typedef struct a {
	int y;
	int x;
}pos;

int n, m, f;
int arr[21][21] = { 0, };
int visited[21][21];
pos taxi;
vector <pos> people;
vector <pos> destination;

int y_ar[4] = { 0,1,0,-1 };
int x_ar[4] = { 1,0,-1,0 };

void bfs(int y, int x) {
	queue <pair<int, int>> que;
	que.push(make_pair(y, x));
	visited[y][x] = 1; // -1 해야함 

	while (!que.empty()) {
		int cy = que.front().first;
		int cx = que.front().second;
		que.pop();

		for (int i = 0; i < 4; i++) {
			int ny = cy + y_ar[i];
			int nx = cx + x_ar[i];

			if (ny >= 1 && ny <= n && nx >= 1 && nx <= n) {
				if (arr[ny][nx] == 0 && visited[ny][nx] == 0) {
					que.push(make_pair(ny, nx));
					visited[ny][nx] = visited[cy][cx] + 1;
				}
			}
		}
	}
}

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

	cin >> n >> m >> f;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++)
			cin >> arr[i][j];
	cin >> taxi.y >> taxi.x;
	for (int i = 0; i < m; i++) {
		int t1, t2, t3, t4;
		cin >> t1 >> t2 >> t3 >> t4;
		people.push_back({ t1,t2 });
		destination.push_back({ t3,t4 });
	}

	for (int k = 0; k < m; k++) {
		//1. 이동 거리 측정
		memset(visited, 0, sizeof(visited));
		bfs(taxi.y, taxi.x);
		/*
		for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++)
		cout << visited[i][j] << ' ';
		cout << endl;
		}*/

		//2. 가장 가까운 사람 선택
		int dis = 1000000000;
		int ny = 0, nx = 0, index = -1;
		for (int i = 0; i < people.size(); i++) {
			int y = people[i].y;
			int x = people[i].x;
			if (visited[y][x] < dis) {
				ny = y;
				nx = x;
				index = i;
				dis = visited[y][x];
			}
			else if (visited[y][x] == dis) {
				if (ny > y) {
					ny = y;
					nx = x;
					index = i;
				}
				else if (nx > x && ny == y) {
					ny = y;
					nx = x;
					index = i;
				}
			}
		}
		people.erase(people.begin() + index);
		taxi.y = ny, taxi.x = nx;
		f -= (visited[ny][nx] - 1);
		if (visited[ny][nx] == 0) {
			f = -1;
			break;
		}
		if (f <= 0)
			break;
		//cout << "y " << ny << "x " << nx << "i " << index << endl;

		//3. 목적지까지 거리 도출
		memset(visited, 0, sizeof(visited));
		bfs(taxi.y, taxi.x);
		//4. 목적지로 이동 
		int dy = destination[index].y;
		int dx = destination[index].x;
		if (visited[dy][dx] == 0) {
			f = -1;
			break;
		}
		taxi.y = dy, taxi.x = dx;
		destination.erase(destination.begin() + index);
		f -= (visited[dy][dx] - 1);
		if (f < 0)
			break;
		f += ((visited[dy][dx] - 1) * 2);
	}


	if (f <= 0)
		cout << -1 << endl;
	else
		cout << f << endl;
	return 0;
}

c++에서는 new 키워드를 사용해서 동적으로 메모리를 할당합니다.

그리고 이러한 메모리는 반드시 delete 키워드를 사용하여 메모리 할당을 해제합니다.

스마트 포인터(smart pointer)란 포인터처럼 동작하는 클래스 템플릿으로, 사용이 끝난 메모리를 자동으로 해제해 줍니다.

java에서의 가비지 컬렉션과 같은 역할을 해주는 것입니다.

C++11 이전에는 auto_ptr이라는 스마트 포인터를 사용하여 이 작업을 수행하였습니다.

하지만 C++11부터는 다음과 같은 새로운 스마트 포인터를 제공하고 있습니다.

•  unique_ptr
•  shared_ptr
•  weak_ptr

1. unique_ptr 

하나의 스마트 포인터만 특정 객체를 소유하는 것입니다. 해당 스마트 포인터는 move 함수를 통해서 소유권을 이전할  수는 있지만 복사는 불가능합니다.

unique_ptr<int> ptr01(new int(5)); // int형 unique_ptr인 ptr01을 선언하고 초기화함.

auto ptr02 = move(ptr01);          // ptr01에서 ptr02로 소유권을 이전함.

// unique_ptr<int> ptr03 = ptr01;  // 대입 연산자를 이용한 복사는 오류를 발생시킴. 

ptr02.reset();                     // ptr02가 가리키고 있는 메모리 영역을 삭제함.

ptr01.reset();                     // ptr01가 가리키고 있는 메모리 영역을 삭제함.

예시코드입니다.

#include <iostream>

#include <memory>

using namespace std;

 

class Person

{

private:

    string name_;

    int age_;

public:

    Person(const string& name, int age); // 기초 클래스 생성자의 선언

    ~Person() { cout << "소멸자가 호출되었습니다." << endl; }

    void ShowPersonInfo();

};

 

int main(void)

{

    unique_ptr<Person> hong = make_unique<Person>("길동", 29);

    hong->ShowPersonInfo();

    return 0;

}

 

Person::Person(const string& name, int age) // 기초 클래스 생성자의 정의

{

    name_ = name;

    age_ = age;

    cout << "생성자가 호출되었습니다." << endl;

}

 

void Person::ShowPersonInfo() { cout << name_ << "의 나이는 " << age_ << "살입니다." << endl; }

실행 결과입니다.

생성자가 호출되었습니다.

길동의 나이는 29살입니다.

소멸자가 호출되었습니다.

자동으로 메모리를 해제해주기 때문에 개발자가 메모리에 대한 신경을 덜 써줘도 되는 장점이 있습니다.

2. shared_ptr

하나의 특정 객체를 참조하는 스마트 포인터가 총 몇 개인지 참조하는 스마트 포인터입니다.

아래는 예시 코드입니다.

shared_ptr<int> ptr01(new int(5)); // int형 shared_ptr인 ptr01을 선언하고 초기화함.

cout << ptr01.use_count() << endl; // 1

auto ptr02(ptr01);                 // 복사 생성자를 이용한 초기화

cout << ptr01.use_count() << endl; // 2

auto ptr03 = ptr01;                // 대입을 통한 초기화

cout << ptr01.use_count() << endl; // 3  

make_shared() 함수를 사용하면 shared_ptr 인스턴스를 안전하게 생성할 수 있습니다.

예시 코드입니다.

shared_ptr<Person> hong = make_shared<Person>("길동", 29);

cout << "현재 소유자 수 : " << hong.use_count() << endl; // 1

auto han = hong;

cout << "현재 소유자 수 : " << hong.use_count() << endl; // 2

han.reset(); // shared_ptr인 han을 해제함.

cout << "현재 소유자 수 : " << hong.use_count() << endl; // 1

3. weak_ptr 

하나 이상의 shared_ptr 인스턴스가 소유하는 개체에 대한 접근을 제공하지만 소유자의 수에는 포함되는 않는 스마트 포인터입니다.

4. enable_shared_from_this

 이 친구는 아래와 같은 형태로 사용된다.

class type : public std::enable_shared_from_this<type>
{
public:
    type(){ std::cout << __FUNCTION__ << std::endl;}
    ~type(){ std::cout << __FUNCTION__ << std::endl;}
     
    std::shared_ptr<type> getPtr()
    {
        //return std::shared_ptr<type>(this);
        return shared_from_this();
    }   
};

정상적인 동작을 위해서 사용한다.

아래코드를 보자

#include <iostream>
#include <memory>
 
class type
{
public:
    type(){ std::cout << __FUNCTION__ << std::endl;}
    ~type(){ std::cout << __FUNCTION__ << std::endl;}
     
    std::shared_ptr<type> getPtr()
    {
        return std::shared_ptr<type>(this);
    }   
};
 
int main()
{
    type *p = new type;
     
    std::shared_ptr<type> ptr1(p); //p object를 가르키는 shared_ptr 생성자 호출
    std::cout <<"ptr1.use_count(): " << ptr1.use_count() << std::endl;
 
    // ptr2에 ptr1에서 객체의 주소를 return 받아 할당한다.
    std::shared_ptr<type> ptr2 = ptr1->getPtr();
    std::cout <<"ptr2.use_count(): " << ptr2.use_count() << std::endl;
     
    return 0;
}

type이라는 클래스 하나를 동적선언하고 ptr1에 할당한다. 그리고 ptr1이 사용되지 않기에 메모리를 소멸시키게 되는데 그렇기 때문에 ptr2에서는 오류가 발생한다. (Segmentation fault) 

이를 방지하고자 사용된다.

#include <iostream>
#include <memory>
 
class type : public std::enable_shared_from_this<type>
{
public:
    type(){ std::cout << __FUNCTION__ << std::endl;}
    ~type(){ std::cout << __FUNCTION__ << std::endl;}
     
    std::shared_ptr<type> getPtr()
    {
        //return std::shared_ptr<type>(this);
        return shared_from_this();
    }   
};
 
int main()
{
    type *p = new type;
     
    std::shared_ptr<type> ptr1(p); //p object를 가르키는 shared_ptr 생성자 호출
    std::cout <<"ptr1.use_count(): " << ptr1.use_count() << std::endl;
 
    // ptr2에 ptr1에서 객체의 주소를 return 받아 할당한다.
    std::shared_ptr<type> ptr2 = ptr1->getPtr();
    std::cout <<"ptr2.use_count(): " << ptr2.use_count() << std::endl;
     
    return 0;
}

shared_ptr을 추가할 경우에는 std::enable_shared_from_this 클래스로부터 상속을 받게되는 구조이다.

출처: www.tcpschool.com/cpp/cpp_template_smartPointer
출처: https://chipmaker.tistory.com/entry/enablesharedfromthis-정리 [CHIPMAKER]

문제링크: www.acmicpc.net/problem/12996

dp 문제입니다.

아이디어 도출이 어려운 문제지만 구현난이도는 최하입니다.

3명의 친구들이 불러야 하는 곡수와 전체곡의 갯수가 주어지기 때문에 

long long dp[51][51][51][51]; // s,dotorya, kesakiyo, hongjun7 라는 dp배열을 만들어 메모이제이션 하면 됩니다.

dp[s][d][k][h]는 s곡 남았을때, 1번 친구가 d개 남고, 2번 친구가 k개 남고, 3번 친구가 h개 남았을때의 최대값을 저장합니다.

아래는 정답코드입니다. 막상 구현하니 너무 간단하네요.

주의할 점은 long long을 사용해야 한다는것입니다. 

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

long long dp[51][51][51][51]; // s,dotorya, kesakiyo, hongjun7

long long solved(int s, int d, int k, int h) {

	if (s == 0) {
		if (d == 0 && k == 0 && h == 0)
			return 1;
		else
			return 0;
	}
	
	long long& ret = dp[s][d][k][h];
	if (ret != -1)
		return ret;
	ret = 0;

	ret += solved(s - 1, d - 1, k, h);
	ret += solved(s - 1, d, k - 1, h);
	ret += solved(s - 1, d, k, h - 1);

	ret += solved(s - 1, d - 1, k - 1, h);
	ret += solved(s - 1, d - 1, k, h - 1);
	ret += solved(s - 1, d, k - 1, h - 1);

	ret += solved(s - 1, d - 1, k - 1, h - 1);

	ret %= 1000000007;
	return ret;
}

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

	int s, d, k, h;
	cin >> s >> d >> k >> h;

	memset(dp, -1, sizeof(dp));
	cout << solved(s, d, k, h) << endl;

	return 0;
}