본문 바로가기

전체 글104

[C++]백준 2116번 : 주사위 쌓기 www.acmicpc.net/problem/2116 2116번: 주사위 쌓기 첫줄에는 주사위의 개수가 입력된다. 그 다음 줄부터는 한 줄에 하나씩 주사위의 종류가 1번 주사위부터 주사위 번호 순서대로 입력된다. 주사위의 종류는 각 면에 적혀진 숫자가 그림1에 있는 www.acmicpc.net 1. 접근&풀이 첫번째 주사위의 밑면(혹은 윗면)에 따라 쌓이는 다음 주사위의 밑면(혹은 윗면)이 결정되는 것을 이용한다. 입력은 주사위의 특성을 바로 활용할 수 있도록 주어지지 않으므로 특성을 이용할 수 있도록 입력받는 것이 포인트인 것 같다. (i면의 반대면은 (i+3)%6) #include #include using namespace std; int N, d[10000][6], ans = 0; int main(.. 2020. 11. 29.
[OS] 9. Deadlock 1. 조건 1) Mutual exclusion 2) Hold & Wait 3) No Preemption 4) Circular Wait : 모두를 만족해야 deadlock 생성 가능, 즉 하나만 방지하면 deadlock 불가능 2. Prevention 1) Mutual exclusion - Mutual exclusion 속성을 가지지 않은 resource에 대해서만 가능 2) Hold & Wait - 프로세스가 Task를 위한 모든 Resource를 점유해야 시작 가능하도록 설계, 하나라도 불가능하면 다시 release. - Low resource utilization, possibility of Starvation 3) No preemption - Preemption 속성을 가지지 않은 resource에.. 2020. 11. 29.
[OS] 8. Synchronization 1. 개요 - 하나의 프로세스에서 2개 이상의 Thread가 Concurrent하게 작업할 때 같은 Address space를 공유하기 때문에 같은 Data를 사용할 수 있다. - 이 상황을 Race Condition이라고 하고 이는 Non-deterministic한 결과를 낳는다. - Race Condition 때 발생하는 문제를 해결하기 위해 Synchronization을 수행한다. cf) Scheduling은 OS 권한으로 프로그래머가 통제할 대상이 아님. 2. Critical section : 임계영역 - 공유되는 자원(resource)를 사용하는 Code 부분 3. Lock 프로세스의 shared resource에 대한 점유 상태를 나타내는 것으로써 상호배제(Mutual Exclusion : M.. 2020. 11. 29.
[C++]백준 1027번 : 고층건물 www.acmicpc.net/problem/1027 1027번: 고층 건물 세준시에는 고층 빌딩이 많다. 세준시의 서민 김지민은 가장 많은 고층 빌딩이 보이는 고층 빌딩을 찾으려고 한다. 빌딩은 총 N개가 있는데, 빌딩은 선분으로 나타낸다. i번째 빌딩 (1부터 시작) www.acmicpc.net 1. 접근 기울기에 따라 옥상이 보이는지 확인할 수 있다. 2. 틀린 이유, 보완점 최대 높이가 1000000000000인 것에 따라 초기 각도 변수 값을 적절하게 초기화해주어야한다. 아니면 -DBL_MAX로 초기화해도 좋다. 추가로 선택한 건물에서 양 옆을 매번 확인할 필요없이 i->j 옥상이 보이면 j->i 옥상이 보이는 것을 이용하여 2차원 배열 check를 통해 연산을 최소화하자. #include #in.. 2020. 11. 29.
[OS] 7. Process Scheduling(2) 1. Advanced Scheduling 1) Proportional share scheduling - 프로세스 별로 비율을 정해서 CPU를 사용하는 것 2) Real time system - deadline이 있는 system Soft real time system deadline에 맞추려고 하지만 보장은 없는 system hard real time system deadline에 맞춰지지 않으면 치명적인 system 따라서 preemptive priority-based scheduling이 되어야 한다. 2. Way to guarentee deadline Interval > Deadline > Processing time이면 deadline은 보장된다. * reate of periodic process.. 2020. 11. 18.
[C++]백준 11657번 : 타임머신 www.acmicpc.net/problem/11657 11657번: 타임머신 첫째 줄에 도시의 개수 N (1 ≤ N ≤ 500), 버스 노선의 개수 M (1 ≤ M ≤ 6,000)이 주어진다. 둘째 줄부터 M개의 줄에는 버스 노선의 정보 A, B, C (1 ≤ A, B ≤ N, -10,000 ≤ C ≤ 10,000)가 주어진다. www.acmicpc.net 벨만포드 알고리즘 적용문제. 벨만포드 알고리즘은 최단거리 구하기에서 음이 가중치를 핸들링할 수 있는 알고리즘이다. 음의 사이클이 생기면 최단거리를 구할 수 없고, 이 음의 사이클을 감지할 수 있다. 정당성은 다음과 같다. 음수 사이클이 없는 그래프에서 최단 경로가 한 정점을 두 번 지나는 일은 없다는 점을 떠올리면, 최단 경로가 포함하는 간선 수의 상.. 2020. 11. 9.
[C++]백준 11779번 : 최소비용 구하기 www.acmicpc.net/problem/11779 11779번: 최소비용 구하기 2 첫째 줄에 도시의 개수 n(1≤n≤1,000)이 주어지고 둘째 줄에는 버스의 개수 m(1≤m≤100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스 www.acmicpc.net 기본적인 다익스트라 알고리즘 적용 문제 다익스트라 알고리즘은 하나의 정점에서 다른 모든 정점으로의 최단 거리를 구하는데 사용된다. 우선순위 큐를 사용하여 거리를 가중치로 두고 구현하면 시간복잡도 O(|E|log|V|)를 가진다. #include #include #include #include using namespace std; struct comp{ bool operator().. 2020. 11. 9.
[C++]백준 12094번 : 2048(HARD) www.acmicpc.net/problem/12094 12094번: 2048 (Hard) 첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2 www.acmicpc.net 1. 접근 Easy버전과 다르게 10회 반복이어서 기저를 찾아내야 한다. map을 연산한 뒤에도 이전과 같은 모습이면 해당 탐색은 취소했지만 여전히 시간초과가 났다. 2. 풀이 접근에서 발견한 기저 외에 한 가지가 더 필요했다. 최종단계까지 간 경우 결과를 바탕으로 각 단계별 최소 기댓값을 배열에 저장한다. 이 후의 탐색에서 이를 활용하여 각 단계마다 map의 최대 값을 최소 기댓값.. 2020. 11. 4.
[OS] CPU, Processor, Core, Process, Thread 그리고 관계 정리 1. HW 1) CPU : Central Processing Unit, 중앙처리장치 간단하게 컴퓨터의 뇌로써 '사고'를 담당 기억, 연산, 제어를 담당 cf) MPU, MCU - MPU : Micro Processing Unit CPU의 한 종류로써, 전자부품과 반도체칩을 하나의 작은 칩에 내장한 형태의 CPU - MCU : Micro Controller Unit CPU(또는 MPU) 및 RAM, ROM, I/O 제어회로를 단일 칩에 모두 내장한 것을 의미 한 개의 소자로 하나의 컴퓨터 기능을 수행한다 2) Processor 컴퓨터 운영을 위해 기본적인 명령어에 반응하고 처리하는 논리회로 디바이스가 해야할 일을 총 지휘하는 프로세서를 CPU라고 함(보통 프로세서와 CPU를 같은 의미로 사용) 이외의 프로.. 2020. 11. 4.

티스토리툴바