오구의코딩모험

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...

메모리 모델, TLS, 락 기반 자료구조 학습 정리  이번엔 C++ 멀티스레드 프로그래밍에서 중요한 개념들인 Memory Model, Thread Local Storage, atomic, 그리고 Lock-Based 자료구조(스택/큐)를 공부했습니다.  1. 메모리 모델 (Memory Order) Memory Model (정책) 1) Sequentially Consistent (seq_cst) 2) Acquire-Release (acquire, release) 3) Relaxed (relaxed) (1) seq_cst (가장 엄격 = 컴파일러 최적화 여지 적음 = 직관적)   - 가시성 문제 바로 해결! 코드 재배치 바로 해결! (2) acquire-release  - 딱 중간!  - release 명령 ..

https://www.acmicpc.net/problem/1074  문제 3줄 요약1. 2^N x 2^N 크기의 2차원 배열을 Z모양으로 탐색한다.2. 순서는 왼쪽 위 / 오른쪽 위 / 왼쪽 아래 / 오른쪽 아래 순으로 Z 모양이다.3. r행 c열은 몇 번째로 방문하는지 출력해라!  N=3일 경우는 아래와 같이 탐색한다.  그림만 봐도 끔찍하다. 이번 문제는 큰 문제를 작은 문제로 나누어서 해결하는분할 정복 문제이다. 따라서 Z모양으로 탐색하는 부분과재귀를 통한 2 x 2 사각형 탐색하는 부분이 필요하다. 작성된 코드를 보고 분석해보자.   if(pow(2,w-1) != 1){ for(int i=x; i 한 변의 길이가 2^w이며, (x, y) 좌표부터 시작하는 사각형은2x2 길이의 사..

멀티스레드 동기화와 비동기 처리: condition_variable & future 서버 개발에서는 멀티스레드를 다룰 때 반드시 스레드 간 동기화와 비동기 처리에 대한 이해가 필요합니다.   오늘은 'condition_variable'을 이용한 생산자-소비자 패턴 구현, 그리고 'future', 'promise', 'packaged_task'를 사용한 비동기 처리 방식에 대해 공부했습니다.  1. condition_variable핵심 개념- condition_variable은 한 스레드가 특정 조건을 충족했을 때 다른 스레드에게 알림을 보내는 동기화 도구입니다.   - 일반적으로 mutex와 함께 사용하며, 생산자-소비자 구조에 적합합니다. 아래는 Producer 스레드가 데이터를 추가하고 Consume..

https://school.programmers.co.kr/learn/courses/30/lessons/388353 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 문제 3줄 요약1. n x m 크기의 물류창고에 출고 방식은 지게차와 크레인 두 가지가 있다.2. 지게차는 외부와 접근할 수 있는 경우 / 크레인은 어느 것이든 접근해서 꺼낼 수 있다.3. 출고 요청이 끝나고 난 후, 남은 물류 컨테이너 수를 출력해라.   물류 창고 컨테이너 적재량(= n)은 최대 50,컨테이너 길이(= m)의 최대 또한 50이다. 출고 요청은 최대 100개이며,알파벳 한 개로 구성된 요청은 지게차,알파벳 두 개로 구성된 요..

https://www.acmicpc.net/problem/6443 문제 3줄 요약1. 씬디는 애너그램 프로그램을 만들어 줄 수 있는 남자가 좋다.2. 애너그램은 입력받은 문자열의 단어들을 재배치한 단어들을 출력하는 것이다.3. 재배치한 문자열의 중복은 제외하고 알파벳 순서로 출력해라.  예시를 보면 바로 이해가 가능하다. (입력) abc → (애너그램) → (출력) abc acb bac bca cab cba abc가 입력으로 주어지면a 1개, b 1개, c 1개로 만들 수 있는 문자열들을 출력하면 된다. 출력할 때알파벳 순서대로 출력해야하니 위와 같이 순서로 출력된다. 문자열의 최대 길이가 21이라고문제에 조건으로 주어졌다. 따라서 완전 탐색은 불가능하기에조합 함수를 사용하거나백트래킹을 통한 탐색이 필요..

https://school.programmers.co.kr/learn/courses/30/lessons/388352 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 문제 3줄 요약 1. 비밀 코드는 1 ~ n까지의 서로 다른 정수 5개 (오름차순)이다.2. 이 비밀 코드를 맞추기 위해 m 번의 시도를 하며, 몇 개 맞췄는지 알려준다.3. 시도한 결과를 보고 비밀 코드로 가능한 정수 조합의 개수를 출력하자.    제한 사항을 보니조합의 개수가 최대 30C5 (약 14만개)이다. 따라서 브루트포스 알고리즘을 이용해도풀 수 있을 것이라 생각했고 그 결과..무식하게 5중 포문을 작성했다. 하지만 값을비교하는 과..

https://school.programmers.co.kr/learn/courses/30/lessons/388354 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr  문제 3줄 요약1. 루트 노드에 따라 홀수 / 짝수 / 역홀수 / 역짝수 노드가 정의된다.2. 트리는 어떤 노드를 루트로 설정하느냐에 따라 홀짝 / 역홀짝 트리가 모두가 될 수 있거나 모두가 될 수 없을 수 있다.3. 각 트리에 대해 루트 노드를 설정했을 때, 홀짝 트리와 역홀짝 트리의 개수를 구하려 한다.   도대체 이게 무슨 소리일까.. 문제 자체가 참 읽으면서도 이해가 힘들어몇 번이고 되읽었다. 예시를 참고하니 이해에 조금이나마 도움이..

서버 개발에서 배우는 동기화 기법 서버 개발에서는 성능 최적화와 동기화를 위한 다양한 기법이 사용됩니다.이번 글에서는 volatile, SpinLock, Sleep, Event (Auto Reset Event / Manual Reset Event) 등의 학습한 내용을 정리합니다.  int32 a=0;a = 1;a = 2;a = 3;a = 4;1. volatile: 컴파일러 최적화 방지volatile이란?- volatile 키워드는 컴파일러의 최적화를 방지하는 기능을 합니다.   - 일반적인 코드에서 불필요한 대입 연산이 제거되지만, volatile을 선언하면 모든 연산이 실행됩니다. 예제 개념- 변수 a가 여러 번 대입되는 경우, 컴파일러는 불필요한 연산을 제거하여 최적화합니다.   - 하지만 volat..