본문 바로가기

전체 글153

[백준] 1463 1로 만들기 (자바) : DP ✔️ 문제 설명더보기문제정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.X가 3으로 나누어 떨어지면, 3으로 나눈다.X가 2로 나누어 떨어지면, 2로 나눈다.1을 뺀다.정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.입력첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다.출력첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다.예제 입력 1 2예제 출력 1 1예제 입력 2 10예제 출력 2 3힌트10의 경우에 10 → 9 → 3 → 1 로 3번 만에 만들 수 있다. ✔️ 문제 풀이  [알고리즘 정리] DP(Dynamic Programming) : 동적 계획법✔️ DP(Dynamic Progra.. 2024. 8. 24.
[알고리즘 정리] DP(Dynamic Programming) : 동적 계획법 ✔️ DP(Dynamic Programming) 정의DP(Dynamic Programming) 이란?다이나믹 프로그래밍은 하나의 큰 문제를 여러 개의 작은 문제로 나눈 다음, 그 결과를 저장하여 다시 큰 문제를 해결할 때 사용한다.  ✔️ DP를 쓰는 이유DP는 일반적인 재귀(Recursion) 방식과 매우 유사하다.큰 차이점은 일반적인 재귀의 경우 큰 문제를 작은 하위 문제로 나누어 해결하는 방법으로, 작은 문제들이 여러번 반복(중복 계산)되어 비효율적인 계산이 될 수 있다.반면에, DP는 작은 하위 문제들로부터 시작하여 그 결과를 저장하고 이를 이용하여 큰 문제를 해결한다.즉, DP는 재귀적 호출에서의 중복 계산을 방지하고 계산 속도를 향상시킨다. ✔️ DP 기법을 적용시킬 수 있는 조건1. 중복되는.. 2024. 8. 24.
[운영체제] 데드락(DeadLock) ✔️ 데드락(DeadLock) 정의데드락(DeadLock) 이란?두 개 이상의 프로세스나 스레드가 서로서로 가진 공유 자원을 얻고자 기다리는 경우, 무한히 서로가 서로의 자원을 기다리게 되는 상태를 의미한다. 한정된 자원을 여러 프로세스가 사용하려고 할 때 발생한다.  Thread 1은 공유 자원 L1을 갖고 있고, 공유 자원 L2 를 기다림. Thread 2은 공유 자원 L2을 갖고 있고, 공유 자원 L1 를 기다림. 이런 경우, 현재 서로 원하는 자원이 상대방에 할당되어 있어서 두 프로세스는 무한정 대기(wait) 상태에 빠짐 = DeadLock 상태✔️ 데드락(DeadLock) 발생 조건4가지 조건이 모두 성립해야 발생 ! ( 하나라도 성립하지 않으면 데드락 문제 해결 가능 )상호 배제(Mutual.. 2024. 8. 22.
[백준] 1080 행렬 (자바) : 그리디 알고리즘 ✔️문제 설명 ( 펼치기 ) 더보기문제0과 1로만 이루어진 행렬 A와 행렬 B가 있다. 이때, 행렬 A를 행렬 B로 바꾸는데 필요한 연산의 횟수의 최솟값을 구하는 프로그램을 작성하시오.행렬을 변환하는 연산은 어떤 3×3크기의 부분 행렬에 있는 모든 원소를 뒤집는 것이다. (0 → 1, 1 → 0) 입력첫째 줄에 행렬의 크기 N M이 주어진다. N과 M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 행렬 A가 주어지고, 그 다음줄부터 N개의 줄에는 행렬 B가 주어진다. 출력첫째 줄에 문제의 정답을 출력한다. 만약 A를 B로 바꿀 수 없다면 -1을 출력한다. 예제 입력 1 3 4000000100000100110111001예제 출력 1 2예제 입력 2 3 3111111111000000000예제.. 2024. 8. 22.
[백준] 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.

티스토리툴바