포시코딩

PriorityQueue 사용법 from queue import PriorityQueue pqueue = PriorityQueue() pqueue.put((5, 'Python')) pqueue.put((15, 'Javascript')) pqueue.put((10, 'Java')) arr = [] while not pqueue.empty(): value, data = pqueue.get() arr.append((value, data)) print(arr) # [(5, 'Python'), (10, 'Java'), (15, 'Javascript')] 선언 from queue import PriorityQueue pqueue = PriorityQueue() 데이터 삽입 pqueue.put((1, 'Python'..

https://www.acmicpc.net/problem/17298 17298번: 오큰수 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다. www.acmicpc.net https://www.acmicpc.net/problem/1874 1874번: 스택 수열 1부터 n까지에 수에 대해 차례로 [push, push, push, push, pop, pop, push, push, pop, push, push, pop, pop, pop, pop, pop] 연산을 수행하면 수열 [4, 3, 6, 8, 7, 5, 2, 1]을 얻을 수 있다. www.acmicpc.net https://..

Union-Find 개요 집합에는 두가지 종류의 연산이 필요 membership 연산: 집합에 포함된 값인지 합집합(Union), 교집합(Intersection), 차집합(Difference) 파이썬에서는 Set을 통해 집합을 표현할 수 있다. Dict도 가능하지만 중복 key에 대한 처리를 해줘야 함으로 Set이 더 효과적 집합의 함수 집합에는 다음과 같은 함수들이 필요하다. make-set(x) -> x만으로 구성된 집합을 정의(make) find(x): membership fn -> x가 속한 집합의 대표값 리턴 ex) 두 집합 S, T가 있을 때, find(5)라고 한 경우 T에 5가 포함되어 있다면 T를 대표하는 값을 리턴 union(x, y) -> 두 key 값 x, y를 하나의 집합으로 합침..

https://www.acmicpc.net/problem/1920 1920번: 수 찾기 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들 www.acmicpc.net 위 문제를 풀면서 나는 이진 탐색을 통해 문제를 해결했지만 간단하게 자료구조와 if not in 커맨드를 통해 해결하는 방법도 있어서 공부를 하던 중 N = int(input()) arr = list(map(int, input().split())) M = int(input()) target_arr = list(map(int, input().split..

키워드 synchronization, race condition, critical section 데이터의 접근 추상적으로 아래와 같이 구분됨 Storage Box: 데이터가 저장되어 있는 위치 Execution Box: 실제 연산하는 위치 데이터를 읽기만 하면 누가 먼저 읽든, 읽는 동안 다른 곳에서 읽든 문제될 게 없지만 데이터를 읽어와 연산 후 데이터를 수정하여 저장하는 방식에서는 누가 먼저 읽었느냐에 따라 결과가 달라질 수도 있는 등 여기서 생기는 문제를 Synchronization 문제라고 한다. 마찬가지로 한 곳에선 데이터를 증가시키려 하고 다른 곳에선 데이터를 감소시키려 하면 문제가 발생 -> Race Condition(경쟁 상태) Multiprocessor system처럼 메모리를 공유한다면..

키워드 multiple-processor scheduling, real-time scheduling, thread scheduling, algorithms evaluation, 알고리즘 평가 Scheduling Algorithms Multiple-Processor Scheduling CPU가 여러 개 있는 시스템에서의 스케줄링 Homogeneous processor 어떤 Job은 특정 CPU가 실행해야 되는 경우 ex) 미용실 갔을 때 제일 눈 앞에 보이는 사람한테 깎지 않고 지명한 사람한테 깎는 경우 Load sharing 특정 CPU만 일하고 나머지 CPU는 놀지 않도록 부하를 적절히 조절하는 메커니즘 필요 별개의 큐를 두는 방법 vs 공동 큐를 사용하는 방법 Symmetric Multiprocess..

키워드 scheduling algorithms, 성능 척도, fcfs, sjf, priority scheduling, round robin, multilevel queue, multilevel feedback queue Scheduling Algorithms 성능 척도 (Scheduling Criteria = Performance Index = Performance Measure) 시스템 입장에서의 성능 척도 CPU utilization(이용률) 전체 시간 중 CPU가 놀지 않고 일한 시간의 비율 최대한 일 시키기 Throughput(처리량) 주어진 시간 동안 몇 개의 작업을 완료했나 프로세스 입장에서의 성능 척도 Turnaround time(소요 시간, 반환 시간) 프로세스가 CPU를 쓰러 들어와서 다..

https://www.acmicpc.net/problem/10816 10816번: 숫자 카드 2 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10, www.acmicpc.net https://www.acmicpc.net/problem/1654 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 www.acmicpc.net https://www.a..

문제 https://www.acmicpc.net/problem/2805 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보 www.acmicpc.net 이코테의 떡볶이 떡 만들기 문제와 동일하다. 구현 이진 탐색에 대해서는 숫자로 이루어진 배열 안에서 특정 숫자가 존재하는지 찾는거에 대해서만 배운 상태였어서 이진 탐색을 활용해 어떻게 푸는지도 감을 잡지 못했는데 파라메트릭 서치 알고리즘으로 풀면 된다는 해설을 보면서 점점 이해가 됐던 것 같다. 파라메트릭 서치로 문제를 바라보면 다음과 같다. 최적화 N..

문제 https://www.acmicpc.net/problem/2110 2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 www.acmicpc.net 구현 '공유기 간의 거리'를 줄이면 설치 가능한 '공유기 대수'가 늘어나고 거리를 늘리면 설치 가능한 '공유기 대수'가 줄어든다. 반대로, 설치 가능한 '공유기 대수'가 적다면 거리가 너무 길다는 뜻이니 거리를 줄여 설치 가능 대수를 늘릴 수 있고 설치 가능 대수가 '크거나 같다면' 거리를 늘리면서 (최대거리를 구해야 하니) 최대 거리도 만..