int a = 0;
int b = 0;
void Func()
{
a = 1;
b = 2;
}
위의 코드에서 Func 함수에 2개의 스레드가 접근하였다고 해보자. 이 때, 스레드에서 관찰될 수 있는 (a, b)의 값은 어떤 경우가 있을까?
먼저, a와 b에 아무것도 입력되지 않은 상황인 (0, 0)이 있을 것이다. a만 입력되고 b는 입력되지 않은 (1, 0) 도 가능할 것이다. a와 b가 모두 입력된 (1, 2)또한 가능할 것이다.
그렇다면, (0, 2)는 가능할까?
상식적으로 생각했을 때, 코드는 위에서 아래로 진행되기 때문에 a = 1; 이라는 코드가 실행되지 않았다면, b = 2; 또한 실행될 수 없다.
그러므로, a가 0인 상황에서 b에만 2가 입력되는 상황은 발생하지 않을 것만 같다. 하지만, 실제로는 발생할 수 있다.
왜냐하면, 컴파일러 최적화 때문이다.
Func() 함수를 실행하기 전에, b를 이용한 어떤 연산을 했다고 해보자. 그렇다면, Func에 들어오는 순간 CPU의 캐시에는 b와 관련된 데이터가 있을 것이다. 이 때 Func에서 a = 1; 를 먼저 실행한다면, 캐시를 비워야 하는 상황이 발생할 수도 있다. 그리고 나서, b = 2;을 실행했을 때, b를 다시 캐시에 가져오기 위한 추가적인 작업도 말생할 수 있다.
하지만, b = 2;를 먼저 실행한다면? 이미 캐시에 b에 관한 데이터가 있기 때문에, 캐시를 비울 필요 없이 그대로 연산을 할 수 있다. 즉, b = 2;를 먼저 실행하고 a = 1;을 실행하는 것이 결과적으론 훨씬 효율적인 것이다.
Func()의 코드는 a = 1;을 먼저 실행하든 b = 2;를 먼저 실행하든 결과에는 차이가 없기 때문에 컴파일러는 최대한 효율적인 방식으로 코드의 순서를 재배치한다.
싱글 스레드 환경에선, 결과만 같다면 코드를 아무리 재배치하더라도 별 다른 문제는 발생하지 않을 것이다.
하지만, 멀티 스레드 환경에선 다르다.
위에서 말했듯이, (a,b)의 값을 (0, 2)로 관측하는 상황도 발생하는 것이다. 그런데 이게 왜 문제라는걸까?
int Value = 0;
bool A = false;
void Func1()
{
Value = 100;
A = true;
}
void Func2()
{
if(A == true)
{
std::cout << Value;
}
}
위의 코드를 보자. Func1()과 Func2()를 각각 다른 스레드를 이용하여 병렬적으로 실행하였다고 해보자.
일반적인 상황이라면, Value = 100;이 된 이후에, A = true가 되기 때문에, Func2()에서는 A가 false라서 아무것도 출력하지 않거나, A가 true인 상황에선 100을 출력할 수도 있을 것이다.
하지만, 위에서 말했던 컴파일러 재배치의 문제 때문에, Func1()에서 A = true; 가 먼저 실행될 수도 있고, 이 경우에 Func2()에선 0을 출력하게 될 것이다.
우리가 A == true일 때, Value를 출력하고자 함은 일반적으로 100이라는 값을 출력하기 위함일 것이다. 그런데, 실제로는 0이 출력될 여지가 있는 것이다. 상황에 따라 치명적인 문제가 될 수도 있는 것이다.
이처럼, 컴파일러의 명령어 재배치를 통제하기 위한 수단이, std::memory_order 이다. 아무데서나 쓸 수 있는 건 아니고, atomic객체의 함수에 인자로 넣어서 사용할 수 있다.
종류는 5가지가 있다.
memory_order_relaxed : 명령어의 재배치를 무제한으로 허용함. memory_order_acquire : 해당 명렁어 위로 명령어가 재배치 되지 않도록 막음. memory_order_release : 해당 명령어 아래로 명령어가 재배치 되지 않도록 막음. memory_order_acq_rel : memory_order_acquire 와 memory_order_release 를 모두 수행. memory_order_seq_cst : 어떠한 재배치도 발생하지 않고, 일반적으로 생각하는 논리와 동일하게 명령어가 작동.
std::atomic<int> Value = 0;
std::atomic<int> Value2 = 0;
std::atomic<bool> A = false;
void Func1()
{
Value.store(100);
A.store(true);
}
위에서 보았던 코드를 atomic으로 변경한 코드이다. 위에서도 말했듯이, A에 true를 저장하는 이유는 Func2에서 Value = 100이라는 값을 확인할 수 있도록 하기 위함이었다. 그렇다면, 이 코드에서 Value.store(100); 은 A.store(true); 의 아래로 재배치 되어서는 안된다.
std::atomic<int> Value = 0;
std::atomic<bool> A = false;
void Func1()
{
Value.store(100);
A.store(true, std::memory_order_release);
}
이 때, A의 두번째 인자에 std::memory_order_release 넣어줌으로서, 명령어가 아래로 재배치되는 것을 막아줄 수 있다.
이번엔, Func2()를 보자. 이해를 돕기 위해 아래에 Value2.store(0); 이라는 코드를 추가하였다. 이 코드는 A가 true가 되는 순간 value의 값을 출력한 뒤, Value2의 값을 100으로 변경해주는 작업을 하고 있다.
그렇다면, 우리가 의도한 것은 100이 먼저 출력되고, 그 다음에 value2의 값이 100으로 변경되는 것일 것이다. 하지만, 명령어가 재배치 되면 Value2에 100을 먼저 삽입한 뒤, Value의 값을 출력할 수도 있다. 그러므로, Value2.store(100)을 if 문 위로 재배치 되지 않도록 막아주어야 한다.
이 때, std::memory_order_acquire를 사용하여 해당 메모리 위로 명령어가 재배치 되지 않도록 막아줄 수 있다.
상황의 특성상, std::memory_order_release는 주로 쓰기(store)과 함께 사용되고 std::memory_acquire는 주로 읽기(load)와 함께 사용된다.
반면, 읽기와 쓰기를 함께 하는 작업도 존재한다. 바로, fetch_add()함수이다.(fetch_sub() 등 다른 연산도 존재한다.)
fetch_add()는 atomic객체에 저장된 값에 원하는 값을 더해주는 함수이다. 더하기를 하기 위해선, 먼저 저장되어 있는 값을 읽고, 그 값에 숫자를 더한 뒤 결과값을 써주어야 한다. 즉, 읽기와 쓰기 연산이 모두 사용되는 것이다.
이 경우엔 memory_order_acq_rel 를 사용하여, 아래에 있는 명령어가 위로 배치되지 않도록 하며 동시에 위에 있는 명령어가 아래로 배치되지 않도록 해준다.
하지만, 이 경우에도 메모리 재배치가 아예 발생하지 않는 것은 아니다.
void Func3()
{
int a = 0;
int b = 0;
Value.fetch_add(3, std::memory_order_acq_rel);
int c = 0;
int d = 0;
}
이 코드에선, a와 b를 선언하는 명령어는 fetch_add의 밑으로 내려가지 않는다. c와 d의 선언또한 fetch_add 의 위로 올라가지 않는다.
하지만, int a = 0; 과 int b = 0;의 순서는 바뀔 수 있고, 아래에서도 int c = 0; 과 int d = 0;의 순서는 얼마든지 바뀔 수 있다.
이러한 재배치마저 모두 막아버리고 싶다면, std::memory_order_seq_cst를 사용하면 된다. 참고로 atomic객체의 멤버함수에 인자로 memory_order을 넣지 않는다면 std::memory_order_seq_cst가 디폴트로 설정된다.
std::memory_order_seq_cst의 경우엔 생각보다 상당히 비싼 연산이라, 오버헤드가 많이 발생한다고 한다. 하지만, 현대의 amd나 intel의 일반적인 CPU는 순차적 일관성이 거의 보장되어있기 때문에 std::memory_order_seq_cst를 사용한다고 해서 성능에 큰 문제는 없다고 한다.
하지만, 임베디드에서 사용되는 ARM CPU의 경우에는 치명적일 수 있기 때문에 주의해서 사용해야 한다고 한다.
이처럼, 강산이가 입력한 화살표와 백스페이스, 알파벳 정보를 토대로 최종적으로 입력되는 비밀번호를 출력하면 된다.
문제 풀이
이렇게 문자열의 중간에 문자를 삽입하고 삭제하는 등의 문제의 대부분은 스택을 활용하는 문제라고 생각하면 된다.
문자열의 경우 중간에 문자를 삽입하거나 삭제하는 연산의 시간복잡도는 O(N)이다.
이 문제에선 문자열의 최대 길이가 1000000으로 주어졌기 때문에, 하나 삭제하거나 삽입할 때마다 최대 1000000번의 연산을 실행하는 것이다. 그러므로 문자열 자체를 이용해서는 이 문제를 해결할 수 없다.
Stack을 활용해서 문제를 푸는 방법을 보자.
이렇게, 현재 텍스트 커서를 기준으로 양쪽에 2개의 스택을 두고 문제를 해결할 것이다.
입력은 <<BP<A>>Cd- 가 들어온다고 가정할 것이다.
먼저,<<를 입력받으면 텍스트 커서는 왼쪽으로 한 칸씩 움직여야 할 것이다. 하지만, 현재 아무런 문자도 입력되지 않은 상황이라 텍스트 커서를 아무리 왼쪽으로 옮겨도 텍스트 커서는 움직이지 않는다.
그러므로, <<는 아무런 변화를 주지 않는다.
다음, B를 입력받았다고 해보자. 우리가 키보드에 A를 쳐보면, 텍스트 커서는 A의 바로 뒤에 붙어있는 것을 볼 수 있다.
그러므로, 입력반은 문자도 이와 동일하게 텍스트 커서의 앞에 입력해주자.
LeftStack에 문자를 삽입하는 것을 입력하는 것이라고 가정하겠다. LeftStack에 B를 삽입해주자.
스택은 이렇게 변화하게 된다.
다음 입력 P에 대해서도 동일하게 실행해보자.
스택은 위 그림과 같아진다.
다음 입력은 < 이다. 처음 <를 입력받았을 때엔 문자가 아무것도 입력되어 있지 않았기 때문에 텍스트 커서가 움직이지 않았지만, 이번엔 BP가 입력되어 있기 때문에, 텍스트 커서를 왼쪽으로 한 칸 움직이면 텍스트 커서는 B와 P사이에 위치하게 된다. 그러므로 스택은 아래와 같이 변하게 된다.
LeftStack은 텍스트 커서를 기준으로 왼쪽에 있는 문자들이며, RightStack은 텍스트 커서 기준으로 오른쪽에 있는 문자들인 셈이다. 그러므로, LeftStack의 가장 위의 원소를 빼서 RightStack으로 넣어주는 것을 텍스트 커서를 왼쪽으로 한 칸 움직인 것이라고 할 수 있는 것이다.
다음 입력 A에 대해서도 위에서 보았던 과정을 그대로 거쳐주자.
입력받은 문자는 텍스트 커서를 기준으로 위치하게 되므로, A는 위처럼 LeftStack에 삽입된다
다음 입력은 >이다. 텍스트 커서를 우측으로 한 칸 이동하는 것이다.
이는 <와 반대로 하면 된다. RightStack의 top을 LeftStack으로 넣어주자.
위의 그림과 같은 상태에서 다시 >를 입력받게 된다면, 텍스트 커서는 이미 문자의 마지막에 위치하기 때문에 아무런 변화가 없다. 그대로, 다음 입력을 받아주면 된다.
다음 입력은 C이다. C를 입력받으면, LeftStack에는 C가 추가될 것이다. 다음 d에 대해서도 똑같이 LeftStack에 d가 추가될 것이다.
스택은 위 그림과 같아질 것이다.
마지막으로, -입력이 들어온다면 텍스트 커서 바로 앞의 문자를 지워주면 된다.
그러므로, LeftStack의 top을 제거해주면 된다.
최종적으로 스택은 위와 같아진다.
그대로, LeftStack과 RightStack에 있는 문자열을 순서대로 string에 옮겨서 출력해주면 된다.
여기서 유의할 점은, 우리가 출력해야 하는 답과 LeftStack에서 꺼내는 순서가 반대라는 것이다.
LeftStack에서 차례대로 원소를 꺼내면, CPAB가 된다. 하지만, 우리가 원하는 답은 BAPC이다. 이를 고려하여 순서를 바꿔주어야 한다.
반면, RightStack은 위 경우에서는 남아있는 문자가 없기 때문에 확인할 수 없지만 RightStack은 꺼내는 순서가 문자열의 순서와 일치하기 때문에 RightStack의 원소는 뒤집지 않고 그대로 저장하여주면 된다.
풀이 코드
int NumCase = 0;
std::cin >> NumCase;
std::vector<std::string> Answers(NumCase);
