max) max = size; } } } printf("%.9f", max); }"> max) max = size; } } } printf("%.9f", max); }"> max) max = size; } } } printf("%.9f", max); }">

<aside> 1️⃣

문제: 1198번 삼각형으로 자르기

볼록 다각형에서 연속된 3개의 점을 선택해 삼각형을 잘라내는 것을 삼각형만이 남을 때까지 반복

마지막에 남은 삼각형의 최대 넓이를 구하기

</aside>

#include <stdio.h>

double triangle (int x1,int y1,int x2,int y2,int x3,int y3){
    //삼각형 넓이 구하는 신발끈 공식
    //이 부분 타입 때문에 틀렸었음
    long long sums1 = (long long)x1*y2 + (long long)x2*y3 + (long long)x3*y1;
    long long sums2 = (long long)y1*x2 + (long long)y2*x3 + (long long)y3*x1;
    double result = (double)(sums1 - sums2) / 2.0;
    if (result < 0) result = -result;
    return result;
}

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

    int x[35]; //x좌표
    int y[35]; //y좌표

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

    double max = 0;

    //좌표 세개를 골랐을 때 삼각형의 넓이가 젤 큰 넓이 구하기
    for(int i = 0; i < N-2; i++){
        for(int j = i+1; j < N-1; j++){
            for(int k = j+1; k < N; k++){
              //좌표 세개 i, j, k를 구해서 넓이 구하기
              double size = triangle(x[i], y[i], x[j], y[j], x[k], y[k]);
              if (size > max) max = size;
            }
        }
    }

    printf("%.9f", max);
}

image.png

<aside> 2️⃣

문제: 1260번 DFS와 BFS

그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램 작성하기

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

#define MAX 1001

int N, M, V; //정점, 간선, 시작 정점
int graph[MAX][MAX]; //인접 행렬
int visited[MAX];

//DFS
void DFS(int v) {
    visited[v] = 1;
    printf("%d ", v); //방문한 것 출력
    for(int i = 1; i <= N; i++) { //작은 것부터 방문하여
        if(graph[v][i] && !visited[i]) {
            DFS(i); //재귀
        }
    }
}

//BFS
void BFS(int start) {
    int queue[MAX]; //큐
    int front = 0, rear = 0;

    for(int i = 1; i <= N; i++) visited[i] = 0; //초기화

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

    while(front < rear) {//큐가 빌 때까지 반복
        int v = queue[front++];
        printf("%d ", v);

        for(int i = 1; i <= N; i++) {
            if(graph[v][i] && !visited[i]) { //미방문이면 큐에 넣기
                queue[rear++] = i;
                visited[i] = 1;
            }
        }
    }
}

int main() {
    scanf("%d %d %d", &N, &M, &V);

    for(int i = 0; i < M; i++) {
        int a, b;
        scanf("%d %d", &a, &b);
        graph[a][b] = 1;
        graph[b][a] = 1; //양방향
    }

    for(int i = 1; i <= N; i++) visited[i] = 0;
    DFS(V); //dfs 수행 및 출력
    printf("\\n");
    BFS(V); //bfs
}

image.png