✍️Today I Learned

📅 2025-08-11

• 프로그래머스 - 가장 큰 수
• CS - 스레드간 동기화 방법

프로그래머스 - 가장 큰 수

문제 링크
문제 설명
0 또는 양의 정수가 주어졌을 때, 정수를 이어 붙여 만들 수 있는 가장 큰 수를 알아내 주세요.
예를 들어, 주어진 정수가 [6, 10, 2]라면 [6102, 6210, 1062, 1026, 2610, 2106]를 만들 수 있고, 이중 가장 큰 수는 6210입니다.
0 또는 양의 정수가 담긴 배열 numbers가 매개변수로 주어질 때, 순서를 재배치하여 만들 수 있는 가장 큰 수를 문자열로 바꾸어 return 하도록 solution 함수를 작성해주세요.

제한 사항

• numbers의 길이는 1 이상 100,000 이하입니다.
• numbers의 원소는 0 이상 1,000 이하입니다.
• 정답이 너무 클 수 있으니 문자열로 바꾸어 return 합니다.

풀이

람다를 이용해 compare 함수를 정의했다. 처음에는 while 문으로 문자열로 바꾼 두 수를 앞자리부터 차례대로 비교하는 방식을 생각했는데 풀다 보니 문자열로 바꾼 두 수를 붙여서 어떤 게 더 큰지 비교하는 로직으로 단순화시킬 수 있었다.

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

string solution(vector<int> numbers) {
    string answer = "";
    sort(numbers.begin(), numbers.end(),
        [](int a, int b)
         {
             string str_a = to_string(a);
             string str_b = to_string(b);
             return str_a+str_b > str_b+str_a;
         }
        );
    if(numbers[0]==0) return "0";
    for(int i : numbers)
    {
        answer+=to_string(i);
    }
    return answer;
}

---

CS - 스레드간 동기화

여러 스레드가 공유 자원에 접근할 때 생기는 문제

1. 데이터 경쟁 (Data Race)
   여러 스레드가 동시에 공유 메모리에 접근하여 값을 읽거나 쓸 때 발생하는 문제. 최종 결과가 스레드들의 실행 순서에 따라 달라진다.

2. 교착 상태 (Deadlock)
   둘 이상의 스레드가 서로 점유하고 있는 자원을 영원히 기다리는 상태. 모든 스레드가 작업을 멈추고 갇히게 되어 프로그램이 정지된다.

이와 같은 문제를 해결하기 위해 스레드간의 동기화가 필요하다.

C++에서 멀티스레드 환경에서 안전하게 사용할 수 있는 자료구조는 크게 두 가지 접근법을 통해 구현된다.

Lock-Based 자료구조

Lock-Based 방식은 Mutex(뮤텍스)나 Semaphore(세마포어) 같은 잠금 메커니즘을 사용하여 공유 자원에 대한 접근을 제어한다. 한 스레드가 자료구조에 접근할 때 잠금을 획득하고, 작업이 끝나면 잠금을 해제하여 다른 스레드가 접근할 수 있도록 허용한다.

왜 안전한가?

이 방식은 여러 스레드가 동시에 자료구조를 수정하는 것을 막아 Race Condition(경쟁 상태)을 방지하기 때문에 안전하다. 예를 들어, 두 스레드가 동시에 std::vector에 요소를 추가하려고 할 때, 잠금이 없다면 메모리 할당과 포인터 갱신 과정에서 데이터가 손상될 수 있다. 하지만 Mutex로 보호하면, 한 스레드가 vector를 수정하는 동안 다른 스레드는 대기하게 되어 데이터 일관성을 유지할 수 있다.

예시

• std::mutex를 활용한 std::vector:

  • std::mutex mtx;
  • std::vector<int> data;
  • void add_data(int value) { std::lock_guard<std::mutex> lock(mtx); data.push_back(value); }
  • std::lock_guard는 스코프를 벗어나면 자동으로 Mutex를 해제해주는 RAII(Resource Acquisition Is Initialization) 기법을 사용하므로, 예외가 발생해도 잠금이 해제되어 데드락(Deadlock)을 방지한다.

• std::queue와 std::mutex를 이용한 스레드 안전 큐:

  • 생산자-소비자(Producer-Consumer) 모델에서 유용하게 사용된다. 데이터 추가/삭제 시 Mutex로 보호한다.
    뮤텍스(Mutex)와 세마포어(Semaphore)는 멀티스레드 환경에서 공유 자원에 대한 접근을 제어하는 동기화 메커니즘이다.

📜 뮤텍스 (Mutex)

뮤텍스는 "Mutual Exclusion"의 약자로, 상호 배제를 의미한다. 이는 공유 자원에 단 하나의 스레드만 접근하도록 보장하는 잠금(lock) 메커니즘이다.

• 원리: 뮤텍스는 소유권 개념이 있다. 한 스레드가 뮤텍스를 잠그면(lock), 해당 스레드만 뮤텍스를 소유하게 된다. 이 스레드가 작업을 마친 후 뮤텍스를 해제(unlock)하면, 다른 스레드가 잠금을 획득하여 공유 자원에 접근할 수 있게 된다.
• 특징:
  • 잠금(Lock)과 해제(Unlock)는 반드시 같은 스레드에 의해 이루어져야 한다.
  • 주로 공유 자원(데이터) 자체를 보호하는 데 사용된다.

📜 세마포어 (Semaphore)

세마포어는 공유 자원에 동시에 접근할 수 있는 스레드의 수를 제한하는 카운터이다.

• 원리: 세마포어는 동시에 공유 자원에 접근할 수 있는 스레드의 최대 개수를 나타낸다.
  • 스레드가 자원에 접근할 때 세마포어의 값을 1 감소시킨다 (P 연산 또는 wait() 연산).
  • 자원 사용이 끝나면 값을 1 증가시킨다 (V 연산 또는 signal() 연산).
  • 만약 세마포어 값이 0이면, 더 이상 스레드가 접근할 수 없고, 다른 스레드가 자원을 해제할 때까지 기다려야 한다.
• 특징:
  • 소유권 개념이 없다. 한 스레드가 세마포어 값을 감소시켰더라도, 다른 스레드가 값을 증가시킬 수 있다.
  • 주로 자원의 가용성(availability)을 관리하는 데 사용된다.

📝 주요 차이점

특징	뮤텍스 (Mutex)	세마포어 (Semaphore)
목적	상호 배제 (Mutual Exclusion)	자원 가용성 관리
동시 접근	1개의 스레드만 허용	N개의 스레드 허용 (N >= 1)
소유권	소유권 개념이 존재	소유권 개념이 없음
사용 예시	특정 데이터 구조 (예: std::vector)를 한 번에 한 스레드만 수정하게 할 때	리소스 풀 (예: 데이터베이스 커넥션)의 최대 동시 접속자 수를 제한할 때

---

Lock-Free 자료구조

Lock-Free 방식은 잠금(Lock)을 사용하지 않고, CPU가 제공하는 원자적(Atomic) 연산을 활용하여 동시성을 제어한다. 원자적 연산은 중간에 다른 스레드에 의해 중단되지 않고 한 번에 완료되는 연산을 의미한다. 주로 Compare-And-Swap(CAS) 같은 기법을 사용하다.

왜 안전한가?

잠금 없이 동시성 문제를 해결하기 때문에 안전하다. Lock-Based 방식은 잠금을 획득하지 못한 스레드가 잠금이 해제될 때까지 대기해야 하지만, Lock-Free 방식은 대기 없이 계속해서 작업을 시도한다. 따라서 데드락이나 우선순위 역전(Priority Inversion) 같은 문제가 발생하지 않아 Lock-Based 방식보다 더 높은 성능과 실시간성을 요구하는 시스템에 적합하다.

예시

• std::atomic<T>:

  • std::atomic<int> counter{0};
  • counter.fetch_add(1);
  • fetch_add는 기존 값을 가져오면서 1을 더하는 원자적 연산이다. 여러 스레드가 동시에 fetch_add를 호출해도 안전하게 카운터 값을 증가시킬 수 있다.

• Lock-Free 큐 또는 스택:

  • CAS(Compare-And-Swap) 연산을 사용하여 구현된다.
  • 예를 들어, 큐의 맨 앞에 노드를 추가할 때, 헤드 포인터를 CAS 연산을 통해 원자적으로 갱신한다.
  • head.compare_exchange_weak(expected, new_value)는 head의 현재 값이 expected와 같으면 new_value로 교체하고, 성공 여부를 반환한다. 이 과정을 반복하여 다른 스레드의 변경사항과 충돌하지 않도록 한다.

---

정리

	Lock-Based 자료구조	Lock-Free 자료구조
원리	Mutex, Semaphore 등 잠금 메커니즘 사용	Atomic 연산(CAS 등) 사용
장점	구현이 비교적 쉽고 직관적, 일반적인 상황에서 무난한 성능	데드락, 우선순위 역전 문제 없음, 높은 동시성과 성능
단점	데드락, 우선순위 역전 발생 가능, 잠금 경합 시 성능 저하	구현이 매우 복잡하고 어렵다, 특정 상황에서 스핀락(spin-lock)처럼 동작 가능
예시	Mutex로 보호되는 std::vector, std::queue	std::atomic<int>, CAS를 활용한 Lock-Free 큐

두 방식 모두 멀티스레드 환경에서 안전성을 보장하지만, 시스템의 특성과 요구사항에 따라 적절한 방식을 선택해야 합니다. 일반적인 경우 Lock-Based 방식이 구현이 간단하여 많이 사용되며, 매우 높은 동시성과 낮은 지연 시간이 요구되는 경우 Lock-Free 방식이 고려된다.

💡 느낀 점 (What I Felt)

---

출처 프로그래머스: 가장 큰 수