2JINISHAPPY 2JINISHAPPY

https://www.acmicpc.net/problem/1495 1495번: 기타리스트 첫째 줄에 N, S, M이 주어진다. (1 ≤ N ≤ 100, 1 ≤ M ≤ 1000, 0 ≤ S ≤ M) 둘째 줄에는 각 곡이 시작하기 전에 줄 수 있는 볼륨의 차이가 주어진다. 이 값은 1보다 크거나 같고, M보다 작거나 같다. www.acmicpc.net 현재 볼륨이 범위에 적합하지 않는 경우(불가능)일 때와, 아직 계산하지 않은 경우(가능 여부 모름)일 때를 분리해주어야 한다는 걸 시간초과 덕분에 알았다 #include #include using namespace std; int n, s, m; int v[101], cache[101][1001]; int dp(int cur, int dep) { if (cur..

프로그램을 실행하기 위해서는 프로세스를 메모리에 올려야 한다. 운영체제는 한정된 메모리 공간을 활용하기 위한 메모리 관리 전략을 지니고 있다 Logical Address(Virtual Address) : 프로세스마다 독립적으로 가지는 주소공간. CPU가 보는 주소. 각 프로세스마다 0번지 부터 시작 Physical Address: 메모리에 실제로 올라가는 위치 Address Binding : Symbolic Address ➡ Logical Address ➡ Physical Address로 변환하는 과정 사용자 프로그램을 물리적 메모리에 직접 접근할 수 없기 때문에(권한을 가져서는 안 된다) 상징 - 논리 - 물리 주소로 바인딩하는 과정이 필요하다 주소 바인딩은 다음의 세 시점에 발생할 수 있다. 1️⃣ ..

https://www.acmicpc.net/problem/20160 20160번: 야쿠르트 아줌마 야쿠르트 주세요 첫 줄에는 정점의 개수 V(1 ≤ V ≤ 10,000)와 도로의 개수 E(0 ≤ E ≤ 100,000)가 정수로 주어진다. 그 다음 E 줄에 걸쳐 각 도로를 나타내는 세 개의 정수 (u, v, w)가 순서대로 주어진다. 이는 u 와 v(1 ≤ www.acmicpc.net 값의 범위를 신경써야 하는 다익스트라 문제 정점은 10000개라서 인접행렬을 만들 시 10000*10000=1억개 * 4byte의 메모리가 필요한데 간선이 최대 10만개 들어오므로 꼭 인접리스트로 처리해야 한다 #include #include #include #define ull unsigned long long #defin..

https://www.acmicpc.net/problem/22114 22114번: 창영이와 점프 창영이는 버스에서 내린 뒤 회사로 걸어가고 있다. 창영이가 걸어가는 길은 대부분 회색 보도블럭으로 포장되어 있는데, 가끔씩 빨간 보도블럭이 놓여있을 때가 있다. 창영이는 어린 시절 빨간 www.acmicpc.net 오랜만에 푸는 DP문제 처음에 bottom-up으로 풀려고 했는데 점화식이 계속 생각이 안 나서 재귀로 푼 다음에 메모이제이션 적용했다 dp도 재귀(top-down)이기 때문에 base case, inductive step, memoization 이 세 가지 위주로 설계해야 할 듯 #include #include using namespace std; int n, k, l[100005], dp[2][..

객체 지향의 개념에는 값과 객체를 명확히 구분한다. Pizza pizza = new Pizza("Margherita"); Value and Equality 값이란 숫자, 문자, 문자열, 날짜 같이 그 자체로 변하지 않는 데이터를 의미한다. 5, "Hello", 'E', 등등은 변하지 않는 속성인 immutable state를 지닌다. 서로 다른 두 인스턴스가 같은 값인지 확인하기 위해서는 두 인스턴스의 상태가 동일한지 확인한다. 동일한 숫자 두 개가 있고 같은지 다른지 판별해야 한다면 똑같은 숫자 값을 가지고 있는지 확인해서 그 여부를 가릴 수 있다. 이렇게 두 인스턴스의 상태를 이용해 동일하다고 판별하는 성질을 동등성(equality)이라고 한다. 값의 상태는 절대 변하지 않기 때문에 특정 시점에 동일..

DP를 사용하는 알고리즘들은 처음의 문제를 더 작은 문제로 분할하고, subproblem들로부터 원래 문제의 답을 계산해 나가는, 분할정복과 비슷한 재귀적 문제 해결 방식이다. DP가 분할정복과 구분되는 점은 어떤 부분 문제가 두 번 이상 사용될 시 이를 여러 번 구하지 않고 한 번만 구한 뒤 계산 결과를 재활용 할 수 있다는 특징이다. 이렇게 한 번 계산한 값을 저장해 두었다 재활용하는 최적화 기법을 memoization(메모이제이션)이라 한다 ❗ 1. 문제 정의 조건과 구하고자 하는 바를 정확하게 정의 2. Recursion 정의 정의된 문제에 대한 부분 문제를 정의한 뒤 부분 문제를 이용한 점화식을 세운다 3. DP 적용 - 메모이제이션을 적용하여 점화식 계산 - 중간 계산 값을 저장할 data s..

Deadlock(데드락): 일련의 프로세스들이 서로가 가진 자원을 기다리며 block된 상태 Resouce(자원)이란? 하드웨어, 소프트웨어 등을 포함하는 개념 ex) I/O Device, CPU Cycle, Memory Space, Semaphore 등 프로세스가 자원을 사용하는 절차(request, allocate, use, release) Deadlock 예시 DeadLock 발생 조건 4가지 1. Mutual Exclusion : 매 순간 하나의 프로세스만이 자원을 선점할 수 있다 2. No Preemption : 프로세스는 스스로 자원을 내놓기 전까지는 강제로 빼앗기지 않는다 3. Hold and Wait : 자원을 가진 프로세스가 추가 자원을 기다릴 때 보유한 자원을 포기하지 않는다 4. Ci..

많은 프로세스들은 자원 혹은 메모리를 공유한다. ex) 공유 메모리를 사용하는 프로세스들, 커널 내부 데이터를 접근하는 루틴들 Storage-Box: Memory Address Space / Execution-Box: CPU Process 프로세스의 수행은 공유 자원에 변화를 끼치게 되고, 여러 프로세스가 동시에 공유 자원에 접근하면 데이터의 일관성을 보장받을 수 없다. 그래서 프로세스는 특정 공유 자원을 선점할 때 다른 프로세스가 접근할 수 없게끔 제한한다. 하지만 특정 자원에 접근하려는 프로세스가 여러 개 일 경우 Race Condition이 발생할 수 있다 공유 데이터의 동시 접근은 데이터의 불일치 문제(inconsistency)를 발생시킬 수 있다 !! 따라서 consistency 유지를 위해서는..