[SISS/C언어 스터디] 2학기 2주차 스터디

2학기 2주차 스터디

백준 제출 내역 화면 캡쳐

자율 2문제를 풀어서 제출하면 됩니다.

언어는 C언어만 가능합니다.

​레벨 제한사항: Silver 5 이상

 

12865

---

• 동적 프로그래밍 → 배낭에 넣을 수 있는 물건의 최대 가치 합을 출력
• 참고 링크 → https://cotak.tistory.com/38

// 12865.c

#include <stdio.h>

// 물건 개수, 최대 무게
int n, k;
// 각갹의 무게 및 가치
int w[101], v[101];

// dp 테이블
int dp[101][100001];

int main()
{
    int i, j;

    // 물건 개수, 최대 무게 입력
    scanf("%d %d", &n, &k);
    // 각각의 물건 입력
    for (i = 1; i <= n; i++)
    {
        scanf("%d %d", &w[i], &v[i]);
    }

    // dp
    for (i = 1; i <= n; i++)
    {
        for (j = 1; j <= k; j++)
        {
            // 무게가 더 클 경우
            if (j < w[i])
            {
                // 이전 값
                dp[i][j] = dp[i - 1][j];
            }
            // 무게가 같거나 작을 경우
            else
            {
                // 이전 값과 현재 값 중 큰 값을 저장
                dp[i][j] = dp[i - 1][j] > dp[i - 1][j - w[i]] + v[i] ? dp[i - 1][j] : dp[i - 1][j - w[i]] + v[i];
            }
        }
    }

    printf("%d\n", dp[n][k]);

    return 0;
}

 

1991

---

• 트리 순회 → 입력받은 이진트리의 전위, 중위, 후위 순회 결과를 출력

// 1991.c

#include <stdio.h>

// 노드 개수
int n;
// 트리
int tree[26][2];

// 전위 순회
void preorder(int node)
{
    // 노드가 없으면 종료
    if (node == -1)
    {
        return;
    }

    // 노드 출력
    printf("%c", node + 'A');
    // 왼쪽 자식
    preorder(tree[node][0]);
    // 오른쪽 자식
    preorder(tree[node][1]);
}

// 중위 순회
void inorder(int node)
{
    // 노드가 없으면 종료
    if (node == -1)
    {
        return;
    }

    // 왼쪽 자식
    inorder(tree[node][0]);
    // 노드 출력
    printf("%c", node + 'A');
    // 오른쪽 자식
    inorder(tree[node][1]);
}

// 후위 순회
void postorder(int node)
{
    // 노드가 없으면 종료
    if (node == -1)
    {
        return;
    }

    // 왼쪽 자식
    postorder(tree[node][0]);
    // 오른쪽 자식
    postorder(tree[node][1]);
    // 노드 출력
    printf("%c", node + 'A');
}

int main()
{
    int i;
    char a, b, c;

    // 노드 개수 입력
    scanf("%d", &n);
    // 트리 초기화
    for (i = 0; i < n; i++)
    {
        tree[i][0] = tree[i][1] = -1;
    }

    // 트리 입력
    for (i = 0; i < n; i++)
    {
        // 노드, 왼쪽 자식, 오른쪽 자식 입력
        scanf(" %c %c %c", &a, &b, &c);

        // 왼쪽 자식
        if (b != '.')
        {
            tree[a - 'A'][0] = b - 'A';
        }
        // 오른쪽 자식
        if (c != '.')
        {
            tree[a - 'A'][1] = c - 'A';
        }
    }

    // 전위 순회
    preorder(0);
    printf("\n");

    // 중위 순회
    inorder(0);
    printf("\n");

    // 후위 순회
    postorder(0);
    printf("\n");

    return 0;
}