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

2학기 4주차 스터디

백준 제출 내역 화면 캡쳐

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

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

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

 

10815

---

• 이분 탐색 → 값을 정렬한 후 필요한 부분에서만 탐색을 진행

// 10815.c

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

// 정렬을 위한 비교 함수 (qsort에 사용함)
int compare(const void *a, const void *b)
{
    return (*(int *)a - *(int *)b);
}

// 이분 탐색
int binary_search(int *arr, int size, int target)
{
    int low = 0, high = size - 1;

    while (low <= high)
    {
        int mid = (low + high) / 2;

        if (arr[mid] == target)
        {
            return 1; // 찾은 경우
        }
        else if (arr[mid] < target)
        {
            low = mid + 1;
        }
        else
        {
            high = mid - 1;
        }
    }

    return 0; // 못 찾은 경우
}

int main()
{
    int M, N, num;

    // M 입력 및 배열 동적 할당
    scanf("%d", &M);
    int *arr = (int *)malloc(M * sizeof(int));

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

    // 배열 정렬 (qsort 사용)
    qsort(arr, M, sizeof(int), compare);

    // N 입력 및 이분 탐색 실행
    scanf("%d", &N);
    for (int i = 0; i < N; i++)
    {
        scanf("%d", &num);
        if (binary_search(arr, M, num))
        {
            printf("1 ");
        }
        else
        {
            printf("0 ");
        }
    }

    // 메모리 해제
    free(arr);

    return 0;
}

 

10815

---

• 이분 탐색 → 값을 정렬한 후 필요한 부분에서만 탐색을 진행

// 14425.c

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

#define MAX 10000  // 10000개
#define STRLEN 501 // 500개

// 문자열 비교 함수 (qsort, bsearch)
int compare(const void *a, const void *b)
{
    return strcmp((const char *)a, (const char *)b);
}

// 이분 탐색
int binary_search(char arr[][STRLEN], int size, const char *target)
{
    int low = 0, high = size - 1;

    while (low <= high)
    {
        int mid = (low + high) / 2;
        int cmp = strcmp(arr[mid], target);

        if (cmp == 0)
        {
            return 1; // 찾은 경우
        }
        else if (cmp < 0)
        {
            low = mid + 1;
        }
        else
        {
            high = mid - 1;
        }
    }

    return 0; // 찾지 못한 경우
}

int main()
{
    int N, M, count = 0;
    char str[STRLEN];      // 입력받을 문자열
    char arr[MAX][STRLEN]; // 문자열 저장 배열

    // N, M 입력
    scanf("%d %d", &N, &M);

    // 문자열 입력
    for (int i = 0; i < N; i++)
    {
        scanf("%s", arr[i]);
    }

    // 정렬
    qsort(arr, N, STRLEN, compare);

    // 문자열 입력 및 이분 탐색
    for (int i = 0; i < M; i++)
    {
        scanf("%s", str);
        if (binary_search(arr, N, str))
        {
            count++;
        }
    }

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

    return 0;
}