문제 이해 단계 https://www.acmicpc.net/problem/11779 11779번: 최소비용 구하기 2 첫째 줄에 도시의 개수 n(1≤n≤1,000)이 주어지고 둘째 줄에는 버스의 개수 m(1≤m≤100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스 www.acmicpc.net n개의 도시와 m개의 버스가 존재한다. 버스는 A도시에서 출발하여 B도시에 도착하는 정보로 주어진다. 그리고 각 버스마다 드는 비용이 존재한다. 또한 입력으로 출발지와 도착지가 주어질 때, 출발지에서 도착지까지 가는데 드는 최소 비용과 경로를 출력하는 것 문제 접근 단계 일단 문제 조건부터 살펴보자. 도시의 개수 n은 최대 1,000 간선의 개수(버..
문제 이해 단계 https://www.acmicpc.net/problem/2448 2448번: 별 찍기 - 11 첫째 줄에 N이 주어진다. N은 항상 3×2k 수이다. (3, 6, 12, 24, 48, ...) (0 ≤ k ≤ 10, k는 정수) www.acmicpc.net N = 24 일 때의 출력이다. 예제를 보고 규칙을 유추하고 별을 찍는 문제 입력 N은 무조건 3 * 2^k로 들어온다. 여기서 k의 범위는 0≤k≤10이다. 문제 접근 단계 별 찍기 시리즈 문제이다. 때문에 구현문제인 것 같은데, 어떤 식으로 구현해야 할까? k의 범위가 0부터 10까지니까 순서대로 해봤다. 이 이상은 그림이 너무 커질 것 같아서 k = 2 일 때까지만 그려보도록 하겠다. 이렇게 k가 1씩 커져갈 때의 규칙을 보면 ..
알고리즘의 평가 특정 시스템을 위한 CPU 스케줄링 알고리즘은 어떻게 선택하는가? 알고리즘을 선택하는 데 사용할 기준을 정의 알고리즘을 선택하기 위해 매개변수들의 상대적인 중요성을 반드시 정의해야 한다. 기준은 종종 CPU 이용률, 응답시간 또는 처리량에 의해 정의된다. 기준은 아래와 같은 대책을 포함할 수도 있음 최대 응답 시간은 300ms라는 제약 조건에서 CPU 이용률을 극대화한다. 총 처리 시간이 전체 실행 시간에 평균적으로 선형 비례가 되도록 처리량을 극대화한다. 선택 기준의 정의되면, 여러 가지 알고리즘들을 평가하기를 원한다. → 아래에서 사용할 수 있는 여러 평가 방법들을 기술 결정론적 모델링 분석적 평가(analytic evaluation) 평가 방법의 중요한 부류 중 하나 주어진 작업 부..
실시간 CPU 스케줄링 실시간 CPU 스케줄링은 연성(soft) 실시간 시스템과 경성(hard) 실시간으로 구분 연성 실시간 시스템 중요한 실시간 프로세스가 스케줄 되는 시점에 관해 아무런 보장을 하지 않는다. 오직 중요 프로세스가 그렇지 않은 프로세스들에 비해 우선권을 가진다는 것만 보장 경성 실시간 시스템 태스크는 반드시 마감시간까지 서비스를 받아야 한다. → 더 엄격한 요구 조건을 만족해야 함 마감시간이 지난 이후에 서비스를 받는 것은 서비스를 받지 않는 것과 같다. 지연시간 최소화(Minimizing Latency) 실시간 시스템의 이벤트-중심 특성 시스템은 일반적으로 실시간으로 발생하는 이벤트를 기다린다. 이벤트가 발생하면 시스템은 가능한 한 빨리 그에 응답하고 그에 맞는 동작을 수행해야 한다...
다중 처리기 스케줄링 여러 개의 CPU가 사용 가능 → 여러 스레드가 병렬로 실행 가능 → 부하 공유(load sharing) 가능 스케줄링 문제는 그에 상응하여 더욱 복잡해짐 다중 처리기란? 여러 개의 물리적 프로세서를 제공하는 시스템 각 프로세서에는 하나의 단일 코어 CPU가 포함되어 있음 최신 컴퓨팅 시스템에서의 다중 처리기는 아래의 아키텍처들을 사용 가능 다중 코어 CPU 다중 스레드 코어 NUMA 시스템 이기종 다중 처리 다중 처리기 스케줄링에 대한 접근 방법 다중 처리기 시스템의 CPU 스케줄링에 관한 해결 방법 비대칭 다중 처리(asymmetric multiprocessing) 마스터 서버라는 하나의 처리기가 모든 스케줄링 결정과 I/O 처리, 다른 시스템의 활동을 취급 다른 처리기들은 사용..
문제 이해 단계 https://www.acmicpc.net/problem/13172 13172번: Σ 모듈러가 11에서 1,000,000,007이 되어 답이 달라졌지만, 역시 3을 곱한 다음 1,000,000,007으로 나눈 나머지는 7이 된다. www.acmicpc.net 문제가 거의 비문학 지문이다. 여기서 문제 풀이에 필요한 정보만 뽑아보자. 1. 각 주사위에서 얻을 수 있는 기댓값은 a * b^(-1) modX를 계산해야 한다. 여기서 a는 모든 면에 적힌 숫자의 합이고, b는 주사위 면에 개수이다. 2. b^(-1)는 b의 모듈러 곱셈에 대한 역원인데, 구하는 방법은 b^(X-2) = b^(-1) modX이다. 3. 모든 주사위를 한 번씩 던졌을 때 나온 숫자들의 합의 기댓값을 얻기 위해서는 각..
문제 이해 단계 https://www.acmicpc.net/problem/12851 12851번: 숨바꼭질 2 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 www.acmicpc.net X좌표로만 이루어진 맵이 존재한다. 출발점 N과 도착점 K가 입력으로 들어온다. 출발점 N에서 할 수 있는 움직임은 총 3개이다. 1. X+1 2. X-1 3. X*2 3개의 움직임을 적절히 조합해서 도착점 K까지 갈 수 있는 가장 빠른 시간을 구하고, 가장 빠른 시간으로 갈 수 있는 경우의 수를 출력하는 문제 문제 접근 단계 숨바꼭질 시리즈 ..
문제 이해 단계 https://www.acmicpc.net/problem/11054 11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net 바이토닉 수열이란 어떤 수를 A라고 했을 때, a d > e > f.. 이런 식으로 이루어져야 한다. 수열 A가 입력으로 들어올 때 그 수열의 부분이 바이토닉 수열이면서, 가장 긴 수열의 길이를 구하여 그 길이를 출력해라. 문제 접근 단계 가장 긴 ~~ 수열 시리즈 문제이다. 일단 제한사항부터 살펴보면, 수열의 길이는 최대 1000까지이다. 만약 시간복잡도가 O(n^2)까지 ..