Little Jay

Condition Synchronization 지금까지의 Mutex는 임계영역에 들어갈 때 하나의 Thread 혹은 하나의 Process만 사용할 수 있도록 보장해준다고 배웠다. Mutex를 Guarantee하지 않으면 결국 Non-Deterministic한 동작으로 인해 잘못된 결과가 초래될 수 있다. 그렇다고 해서 Mutex가 동기화를 보장해주는 유일한 방법은 아니다. 조건 동기화(Conditional Synchronization)은 특정 조건(condition, or state)이 만족할 때까지 대기하게 해서 다수의 쓰레드의 흐름을 Re-Ordering하는 것이다. 다시 말해서 조건에 따라 실행 흐름을 대기시키고 재개시킬 수 있다는 것이다. 우리는 앞에서 Mutex는 P와 V Operation이 서..

Greedy하게 풀 수 있는 문제이다. 아이디어를 한번에 떠올리기가 어려워서 다른분들의 블로그를 참고했다. 사실 아이디어는 여러개가 있었지만 (부분 합 문제 등) 너무 구현이 어려워서 다른 분들의 블로그를 참고했다. 결국 우리가 원하는것은 앞사람과 뒷 사람의 차이(변화량)을 찾는것이다. 따라서 이를 sort시켜서 k-1개 만큼 뽑아내면 된다. #include #define endl '\n' using namespace std; int n, k; int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin >> n >> k; vector v(n); for (auto& i : v) cin >> i; vector diff(n - 1); for ..

‘노인과 바다’는 1952년에 최초로 출간된 소설책으로 헤밍웨이 작가가 1954년 노벨 문학상을 수상하는데 있어 큰 영향을 끼쳤다. 소설로서의 성공은 물론 영화로도 여러번 제작되어 글을 읽지 못하는 사람이라도 헤밍웨이의 ‘노인과 바다’는 가슴깊이 잘 간직되어 있는 소설이라 할 수 있다. 오랜 시간이 지나서도 계속해서 새로운 개정판이 출간되는 ‘노인과 바다’는 인간이 세상을 살아가는데 겪는 희망, 좌절, 어려움 등의 감정들을 극복해 나가는 장면들을 담아 그려낸 소설이다. 다른 소설들과는 다르게 간결하게 그려졌다. 이 책은 어부로 살아가는 어느 한 노인, 산티아고를 보여주며 이야기는 시작된다. 하루도 빠짐없이 물고기를 잡아야 하는 어부지만, 84일간 단 한 마리도 물고기를 잡지 못해 주변 사람들은 산티아고가..

BFS를 기반으로 하는 문제이다. 단순히 BFS를 두번 돌리면 되는데, 첫 번째는 정상적인 BFS로, 두 번째는 R==G일때도 통과되게 만들면 된다. #include #define endl '\n' #define pii pair using namespace std; int t; int n; char graph[101][101]; bool visited[101][101]; const int dx[] = { 1, -1, 0, 0 }; const int dy[] = { 0, 0, 1, -1 }; int bfs(int x, int y, bool eye) { visited[x][y] = true; char target = graph[x][y]; queue q; q.push({ x, y }); while (!q.e..

문제를 잘 곱씹어보면 아이디어가 하나 떠올랐는데, 백준 문제의 '가장 긴 증가하는 부분 수열' 이 떠올랐다. 생각해보면 이 아이디어가 Correct하게 맞아떨어지는데, 이는 해당 구간에서 오름차순으로 증가하는 수열이 결국 이 문제의 상자와 같기 때문이다. #include #define endl '\n' using namespace std; int n; int dp[1001]; int arr[1001]; int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin >> n; for (int i = 1; i > arr[i]; } int ans = -1; for (int i = 1; i

Spin Lock 우리는 Busy Waiting하는 것을 Spin Lock이라고 한다. 이는 당연하게 Mutual Exclusion을 제공해준다. 그러나 Busy Waiting을 할때는 CPU의 낭비는 필연적이게 된다. 그러나 CPU 자원을 소모한다고 해서 Spin Lock 자체가 비효울적이라고는 할 수 없다. 이 시점에서 우리는 Context Switch의 비용과 Busy Waiting의 비용을 비교해야한다. 계속 Context Switching을 한다면 계속 Thread/Process를 바꾸는 비용이 기하급수적으로 증가할 수도 있다. 그러나 Spin Lock 자체는 fair한 것은 아니다. 결국 대기하면서 Thread/Process가 계속해서 Progress를 하지 못해 Starvation이 발생할 ..

Critical Section Problem 임계 영역에 대해서는 아래의 세 가지의 조건을 만족시켜야한다. Mutual Exclusion(상호 배제) : Critical Section에는 반드시 하나의 Thread/Process만 있어야 한다. Progress(진행): 만약 Critical Section을 사용하는 Thread/Process가 없고, 현재 임계영역의 자원을 사용하려고 누군가 기다려야한다면 적절한 Algorithm을 통해서 해당 Thread/Process를 진행시켜야 한다. Bounded Waiting(한정 대기): Process/Thread가 임계 영역을 위해 무한정 기다려서는 안된다. Naive Approach (Wrong Case) 위 그림을 보자. 이는 우리가 가장 간단하게 생각해볼..

사실 머리로 생각만 하면 간단한 문제인데 코드로 구현하려고 하니까 조금은 복잡한 문제였다. def solve(): A=[0, 0, 1, 8, 2, 2, 8, 9, 0, 3, 4, 0, 0] A.sort() i= A.count(0) if len(A) 2: count+=(A.pop()+A.pop())*i i*=10 count+=sum(A)*i return count

오랜만에 풀어본 Brute Force 문제 C++에는 순열을 쉽게 만들 수 있는 algorithm 헤더에 next_permutation(혹은 prev_permutation) 메서드가 존재한다. 그러나 우리가 풀고자 하는 것은 조합을 만들어야 하는 것이기 때문에 1의 개수를 L개 만큼, 그리고 0의 개수를 C-L개 만큼 넣어준다음에 해당 벡터에 1이 나온다면 출력하는 식으로 조합을 만들 수 있다. 그렇게 Possible한 String을 만들었다면 vowel과 noun의 개수가 맞는지 체크하고 출력해주면 되는 문제이다. #include #define endl '\n' using namespace std; int l, c; int main() { ios::sync_with_stdio(false); cin.ti..

질문 출처: https://www.frontendinterviewhandbook.com/javascript-questions#explain-event-delegation JavaScript trivia questions in front end interviews | Front End Interview Handbook Answers to Front-end Job Interview Questions - JS Questions. Pull requests for suggestions and corrections are welcome! www.frontendinterviewhandbook.com 이벤트 위임 이벤트 위임이라고 하는 것은 부모 요소에 이벤트를 등록해서 하위의 자식 요소들을 제어하는 방식이다. 이벤트..