1. 순차탐색과 이분탐색

• 단순히 각각의 탐색에 대해 횟수만 구하면 되는 문제이다.
• 각 탐색법을 구현해둔 뒤, 횟수만 세도록 하자.
• 이분탐색만 사용하고도 풀 수는 있으나, 예외를 조심하자 : 찾고자 하는 값이 없을 때.

#include <stdio.h>

int a[1010101];
int n, k;

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

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

    scanf("%d", &k);

    int b=0, c=0;

    for (int i=1; i<=n; i++)
    {
        b++;
        if (a[i] == k)  break;
    }

    int s=1, e=n;

    while (s <= e)
    {
        c++;
        int mid = (s+e)/2;
        
        if (a[mid] == k) break;
        else if (a[mid] > k) e = mid - 1;
        else s = mid + 1;
    }

    printf("%d %d", b, c);
}

2. 두 수 사이의 수 2

• 정렬이 되어있지 않으므로 정렬만 수행한 뒤 이분탐색을 수행하자.
• 이 문제는 모르면 안된다!

#include <stdio.h>
#include <algorithm>

using namespace std;

int arr[100000];

int lb(int s, int e, int k)
{
    int r = e+1;
    
    while (s <= e)
    {
        int m = (s+e)/2;
        if (arr[m] >= k)
        {
            r = m;
            e = m-1;
        }
        else
        {
            s = m+1;
        }
    }
    return r;
}

int ub(int s, int e, int k)
{
    int r = e+1;
    
    while (s <= e)
    {
        int m = (s+e)/2;
        if (arr[m] > k)
        {
            r = m;
            e = m-1;
        }
        else
        {
            s = m+1;
        }
    }
    return r;
}

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

    for (int i=0; i<n; i++)
        scanf("%d", &arr[i]);
    
    sort(arr, arr+n);

    while (q--)
    {
        int a, b;
        scanf("%d %d", &a, &b);
        printf("%d\n", ub(0, n-1, b) - lb(0, n-1, a));
    }
}

3. 라운드 로빈

• 큐를 이용하여 실제 라운드 로빈을 돌려보는 문제.
  • 정과개때 “라운드 로빈 스케줄러”가 기억이 날 것이다
• 2개의 정보가 필요하다
  • 몇 번 작업인가
  • 남은 시간이 얼마인가
• 그래서 큐에서 꺼낼 때마다 이 동작을 반복하자
  • q만큼 시간을 들여도 작업이 안끝난다면, 시간을 q만큼 뺀 다음 다시 큐에 집어넣자
  • 그렇지 않으면 출력하자
• 대신 작업 완료 시간이 필요하므로, 현재 시간인 ct라는 변수를 따로 관리하자.

#include <stdio.h>
#include <queue>

using namespace std;

int main()
{
    int n, k;
    queue<pair<int, int>> q;

    scanf("%d %d", &n, &k);

    for (int i=1; i<=n; i++)
    {
        int v;
        scanf("%d", &v);

        q.push({i, v});
    }

    int ct = 0;

    while (!q.empty())
    {
        pair<int, int> p = q.front(); q.pop();
        if (p.second <= k)
        {
            ct += p.second;
            printf("%d %d\n", p.first, ct);
        }
        else
        {
            p.second -= k;
            ct += k;

            q.push(p);
        }
    }
}