https://school.programmers.co.kr/learn/courses/30/lessons/43105?language=cpp

 

프로그래머스

SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프

programmers.co.kr

이 문제는 프로그래머스 알고리즘 고득점 Kit의 문제이다 
Programmers LV3 문제 치고는 접근 법이 매우 쉬웠다 이 문제의 경우

이렇게 생긴 벡터가 제공이 된다 

실제 자료형은 이렇게 제공이 되는데
이 문제는 똑같은 삼각형을 만들고 나의 이전 행에 있는 나를 기준으로 양대각선의 있는 값중 나와의 합이 최대가 되는 애와의 합을 내가 현재 있는 위치에 넣는 것이다

즉 이그림을 보면 3번 째줄에 와서 보면 1을 기준으로 내가 선택할 수 있는 것은 이전행의 10과 15이다 이중 두값중 1과 합했을때 큰값을 16임으로 나의 위치에 16을 넣어준다 이를 계속 반복 해주면 된다

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

int solution(vector<vector<int>> triangle) {
    vector<vector<int>> dpV;
    vector<int> rowV1;
    dpV.push_back(rowV1);
    dpV[0].push_back(triangle[0][0]);
    for(int i=1; i<triangle.size(); i++){
        vector<int> rowV;
        dpV.push_back(rowV);
        
        for(int j=0; j<triangle[i].size(); j++){
            if(j==0){
                dpV[i].push_back(dpV[i-1][j]+triangle[i][j]);
            }
            else if(j==triangle[i].size()-1){
                dpV[i].push_back(dpV[i-1][j-1]+triangle[i][j]);
            }
            else{
                dpV[i].push_back(max(triangle[i][j]+dpV[i-1][j-1],triangle[i][j]+dpV[i-1][j]));
            }
        }
    }
    int answer = 0;
    for(int i=0; i<dpV[triangle.size()-1].size(); i++){
        answer=max(answer,dpV[triangle.size()-1][i]);
    }
    return answer;
}

위에 코드를 보게 되면 똑같은 이차원 벡터를 만들어 주고 해당 벡터를 dp 로 놓고 이전 행과의 합을 계속 누적 하고 마지막행에서 최댓값을 구하는 방법으로 코드를 구현 했다

'백준(코테준비) > DP' 카테고리의 다른 글

백준 17404 / CPP / Dp  (0) 2025.01.16
백준 17396 / CPP  (0) 2024.11.28
백준 17396 /CPP 다익스트라  (0) 2024.10.17
백준 1956/C++  (0) 2024.10.17
백준 2133 / c++  (0) 2024.08.15

 

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

이 문제의 경우 전형 적인 다익스트라 알고리즘으로 풀 수 있을거 같았다 그 이유는 첫시작 점이 0 그리고 endPoint인 n-1 까지 가는 것으로 정해졌기에

void djikstraSolution(int start) {
	int startNode = start;
	int toCost = 0;
	djikstra_pq.push({ toCost,start });

	while (!djikstra_pq.empty()) {
		int toVertex = djikstra_pq.top().second;
		long long toCost = djikstra_pq.top().first;
		djikstra_pq.pop();

		if (distanceV[toVertex] < toCost)
			continue;

		for (int i = 0; i < edgeList[toVertex].size(); i++) {
			int nextVertex = edgeList[toVertex][i].second;
			long long nextCost = edgeList[toVertex][i].first;
			if (distanceV[nextVertex] > toCost + nextCost && (canGo[nextVertex] || nextVertex==n-1)) {
				distanceV[nextVertex] = toCost + nextCost;
				djikstra_pq.push({ toCost + nextCost,nextVertex });
			}
		}

	}
}

굳이 플로이드  와샬로 전체 의 거리는 구할 필요가 없기 때문이다 

항상 다익스트라에서 쓰는 로직과 비슷하다 일단 StartVertex를 StarVertex까지의 거리가 0이라 두고 큐에다가 넣는다

그후 edgeList에서  startNode와 연결된 모든 노드들과 계산하여 거리를 구한후 priority queue에 넣는다 이를 반복하면 결국에 마지막 노드까지 가는거리가 최단거리로 완성이 된다.

이문제의 경우 단 djikstra를 풀때 조건이 하나가 추가되는데 해당 vertex의 시야값이 1이면 가지 않는 것이다

#include<iostream>
#include<queue>
#include<algorithm>
using namespace std;
#define INF 1234987654321
priority_queue < pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> djikstra_pq;
vector<pair<int, long long>> edgeList[300000];
vector<long long> distanceV(300000);
bool canGo[300000] = { 0, };
int n, m;
void djikstraSolution(int start) {
	int startNode = start;
	int toCost = 0;
	djikstra_pq.push({ toCost,start });

	while (!djikstra_pq.empty()) {
		int toVertex = djikstra_pq.top().second;
		long long toCost = djikstra_pq.top().first;
		djikstra_pq.pop();

		if (distanceV[toVertex] < toCost)
			continue;

		for (int i = 0; i < edgeList[toVertex].size(); i++) {
			int nextVertex = edgeList[toVertex][i].second;
			long long nextCost = edgeList[toVertex][i].first;
			if (distanceV[nextVertex] > toCost + nextCost && (canGo[nextVertex] || nextVertex==n-1)) {
				distanceV[nextVertex] = toCost + nextCost;
				djikstra_pq.push({ toCost + nextCost,nextVertex });
			}
		}

	}
}
int main() {
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		cin >> canGo[i];
		canGo[i] = !canGo[i];
	}

	for (int i = 0; i < m; i++) {
		int from, to, cost;
		cin >> from >> to >> cost;
		edgeList[from].push_back({ cost,to });
		edgeList[to].push_back({ cost,from });
	}
	distanceV.assign(n , INF);
	djikstraSolution(0);
	if (distanceV[n - 1] >= INF)
		cout << -1;
	else
		cout << distanceV[n-1];
}


전체 코드는 위와 같다

'백준(코테준비) > DP' 카테고리의 다른 글

백준 17396 / CPP  (0) 2024.11.28
프로그래머스 LV3 / 정수 삼각형 /DP/ C++  (1) 2024.11.21
백준 1956/C++  (0) 2024.10.17
백준 2133 / c++  (0) 2024.08.15
백준 2225 / CPP  (0) 2024.08.15

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

이 문제의 경우 전형적인 플로이드 워셜 알고리즘을 사용 하여 구현한다
핵심이 되는  부분은

void floyd() {
	//k는 경유점
	for (int k = 1; k <= v; k++) {
		for (int i = 1; i <= v; i++) {
			for (int j = 1; j <= v; j++) {
				dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j]);
			}
		}
	}
}

k즉 i to k , k to j 즉 어떠한 정점 까지 갈때 중간에  거치는 지점이다 즉 계속 거치는 지점을 업데이트 해주면서 최소 거리를 구하는게 플로이드 워셜의 로직이다

#include <iostream>
#define INF 987654321
using namespace std;
int dp[401][401];

int v, e;
void floyd() {
	//k는 경유점
	for (int k = 1; k <= v; k++) {
		for (int i = 1; i <= v; i++) {
			for (int j = 1; j <= v; j++) {
				dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j]);
			}
		}
	}
}
int main() {
	int maxValue = INF;
	cin >> v >> e;
	for (int i = 1; i <= v; i++) {
		for (int j = 1; j <= v; j++) {
			if (i == j)
				dp[i][j] == 0;
			else
				dp[i][j] = INF;
			
		}
	}
	for (int i = 0; i < e; i++) {
		int from, to, value;
		cin >> from >> to >> value;
		dp[from][to] = value;
	}

	floyd();

	for (int i = 1; i <= v; i++) {
		for (int j = 1; j <= v; j++) {
			if (dp[i][j] + dp[j][i] < maxValue && !(i==j)) {
				maxValue = dp[i][j] + dp[j][i];
			}
		}
	}
	if (maxValue >= INF) {
		cout << -1;
	}
	else {
		cout << maxValue;
	}
}

'백준(코테준비) > DP' 카테고리의 다른 글

프로그래머스 LV3 / 정수 삼각형 /DP/ C++  (1) 2024.11.21
백준 17396 /CPP 다익스트라  (0) 2024.10.17
백준 2133 / c++  (0) 2024.08.15
백준 2225 / CPP  (0) 2024.08.15
백준 5972  (0) 2024.08.08

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

이 문제의 경우 처음에 이해하기 좀 어려웠었다

 

이  문제의경우 일단 이경우를 생각 해주어야 한다 길이 2짜리공간에 타일을 넣어서 채울 수 있는 경우의 수는 3이다 4짜리 타일을  채우는 경우의  수는 2가 더있다

#include <iostream>
using namespace std;
int main()
{
    int n;
    cin >> n;

    int dp[31] = { 0 };

    dp[0] = 1;
    dp[2] = 3;

    for (int i = 4; i <= n; i++)
    {
        dp[i] = dp[i - 2] * 3; 
        for (int j = 4; j <= i; j += 2)
        {
            dp[i] += dp[i - j] * 2; 
        }
    }

    cout << dp[n];
    return 0;
}

'백준(코테준비) > DP' 카테고리의 다른 글

백준 17396 /CPP 다익스트라  (0) 2024.10.17
백준 1956/C++  (0) 2024.10.17
백준 2225 / CPP  (0) 2024.08.15
백준 5972  (0) 2024.08.08
백준 11404/c++  (0) 2024.08.02

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

이 문제의 경우 점화식을 세우기 빡셌다 이문제의 경우 일단 대충의 로직은

이 상태에서 시작하게 된다 맨위에 파란부분은 수고 그이후의 행들은 해당 숫자를 만드는 데 사용하는 수의 개수를 의미합니다 현재 1행에 숫자 1들이 들어간 이유는 각 수를 만드는데는 자기자신 하나만 필요하기 때문입니다.

 

자 그리고 다음 행을 봅시다
0을 만드는데는 어차피 0 하나로 밖에 못만드니 

이렇게 채워 줍시다
그다음 2행을 채우게 되면 숫자 2개로 해당 수를 만드는 방법을 봅시다 1은 1+0 과 0+1 로만들 수 있습니다 2는 1+1과 0+2와  2+0으로 만들 수있습니다 우리는 여기서 알수있는게 해당행의 이전행에서의 나자신까지의 합을 모두 더해주면 된다는 것을 알수 있습니다. 0을 선택하게 되면 자동을 2가선택 1을 선택하면 자동으로 1이선택 2를 선택하면 자동으로 0이선택되니 이전행의 자신 열까지의 합을 넣어주면 됩니다

그후 3행은 숫자 3개를 이용하는 것이기에 이전 행에서 2개를 선택한 로직에서 추가로 확장하면 됩니다 숫자 3개로 1을 만드는 방법은 (0+0)+1 , (1+0)+0,  (0+1)+0 이고 2의경우는 이전에 2개를 선택한거에 추가로 해당 수를 제외한 수를 더해주면 자동으로 더해지게 됨으로 이전행의 열들의 값을 더해주면 됩니다

결과적으로 그림이 이렇게 되서 완료가 됩니다.
해당 코드를 구현하면

#include <iostream>
using namespace std;
long long m = 1000000000;
long long dp[204][204];
int main() {
	long long n, k;
	cin >> n >> k;

	for (int i = 0; i <= n; i++) {
		dp[1][i] = 1;
	}


	for (int i = 2; i <= k; i++) {
		for (int j = 0; j <= n; j++) {
			for (int z = 0; z <= j; z++) {
				dp[i][j] += dp[i - 1][z];
			}
			dp[i][j] %= m;
		}
	}
	cout << dp[k][n];
}

'백준(코테준비) > DP' 카테고리의 다른 글

백준 1956/C++  (0) 2024.10.17
백준 2133 / c++  (0) 2024.08.15
백준 5972  (0) 2024.08.08
백준 11404/c++  (0) 2024.08.02
백준 2294/C++  (0) 2024.08.01

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

 

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
#define INF 987654321
using namespace std;
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> djikstra_pq;
vector<int> distanceV(50001);
vector<pair<int, int>> cowData[50001];
int n, m;
void djikstra(int start) {
	djikstra_pq.push({ 0,start });
	distanceV[start] = 0;

	while (!djikstra_pq.empty()) {
		int costTo = djikstra_pq.top().first;
		int toIdx = djikstra_pq.top().second;
		djikstra_pq.pop();

		if (distanceV[toIdx] < costTo)
			continue;
		for (int i = 0; i < cowData[toIdx].size(); i++) {
			int nextCost = cowData[toIdx][i].first;
			int nextVertex = cowData[toIdx][i].second;
			if (distanceV[nextVertex] > nextCost + costTo) {
				distanceV[nextVertex] = nextCost + costTo;
				djikstra_pq.push({nextCost+costTo,nextVertex});
			}
		}
	}
}
int main() {
	cin >> n >> m;
	int from, to, cost;
	for (int i = 0; i < m; i++) {
		cin >> from >> to >> cost;
		cowData[from].push_back({ cost,to });
		cowData[to].push_back({ cost,from });
	}
	distanceV.assign(50001, INF);
	djikstra(1);
	cout << distanceV[n];
}

그냥 이문제는 다익스트라 문제이다 다익스트라를 많이 풀어보신 분이라면 쉽게 풀 수 있었을 것이다

'백준(코테준비) > DP' 카테고리의 다른 글

백준 2133 / c++  (0) 2024.08.15
백준 2225 / CPP  (0) 2024.08.15
백준 11404/c++  (0) 2024.08.02
백준 2294/C++  (0) 2024.08.01
백준 14284  (1) 2024.07.25

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

이 문제는 플로이드 워셜 알고리즘을 다룬다
다익스트라는 하나의 점에서 부터 다른 vertex까지의 최단 경로를 구하는 것이라면
플로이드 워셜은 전체 점에서의 최단 경로를 구하는 문제이다

 

다익스트라 알고리즘의 경우 우선순위 큐에 계속 넣어서 경로의 최솟값들을 소모시키면서 다른 vertex들과의 비용을 업데이트 해줬다.

단 플로이드 워셜 알고리즘의 경우 모든 점을 업데이트 해줘야하므로 dp를 통해 순차 탐색을 진행해준다

	for (int k = 1; k <= n; k++) {
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j]);
			}
		}
	}

핵심 로직은 이부분이다 K라는 경유점을 통해서 i to j 의 값과 기존에 i to j의 값을 비교해서 더작으면 넣어주는게 로직이다 .

#include <iostream>
#include <algorithm>
#define INF 987654321
using namespace std;

int n;
int dp[101][101];
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	cin >> n;
	int m;
	cin >> m;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			if (i == j)
				dp[i][j] = 0;
			else
				dp[i][j] = INF;
		}
	}
	for (int i = 0; i < m; i++) {
		int from, to, cost;
		cin >> from >> to >> cost;
		dp[from][to] = min(dp[from][to], cost);
	}
	//k는 경유점
	for (int k = 1; k <= n; k++) {
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j]);
			}
		}
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			if (dp[i][j] == INF) {
				cout << 0 << ' ';
				continue;
			}
			cout << dp[i][j] << ' ';
		}
		cout << '\n';
	}
	return 0;
}

'백준(코테준비) > DP' 카테고리의 다른 글

백준 2225 / CPP  (0) 2024.08.15
백준 5972  (0) 2024.08.08
백준 2294/C++  (0) 2024.08.01
백준 14284  (1) 2024.07.25
백준 11054  (3) 2024.07.25

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

이 문제는 dp의 기본적인 문제이다 이문제의 경우 동전의 종류 와 만들 수 있는 동전의 크기가 있다.
이문제는 내가 현재 들고있는 동전을 추가해서 현재의 가치를 만들때 최소한의 동저만 쓴경우만 선택해서 진행한다
한번 표로 봐보자

우리가 가진 동전으로 0원을 만들수 있는 경우의 수는 0 이다 만들수 없다
1원은 현재 1원하나로 만들고 5원 12원으로 만들기 위해서는 -4원 -11원 이 있어야 만들 수 있는데 해당 원수는 없으니 제외한다

자 쭉쭉 진행 되었을 때를 보자

이 상태 에서 10원을 만든다고 가정해보자 9원에서 1원을 추가해서 만드는 방법하나와 5원에서 5원을 하나 추가하는 방법이 있다 이경우 5원에서 동전 하나를 추가해서 만드는게 동전 2개이므로 5원에서 현재 5원을 선택해서 +1 해주는 방식으로 2를 넣어준다 

이문제의 점화식은

arr[i]=min(arr[i], arr[i - coin[j]] + 1);
내가 현재 선택한 동전을 추가했을 때 나올수 있는 경우의 수중 최소를 선택해주면 된다 전체 코드는 아래와 같다

#include <iostream>
#include <algorithm>
using namespace std;
#define INF 987654321
int n, k;
int coin[100];
int arr[10000] = { 0, };
int main() {
	cin >> n >> k;
	for(int i=0;i<n; i++){
		cin >> coin[i];
	}
	for (int i = 1; i <= k; i++) {
		arr[i] = INF;
		for (int j = 0; j < n; j++) {
			if (i - coin[j] >= 0) {
				arr[i]=min(arr[i], arr[i - coin[j]] + 1);
			}
		}
	}
	if (arr[k]==INF)
		cout << -1;
	else
		cout << arr[k];
}

'백준(코테준비) > DP' 카테고리의 다른 글

백준 5972  (0) 2024.08.08
백준 11404/c++  (0) 2024.08.02
백준 14284  (1) 2024.07.25
백준 11054  (3) 2024.07.25
백준 9251  (0) 2024.07.17

+ Recent posts