포시코딩

프림 알고리즘(Prim's algorithm) Kruskal's algorithm과 함께 대표적인 최소 신장 트리(Minimum Spanning Tree) 알고리즘 중 하나 Kruskal's algorithm보다 다소 복잡도가 올라간 알고리즘이다. 시작 정점을 선택한 후, 정점에 인접한 간선 중 최소 간선으로 연결된 정점을 선택하고, 해당 정점에서 다시 최소 간선으로 연결된 정점을 선택하는 방식으로 최소 신장 트리를 확장해가는 방식 Kruskal's algorithm과 Prim's algorithm 비교 둘 다 탐욕 알고리즘을 기초로 하고 있음(당장 눈 앞의 최소 비용을 선택해서, 결과적으로 최적의 솔루션을 찾음) Kruskal's algorithm은 가장 가중치가 작은 간선부터 선택하면서 MST를 구한..

키워드 memory, binding, mmu, dynamic loading, dynamic linking, overlay, swapping Memory란? 주소를 통해 접근하는 매체 주소는 두가지로 나눌 수 있다. Logical Address: 논리적 주소 Physical Address: 물리적 주소 Logical vs. Physical Address Logical Address (=Virtual Address) 프로세스마다 독립적으로 가지는 주소 공간 각 프로세스마다 0번지부터 시작 CPU는 하드웨어라 physical address를 바라볼 것 같지만 CPU가 바라보는 주소는 logical address임 -> 컴파일 되면 안에 들어가 있는 주소를 바꿀 수 없기 때문에 즉, 메모리 상의 주소는 바뀌지만..

https://www.acmicpc.net/problem/1374 1374번: 강의실 첫째 줄에 강의의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 줄마다 세 개의 정수가 주어지는데, 순서대로 강의 번호, 강의 시작 시간, 강의 종료 시간을 의미한다. 강의 www.acmicpc.net https://www.acmicpc.net/problem/1439 1439번: 뒤집기 다솜이는 0과 1로만 이루어진 문자열 S를 가지고 있다. 다솜이는 이 문자열 S에 있는 모든 숫자를 전부 같게 만들려고 한다. 다솜이가 할 수 있는 행동은 S에서 연속된 하나 이상의 숫자를 잡고 모 www.acmicpc.net https://www.acmicpc.net/problem/1092 109..

키워드 deadlock, mutual exclusion, no preemption, hold and wait, circular wait, resource-allocation graph, deadlock prevention, deadlock avoidance, deadlock detection and recovery, deadlock ignorance Deadlock(교착상태) 일련의 프로세스들이 서로가 가진 자원을 기다리며 block된 상태 Resource(자원) 하드웨어, 소프트웨어 등을 포함하는 개념 ex) I/O device, CPU cycle, memory space, semaphore 등 프로세스가 자원을 사용하는 절차 Request(요청), Allocate(획득), Use(사용), Releas..

문제 https://www.acmicpc.net/problem/1233 1233번: 주사위 지민이는 주사위 던지기 게임을 좋아하여 어느 날 옆에 있는 동호를 설득하여 주사위 던지기 게임을 하자고 하였다. 총 3개의 주사위가 있다. 그리고 이 주사위는 각각 S1(2 ≤ S1 ≤ 20), S2(2 ≤ S2 www.acmicpc.net 브론즈 2의 난이도 문제 치고 푸는데 생각도 오래 하고 걸리기도 오래 걸린데다 푸는 방법도 여러 방법으로 나와서 따로 포스팅하게 되었다. 일단 들어가기 앞서 완전 탐색만 알았지 브루트 포스는 처음 들어보는 알고리즘이었는데 알고보니 둘 다 같은 말이었다. brute = 단순히, 짐승이란 뜻 force = 힘 그냥 짐승처럼 힘만 갖고 밀어붙인다는 뜻으로 0000부터 9999까지 가..

문제 https://www.acmicpc.net/problem/10809 10809번: 알파벳 찾기 각각의 알파벳에 대해서, a가 처음 등장하는 위치, b가 처음 등장하는 위치, ... z가 처음 등장하는 위치를 공백으로 구분해서 출력한다. 만약, 어떤 알파벳이 단어에 포함되어 있지 않다면 -1을 출 www.acmicpc.net 시간 제한과 메모리 제한도 넉넉하기 때문에 파이썬에서 문자열을 아스키 코드로 변환하는 함수를 알면 쉽게 풀 수 있는 문제다. 난이도도 solved.ac 기준 브론즈 2로 낮은 편에 속한다. 내 풀이 S = input() for x in range(ord('a'), ord('z')+1): print(S.find(chr(x)), end=' ') 알파벳의 아스키 코드 변환 함수인 or..

키워드 process synchronization, concurrency control, 병행 제어, semaphore, monitor Process Synchronization concurrency control, 병행 제어라고도 부른다. Semaphore 프로그래머 관점에서 concurrency control을 잘하기 위한 방법을 제공하기 위한 수단으로 P 연산과 V 연산으로 구성된 일종의 추상자료형 P 연산: 자원을 획득하는 과정을 나타내는 연산 V 연산: 자원을 반납하는 과정을 나타내는 연산 고전적인 프로세스 동기화 문제 세 가지 Bounded-Buffer Problem(Producer-Consumer Problem) Readers and Writers Problem Dining-Philosoph..

키워드 semaphore, synchronization, bounded-buffer problem, producer-consumer problem, readers and writers problem, dining-philosophers problem, monitor Classical Problems of Synchronization Bounded-Buffer Problem(Producer-Consumer Problem) Readers and Writers Problem Dining-Philosophers Problem Bounded-Buffer Problem (=Producer-Consumer Problem) Buffer: 임시로 데이터를 저장하는 공간 Buffer의 크기가 유한한 환경에서의 생산자-소비..

키워드 semaphores, busy-wait, block/wakeup, deadlock, starvation Semaphores P(S): while (S 식사하는 철학자 문제에서 더 자세히 Dining-Philosophers Problem (=식사하는 철학자 문제) starvation 한쪽에서 식사를 위해 양쪽의 젓가락을 잡은 경우 그 옆에 사람은 식사를 마칠 때까지 기다리지만 만약 식사가 끝난 직후 옆옆 사람이 양쪽 젓가락을 잡고 식사를 시작하고, 그게 반복되면 그 중간의 사람은 영원히 식사를 할 수 없게 됨 deadlock 만약 모든 사람이 동시에 왼쪽 젓가락을 잡아 버리면 다섯 명이 모두 영원히 식사를 하지 못하게 됨

키워드 critical-sectioin, peterson's algorithm, synchronization hardware, semaphores The Critical-Section Problem 프로그램적 해결법 충족 조건 Mutual Exclusion(상호 배제) 어떤 프로세스가 크리티컬 섹션에 들어가 있으면 다른 모든 프로세스는 크리티컬 섹션에 들어가지 못하게 한다. Progress(진행) 크리티컬 섹션에 아무도 들어가있지 않은 상황에서 내가 들어가고자 하면 들어가게 해줘야 한다. 둘이 동시에 들어가려는 상황에서 둘 다 안들어가있음에도 둘 다 못들어가는 문제 고려 Bounded Waiting(유한 대기) 기다리는 시간이 유한해야함 크리티컬 섹션에 들어가고자 하는 프로세스가 세 개 있을 때 둘이서만..