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

 

2293번: 동전 1

첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다.

www.acmicpc.net

DP는 해도해도 실력이 확실히 점화식을 잘세워야 하는 것 같다 이문제의 경우 점화식이 무조건 필요했는데 사실 문제 이해가 잘 안 갔어서 푸는데 4시간 걸렸다......알고리즘 빨리 풀어야하는데  이문제의 경우는 일단 예시로 나온

을 기준으로 하면 동전의 갯수 만큼의 경우의 수를 생각 해주어야 했다

맨처음 첫번째 동전인 1원만으로 1원 부터 10원 까지 만들 수 있는 경우의 수를 dp 에 채워 준다 그 후

2원 부분의 행을 채워 줘야한다 2원 부분의 행은 무조건 해당 단계에서 2원만을 사용해서 그 해당 수를 만들어 주는 경우의 수다 이부분에서는 5원에 대한 생각은 해주지 않습니다 2원의 행은 2원과 1원 부분만을 이용해서 그 해당 원수를 만드는 것 입니다

이에 이렇게 쭉 구하면서 5원 부분까지 가면 10월을 만들 때 딱 5원을 추가하여 10원을 만드는 경우의 수는 5원으로 5원을 만든 경우의수와 1원과 2원으로 만든 5원의 경우의 수와 1원으로만 만든 5원의 경우의 수를 더하여 4가지가 나온다 이렇게 생각을 하게 되면 이문제의 dp를 추정 할 수 있습니다 하지만 위에거를 그대로 사용하여 2차원 배열을 사용하게 되면 4mb를 초과하는 사태가 발생하여 틀렸습니다가 생겼습니다 이에 우리는 위에 식을 이용해 점화식을 더간단한 점화식을 만들어야합니다.

점화식을 세울때 우리가 봐야할 부분은 합계입니다  2원에서의 합계를 보시지요 자 기존에 1원에서 만 만들었던 값에서 자기자신을 뺀 부분에서의 값을 더해줌으로서 지금 원을 만드는데 2원을 넣었다고 가정했을 때의 경우의 수를 더해주게 됩니다.

각 2원의 행을 예시로 봅시다 2원의 행은 지금 계속 표를 보면 0원에서 2원

dp[2] += dp [0]   2

dp[3] += dp [1]   2

dp[4] += dp [2]   3

즉 dp[2] 의경우 1원으로 만든 경우의 수 + 0원의 경우의 수가 됩니다 이유는 0원에서 2원을 고름으로서 2원을 만들 것이기 때문입니다 이에

dp 배열의 합계 부분들은 이런식으로 값이 바뀌게 됩니다.

즉 먼저 하나의 코인으로 해당 값을 만든 다고 가정하고 그 경우의 수에서 나의 동전값을 뺏을 때의 경우의 수를 더해줘야 합니다 

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

백준 12865  (0) 2023.06.13
백준 9095  (0) 2023.05.25
백준 12865  (0) 2023.01.08
백준 9465  (0) 2022.12.28
백준 11052  (0) 2022.12.26

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

 

1074번: Z

한수는 크기가 2N × 2N인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다. N > 1인 경우, 배열을

www.acmicpc.net

이 문제는 앞으로 보나 뒤로 보나 분할 정복을 쓸거 같은 문제였다 처음에는 배열의 값을 분할정복을 이용해서 넣어주려했으나 이문제의 배열만큼의 크기를 선언하려면은 이문제의 메모리 제한을 넘는 배열이 생성 된다 이에 이문제는 소속 해 있는 행과 렬을 계산 해주면서 푸는 문제가 되겠다.

#include <iostream>
#include <cmath>
using namespace std;
int n, r, c;
int ans;
void solution(int row , int col , int size) {
	if (r == row && c == col) {
		cout << ans;
		return;
	}
	if (r >= row && r < row + size && c >= col && c < col +size)
	{
		solution(row, col, size / 2);//1사분면
		solution(row, col + size/2, size / 2); //2사분면
		solution(row + size/2, col, size / 2); // 3사분면
		solution(row + size / 2, col + size / 2, size / 2); //4사분면
	}
	else {
		ans += size * size;
	}
}
int main() {
	cin >> n >> r >> c;
	solution(0, 0, pow(2,n));
}

이 문제의 설명을 하자면

일단 초기값을 입력 받았을때 size의 크기의 col이 0~7 row가 0~7에 있는지 확인한다 그후 n과 r이 있는 사분면을 만났을 때 그 4분면을 4개로 쪼갠후 자신의 값이 포함되어 있는 4분면 쪽으로 들어가 답이 나올 때 까지 쪼개면서 결국에는 size가 1이 될 때까지 4분면의 4분면...을 찾아 들어간다 만약 4분면에 포함이 안되면 그 4분면의 크기만큼 ans값에 더해준다. 왜냐면 그만큼의 크기를 뛰어넘은것으로 생각되기 때문이다 

이에 이렇게 풀면 분할정복으로 이문제를 풀 수 있다

'백준(코테준비) > 분할정복' 카테고리의 다른 글

백준 5639  (1) 2023.06.22
백준 2630  (1) 2023.05.25
백준 1764  (0) 2023.02.21

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

 

1715번: 카드 정렬하기

정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장

www.acmicpc.net

이 문제의 경우 생각하는건 쉬웠다 사실 어떠한 배열에서 가장 작은 2개를 선택한 후 이를 그다음 작은애랑 더해주면 되는 문제였다 그래서 이문제를 나는 큐를 사용해서 풀고 싶었다. priority queue를 사용해서 풀고 싶었기 때문에 사실 데큐를 사용해서 풀수도 있는 문제기는 하다 데큐로 푸는 방식은 그냥 입력받은애들을 작은애들 순으로 소팅한 후 더한후 front에 넣고 다시 front에서 두개를 더한후 넣고 다시 두개 팝해서 넣고 하는 방식으로 하면 된다 이러한 로직도 priority queue에 적용이 되기 때문에 사용하면 된다 소스코드는 이렇게 된다

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
priority_queue<int, vector<int>, greater<int> > pq;
int main() {
	int card;
	int n;
	int sum = 0;
	cin >> card;
	for (int i = 0; i < card; i++) {
		cin >> n;
		pq.push(n);
	}

	while (pq.size() > 1) {
		int x, y;
		x = pq.top();
		pq.pop();
		y = pq.top();
		pq.pop();
		sum += (x + y);
		pq.push(x + y);
	}
	
	cout << sum;

}

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

백준 1202  (0) 2024.07.27
백준 2437  (0) 2024.07.20
백준 13904  (0) 2024.07.18
백준 16953  (0) 2022.12.26
백준 1946  (0) 2022.12.20

 

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

 

12865번: 평범한 배낭

첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000)

www.acmicpc.net

이 문제는 내가 지금 까지 DP배열을 1차원 배열로 만드는데 익숙 해져서 그런지 2차원 배열로 설정 하는 것을 생각을 못해서 어려운 문제 였다. 이 문제의 경우 나는 이렇게 생각 해주었다.

일단 나는 이문제를 1번 아이템 부터 4번아이템을 넣어준다고 가졍하였다 이문제에서 0은 어떠한 아이템도 안 넣었다고 생각해서 0이자 무게가 0이라고 생각을 했다 이렇게 생각하지 않으면 너무 헷갈렸다 그래서 1번을 넣었을 때 무게가 6이고 7인 경우에는 1을 넣었기 때문에 1의 무게인 13을 넣었다. 1을 넣었을 때 무게가 1,2,3,4 일 수는 없으니 1을 넣지 않았다는 표시이자 안 넣었고 무게도 0이니 0으로 한다. 2번아이템을 넣었을 때 도 마찬가지 무게가 1,2,일 때는 2번을 넣었을 때

무게가 4로 초과되니 0으로 표시한다 그후 무게가 4랑 5일때는 

나의 이전 단계인 1을 넣었을 때의 무게들 중 나를 안넣었다고 가정한 무게 + 나의 무게를 했을 때와 이전단계의 무게들과 비교하여 더큰 값을 넣어준다. 이것을  dp로 표현 하면

dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - W[i]] + V[i]); 

예시로 dp[2][6]은 dp[1][2]+v[2] 과 dp[1][6]일 때를 비교한다 이 의미는 1을 먼저 넣을 안넣을 지 결정하는 상태에서 무게가 2일때+나의 더했을 때의 가치와 1을 넣을 안넣을지 결정했을 무게가 6인 경우를 비교하여 더 큰 값을 선택한다.

쉽게 설명하자면

1을 넣을지 말지 결정했을 때  특정 무게를 맞춘다고 가정했을 때 나의 무게를 더해서 그 무게를 맞춘다고 가정한 값과 이전 단계에서 그 무게를 달성했을 때의 값을 비교하여 큰값을 선택해 주는것이다.

#include <iostream>
#include <algorithm>
using namespace std;
long long dp[101][100001];//가방 물건의 번호,내가방의 무게
int W[101];
int V[101];
int main() {
	int maxItemNum;
	int maxItemWeight;
	cin >> maxItemNum >> maxItemWeight;

	for(int i=1; i<=maxItemNum; i++){
		cin >> W[i] >> V[i];
	}

	for (int i = 1; i <= maxItemNum; i++) {
		for (int j = 1; j <= maxItemWeight; j++) {
			if (j - W[i]>=0) {
				dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - W[i]] + V[i]);
			}
			else {
				dp[i][j] = dp[i - 1][j];
			}
		}
	}
	cout << dp[maxItemNum][maxItemWeight];
}

그래서 이러한 점화식으로 이문제를 풀면 전체 식이 이렇게 된다. 1차원으로 dp를 세우는 거 뿐만 아니라 다차원의dp 도 세우는 방법을 연습해야 할거 같다.

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

백준 9095  (0) 2023.05.25
백준 2293  (0) 2023.01.09
백준 9465  (0) 2022.12.28
백준 11052  (0) 2022.12.26
백준 10844  (0) 2022.12.19

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

 

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

이 문제의 경우 백준의 dp문제에 항상 시달리던내가 풀기에도 쉬운 문제였다 처음 이문제를 풀때는 dfs로 접근해볼까라는 생각을 하고 풀어보았다 하지만 dfs의 특징상 하나한 다해보기때문에 경우의 수가 기하급수적으로 늘어나 시간복잡도가 무지막지하게 늘어나는 현상을 보여주었기 떄문에 결국에 이전값을 사용하는 dp로 이문제를 풀었다 이문제의 경우 어떠한 발판에 도착하는  경우의 수는 총 2가지이다 내 2번째  전 발판에서 오거나 내 저에 발판에서 오거나 이다. 2번째 발판 전도 마찬가지고 전 발판들도 똑같다 즉 나까지 도착하는 경우의수는 내 2번째전 발판까지 오는 경우의수와 나의 전 발판 까지 오는 경우의 수의 합이다. 이에 점화식은 

 dp[i] = (dp[i - 1] + dp[i - 2]) 이것이다

long long dp[2001];
long long solution(int n) {
    dp[0] = 1;
    dp[1] = 1;
    dp[2] = 2;
    for (int i = 3; i <= n; i++) {
        dp[i] = (dp[i - 1] + dp[i - 2])%1234567;
    }
    long long answer = dp[n];
    return answer;
}

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

 

2667번: 단지번호붙이기

<그림 1>과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여

www.acmicpc.net

이러한 문제류는 이제 dfs든 bfs로 풀기 쉬워졌다 이문제의 경우 자신을 기준으로 상하좌우로만 이동 할 수있기때문에 깊이우선 탐색으로 풀어 보았다 이문제는 어차피 단지의 개수를 세야 하기때문에 모든점을 한번에 다방문하면서 개수를 셀수 있는 dfs를 사용하였다. 이문제의 핵심 부분은

	if ((!visited[i][j + 1]) && map[i][j+1]==1)
		dfs(i, j + 1);
	if ((!visited[i][j - 1]) && map[i][j - 1]==1)
		dfs(i, j - 1);
	if ((!visited[i - 1][j]) && map[i-1][j]==1)
		dfs(i - 1, j);
	if ((!visited[i + 1][j]) && map[i + 1][j]==1)
		dfs(i + 1, j);

이부분이다 나를 기준으로 내 상하좌우중 방문한적이 없는 애들이 없으면 방문한다 그후 이함수 부분을 재귀적으로 호출하기 때문에 내 다음애들이 없으면 다시 부모로 돌아가서 다음거를 탐색한다 즉 재귀함수로 dfs를 구현한것이다

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;
int map[26][26];
bool visited[26][26];
int countnum = 0;
int danjicount = 0;
vector<int> answer;
void dfs(int i, int j) {
	countnum++;
	visited[i][j] = true;
	if ((!visited[i][j + 1]) && map[i][j+1]==1)
		dfs(i, j + 1);
	if ((!visited[i][j - 1]) && map[i][j - 1]==1)
		dfs(i, j - 1);
	if ((!visited[i - 1][j]) && map[i-1][j]==1)
		dfs(i - 1, j);
	if ((!visited[i + 1][j]) && map[i + 1][j]==1)
		dfs(i + 1, j);
}
int main() {
	int N;
	string temp;
	cin >> N;
	for (int i = 1; i <= N; i++) {
		cin >> temp;
		for (int j = 0; j <N; j++) {
			map[i][j + 1] = temp[j]-'0';
		}
	} 

	for (int i = 1; i <= N; i++) {	
		for (int j = 1; j <= N; j++) {
			countnum = 0;
			if (visited[i][j] || map[i][j]==0)
				continue;
			dfs(i, j);
			danjicount++;
			if(countnum)
				answer.push_back(countnum);
		}
	}
	
	sort(answer.begin(), answer.end());
	cout << danjicount << '\n';
	for (int i = 0; i < answer.size(); i++) {
		cout << answer[i] << '\n';
	}

}

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

백준 14940  (1) 2023.06.08
백준 11724  (0) 2023.06.01
백준 1012  (0) 2022.12.29
백준 1697  (0) 2022.12.27
백준 24480  (1) 2022.12.21

 

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

 

1012번: 유기농 배추

차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 

www.acmicpc.net

이문제는 요즘 나의 경악스러운 알고리즘 실력에 실망하던차에 내가 빠르게 풀 수 있는 문제였다. 아직  고수가 되긴 멀었지만 빨리 이런 문제쯤은 10분만에 해치울 수 있는 파워 프로그래머가 되고 싶다!!!!!

이 문제의 경우 여러방식으로 풀 수 있다. 나의 경우 일반적으로 성능이 나쁘지 않은 BFS를 사용해서 풀었다 

자 이문제를 풀때는 처음 1인애를 만나면 루프를 돌면서 자신을 기준으로 갈 수 있는 모든 점들을 BFS로 접근하여 visited배열에 마킹합니다 visited 배열이 1로 마킹되면 다시 해당하는 곳을 접근 하지 않습니다 이렇게 빨간색으로 체크 된 1을 root로 나머지 1로마킹된 애들이 BFS 로서 빨갛게 1로 마킹된 애들부터 같은색깔안에 있는 영역으로 접근합니다.

#include <iostream>
#include <queue>
using namespace std;
bool cabbage[52][52];
int visited[52][52];
int main() {
	int T; //테스트 케이스의 개수
	int M, N, K;//M:가로길이 N:세로길이 K: 배추가 심어져있는 위치의 개수;'
	cin >> T;
	queue<pair<int, int>> bfsQueue;
	for (int i = 0; i < T; i++) {
		cin >> M >> N >> K;
		for (int j = 0; j < M; j++) {
			for (int k = 0; k < N; k++) {
				cabbage[j][k] = 0;
				visited[j][k] = 0;
			}
		}
		for (int j = 0; j < K; j++) {
			int temp1, temp2;
			cin >> temp1 >> temp2;
			cabbage[temp1][temp2] = 1;
		}
		int countnum = 0;
		for (int j = 0; j < M; j++) {
			for (int k = 0; k < N; k++) {
				if (visited[j][k] == 1 && cabbage[j][k]==1)
					continue;
				else if(visited[j][k]==0 && cabbage[j][k]==1){
					countnum += 1;
					cabbage[j][k] = 1;
					bfsQueue.push(pair<int, int>(j, k));
					while (!bfsQueue.empty()) {
						int firstn,secondn;
						firstn = bfsQueue.front().first;
						secondn = bfsQueue.front().second;
						bfsQueue.pop();
						if (firstn >= 1) {
							if (visited[firstn - 1][secondn]==0 &&cabbage[firstn-1][secondn] == 1) {
								bfsQueue.push(pair<int, int>(firstn - 1, secondn));
								visited[firstn - 1][secondn] = 1;
							}
						}
						if (secondn >= 1) {
							if (visited[firstn][secondn - 1] == 0 && cabbage[firstn][secondn - 1]==1) {
								bfsQueue.push(pair<int, int>(firstn, secondn - 1));
								visited[firstn][secondn - 1] = 1;
							}
						}
						if (visited[firstn + 1][secondn] == 0 && cabbage[firstn + 1][secondn]==1) {
							bfsQueue.push(pair<int, int>(firstn + 1, secondn));
							visited[firstn + 1][secondn] = 1;
						}
						if (visited[firstn ][secondn+1] == 0 && cabbage[firstn][secondn + 1]==1) {
							bfsQueue.push(pair<int, int>(firstn , secondn+1));
							visited[firstn][secondn + 1] = 1;
						}
					}
				}
			}
			
		}
		cout << countnum << '\n';
	}
}
		for (int j = 0; j < M; j++) {
			for (int k = 0; k < N; k++) {
				cabbage[j][k] = 0;
				visited[j][k] = 0;
			}
		}
		for (int j = 0; j < K; j++) {
			int temp1, temp2;
			cin >> temp1 >> temp2;
			cabbage[temp1][temp2] = 1;
		}

일단 이부분은 각 케이스의 접근할때 배열들을 초기화 한후 양배추가 위치한곳을 1로 체크해줍니다

for (int k = 0; k < N; k++) {
				if (visited[j][k] == 1 && cabbage[j][k]==1)
					continue;
				else if(visited[j][k]==0 && cabbage[j][k]==1){
					countnum += 1;
					cabbage[j][k] = 1;
					bfsQueue.push(pair<int, int>(j, k));
					while (!bfsQueue.empty()) {
						int firstn,secondn;
						firstn = bfsQueue.front().first;
						secondn = bfsQueue.front().second;
						bfsQueue.pop();
						if (firstn >= 1) {
							if (visited[firstn - 1][secondn]==0 &&cabbage[firstn-1][secondn] == 1) {
								bfsQueue.push(pair<int, int>(firstn - 1, secondn));
								visited[firstn - 1][secondn] = 1;
							}
						}
						if (secondn >= 1) {
							if (visited[firstn][secondn - 1] == 0 && cabbage[firstn][secondn - 1]==1) {
								bfsQueue.push(pair<int, int>(firstn, secondn - 1));
								visited[firstn][secondn - 1] = 1;
							}
						}
						if (visited[firstn + 1][secondn] == 0 && cabbage[firstn + 1][secondn]==1) {
							bfsQueue.push(pair<int, int>(firstn + 1, secondn));
							visited[firstn + 1][secondn] = 1;
						}
						if (visited[firstn ][secondn+1] == 0 && cabbage[firstn][secondn + 1]==1) {
							bfsQueue.push(pair<int, int>(firstn , secondn+1));
							visited[firstn][secondn + 1] = 1;
						}
					}
				}
			}

이부분은 모든 배열을 돌면서 visited배열이 1로된 위치이거나 양배추가 심어지지않는 cabbage 가 0인쪽은 방문하지 않게 합니다 만약에 visited가 0이고 cabbage가 1이면 방문하게 합니다 그후 BFS를 위해 큐에다가 각각의 자식들을 집어넣고 

BFS를 실행하여 인접한 모든 cabbage가 1인 요소들에 대하여 visited 배열을 1로 초기화 해줍니다

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

백준 11724  (0) 2023.06.01
백준 2667  (0) 2023.01.02
백준 1697  (0) 2022.12.27
백준 24480  (1) 2022.12.21
백준 24479  (0) 2022.12.20

https://school.programmers.co.kr/learn/courses/30/lessons/12939

 

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

프로그래머스를 풀면서 느끼고 있는게 기업 코테에서 문자열 처리가 은근 많이 나오는거 같다 그래서 나도 기존에 c++로 문자열 파싱까지 했었는데 문자열 관련 구현은 c++ 로 하기에는 시간적으로 많이 부족한거 같다. 이에 기본적으로 문자열 처리에 많은 도움을 주는 파이썬을 사용해서 문자열 처리 문제는 앞으로 처리 하기로 했다 실제로 c++로 구현하면 엄청 오래걸릴 코드들도 파이썬의 문자열 인덱싱 기능만 사용하면 빠른시간안에 끝난다. 이번문제는 이러한 이유로 파이썬으로 풀었다 c++로 풀고싶지는 않다 이러한 문제를 일단 이문제는 그냥 쉽다 파이썬의 split을 이용해서 빈칸으로 각 요소들을을 분할해주고 그 list들의 요소들의 값을 서로 비교해서 최대 최솟값을 구한다이다. 아마도 코드를 보면 이해가 쉽게 될 것 이다

def solution(s):
    answer = ''
    a = []
    s = s.split(' ')
    for i in s:
        a.append(int(i))

    max=a[0]
    min=a[0]
    for i in a:
        if i >max:
            max=i
        if i<min:
            min=i
    answer=answer+str(min)
    answer=answer+" "
    answer=answer+str(max)
    return answer

+ Recent posts