JXNVCE ALGO-LOG YouJin Jung

BOJ-11051

29 Jul 2021 
#include <iostream>
#include <typeinfo>

using namespace std;

#define NUM 10007

long long gcd(long long a, long long b) {
    long long c;
    while (b!=0) {
        c = a%b;
        a = b;
        b = c;
    }
    return a;
}

int comb(int n, int k) {
    long long numerator = 1;
    long long denominator = 1;
    int ans = 1;
    for (int i=k; i>=1; i--) {
        numerator=numerator%NUM*n;
        n--;
        denominator=denominator%NUM*i;
        cout << denominator << endl;
        long long div = gcd(numerator, denominator);
        numerator/=div; 
        denominator/=div;
        
    } 
    cout << numerator << endl;
    cout << denominator << endl;
    return numerator/denominator % NUM;
    // return int(numerator/denominator%10007);
}

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

    int N, ans, K;
    cin >> N >> K;

    if (N<1 || N>1000 || K<0 || K>N) return 0;
    
    if (N==K) ans = 1;
    else if (K==0) ans = comb(N,N);
    else {
        if (K>N/2) K=N-K;
        ans = comb(N,K);
    }
    cout << ans << endl;
}

BOJ-1932

27 Jul 2021

정답률이 매우 높은 DP문제 였지만, 막상 구현하려니 살짝 부담스럽긴했다…!

#include <iostream>
#include <algorithm>

using namespace std;

// int getMax(int a, int b) { return a > b ? a : b; }

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    int n;
    int dp[500][500] = {0};

    cin >> n;
    if (n<1 || n>500) return 0;

    for (int i = 1; i < n; i++) 
        for (int j = 0; j <= i; j++) 
            cin >> dp[i][j];
     
    for (int i=1; i<n; i++) {
        for (int j=0; j<=i; j++) {
        if (j == 0) { 
            dp[i][j] += dp[i-1][j]; 
        } 
        else if (j == i) {
            dp[i][j] += dp[i-1][j-1];
        } 
        else {
            dp[i][j] = max(dp[i][j] + dp[i-1][j-1], dp[i][j] + dp[i-1][j]);
        }
    }

    int max = 0;
    for (int i=0; i<n; i++) {
	if (max < dp[n-1][i]) {
	    max = dp[n-1][i];
	}
    }
    cout << max << endl;
}

BOJ-13574

27 Jul 2021

성공만으로 깔끔했던 문제에 첫 오답이라는 허점을 남긴 나… HackerRank Easy 문제인데 Test Case 0 빼고 다 틀렸다… 왜일까? DP를 쓰는 문제인지 헷갈린다


#include <iostream>

using namespace std;

int A[11][100001];
int temp[100001];
int ret[2]={0};

int* getMax(int a, int b, int* temp) { 
    if (temp[a]>=temp[b]) {
        ret[0] = a;
        ret[1] = temp[a];
    }
    return ret;
}

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

    int T, Ai, N;
    cin >> T;
    if (T>10 || T<1) return 0;
    for (int i=0; i<T; i++) {
        int num;
        cin >> N;
        if (N<1 || N>100000) return 0;
        for (int j=0; j<N; j++) {
            cin >> Ai;
            if (Ai<1 || Ai>1000000000) return 0;
            A[i][j] = Ai;
        }
    }

    int comp = 0;
    
    for (int i=0; i<T; i++) {
        for (int k=0; k<=N-3; k++) {
            temp[k] = A[i][k] + A[i][k+1] + A[i][k+2];
            int* result = getMax(comp, k, temp);
            comp = result[0];
        }
        cout << A[i][comp] << " " << A[i][comp+1] << " " << A[i][comp+2] << " " << endl;
    }
    return 0;
}

image

사진은 짝퉁 포켓몬인 타타몬이 귀여워서….. 두시니까 자야겠다 ㅜㅜ 😱😱😥😨

BOJ-5557

23 Jul 2021

DP 문제! 구글링으로 러페런스를 구해서 풀었다.. DP 화이팅

#include<iostream>
#include<cstring>

using namespace std;

#define MAX 101

int N;
int arr[MAX];
long long DP[MAX][1001];
int result;

long long checkDP(int index, int sum) {
	if (sum < 0 || sum > 20) return 0;
	if (index == N - 2) {
		if (sum == result)
			DP[index][sum] = 1;
		else
			DP[index][sum] = 0;
		return DP[index][sum];
	}

	if (DP[index][sum] != -1)
		return DP[index][sum];

	long long check = 0;

	check += checkDP(index + 1, sum + arr[index + 1]);
	check += checkDP(index + 1, sum - arr[index + 1]);

	return DP[index][sum] = check;
}

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

	cin >> N;

	for (int i = 0; i < N - 1; i++)
		cin >> arr[i];

	cin >> result;
    // memset function => set memory's value with wanted size!
	memset(DP, -1, sizeof(DP));
    
	cout << checkDP(0, arr[0]);
	return 0;
}

image 내일 기세 기말과제가 마감인데, 아직 시작도 못했다. 오전에 멘티들끼리 만나서 회의를 해서……. 아침까지 끝내야하는데 걱정이 이만저만이 아니다… 해커톤 워크플로우 업무도 아직 남아있는데, 사실 잘 못해서 팀에게 민폐끼치는 중이다ㅜㅜ ㅜㅜ 오늘까지만 밤 진짜 제대로 새서 다 끝내보자!!! 💪🏼💪🏼

BOJ-12865

22 Jul 2021

아주 고전 문제인 배낭 문제 컴알 수업때 교수님이 이걸로 설명해주신게 기억이 난다. 그 때 DP 개념을 처음 접했는데, 아 완전 신세계를 본 듯한 느낌이었다. 어떻게 하면 저렇게 문제에 접근할 수 있는가에서 부터 참 컴퓨터가 좋아할 풀이방식이겠구나 라고 느꼈다. 아직 나랑은 친하 않은 디피야… 이제 좀 친해지자 우리~~~ 😉😉

#include <iostream>
#include <algorithm>

using namespace std;

int dp[101][100001];
pair<int, int> arr[101];
int n, k;

int bag() {
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= k; j++) {
			if (arr[i].first > j) dp[i][j] = dp[i-1][j];
			else dp[i][j] = max(dp[i-1][j], dp[i-1][j-arr[i].first] + arr[i].second);
		}
	}
	return dp[n][k];
}

int main() {
    ios::sync_with_stdio(false);
    cout.tie(NULL); cin.tie(NULL);
	scanf("%d %d", &n, &k);
	for (int i = 1; i <= n; i++) {
		scanf("%d %d", &arr[i].first, &arr[i].second);
	}
	sort(arr, arr + n + 1);
    printf("%d", bag());
}

image

요즘 좋은 감사한 기회로 해커톤 기획에 참가하게 되었는데, GitHub Actions 를 기반으로 자동으로 워크플로우가 흐르도록 하는 해커톤이어서 요즘 관련 다양한 오픈소스 리포지토리를 많이 방문하고 조사해보며 적용시키는게 재밌다!!! 이래서 DevOps 분야가 점점 더 확장되는 이유를 알 것도 재밌다. CI/CD란 참 흥미로운 분야인 것같다… 아직 발가락도 못 담구어 본 상태지만, 아주아주 즐겁게 코드도 짜보고 삽질 중이다~ 🚧🏁🧹

다만 문제가 있다면 잘 못해서 일이 아주아주 미루어진 점… 자꾸 오류가 나고 플로우를 지속적으로 수정하면서 푸시로만 확인이 가능하니… 내가 팀에 민폐를 끼치는 것 같아 죄송하다ㅜㅜ 사실 얼추 다 되었는데, 하면 할수록 더 효율적으로, 간지나게 코드를 짜고 싶은 욕심에 일이 자꾸 딜레이된다…오늘 밤새서 완벽하게 구현해낼거다!!@!@! 🚀🚀