우선 한줄의 입력을 받은 다음에 문자열을 순회하면서 단어일때는 제외하고 시작하는 괄호일때 ( 나 [ 를 stack에 각각 push해주고 비어있지않고 짝이 맞는 괄호가 있다면 pop을 해주고 비어있다면 순회를 종료한다. 이러한 처리를 통해 yes인지 no인지 출력해줄 수 있다.
정답코드
#include <iostream>
#include <stack>
#include <string>
using namespace std;
int main() {
while (true) {
string line;
getline(cin, line); // 한 줄 전체 입력
if (line == ".") break; // 종료 조건
stack<char> s;
bool isBalanced = true; // 균형 여부 체크
for (int i = 0; i < line.size(); i++) {
if (line[i] == '(' || line[i] == '[') {
s.push(line[i]); // 여는 괄호를 스택에 넣음
}
else if (line[i] == ')') {
if (!s.empty() && s.top() == '(') {
s.pop(); // 괄호가 짝이 맞으면 스택에서 제거
}
else {
isBalanced = false; // 짝이 맞지 않으면 불균형
break;
}
}
else if (line[i] == ']') {
if (!s.empty() && s.top() == '[') {
s.pop(); // 대괄호가 짝이 맞으면 스택에서 제거
}
else {
isBalanced = false;
break;
}
}
}
if (!s.empty()) isBalanced = false; // 스택이 비어 있지 않으면 불균형
if (isBalanced) cout << "yes" << endl;
else cout << "no" << endl;
}
return 0;
}
처음에 봤을 때 부분 문자열의 조합을 이중반복문을 통해 구하고 이를 set 자료형을 통해 하나씩 넣고 마지막에 그 크기를 출력해주는 것으로 생각했다. 이렇게 풀어도 정답이 된다.
정답코드1(반복문 사용)
#include <iostream>
#include <set>
using namespace std;
set<string> s;
int main()
{
string word;
cin >> word;
//부분 문자열 시작위치
for (int i = 0; i < word.size(); i++)
{
string w = "";
for (int j = i; j < word.size(); j++) //부분 문자열 길이
{
w += word[j];
s.insert(w);
}
}
cout << s.size() << endl;
}
하지만 더 최적화해보자면 접미사 배열 (Suffix Array) 이라는 것을 사용해서 풀면 된다.
이때 접미사 배열은 문자열 s의 모든 접미사를 사전 순으로 정렬한 것으로 각 접미사가 문자열에서 시작하는 인덱스를 기준으로 정렬 한다. 예시 입력을 바탕으로 보자면
s의 접미사 목록:
s[0:] = "ababc"
s[1:] = "babc"
s[2:] = "abc"
s[3:] = "bc"
s[4:] = "c"
이런식으로 접미사가 만들어진다.
여기서 중복되는 부분 문자열을 제거하기 위해 접미사 배열을 활용한 LCP 배열이라는 것을 사용하게 되는데 이는 은 접미사 배열의 인접한 접미사들 간에 겹치는 접두사의 길이를 저장한 배열이다.
인접한 접미사들 간의 공통 접두사:
"ababc"와 "abc"의 공통 접두사: "ab" → 길이 2
"abc"와 "babc"의 공통 접두사: 없음 → 길이 0
"babc"와 "bc"의 공통 접두사: "b" → 길이 1
"bc"와 "c"의 공통 접두사: 없음 → 길이 0
이렇게 되면 LCP배열은 [2, 0, 1, 0] 이런식으로 만들어 진다.
이제 중복되는 것을 포함한 전체 부분 문자열의 개수를 구해준 다음 중복되는 수를 빼주면 된다.
부분 문자열의 개수는 n(n+1) /2 로 계산할 수 있다.
이를 코드로 구현하면 다음과 같다.
정답코드2(접미사 배열활용)
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;
// 접미사 배열 구하기
vector<int> build_suffix_array(const string& s) {
int n = s.size();
vector<int> suffix_array(n), rank(n), temp(n);
// 초기 순위 설정 (문자의 아스키 값에 따른 정렬)
for (int i = 0; i < n; i++) {
suffix_array[i] = i;
rank[i] = s[i];
}
// 접미사 길이 1, 2, 4, 8...씩 늘려가며 정렬
for (int len = 1; len < n; len *= 2) {
auto cmp = [&](int i, int j) {
if (rank[i] != rank[j]) return rank[i] < rank[j];
int ri = (i + len < n) ? rank[i + len] : -1;
int rj = (j + len < n) ? rank[j + len] : -1;
return ri < rj;
};
sort(suffix_array.begin(), suffix_array.end(), cmp);
// 임시 순위 갱신
temp[suffix_array[0]] = 0;
for (int i = 1; i < n; i++) {
temp[suffix_array[i]] = temp[suffix_array[i - 1]] + cmp(suffix_array[i - 1], suffix_array[i]);
}
rank = temp;
}
return suffix_array;
}
// LCP 배열 구하기
vector<int> build_lcp_array(const string& s, const vector<int>& suffix_array) {
int n = s.size();
vector<int> rank(n), lcp(n);
for (int i = 0; i < n; i++) {
rank[suffix_array[i]] = i;
}
int h = 0;
for (int i = 0; i < n; i++) {
if (rank[i] > 0) {
int j = suffix_array[rank[i] - 1];
while (i + h < n && j + h < n && s[i + h] == s[j + h]) {
h++;
}
lcp[rank[i]] = h;
if (h > 0) h--;
}
}
return lcp;
}
// 서로 다른 부분 문자열 개수 구하기
int count_unique_substrings(const string& s) {
int n = s.size();
// 접미사 배열과 LCP 배열 생성
vector<int> suffix_array = build_suffix_array(s);
vector<int> lcp = build_lcp_array(s, suffix_array);
int total_substrings = n * (n + 1) / 2; // 모든 부분 문자열의 개수
int lcp_sum = 0; // LCP들의 합
for (int i = 1; i < n; i++) {
lcp_sum += lcp[i]; // LCP 값의 합
}
return total_substrings - lcp_sum; // 전체 부분 문자열에서 중복된 부분을 빼기
}
int main() {
string s;
cin >> s;
int result = count_unique_substrings(s);
cout << result << endl;
return 0;
}
확실히 공간,시간 복잡도가 확연히 줄어든 모습을 볼 수있다. 이론은 이해할 수 있었지만 이를 구현하기는 어렵지만 최적화가 필요할 때는 이 방법을 활용하면 좋을 것같다.
각 집합 A,B에 대한 입력을 받고 A-B와 B-A의 합집합을 구하면 된다. 나는 set 자료형을 사용하여 두 집합을 입력받은 뒤 각 집합을 순회하면서 find함수를 통해 해당원소가 다른 집합의 원소가 아니라면 정답 set자료형에 넣어주고 마지막으로 그 자료형의 크기를 출력해주었다.
하지만 STL의 set_difference 알고리즘을 사용하는 것이 각 집합간의 차집합을 구하는데 효율적일 수 있다.
set_difference는 정렬된 범위에서 한 집합에서 다른 집합에 없는 요소를 추출한다.
set_difference 함수는 각 집합의 시작과 끝, 결과값을 저장할 변수를 매개변수로 사용한다.
set_difference
template< class InputIt1, class InputIt2, class OutputIt >
OutputIt set_difference( InputIt1 first1, InputIt1 last1,
InputIt2 first2, InputIt2 last2,
OutputIt d_first );
정답코드1(순회)
#include "iostream"
#include "set"
using namespace std;
set<int> s1, s2, answer;
int main()
{
int n, m;
cin >> n >> m;
//집합만들기
for (int i = 0; i < n; i++)
{
int x;
cin >> x;
s1.insert(x);
}
for (int i = 0; i < m; i++)
{
int x;
cin >> x;
s2.insert(x);
}
int cnt = 0;
for (auto it = s1.begin(); it != s1.end(); it++)
{
if (s2.find(*it) == s2.end()) cnt++;
}
for (auto it = s2.begin(); it != s2.end(); it++)
{
if (s1.find(*it) == s1.end()) cnt++;
}
cout << cnt << endl;
}
정답코드2(STL알고리즘 활용)
#include <iostream>
#include <set>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
int n, m;
cin >> n >> m;
set<int> s1, s2; // 두 집합을 저장할 set
// 집합 A 입력
for (int i = 0; i < n; i++) {
int x;
cin >> x;
s1.insert(x);
}
// 집합 B 입력
for (int i = 0; i < m; i++) {
int x;
cin >> x;
s2.insert(x);
}
vector<int> diff1, diff2; // 차집합을 저장할 벡터
// A - B 차집합
set_difference(s1.begin(), s1.end(), s2.begin(), s2.end(), back_inserter(diff1));
// B - A 차집합
set_difference(s2.begin(), s2.end(), s1.begin(), s1.end(), back_inserter(diff2));
// 대칭 차집합의 원소 개수
cout << diff1.size() + diff2.size() << endl;
return 0;
}
컴퓨팅쉐이더에 대해 알아보자. 이 쉐이더를 통해 cpu가 아닌 gpu에 일을 어떻게 넘기는지 그 방식에 대해 알 수 있다.
우리가 지금까지 작업해준 메인 코드는 모두 CPU에서 돌아가는 코드이고 엔진쪽에서 DX에 의해 처리되고 있는 버퍼와
같은 코드들이 GPU에 의해 처리된다. 결과물이 렌더링 파이프라인을 통해서 GPU 를 통해 렌더링된다고 보면된다.
GPU에게 일을 시키기 위해 쉐이더파일(.fx)을 만들어줬다.
GPU는 연산에 특화되어있다. 병렬로 처리할 수 있는 단순 작업을 CPU를 대신하여 GPU에서 처리를 해주면 좋은데
이렇게 일반적인 그래픽스 용도가 아닌 범용적인 용도로 GPU를 사용하는 것을 GPGPU라고 한다.
DX에서도 결국에는 컴퓨팅쉐이더를 이용해서 일반적인 쉐이더가 아니라 GPU에 단순 연산을 시키는 방식을 이용할 수 있다. 이러한 방식을 텍스처를 조작해서 다른 파일을 만들거나 하나의 스트림을 압축하거나 애니메이션에서 순간적인 상태의 애니메이션 위치를 알 수 있는 처리에 사용할 수 있다.
현재는 공용정보가 있다면 락을 거는 방식을 사용해서 다수의 스레드를 적용시켜 멀티셋 환경에서 작업을 할 수 있지만 이 작업 GPU를 통해 이제 해주어야한다.
일단 이 컴퓨팅 쉐이더를 사용하면서 배워보자. 핵심은 GPU에 어떤식으로 일을 분배할 것인가 이다.
먼저 GPU에 데이터를 넘겼다가 다시 받으려면 리소스가 필요하다.
여러 리소스의 종류 중에 지금은 Raw Buffer(Byte Address Buffer)를 사용해보자. 이 Raw Buffer는 주소를 이용해서
우리가 직접 주소값을 연산해서 접근하는형태로 바이트형 포인터를 다루는 느낌이라고 생각하면 된다. 이것도 리소스이기 때문에 리소스를 만들어주고 이를 묘사하는 view를 만들어주어야 한다. 실질적으로 GPU와 통신할 때는 이 View의 정보를 건네주고 이를 바탕으로 작업을 하고 받아 올때도 View를 통해 컴퓨팅 쉐이더에 건내준 다음 임시 버퍼를 통해 결과값을 취합한다.
2.코드
우선 RawBuffer 클래스를 만들어주자. 우리가 이 클래스로 입력을 받아주고 컴퓨팅 쉐이더에 연산을 요청한 다음 이 결과값을 받아주면 된다.
이를 위해 입력값을 받아주는 변수는 어떤값이 들어올지 모르기 때문에 보이드형 포인터로 선언해주자. 이는 cpu 메모리에 있는 정보이다. 예를 들어 벡터가 있다면 벡터의 첫번째 데이터의 주소를 주고 이를 통해 크기정보를 받아온다.
그리고 입출력의 크기값을 저장할 변수를 만들어주고 입력값은 생성자에서 받아주자. 이 입력값을 바탕으로 지정한 크기의 버퍼를 만들고 작업해주면 된다.
View를 통해 받아온 정보를 꺼내주기 위한 버퍼도 만들어주자.
결과값도 View에서 바로 가져올 수 는 없고 임시 버퍼를 통해 복사 한 다음 작업을 해서 가져와야한다.
버퍼를 만든다음 cpu 메모리에서 데이터를 만들어주면 그것을 건네주는 함수와 컴퓨팅 쉐이더를 통한 호출이 완료된 다음에 임시 버퍼의 값을 가져오는 함수를 만들어주자. 이 과정은 맵과 언맵을 통해 해준다.
이렇게 만들어준 버퍼를 메인쪽에서 사용할 수 있도록 코드를 구현해보자. 일단은 Input 없이 Output만 받아주는 방식으로 만들어주자. 먼저 컴퓨트 쉐이더를 사용하여 연산을 해줄 shader 코드를 구현하자. 이때 output의 offset은 받아주는 구조체의 크기와 바이트 개수를 통해 계산한다. 이를 통해 데이터가 연속해서 배열로 있다면 그 데이터를 캐릭터 / 바이트 포인터로 연산해서 주소를 찾아가야 한다면 몇번째 데이터인지 각 데이터의 크기를 통해 offset을 정해줘서 넘어갈 수 있다. 결국 이 쉐이더 코드는 CPU에서 하는 작업으로 치자면 구조체를 만들고 이 구조체변수에 값을 할당해주는 작업이라고 보면 된다.
Group ThreadID는 하나의 그룹내에서 나의 쓰레드 ID는 몇번이지를 나타낸다. 이 값은 그룹내에서는 고유하다.
GroupID는 몇번째 그룹인지를 나타낸다.
Dispatch ThreadID는 자신이 몇번째인지 그룹자체의 번호와 해당하는 그룹에서 몇번인지를 구해주는 것으로 이 값은 모든 스레드마다 고유하게 있을 것이다.
GroupIndex는 Group ThreadID의 값을 활용해서 앞자리에 둔다. 7*1 + 5*10 + 0*10*8 끝에 10*8은 10,8,3에서 나온 것이다. 2차원배열을 1차원으로 만들 때 하나는 그냥 더해주고 하나는 사이즈에 곱해서 더해주는 식의 방식과 같이 인덱스를 표현해준 것이다. 결국에는 하나의 그룹내에서 몇번째 쓰레드인지 나타낸다.
이것이 중요한 이유는 어떻게 데이터를 분할해서 시킬지에서 컴퓨트 쉐이더를 이용하는 경우도 있고 행렬을 이용해서 그 행렬을 여러 개의 쓰레드들이 담당하게 만들어 줄 수 있는 등의 다양한 형태로 분배를 해줄텐데 어떤 애가 어떤애를 참고할지는 이 SV값을 따라서 분할해서 일감을 주면 된다.
실습2
지금은 Output만 추출해주고 있지만 원래는 Input을 받아서 가공해서 다시 뱉어주는 것이 일반적이다.
랜덤 값을 하나 정해준 다음 인풋에 넣어서 건네주고 이를 통해 쉐이더 파일을 거친 다음에 읽어오는 Read와 Write를 같이 한번 해보자.
결국 굉장히 많은 데이터를 건네줬을 때 특정 쓰레드가 담당하는 그 공간에 있는 인풋을 가져와서 복사한 뒤 반환하는 것을 보고 싶은 것이다.
n개의 단어에서 나온 값과 m개의 단어에서 나온 값이 같은게 몇개인지 출력하고 해당하는 단어를 사전 순으로 출력해주면 되는 문제이다.
나는 map자료형을 통해 중복되는 단어를 vector에 저장하고 sort를 통해 사전순으로 정렬한 다음 해당 vector의 크기와
원소를 순서대로 출력해주었다.
정답코드
#include <iostream>
#include <unordered_map>
#include <vector>
#include <algorithm>
using namespace std;
unordered_map<string, bool>hear;
vector<string> both;
int main()
{
int n, m, cnt = 0;
cin >> n >> m;
for (int i = 0; i < n; i++)
{
string person;
cin >> person;
hear[person] = true;
}
for (int i = 0; i < m; i++)
{
string person;
cin >> person;
if (hear[person])
{
both.push_back(person);
}
}
// 사전 순으로 정렬
sort(both.begin(), both.end());
cout << both.size() << '\n';
for (const auto& name : both) {
cout << name << '\n';
}
return 0;
}
GameObject에서 Light Component를 사용할 수 있도록 헬퍼함수를 추가해주자.
GameObject.h
#pragma once
#include "Component.h"
class MonoBehaviour;
class Transform;
class Camera;
class MeshRenderer;
class ModelRenderer;
class ModelAnimator;
class Light;
class GameObject : public enable_shared_from_this<GameObject>
{
public:
shared_ptr<Light> GetLight();
};
이 Scene의 Update에서는 카메라를 Update하는 부분은 다른 연산이나 기능 중에 바뀌게 되면 뷰 프로젝션 연산값이 달라지게 되는데 이는 부자연스러운 움직임이 연출 되거나 위치가 이상해질 수 있기 때문에 카메라는 모든 Update가 끝난 LateUpdate나 그 후에 해주는것이 좋다.
그리고 Update나 Start의 과정에서 오브젝의 Update Start가 작동할텐데 이때 이 함수가 끝나거나 추가될 때까지는 set의 값이 바뀌면 안되기 때문에 한번 임시적으로 캐싱을 해주고 이 캐싱한 값을 순회하도록 하자.
문제가 굉장히 길다 앞부분보다는 입력과 출력 위주로 보고 풀면된다. 나는 입력을 받은 다음에 map과 vector자료형을
사용하여 만약 문자가 온다면 string과 저장순서가 int로 기록된 map을 통해 출력해주고 만약 숫자가 온다면 벡터안에 저장된 순서에서 1을 빼준 인덱스의 문자를 출력해주는 방식으로 풀어보았다.
처음에 시간초과가 났는데 이유는 입출력의 크기가 크기 때문이라고 생각해서 cin과 cout를 scanf와 printf 로 바꿔서 풀어주었더니 시간안에 풀 수 있었다.
정답코드
#include <iostream>
#include <unordered_map>
#include <vector>
#include <string>
using namespace std;
vector<string> pocket;
unordered_map<string, int> pocket2;
int main()
{
int n, m;
char buffer[21]; // 포켓몬 이름을 받을 버퍼
scanf("%d %d", &n, &m);
for (int i = 0; i < n; i++)
{
string pocketmon;
scanf("%s", buffer);
pocket.push_back(buffer);
pocket2[buffer] = i + 1;
}
for (int i = 0; i < m; i++)
{
scanf("%s", buffer);
if (isdigit(buffer[0]))
{
printf("%s\n", pocket[stoi(buffer)-1].c_str());
}
else
{
printf("%d\n", pocket2[buffer]);
}
}
return 0;
}
