programmer life guidance 101

[ 메모리 관리 전략 ] 메모리 관리 전략에 대한 내용은 https://jhnyang.tistory.com/ 를 일부 참고하였습니다. 프로세스는 실행중인 프로그램이고, 각각의 프로세스는 독립된 메모리 공간을 갖고, 운영체제 혹은 다른 프로세스의 메모리 공간에 접근할 수 없는 제한이 걸려있다. 단지, 운영체제만이 운영체제 메모리 영역과 사용자 메모리 영역의 접근에 제약을 받지 않는다. 따라서 우리가 컴퓨터를 잘 활용하려면, 가능한 가장 효율적인 방법으로 메인 메모리를 분할하고 할당해야 한다. Dynamic Loading Loading이란, 데이터를 메모리에 옮기는 것이다. 프로그램을 실행시키면, .exe에 있는 파일이 메모리에 올라가야 실행이 되는 것과 같이 데이터를 메모리에 옮기는 것을 로딩 즉, 메모리..

https://www.acmicpc.net/problem/11000 11000번: 강의실 배정 첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000) 이후 N개의 줄에 Si, Ti가 주어진다. (1 ≤ Si < Ti ≤ 109) www.acmicpc.net 시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율 1 초 256 MB 9789 2919 2065 29.179% 문제 수강신청의 마스터 김종혜 선생님에게 새로운 과제가 주어졌다. 김종혜 선생님한테는 Si에 시작해서 Ti에 끝나는 N개의 수업이 주어지는데, 최소의 강의실을 사용해서 모든 수업을 가능하게 해야 한다. 참고로, 수업이 끝난 직후에 다음 수업을 시작할 수 있다. (즉, Ti ≤ Sj 일 경우 i 수업과 j 수업은 같이 들을 수 있다..

https://www.acmicpc.net/problem/1543 1543번: 문서 검색 세준이는 영어로만 이루어진 어떤 문서를 검색하는 함수를 만들려고 한다. 이 함수는 어떤 단어가 총 몇 번 등장하는지 세려고 한다. 그러나, 세준이의 함수는 중복되어 세는 것은 빼고 세야 한 www.acmicpc.net 시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율 2 초 128 MB 9165 3397 2678 36.730% 문제 세준이는 영어로만 이루어진 어떤 문서를 검색하는 함수를 만들려고 한다. 이 함수는 어떤 단어가 총 몇 번 등장하는지 세려고 한다. 그러나, 세준이의 함수는 중복되어 세는 것은 빼고 세야 한다. 예를 들어, 문서가 abababa이고, 그리고 찾으려는 단어가 ababa라면, 세준이의 이..

Deadlock RAG Resource Allocation Graph (자원 할당 그래프) 자원할당 그래프란, 프로세스의 자원 할당 상태를 표현해주는 그래프이다. 동그라미는 프로세스, 네모는 자원, 점은 자원의 Instance를 의미한다. 프로세스 -> 자원 : 프로세스가 해당 자원을 요청하는 것을 의미한다. 자원 -> 프로세스 : 프로세스가 해당 자원을 소유하는 것을 의미한다. 위 RAG는 Deadlock이 아니다. P3가 작업을 마치고 자원 R3을 반납한다면, P2는 R3를 할당받아 잡업을 수행할 수 있다. RAG에 Cycle이 존재 하지 않으면 Deadlock이 아니다. RAG에 Cycle이 존재 한다면, Deadlock일 수도, 아닐수도 있다. 위의 두 RAG모두 Cycle이 존재하지만, 왼쪽 그..

전통적인 동기화 문제 1. Producer-Consumer Problem 생산자-소비자 문제 데이터를 생산하는 쪽이 생산자, 소비하는 쪽이 소비자이다. 생산자-소비자 문제란 생산자가 데이터를 생성하여 버퍼에 저장하고, 소비자가 버퍼에서 데이터를 가져와 소비하는 과정에서 발생할 수 있는 문제이다. 대표적으로 공유 자원에 대한 임계구역 문제와, busy waiting문제가 있으며 프로세스 동기화로 이 문제를 해결한다. 2. Readers - Writers Problem 독자-저자 문제 독자(Reader)는 데이터를 읽기만하는 프로세스, 저자(Write)는 읽고 수정하는 프로세스이다. 따라서 이들의 차이점은 데이터를 수정할 수 있느냐, 없느냐이다. 독저-저자 문제란 다수의 독자와 다수의 저자가 하나의 공통 데..

https://www.acmicpc.net/problem/13565 13565번: 침투 첫째 줄에는 격자의 크기를 나타내는 M (2 ≤ M ≤ 1,000) 과 N (2 ≤ N ≤ 1,000) 이 주어진다. M줄에 걸쳐서, N개의 0 또는 1 이 공백 없이 주어진다. 0은 전류가 잘 통하는 흰색, 1은 전류가 통하지 않 www.acmicpc.net 시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율 1 초 512 MB 3049 1282 967 44.236% 문제 인제대학교 생화학연구실에 재직중인 석교수는 전류가 침투(percolate) 할 수 있는 섬유 물질을 개발하고 있다. 이 섬유 물질은 2차원 M × N 격자로 표현될 수 있다. 편의상 2차원 격자의 위쪽을 바깥쪽(outer side), 아래쪽을 ..

https://www.acmicpc.net/problem/12757 12757번: 전설의 JBNU 첫 줄에는 초기 데이터의 개수인 \(N(1 \le N \le 100,000)\) 과 명령 횟수인 \(M(1 \le M \le 100,000)\), 가장 근접한 Key까지의 거리의 제한인 \(K(1 \le K \le 10,000)\)가 주어진다. 입력의 둘째 줄부터 N개의 줄에 www.acmicpc.net 시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율 2 초 128 MB 481 135 107 33.127% 문제 전설의 프로그래머 윤준하는 독자적인 데이터베이스 시스템 JBNU(Jeong Bo Neoh Um)를 만들었다. 준하가 생각한 데이터베이스의 기본 골자는 데이터에 접근하기 위한 Key와 그 데이터..

https://www.acmicpc.net/problem/11085 11085번: 군사 이동 전쟁 당시 Baekjoon World의 국왕은 Cube World를 공격할 작전을 세운 적이 있습니다. Baekjoon World와 Cube World는 p개의 지점과 w개의 길로 표현됩니다. 모든 길은 양방향이며, 각 길마다 너비가 존재하여 www.acmicpc.net 시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율 2 초 256 MB 514 330 262 61.358% 문제 전쟁 당시 Baekjoon World의 국왕은 Cube World를 공격할 작전을 세운 적이 있습니다. Baekjoon World와 Cube World는 p개의 지점과 w개의 길로 표현됩니다. 모든 길은 양방향이며, 각 길마다 너비..

https://www.acmicpc.net/problem/10423 10423번: 전기가 부족해 첫째 줄에는 도시의 개수 N(1 ≤ N ≤ 1,000)과 설치 가능한 케이블의 수 M(1 ≤ M ≤ 100,000)개, 발전소의 개수 K(1 ≤ K ≤ N)개가 주어진다. 둘째 줄에는 발전소가 설치된 도시의 번호가 주어진다. 셋째 www.acmicpc.net 시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율 1 초 256 MB 1149 746 573 68.133% 문제 세계에서 GDP가 가장 높은 서강 나라는 소프트웨어와 하드웨어 기술이 모두 최고라서 IT강국이라 불리고, 2015년부터 세상에서 가장 살기 좋은 나라 1등으로 꼽히고 있다. 살기 좋은 나라 1등으로 꼽힌 이후 외국인 방문객들이 많아졌고, ..

Priority Inversion & Priority Inheritance 우선순위 역전과 우선순위 상속 이제 한번 progress(No Deadlock)하고, bounded-waiting(No Prioity Inversion)의 문제까지 해결해보자. 데드락 : 두 개 이상의 프로세스가 영원히 기다려야 한다. 우선순위 역전 : 높은 우선순위의 프로세스가 낮은 우선순위 프로세스에게 밀리는 현상 ## 예시 예를 들어 집에서 우선순위가 가장 높은 아빠가 TV를 보기 위해 막내에게 나가라고 한다. 근데 막내가 리모컨을 들고 나가면, 자발적으로 리모컨을 내려 놓을 때까지 티비를 보지 못한다. priority가 높음에도 불구하고 waiting queue에서 계속해서 기다리게 된다. 이를 priority-Inheri..

모니터 세마포어나 뮤텍스를 잘못 사용해서 일어나는 에러가 발생할 수 있다. 따라서 자바에서는 더욱 심플한 동기화 툴인 "모니터"를 제공한다. 고급 언어의 설계 구조물로서, 개발자의 코드를 상호배제 하게끔 만든 추상화된 데이터 형태이다. 공유자원에 접근하기 위한 키 획득과 자원 사용 후 해제를 모두 처리한다. (세마포어는 직접 키 해제와 공유자원 접근 처리가 필요하다. - 모니터의 개념 하나의 데이터(객체)마다 하나의 모니터를 결합할 수 있으며, 모니터는 그것이 결합된 데이터(객체)가 동시에 두 개 이상의 스레드에 의해 접근할 수 없도록 막는 잠금(lock)기능을 제공함으로써, 동기화를 수행하는 동기화 도구이다. 즉, 데이터(객체)에 모니터를 결합하면 하나의 스레드가 그 데이터를 사용하는 동안에는 다른 스..

앞서 총 두 가지의 임계영역 문제의 솔루션을 알아보았다. SW 솔루션 : Peterson&#39;s Algorithm HW 솔루션 : "test-and-set" , "compare-and-swap" 을 이용한 Atomic Variable HW instruction이다. 이제 조금 더 SW에서 고급 레벨의 솔루션을 알아 볼 것이다. Mutex (Binary Semaphore) : 가장 간단한 동기화 툴 (locking : 열쇠) Semaphore(Counting Semaphore) : 더욱 편리하고 효과적 Monitor : 뮤텍스와 세마포어의 단점을 극복 --> Java에서 생각하는 locking은 모두 Monitor이다. Lock 하드웨어 기반 해결책으로써, 동시에 공유 자원에 접근하는 것을 막기 위해 ..

[ 프로세스 동기화 ] Critical Section 임계영역 멀티 스레딩에 문제점에서 나오듯, 동일한 자원을 동시에 접근하는 작업(e.g. 공유하는 변수 사용, 동일 파일을 사용하는 등)을 실행하는 코드 영역을 Critical Section 이라 칭한다. 다른 프로세스와 공동으로 사용하는 변수, 테이블, 파일 등을 변경하는 부분이다. Critical Section Problem 임계영역 문제 프로세스들이 Critical Section 을 함께 사용할 수 있는 프로토콜을 설계하는 것이다. Race Conditoin 여러 프로세스가 공통된 데이터를 조작할 때 결과가 조작의 타이밍이나 접근 순서에 의해 결정되는 현상 Requirements 해결을 위한 기본 조건 Mutual Exclusion(상호 배제) 프..

https://www.acmicpc.net/problem/14675 14675번: 단절점과 단절선 프로그램의 입력은 표준 입력으로 받는다. 입력의 첫 줄에는 트리의 정점 개수 N이 주어진다. (2 ≤ N ≤ 100,000) 트리의 정점은 1번부터 n번까지 존재한다. 다음 줄부터 N-1개의 줄에 걸쳐 간선의 정 www.acmicpc.net 시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율 1 초 512 MB 976 508 407 55.000% 문제 그래프 이론에서 단절점(cut vertex)과 단절선(bridge)은 다음과 같이 정의 된다. 단절점(cut vertex) : 해당 정점을 제거하였을 때, 그 정점이 포함된 그래프가 2개 이상으로 나뉘는 경우, 이 정점을 단절점이라 한다. 단절선(bridg..

https://www.acmicpc.net/problem/10159 10159번: 저울 첫 줄에는 물건의 개수 N 이 주어지고, 둘째 줄에는 미리 측정된 물건 쌍의 개수 M이 주어진다. 단, 5 ≤ N ≤ 100 이고, 0 ≤ M ≤ 2,000이다. 다음 M개의 줄에 미리 측정된 비교 결과가 한 줄에 하나씩 www.acmicpc.net 시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율 1 초 256 MB 5010 3068 2484 63.709% 문제 무게가 서로 다른 N 개의 물건이 있다. 각 물건은 1부터 N 까지 번호가 매겨져 있다. 우리는 일부 물건 쌍에 대해서 양팔 저울로 어떤 것이 무거운 것인지를 측정한 결과표를 가지고 있다. 이 결과표로부터 직접 측정하지 않은 물건 쌍의 비교 결과를 알아..