study

문제 https://www.acmicpc.net/problem/1309 1309번: 동물원 첫째 줄에 우리의 크기 N(1≤N≤100,000)이 주어진다. www.acmicpc.net 문제해결 - dp[n][0] : 사자를 넣지 않는 경우, 모든 경우의 수를 더해야됨 - dp[n][1] : 사자를 왼쪽 우리에 넣는 경우, 바로 위쪽에 있는 경우를 제외한 모든 경우를 더함 - dp[n][2] : 사자를 오른쪽 우리에 경우, 바로 위쪽에 있는 경우를 제외한 모든 경우를 더함 import java.util.Scanner; public class B1309 { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = ..

- 메모리 관리 - 메모리는 주소를 통해서 접근이 가능함 - 주소는 논리적 주소(logical address)와 물리적주소(physical address)가 있음 - 주소 바인딩: 논리적 주소를 실제 어느 물리적주소에 올릴지 정함 - Symbolic Addredd: 프로그래머 입장에서는 해당 데이터를 몇번지 주소에 올릴지 생각하지 않음, 그냥 변수에 담음, 변수가 심볼릭 어드레스 - CPU가 참조하는건 논리적 주소 실제 물리적 주소에 올리는 방법3가지(주소 바인딩): 1) Compile time binding - 컴파일시에 물리적주소에 올라감, 논리적 주소와 물리적 주소 번지가 똑같음, 프로그램 시작중에 주소가 바뀌지 않음 2) Load time binding - 논리적주소만 가지고 있다가 프로그램이 시..

문제 https://www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 문제해결 - dp 배열에 n번째 집을 각 색으로 칠하는데 최소값을 집어 넣는다 - 연속된 색을 칠하면 안되니 1일때는 2,3의 최소값 2일때는 1,3의 최소값... 이런식으로 같은 색은 제외한다 - dp[n] 에서 가장 작은 수가 답인데, 이때 나올수 있는 수중 가장 큰 값인 1000*1000으로 min을 초기화해서 가장 작은 수를 구한다 import java.util...

문제 https://www.acmicpc.net/problem/15988 15988번: 1, 2, 3 더하기 3 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다. www.acmicpc.net 문제해결 https://broship.tistory.com/219 - 백준 9095 문제와 똑같은 문제다, 다만 n의 최대값이 1000000으로 바뀌었다 - 처음 dp 배열을 1000000 크기로 생성 후 오버플로우를 방지하기 위해 모든 덧셈을 한 후 1000000009을 나눠주면 된다. import java.util.Scanner; public class Main { public static void main(String[] args) { ..

- 두 프로세스가 각자 자원을 가지고 있으면서 상대방이 가지고 있는 자원을 요구하는 경우 아무것도 진행되지 않아 데드락이 걸림 - 하드웨어던 소프트웨어던 공유자원을 서로 보유한 채 서로껄 요구하면 데드락이 걸림 - 데드락이 걸리는 4가지 조건: 1. 해당 자원을 독점적으로 가지고 있을때 2. 가지고 있는 자원을 강제적으로 빼앗을수 없을때 3. 가지고 있는 자원은 내놓지 않고 가지고 있으면서 추가적인 데이터를 요구할때 4. 서로가 가진자원을 요구하는 사이클이 형성될 때 - 데드락이 걸려있는지 확인 여부는 자원할당 그래프를 통해 할수있음 - 원형은 프로세스(P) - 사각형은 자원, 검은 동그라미는 자원 개수 - 자원->프로세스 화살표: 해당 자원을 해당 프로세스가 가지고 있다 - 프로세스->자원 화살표: 해..

- 세마포어는 코딩할때 실수가 발생하기 쉽고, 에러가 나면 찾기 힘듬 - 모니터는 lock, unlock을 자동으로 수행해줘서 프로그래머의 부담을 줄여줌 - 공유데이터(필드값)와 공유데이터를 접근하는 코드(함수)를 하나의 모니터(객체)에 담아놓는다 - 공유데이터는 모니터 안의 코드를 통해서만 접근이 가능함 - 모니터 자체가 하나의 active한 프로세스만 공유데이터에 접근 가능하도록 함 - 이미 한 프로세스가 공유데이터를 사용중이면 다른 프로세스는 모니터 밖에 큐에서 기다림 - 공유데이터를 사용중이던 프로세스가 빠져나가던지 잠들던지 하면 그때 기다리던 프로세스가 와서 사용 - 잠든다는건 공유데이터를 사용 중 특정 조건이 안 맞아서 오래 기다릴 경우 프로세스를 잠시 잠들게 하는것 - 특정 조건은 모니터 안..

- 세마포어 방식으로 여러 문제들을 해결하는 방법 1) Bounded-Buffer Problem(Producer-Consumer Problem) - 버퍼의 길이가 유한일때 - Producer, 생산자 프로세스와 Consumer, 소비자 프로세스가 존재함 - 생산자 프로세스는 버퍼에 자원을 넣는 역할을 담당(원 안에 주황색) - 소비자 프로세스는 버퍼에 자원을 사용하는 역할(원안에 아무것도 없음) 세마포어를 이용해 해결해야할 업무 2가지: 1. 2개의 프로세스가 동시에 접근할때 - 만약 생산자 2개가 같은 원안에 자원을 넣으려고 하면 critical section과 비슷한 문제가 발생함 - 하나의 생산자 프로세스가 자원을 넣으려 할때는 전체 버퍼에 lock을 거는 방식으로 해결 - 마찬가지로 여러 소비자가..

Semaphores 세마포어(추상화): - 세마포어 변수는 int형 변수(S)가 들어간다 - 공유자원을 획득하고 반납하는걸 세마포어가 처리해줌 - P연산은 공유자원을 획득하는 과정, V연산은 자원을 반납하는 과정 - S 에는 자원 개수가 들어감, lock, unlock일때는 1인 경우를 생각하면 됨 - 세마포어 변수 mutex를 1로 두고 들어갈때 P연산, 나올때 V연산 하면됨 - 추상자료형(?)이기 때문에 이렇게 작성하고 P연산과 V연산을 어떻게 구현할지는 그떄그떄 구현할 시스템에 맞게 구현해야됨 - 이것도 busy waiting 문제가 발생함, Block & Wakeup(sleep lock) 방식을 사용하면 좀더 효율적으로 구현할수있음 - 세마포어를 세마포어변수 value와 wait queue인 L로..

컴퓨터 시스템 내에서 데이터가 접근되는 패턴: 1. storage box에 data가 저장되어 있다 2. 연산할 data를 가져온다 3. data 연산 4. 연산 결과를 다시 storage box에 저장한다 이럴때 발생할수 있는 문제점: - count++하는 연산을 하는 도중 count--하는 연산이 들어올 경우, 아직 count++의 결과가 반영되지 않은 상태에서 count--를 한 값이 최종적으로 S-box에 저장되므로 count++의 결과가 누락됨 - 이런 경우를 Race Condition, 경쟁상태라고 함 - CPU가 여러개인 경우 같은 주소공간을 사용할수 있기 때문에 Race Condition이 발생할 수 있음 - 여러 프로세스가 주소공간을 공유하는 경우도 Race Condition이 발생할 수..

- 각 알고리즘 성능 척도(하나의 CPU brust 동안) 1) 시스템 입장에서의 성능 척도 - CPU 하나 가지고 최대한 많은 일을 시킬수 있으면 성능이 좋음 1. CPU utilization(이용률) - 전체 시간 중 CPU가 놀지 않고 일한 시간 비율 - 가능한 CPU를 바쁘게 2. Throughput(처리량) - 주어진 시간 동안 몇개의 작업을 완료 했나 2) 프로그램 입장에서의 성능 척도 - 프로그램이 최대한 빨리 끝날 수 있으면 성능이 좋음 1. Turnaround time(소요시간, 변환시간) - CPU를 쓰러 와서 다 쓰고 나갈때까지의 시간(CPU brust time) - wating time + CPU 사용 시간 2. Waiting time(대기 시간) - ready 상태에서 CPU를 기..