[SISS/C언어 스터디] 여름 5주차 스터디

여름 5주차 스터디

백준 제출 내역 화면 캡쳐

C언어 문제 풀이(2) + 회의 불참 과제(3)
자율 2문제를 풀어서 제출하면 됩니다.

언어는 C언어만 가능합니다.
레벨 제한사항: Bronze 3 이상

 

2606

---

• bfs

// 2606.c

#include <stdio.h>
#include <stdlib.h>

// 노드 구조체
typedef struct Node
{
    int vertex;
    struct Node *next;
} Node;

Node **graph;
int *visited;
int n;

Node *createNode(int v)
{
    Node *newNode = (Node *)malloc(sizeof(Node));
    newNode->vertex = v;
    newNode->next = NULL;
    return newNode;
}

void addEdge(int src, int dest)
{
    Node *newNode = createNode(dest);
    newNode->next = graph[src];
    graph[src] = newNode;

    newNode = createNode(src);
    newNode->next = graph[dest];
    graph[dest] = newNode;
}

// bfs 함수 정의
int bfs(int start)
{
    int *queue = (int *)malloc(n * sizeof(int));
    int front = 0, rear = 0;
    int count = 0;

    queue[rear++] = start;
    visited[start] = 1;

    while (front < rear)
    {
        int before_v = queue[front++];
        count++;

        Node *temp = graph[before_v];
        while (temp)
        {
            int adj_v = temp->vertex;
            if (!visited[adj_v])
            {
                queue[rear++] = adj_v;
                visited[adj_v] = 1;
            }
            temp = temp->next;
        }
    }

    free(queue);
    return count - 1;
}

int main()
{
    int m;
    scanf("%d", &n);
    scanf("%d", &m);

    graph = (Node **)malloc((n + 1) * sizeof(Node *));
    visited = (int *)malloc((n + 1) * sizeof(int));

    // 입력 받아 그래프 생성
    for (int i = 0; i <= n; i++)
    {
        graph[i] = NULL;
        visited[i] = 0;
    }

    for (int i = 0; i < m; i++)
    {
        int a, b;
        scanf("%d %d", &a, &b);
        addEdge(a, b);
    }

    printf("%d\n", bfs(1));

    // 메모리 할당 해제
    for (int i = 0; i <= n; i++)
    {
        Node *temp = graph[i];
        while (temp)
        {
            Node *free_node = temp;
            temp = temp->next;
            free(free_node);
        }
    }

    free(graph);
    free(visited);

    return 0;
}

 

11053

---

• dp

// 11053.c

#include <stdio.h>
#include <stdlib.h>

int main()
{
    int n;
    scanf("%d", &n);

    // 동적 배열 할당
    int *a = (int *)malloc(n * sizeof(int));
    int *d = (int *)malloc(n * sizeof(int));

    for (int i = 0; i < n; i++)
    {
        scanf("%d", &a[i]);
    }

    // 수열 길이 계산
    for (int i = 0; i < n; i++)
    {
        d[i] = 1;
        for (int j = 0; j < i; j++)
        {
            if (a[j] < a[i] && d[i] < d[j] + 1)
            {
                d[i] = d[j] + 1;
            }
        }
    }

    // 최대 길이
    int max = d[0];
    for (int i = 1; i < n; i++)
    {
        if (d[i] > max)
        {
            max = d[i];
        }
    }

    printf("%d\n", max);

    // 메모리 해제
    free(a);
    free(d);

    return 0;
}

 

2579

---

• dp

// 2579.c

#include <stdio.h>
#include <stdlib.h>

int main()
{
    int n;

    // 입력: 계단의 수 n
    scanf("%d", &n);

    // 동적 배열 할당
    int *a = (int *)malloc((n + 1) * sizeof(int));
    int *d = (int *)malloc((n + 1) * sizeof(int));

    // 계단 값 입력
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &a[i]);
    }

    // DP 초기값 설정
    if (n == 1)
    {
        d[1] = a[1];
    }
    else if (n == 2)
    {
        d[1] = a[1];
        d[2] = a[1] + a[2];
    }
    else
    {
        d[1] = a[1];
        d[2] = a[1] + a[2];

        // DP 계산
        for (int i = 3; i <= n; i++)
        {
            d[i] = (d[i - 2] + a[i] > d[i - 3] + a[i - 1] + a[i]) ? d[i - 2] + a[i] : d[i - 3] + a[i - 1] + a[i];
        }
    }

    // 결과 출력
    printf("%d\n", d[n]);

    // 동적 메모리 해제
    free(a);
    free(d);

    return 0;
}

 

7576

---

• bfs

// 7576.c

#include <stdio.h>
#include <stdlib.h>

#define MAX_SIZE 1000

int queue[MAX_SIZE * MAX_SIZE][2];
int front = 0, rear = 0;

void enqueue(int x, int y)
{
    queue[rear][0] = x;
    queue[rear][1] = y;
    rear++;
}

void dequeue(int *x, int *y)
{
    *x = queue[front][0];
    *y = queue[front][1];
    front++;
}

int isEmpty()
{
    return front == rear;
}

int main()
{
    int m, n;
    scanf("%d %d", &m, &n);

    int **graph = (int **)malloc(n * sizeof(int *));
    for (int i = 0; i < n; i++)
    {
        graph[i] = (int *)malloc(m * sizeof(int));
    }

    int dx[] = {0, 0, -1, 1};
    int dy[] = {-1, 1, 0, 0};

    // 입력 및 초기화
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            scanf("%d", &graph[i][j]);
            if (graph[i][j] == 1)
            {
                enqueue(i, j);
            }
        }
    }

    // BFS
    while (!isEmpty())
    {
        int x, y;
        dequeue(&x, &y);
        for (int i = 0; i < 4; i++)
        {
            int nx = x + dx[i];
            int ny = y + dy[i];

            if (nx >= 0 && nx < n && ny >= 0 && ny < m && graph[nx][ny] == 0)
            {
                graph[nx][ny] = graph[x][y] + 1;
                enqueue(nx, ny);
            }
        }
    }

    // 메모리 할당 해제
    int result = 0;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            if (graph[i][j] == 0)
            {
                printf("-1\n");
                for (int k = 0; k < n; k++)
                {
                    free(graph[k]);
                }
                free(graph);
                return 0;
            }
            if (graph[i][j] > result)
            {
                result = graph[i][j];
            }
        }
    }

    printf("%d\n", result - 1);

    for (int i = 0; i < n; i++)
    {
        free(graph[i]);
    }
    free(graph);

    return 0;
}

 

24313

---

• 시간복잡도

// 24313.c

#include <stdio.h>

int main()
{
    // 변수 선언
    int a1, a2;
    int c, n0;

    // 입력 받기
    scanf("%d %d", &a1, &a2);
    scanf("%d", &c);
    scanf("%d", &n0);

    // O(n) 정의를 만족하는지 확인
    if (a1 <= c && a2 <= (c - a1) * n0)
    {
        printf("1\n");
    }
    else
    {
        printf("0\n");
    }

    return 0;
}