programmer life guidance 101

https://www.acmicpc.net/problem/8980 8980번: 택배 입력의 첫 줄은 마을 수 N과 트럭의 용량 C가 빈칸을 사이에 두고 주어진다. N은 2이상 2,000이하 정수이고, C는 1이상 10,000이하 정수이다. 다음 줄에, 보내는 박스 정보의 개수 M이 주어진다. M은 1이 www.acmicpc.net 시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율 1 초 128 MB 5058 1744 1275 36.242% 문제 아래 그림과 같이 직선 도로상에 왼쪽부터 오른쪽으로 1번부터 차례대로 번호가 붙여진 마을들이 있다. 마을에 있는 물건을 배송하기 위한 트럭 한 대가 있고, 트럭이 있는 본부는 1번 마을 왼쪽에 있다. 이 트럭은 본부에서 출발하여 1번 마을부터 마지막 마을까지..

https://www.acmicpc.net/problem/2458 2458번: 키 순서 1번부터 N번까지 번호가 붙여져 있는 학생들에 대하여 두 학생끼리 키를 비교한 결과의 일부가 주어져 있다. 단, N명의 학생들의 키는 모두 다르다고 가정한다. 예를 들어, 6명의 학생들에 대하여 www.acmicpc.net 시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율 1 초 128 MB 8063 4252 3086 52.172% 문제 1번부터 N번까지 번호가 붙여져 있는 학생들에 대하여 두 학생끼리 키를 비교한 결과의 일부가 주어져 있다. 단, N명의 학생들의 키는 모두 다르다고 가정한다. 예를 들어, 6명의 학생들에 대하여 6번만 키를 비교하였고, 그 결과가 다음과 같다고 하자. 1번 학생의 키 < 5번 학..

[ 동기와 비동기 ] 동기 Synchronous 동기는 말 그대로 동시에 일어난다는 뜻이다. 요청과 그 결과가 동시에 일어난다는 약속이다. 바로 요청을하면 시간이 얼마가 걸리던지 요청한 자리에서 결과가 주어져야 한다. 요청과 결과가 한 자리에서 동시에 일어남 A노드와 B노드 사이의 작업 처리 단위(transaction)을 동시에 맞추겠다. 설계가 매우 간단하고 직관적이지만 결과가 주어질 때까지 아무것도 못하고 대기해야 하는 단점이 있다. 비동기 Asynchoronous 비동기는 동시에 일어나지 않는다를 의미한다. 요청과 그 결과가 동시에 일어나지 않을거라는 약속이다. 요청한 그 자리에서 결과가 주어지지 않음 노드 사이의 작업 처리 단위를 동시에 맞추지 않아도 된다. 동기보다 복잡하지만 결과가 주어지는데 ..

[ CPU 스케쥴러 ] 여러 프로세스를 concurrent하게 쓰는게 멀티프로그래밍과 멀티쓰레딩이었고, 그 전제조건으로 바로 CPU Scheduling이 필요하다. 스케줄링 대상은 Ready Queue 에 있는 프로세스들이다. (이 Ready Queue는 LinkedList or Binary Tree or FIFO Queue or PriorityQueue를 사용하여 만들어진다.) 들어가기 전에 먼저 용어 정리 부터 하겠다. 선점(preemptive) : 우선순위가 높은 작업이 오거나, 해당 작업이 더 우선되어야 한다고 판단되면 해당 작업에게서 CPU를 빼앗을 수 있다. 비선점(non-preemptive) : 일단 CPU를 할당받으면 해당 프로세스가 끝날때까지 CPU를 빼앗기지 않는다. 스케쥴링 알고리즘에..

https://www.acmicpc.net/problem/14950 시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율 2 초 256 MB 543 297 237 54.483% 문제 서강 나라는 N개의 도시와 M개의 도로로 이루어졌다. 모든 도시의 쌍에는 그 도시를 연결하는 도로로 구성된 경로가 있다. 각 도로는 양방향 도로이며, 각 도로는 사용하는데 필요한 비용이 존재한다. 각각 도시는 1번부터 N번까지 번호가 붙여져 있다. 그 중에서 1번 도시의 군주 박건은 모든 도시를 정복하고 싶어한다. 처음 점거하고 있는 도시는 1번 도시 뿐이다. 만약 특정 도시 B를 정복하고 싶다면, B와 도로로 연결된 도시들 중에서 적어도 하나를 정복하고 있어야 한다. 조건을 만족하는 도시 중에서 하나인 A를 선택하면, B..

https://www.acmicpc.net/problem/10713 시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율 1 초 256 MB 961 398 279 42.401% 문제 JOI나라에는 N개의 도시가 있고, 각 도시에 1,2,...,N까지의 번호를 갖고 있다. 그리고, 철도가 N-1개 있고, 각 철도에 1,2,...N-1의 번호를 갖고 있다. 철도 i (1 ≦ i ≦ N − 1)는 도시 i과 도시 i+1을 양방향으로 연결시키는 철도를 의미한다. JOI나라의 철도를 타는 방법에는, 티켓을 구입해 승차하는 방법과 IC카드로 승차하는 방법 두 가지가 존재한다. 철도 i에 티켓을 구입해 승차할 때는 Ai 원의 비용이 든다. 철도 i에 IC카드로 승차하는 경우에는 Bi 원의 비용이 든다. 하지만 IC..

https://www.acmicpc.net/problem/10427 시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율 1 초 256 MB 106 52 48 56.471% 문제 민균이에게는 ‘빚쟁이’ 라는 별명이 있다. 이 별명은 악덕 사채업을 하는 김우현연구소에서 민균이가 빌린돈을 잘 갚지 않는다고 하여 붙여준 이름이다. 민균이가 최근 N (1 ≤ N ≤ 4000) 번 돈을 빌렸고, 그때마다 빌린 돈이 각각 A(1), A(2), …, A(N) (1 ≤ A(i) ≤ 104) 라고 하자. 악덕 사채업소 김우현 연구소는 이름만큼이나 빌린 돈을 갚는 방식이 독특하다. 먼저, 김우현 연구소가 민균이에게 M번 (1 ≤ M ≤ N) 의 빚을 갚으라고 명령하면, 민균이는 N번중 아무렇게나 M 번을 고르고, 고른 ..

[ 스케쥴러 ] 프로세스를 스케줄링하기 위한 Queue 에는 세 가지 종류가 존재한다. Job Queue : 현재 시스템 내에 있는 모든 프로세스의 집합 Ready Queue : 현재 메모리 내에 있으면서 CPU 를 잡아서 실행되기를 기다리는 프로세스의 집합 Device Queue : Device I/O 작업을 대기하고 있는 프로세스의 집합 각각의 Queue 에 프로세스들을 넣고 빼주는 스케줄러에도 크게 세 가지 종류가 존재한다. 장기스케줄러 Long-term Scheduler or Job Scheduler 메모리는 한정되어 있는데 많은 프로세스들이 한꺼번에 메모리에 올라올 경우, 대용량 메모리(일반적으로 디스크)에 임시로 저장된다. 이 pool 에 저장되어 있는 프로세스 중 어떤 프로세스에 메모리를 할..

[ 멀티 스레드 ] 멀티 쓰레드 모델을 살펴보기 전에 먼저 User Thread와 Kernel Thread에 관해 살펴보자. 말 그대로 User Thread는 User level의 Thread 라이브러리를 통해 관리되는 Thread를 말하며 Kernel Thread는 운영체제가 제공하고 직접 관리하는 Thread를 말한다 Multi-Thread에는 총 네 가지 모델이 있다. Many-to-One Model Kernel Thread가 다수의 User Thread를 처리하는 구조이다. 이러한 구조는 User Thread를 처리하던 중 System call에 의해 blocking이 된다면 전체 프로세스가 막히는 병목현상이 일어나게 되는 문제점을 갖고 있다. One-to-One Model One-to-One m..

https://www.acmicpc.net/problem/20495 20495번: 수열과 헌팅 예제에서, 수열의 수들을 차례로 x1, x2, x3이라 하자. -10 ≤ x1 ≤ 30, 25 ≤ x2 ≤ 55, 55 ≤ x3 ≤ 85이다. 만약 (x1, x2, x3) = (28, 25, 70)이라면, x2가 첫번째, x1이 두번째, x3이 세 번째 수가 된다. 또, (x1, x2 www.acmicpc.net 시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율 1 초 1024 MB 175 74 63 51.220% 문제 준원이는 여자친구를 만들 시나리오를 진지하게 세우고 있다. 먼저, 지나가던 아름다운 여성 분이 준원이에게 길이가 N인 수열 arr을 정렬해달라고 부탁한다. 그리고 준원이는 #include ..

https://www.acmicpc.net/problem/16719 16719번: ZOAC 2018년 12월, 처음 시작하게 된 ZOAC의 오프닝을 맡은 성우는 누구보다 화려하게 ZOAC를 알리려 한다. 앞 글자부터 하나씩 보여주는 방식은 너무 식상하다고 생각한 성우는 문자열을 보여주는 새로 www.acmicpc.net 시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율 1 초 256 MB 620 298 243 51.812% 문제 2018년 12월, 처음 시작하게 된 ZOAC의 오프닝을 맡은 성우는 누구보다 화려하게 ZOAC를 알리려 한다. 앞 글자부터 하나씩 보여주는 방식은 너무 식상하다고 생각한 성우는 문자열을 보여주는 새로운 규칙을 고안해냈다! 규칙은 이러하다. 아직 보여주지 않은 문자 중 추가..

https://www.acmicpc.net/problem/1368 1368번: 물대기 첫 줄에는 논의 수 N(1 ≤ N ≤ 300)이 주어진다. 다음 N개의 줄에는 i번째 논에 우물을 팔 때 드는 비용 Wi(1 ≤ Wi ≤ 100,000)가 순서대로 들어온다. 다음 N개의 줄에 대해서는 각 줄에 N개의 수가 들어 www.acmicpc.net 시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율 2 초 128 MB 536 213 163 40.148% 문제 선주는 자신이 운영하는 N개의 논에 물을 대려고 한다. 물을 대는 방법은 두 가지가 있는데 하나는 직접 논에 우물을 파는 것이고 다른 하나는 이미 물을 대고 있는 다른 논으로부터 물을 끌어오는 법이다. 각각의 논에 대해 우물을 파는 비용과 논들 사이에 ..

[ 프로세스간 통신 ] IPC Inter Process Communication 각 프로세스들이 통신하는 모든 형태를 일컫는다. 이에는 다양한 형태의 메세지 전달 방식이 포함된다. 종류 Shared Memory 프로세스간 공유되는 메모리 영역을 만들어 사용하는 방법 프로세스들은 읽기/쓰기를 통해 공유영역을 수정할 수 있다. 주로 부모/자식 프로세스 간에 사용한다. Message Passing 다른 프로세스에 message 를 보내 정보를 교환하는 방법 주로 작은 데이터를 교환하며 구현이 쉽다. system call이 잦아 자칫 느려질 수 있다. Sockets Network Communication의 Endpoint 간의 통신이다. IP Address, Port를 이용해 직접 통신한다. Pipe Messa..

[ 프로세스와 스레드의 차이 ] OS -> 프로세스 -> Thread OS에서 여러 개의 프로세스를 관리하고, 프로세스 안에서 여러 개의 Thread를 관리하는 것이 가능하고, 효율적이다. 프로세스 A Program in execution : 실행중인 프로그램 프로세스는 실행 중인 프로그램으로 디스크로부터 메모리에 적재되어 CPU 의 할당을 받을 수 있는 것을 말한다. 운영체제로부터 주소 공간, 파일, 메모리 등을 할당받으며 이것들을 총칭하여 프로세스라고 한다. 구체적으로 살펴보면 프로세스는 함수의 매개변수, 복귀 주소와 로컬 변수와 같은 임시 자료를 갖는 프로세스 스택과 전역 변수들을 수록하는 데이터 섹션을 포함한다. 또한 프로세스는 프로세스 실행 중에 동적으로 할당되는 메모리인 힙을 포함한다. 프로세..

https://www.acmicpc.net/problem/14267 14267번: 회사 문화 1 영선회사에는 매우 좋은 문화가 있는데, 바로 상사가 직속 부하를 칭찬하면 그 부하가 부하의 직속 부하를 연쇄적으로 칭찬하는 내리 칭찬이 있다. 즉, 상사가 한 직속 부하를 칭찬하면 그 부하 www.acmicpc.net 시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율 2 초 512 MB 1729 669 508 40.095% 문제 영선회사에는 매우 좋은 문화가 있는데, 바로 상사가 직속 부하를 칭찬하면 그 부하가 부하의 직속 부하를 연쇄적으로 칭찬하는 내리 칭찬이 있다. 즉, 상사가 한 직속 부하를 칭찬하면 그 부하의 모든 부하들이 칭찬을 받는다. 모든 칭찬에는 칭찬의 정도를 의미하는 수치가 있는데, 이 ..