오구의코딩모험

https://www.acmicpc.net/problem/1717 문제 3줄 요약1. n+1개의 집합이 있다.2. 합집합 연산과 두 원소가 같은 집합인지 판별하는 연산을 수행한다.3. 1로 시작하는 입력에 대해서는 포함 여부를 출력한다. 문제의 제한 사항을 확인해보면n은 최대 10^6 이므로 단순히 set를 이용한 집합 연산은 불가능하다고 생각하였다. 해당 문제에서는Disjoint-set(서로소 집합, 분리 집합)을 표현하는 Union-Find 알고리즘을 이용하였다. 해당 알고리즘이 익숙하지 않다면아래 영상을 참고하길 바란다!! https://www.youtube.com/watch?v=rE-OUyZJgOk 위와 같은 집합이 존재할 때,부모 정점 테이블을 이용하여 집합의 연결을 수행한다. 연결..

https://www.acmicpc.net/problem/11657 문제 3줄 요약1. N개의 도시가 있다. 1번 도시가 기준이다.2. 도시를 건너는 버스는 시작 도시, 도착 도시, 걸리는 시간(양수가 아닌 경우 존재)으로 표현한다.3. 나머지 도시로 가는 가장 빠른 시간을 구해라. 만약 시간을 무한히 오래 전으로 되돌릴 수 있다면 -1을 출력한다. 2번 도시부터 차례대로 시간을 출력하되해당 도시로 가는 경로가 없는 경우 또한 -1을 출력한다. 여기서무한히 오래 전으로 되돌릴 수 있다는게 무슨 뜻 일까? 걸리는 시간 C가 음수이며,음수가 포함된 경로가 순환을 이루면반복을 통해 최단 시간이 무한한 음수로 가는 경우를 뜻하게 된다. 따라서최단 경로 알고리즘인 다익스트라 알고리즘은 사용할 수 없으며,벨만..

Lock-Free Stack 학습 정리 (上편) 멀티스레드 환경에서 Stack을 공유할 경우, 일반적으로는 mutex를 사용해 동기화합니다.하지만 잠금(lock)은 성능을 떨어뜨릴 수 있습니다.그래서 오늘은 Lock-Free Stack, 즉 락 없이 작동하는 스택에 대해 공부했습니다!compare_exchange_weak 같은 CAS(Compare-And-Swap) 연산을 사용해서 락 없이도다중 스레드 환경에서 안전하게 Push와 Pop을 수행할 수 있다는 게 핵심입니다.   Lock-Free Stack이란? Lock-Free Stack은 이름 그대로 락(mutex 등)을 사용하지 않고도 멀티스레드 환경에서 안전하게 동작하는 자료구조입니다.이 스택은 atomic 포인터와 연산을 기반으로 구현되며, 핵심은..

https://www.acmicpc.net/problem/1749 문제 3줄 요약1. 동주와 점수 따먹기 게임을 한다.2. N*M 행렬 각 칸에 -10'000 ~ 10'000의 정수를 하나씩 쓴다.3. 행렬의 부분 행렬의 합이 최대가 되게 구하라!   예제를 보고누적합을 생각하니 DP를 사용해야겠는데?라는 생각이 떠올랐고풀었던 유사한 문제가 생각났다.  https://59travel.tistory.com/104 [C++] BOJ 15724번 : 주지수https://www.acmicpc.net/problem/15724 문제 3줄 요약1. 네모 왕국의 1X1의 단위 구역을 여러 개 묶으려고 한다.2. 4개의 숫자로 직사각형 범위를 알려준다.3. 해당 직사각형 범위의 내에 살고 있는 사람 수를59travel...