본문 바로가기

분류 전체보기155

[백준] 11399 ATM(자바) : 그리디 알고리즘 [하] ✔️ 문제 설명 더보기 문제인하은행에는 ATM이 1대밖에 없다. 지금 이 ATM앞에 N명의 사람들이 줄을 서있다. 사람은 1번부터 N번까지 번호가 매겨져 있으며, i번 사람이 돈을 인출하는데 걸리는 시간은 Pi분이다.사람들이 줄을 서는 순서에 따라서, 돈을 인출하는데 필요한 시간의 합이 달라지게 된다. 예를 들어, 총 5명이 있고, P1 = 3, P2 = 1, P3 = 4, P4 = 3, P5 = 2 인 경우를 생각해보자. [1, 2, 3, 4, 5] 순서로 줄을 선다면, 1번 사람은 3분만에 돈을 뽑을 수 있다. 2번 사람은 1번 사람이 돈을 뽑을 때 까지 기다려야 하기 때문에, 3+1 = 4분이 걸리게 된다. 3번 사람은 1번, 2번 사람이 돈을 뽑을 때까지 기다려야 하기 때문에, 총 3+1+4 = .. 2024. 8. 22.
[운영 체제] CPU Scheduling ✔️ CPU Scheduling CPU Scheduling은 CPU를 효율적으로 사용하기 위해 프로세스의 스케쥴, 즉 수행 순서를 정하는 과정이다. 운영체제의 CPU 스케줄러는 Ready 상태의 프로세스 중에서 어떤 프로세스에게 CPU를 할당할지 결정합니다.  ✔️ 선점(Preemptive)/ 비선점(Non Preemptive) 스케쥴링선점 (preemtive) : OS가 CPU의 사용권을 선점(강제 회수)할 수 있는 경우, 즉 다른 process 실행을 위해 필요하다면 현재의 process를 중단시킴.• 우선 순위가 높은 프로세스를 빠르게 처리 가능함. • 우선 순위가 낮은 프로세스가 무한정 기다리는 starvation 생길 수 있음비선점(nonpreemtive) : 프로세스 종료 또는 I/O 등의 이.. 2024. 8. 22.
[운영 체제] PCB & Context Switching ✔️ 프로세스 관리 프로세스 관리란 실행중인 프로세스가 여러 개일 때, CPU 스케줄링을 통해 프로세스를 관리하는 것을 의미한다. CPU는 각 프로세스들이 누군지 알아야 관리가 가능한데, 이때 프로세스들의 각자의 특징을 갖고 있는 Process Metadata 라는 정보를 활용한다. 프로세스 메타데이터(Process Metadata) • Process ID• Process State• Process Priority• CPU Registers• Owner• CPU Usage• Memeory Usage 이 메타데이터는 프로세스가 생성되면 PCB(Process Control Block)에 저장된다.  ✔️ PCB(Process Control Block)PCB(Process Control Block)는 프로세스.. 2024. 8. 21.
[백준] 1931 회의실 배정 (자바) : 그리디 알고리즘 [중] ✔️ 문제 설명문제한 개의 회의실이 있는데 이를 사용하고자 하는 N개의 회의에 대하여 회의실 사용표를 만들려고 한다. 각 회의 I에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수를 찾아보자. 단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 회의의 시작시간과 끝나는 시간이 같을 수도 있다. 이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다.입력첫째 줄에 회의의 수 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N+1 줄까지 각 회의의 정보가 주어지는데 이것은 공백을 사이에 두고 회의의 시작시간과 끝나는 시간이 주어진다. 시작 시간과 끝나는 시간은 231-1.. 2024. 8. 21.
[백준] 11047: 동전 0 (자바) : 그리디 알고리즘 ✔️ 문제 설명문제준규가 가지고 있는 동전은 총 N종류이고, 각각의 동전을 매우 많이 가지고 있다.동전을 적절히 사용해서 그 가치의 합을 K로 만들려고 한다. 이때 필요한 동전 개수의 최솟값을 구하는 프로그램을 작성하시오.입력첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000)둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수)출력첫째 줄에 K원을 만드는데 필요한 동전 개수의 최솟값을 출력한다.예제 입력 1 10 4200151050100500100050001000050000예제 출력 1 6예제 입력 2 10 479015105010050010005000100.. 2024. 8. 21.
[알고리즘] 그리디 알고리즘(탐욕법) 정리 ✔️ 그리디 알고리즘(탐욕법) 정의그리디 알고리즘(Greedy Algorithm) 이란?최적의 값을 구해야 하는 상황에서, 각 단계에서 최적이라고 생각 되는 것을 선택해 나가는 알고리즘 입니다. 그리디 알고리즘은 각 단계마다 지역 최적의 해를 찾는 문제로, 문제를 더 작게 쪼개는 형태이다.  ➕ 언제 쓰는가?    최적해를 구하는 문제 !!    ✔️ 그리디 알고리즘으로 문제 해결하기선택 절차(Selection Procedure) : 현재 상태에서의 최적 해답을 선택한다.적절성 검사(Feasibility Check) : 선택된 해가 문제의 조건을 만족하는지 검사한다.해답 검사(Solution Check) : 문제가 해결되었는지 확인하고, 해결되지 않았다면 선택 절차로 되돌아간다. ✔️ 대표적인 문제백준 .. 2024. 8. 20.

티스토리툴바