JXNVCE ALGO-LOG YouJin Jung

BOJ-2565

04 Aug 2021

도무지 왜 LIS를 쓰는지 모르겠어서 질문 게시판이랑 구글링을 참고해서 풀었다… 사람들이 왜 DP 어렵다는지도 알겠고 와 어떻게 문제를 이렇게 나랑 딴판으로 해석하는지 신기하다

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

using namespace std;

// vector<pair<int, int>> sort(vector<pair<int, int>> p) {
//     int small, temp, temp2, i, j;
//     int n = p.size();
//     for (i=0; i<n-1; i++) {
//         small = i;
//     }
//     for (j=i+1; j<n; j++) {
//         if (p.at(j).first <= p.at(small).first) small = j;
//     }
//     temp = p.at(i).first;
//     temp2 = p.at(i).second;
//     p.at(i).first = p.at(small).first;
//     p.at(i).second = p.at(small).second;
//     p.at(small).first = temp;
//     p.at(small).second = temp2;
//     return p;
// }

int main() {
    ios_base::sync_with_stdio(false); 
    cin.tie(NULL); cout.tie(NULL);
    
    int T;
    cin >> T;
    vector<pair<int, int>> p;
    if (T>100) return 0;
    for (int i=0; i<T; i++) {
        int a, b;
        cin >> a >> b;
        if (a<500 && b<500) {
            pair <int, int> t;
            t.first = a;
            t.second = b;
            p.push_back(t);
        }
    }
    sort(p.begin(), p.end());
    for (auto i: p) {
        cout << i.first << " " << i.second << endl;
    }
    // vector<pair<int, int>> q = sort(p);
    // for (auto i: q) {
    //     cout << i.first << " " << i.second << endl;
    // }
    int dp[102], result;
    for (int i=1; i<=T; i++) {
        for (int j=0; j<i; j++) {
            if(p[i].second > p[j].second && dp[j]>=dp[i]) dp[i] = dp[j]+1;
        }
        result = max(result, dp[i]);
    }
    cout << T-result << endl;
    return 0;

}

BOJ-7568

02 Aug 2021 
#include <iostream>
#include <cmath>
using namespace std;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	int n;
	int arr[51][2] = {};
	int result[51];
	cin >> n;
  
	for (int i=0; i<n; i++) {
		cin >> arr[i][0] >> arr[i][1];
		result[i] = 1;	
	}

	for (int i=0; i<n; i++) 
		for (int j=0; j<n; j++) 
			if (arr[i][0]<arr[j][0] && arr[i][1]<arr[j][1]) result[i]=result[i]+1;
	
	for (int i=0; i<n; i++) cout << result[i] << " ";
	cout << endl;
    return 0;
}

image

내일 워크샵 발표…라는 핑계로, 잘 안풀려서 구글링을 했다… 얼른 다시 연습하자 ㅜㅜ

BOJ-11651

02 Aug 2021

간단한 수학 정렬 알고리즘문제

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

using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    int N;
    cin >> N;
    
    vector<vector<int>> arr(N, vector<int>(2,0));
    
    for(int i=0; i<N; i++){
        cin >> arr[i][1];
        cin >> arr[i][0];
    }
    sort(arr.begin(), arr.end());

    for(int i=0; i<arr.size(); i++) 
        cout << arr[i][1]<< " " << arr[i][0] << endl;
    
    return 0;
}

BOJ-11047

30 Jul 2021 
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
int cmp(int a, int b) {return (a>b ? a : b);}

int main() {
    ios::sync_with_stdio(false);
    cout.tie(NULL); cin.tie(NULL);
    
	int n, k;
    int ans = 0;
    vector<int> v;
	cin >> n >> k;
	for (int i = 0; i < n; i++) {
        int a;
        cin >> a;
        v.push_back(a);
    }
	sort(v.begin(),v.end(),cmp);
	for (int i = 0; i < n; i++) {
		while (k >= v[i]) {
			ans++;
			k -= v[i];
		}
	}
	cout << ans << endl;
}

깜깜한 방바닥에 앉아서…

image

BOJ-7562

29 Jul 2021

BFS 를 활용한 문제!!! 아직도 헷갈리니까 연습 많이 하자….✨✨ 이런 방향성이 있는 문제에 대한 접근 방법을 몰라서, 구글링해서 참고를 했다. x축 방향, y축 방향을 나누어 array로 dx dy 이렇게 담아 하는 새로운 테크닉도 배웠다. 참 신기한 알고리즘의 세계….😎

#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
 
int arr[301][301];
bool checked[301][301];

int dx[8] = {2,1,-1,-2,-2,-1,1,2};
int dy[8] = {1,2,2,1,-1,-2,-2,-1};
// 반시계방향

// int dx[8] = {1,2,2,1,-1,-2,-2,-1};
// int dy[8] = {2,1,-1,-2,-2,-1,1,2};
 
int I;
queue<pair<int, int>> q;
int xs, ys, xd, yd;
 
void bfs(int a, int b){
    q.push(make_pair(a, b));
    checked[a][b] = true;
    while(!q.empty()){
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
        
        if(x == dstX && y == dstY){
            cout << arr[x][y] << endl;
            while(!q.empty()) q.pop();
        }
        
        for(int i = 0; i < 8; i++){
            int nx = x + dx[i];
            int ny = y + dy[i];
            
            if(nx >= 0 && nx < I && ny >= 0 && ny < I){
                if(checked[nx][ny] == false){
                    checked[nx][ny] = true;
                    arr[nx][ny] = arr[x][y] + 1;
                    q.push(make_pair(nx, ny));
                }
            }
        }
    }
}
 
int main() {
    ios::sync_with_stdio(false);
    cout.tie(NULL); cin.tie(NULL);
    
    int T;
    cin >> T;
 
    for(int i = 0; i < T; i++){
        cin >> I;
        if (I<4 || I>300) return 0;
        cin >> xs >> ys >> xd >> yd;
        bfs(xs, ys);
        memset(arr, 0, sizeof(arr));
        memset(checked, false, sizeof(checked));
    }
    return 0;
}